Logic synthesis
Encyclopedia
In electronics, logic synthesis is a process by which an abstract form of desired circuit behavior, typically register transfer level
(RTL), is turned into a design implementation in terms of logic gates. Common examples of this process include synthesis of HDL
s, including VHDL and Verilog
. Some tools can generate bitstream
s for programmable logic device
s such as PAL
s or FPGA
s, while others target the creation of ASIC
s. Logic synthesis is one aspect of electronic design automation
.
(1815 to 1864), in what is now termed Boolean algebra. In 1938, Claude Shannon
showed that the two-valued Boolean algebra can describe the operation of switching circuits. In the early days, logic design involved manipulating the truth table representations as Karnaugh map
s. The Karnaugh map-based minimization of logic is guided by a set of rules on how entries in the maps can be combined. A human designer can typically only work with Karnaugh maps containing up to four to six variables.
The first step toward automation of logic minimization was the introduction of the Quine–McCluskey algorithm that could be implemented on a computer.
This exact minimization technique presented the notion of prime implicants and minimum cost covers that would become the cornerstone of two-level minimization. Nowadays, the much more efficient Espresso heuristic logic minimizer
has become the standard tool for this operation. Another area of early research was in state minimization and encoding of finite state machine
s (FSMs), a task that was the bane of designers. The applications for logic synthesis lay primarily in digital computer design. Hence, IBM
and Bell Labs
played a pivotal role in the early automation of logic synthesis. The evolution from discrete logic components to programmable logic array
s (PLAs) hastened the need for efficient two-level minimization, since minimizing terms in a two-level representation reduces the area in a PLA.
However, two-level logic circuits are of limited importance in a very-large-scale integration
(VLSI) design; most designs use multiple levels of logic. As a matter of fact, almost any circuit representation in RTL or Behavioural Description is a multi-level representation. An early system that was used to design multilevel circuits was LSS from IBM. It used local transformations to simplify logic. Work on LSS and the Yorktown Silicon Compiler spurred rapid research progress in logic synthesis in the 1980s. Several universities
contributed by making their research available to the public, most notably SIS from University of California, Berkeley
, RASP from University of California, Los Angeles
and BOLD from University of Colorado, Boulder. Within a decade, the technology migrated to commercial logic synthesis products offered by electronic design automation companies.
of an electronic circuit
is converted into the representation which captures logic operations, arithmetic operations, control flow
, etc. A common output of this step is RTL description. Logic design is commonly followed by the circuit design
step. In modern electronic design automation
parts of the logical design may be automated using high-level synthesis
tools based on the behavioral description of the circuit.
Logic operations usually consist of boolean AND, OR, XOR and NAND operations, and are the most basic forms of operations in an electronic circuit. Arithmetic operations are usually implemented with the use of logic operators. Circuits such as a binary multiplier
or a binary adder are examples of more complex binary operations that can be implemented using basic logic operators.
Starting from an RTL description of a design, the synthesis tool constructs a corresponding multilevel Boolean network.
Next, this network is optimized using several technology-independent techniques before technology-dependent optimizations are performed. The typical cost function during technology-independent optimizations is total literal
count of the factored representation of the logic function (which correlates quite well with circuit area).
Finally, technology-dependent optimization transforms the
technology-independent circuit into a network of gates in a given technology. The simple cost estimates are replaced by more concrete, implementation-driven estimates during and after technology mapping. Mapping is constrained by factors such as the available gates (logic functions) in the technology library, the drive sizes for each gate, and the delay, power, and area characteristics of each gate.
Register transfer level
In integrated circuit design, register-transfer level is a level of abstraction used in describing the operation of a synchronous digital circuit...
(RTL), is turned into a design implementation in terms of logic gates. Common examples of this process include synthesis of HDL
Hardware description language
In electronics, a hardware description language or HDL is any language from a class of computer languages, specification languages, or modeling languages for formal description and design of electronic circuits, and most-commonly, digital logic...
s, including VHDL and Verilog
Verilog
In the semiconductor and electronic design industry, Verilog is a hardware description language used to model electronic systems. Verilog HDL, not to be confused with VHDL , is most commonly used in the design, verification, and implementation of digital logic chips at the register-transfer level...
. Some tools can generate bitstream
Bitstream
A bitstream or bit stream is a time series of bits.A bytestream is a series of bytes, typically of 8 bits each, and can be regarded as a special case of a bitstream....
s for programmable logic device
Programmable logic device
A programmable logic device or PLD is an electronic component used to build reconfigurable digital circuits. Unlike a logic gate, which has a fixed function, a PLD has an undefined function at the time of manufacture...
s such as PAL
Programmable Array Logic
The term Programmable Array Logic is used to describe a family of programmable logic device semiconductors used to implement logic functions in digital circuits introduced by Monolithic Memories, Inc. in March 1978. MMI obtained a registered trademark on the term PAL for use in "Programmable...
s or FPGA
Field-programmable gate array
A field-programmable gate array is an integrated circuit designed to be configured by the customer or designer after manufacturing—hence "field-programmable"...
s, while others target the creation of ASIC
ASIC
ASIC may refer to:* Application-specific integrated circuit, an integrated circuit developed for a particular use, as opposed to a customised general-purpose device.* ASIC programming language, a dialect of BASIC...
s. Logic synthesis is one aspect of electronic design automation
Electronic design automation
Electronic design automation is a category of software tools for designing electronic systems such as printed circuit boards and integrated circuits...
.
History of logic synthesis
The roots of logic synthesis can be traced to the treatment of logic by George BooleGeorge Boole
George Boole was an English mathematician and philosopher.As the inventor of Boolean logic—the basis of modern digital computer logic—Boole is regarded in hindsight as a founder of the field of computer science. Boole said,...
(1815 to 1864), in what is now termed Boolean algebra. In 1938, Claude Shannon
Claude Elwood Shannon
Claude Elwood Shannon was an American mathematician, electronic engineer, and cryptographer known as "the father of information theory"....
showed that the two-valued Boolean algebra can describe the operation of switching circuits. In the early days, logic design involved manipulating the truth table representations as Karnaugh map
Karnaugh map
The Karnaugh map , Maurice Karnaugh's 1953 refinement of Edward Veitch's 1952 Veitch diagram, is a method to simplify Boolean algebra expressions...
s. The Karnaugh map-based minimization of logic is guided by a set of rules on how entries in the maps can be combined. A human designer can typically only work with Karnaugh maps containing up to four to six variables.
The first step toward automation of logic minimization was the introduction of the Quine–McCluskey algorithm that could be implemented on a computer.
This exact minimization technique presented the notion of prime implicants and minimum cost covers that would become the cornerstone of two-level minimization. Nowadays, the much more efficient Espresso heuristic logic minimizer
Espresso heuristic logic minimizer
The Espresso logic minimizer is a computer program using heuristic and specific algorithms for efficiently reducing the complexity of digital electronic gate circuits. Espresso was developed at IBM by Robert Brayton. Rudell later published the variant Espresso-MV in 1986 under the title...
has become the standard tool for this operation. Another area of early research was in state minimization and encoding of finite state machine
Finite state machine
A finite-state machine or finite-state automaton , or simply a state machine, is a mathematical model used to design computer programs and digital logic circuits. It is conceived as an abstract machine that can be in one of a finite number of states...
s (FSMs), a task that was the bane of designers. The applications for logic synthesis lay primarily in digital computer design. Hence, IBM
IBM
International Business Machines Corporation or IBM is an American multinational technology and consulting corporation headquartered in Armonk, New York, United States. IBM manufactures and sells computer hardware and software, and it offers infrastructure, hosting and consulting services in areas...
and Bell Labs
Bell Labs
Bell Laboratories is the research and development subsidiary of the French-owned Alcatel-Lucent and previously of the American Telephone & Telegraph Company , half-owned through its Western Electric manufacturing subsidiary.Bell Laboratories operates its...
played a pivotal role in the early automation of logic synthesis. The evolution from discrete logic components to programmable logic array
Programmable logic array
A programmable logic array is a kind of programmable logic device used to implement combinational logic circuits. The PLA has a set of programmable AND gate planes, which link to a set of programmable OR gate planes, which can then be conditionally complemented to produce an output...
s (PLAs) hastened the need for efficient two-level minimization, since minimizing terms in a two-level representation reduces the area in a PLA.
However, two-level logic circuits are of limited importance in a very-large-scale integration
Very-large-scale integration
Very-large-scale integration is the process of creating integrated circuits by combining thousands of transistors into a single chip. VLSI began in the 1970s when complex semiconductor and communication technologies were being developed. The microprocessor is a VLSI device.The first semiconductor...
(VLSI) design; most designs use multiple levels of logic. As a matter of fact, almost any circuit representation in RTL or Behavioural Description is a multi-level representation. An early system that was used to design multilevel circuits was LSS from IBM. It used local transformations to simplify logic. Work on LSS and the Yorktown Silicon Compiler spurred rapid research progress in logic synthesis in the 1980s. Several universities
contributed by making their research available to the public, most notably SIS from University of California, Berkeley
University of California, Berkeley
The University of California, Berkeley , is a teaching and research university established in 1868 and located in Berkeley, California, USA...
, RASP from University of California, Los Angeles
University of California, Los Angeles
The University of California, Los Angeles is a public research university located in the Westwood neighborhood of Los Angeles, California, USA. It was founded in 1919 as the "Southern Branch" of the University of California and is the second oldest of the ten campuses...
and BOLD from University of Colorado, Boulder. Within a decade, the technology migrated to commercial logic synthesis products offered by electronic design automation companies.
Logic elements
Logic design is a step in the standard design cycle in which the functional designFunctional design
Functional design is a paradigm used to simplify the design of hardware and software devices such as computer software and increasingly, 3D models. A functional design assures that each modular part of a device has only one responsibility and performs that responsibility with the minimum of side...
of an electronic circuit
Electronic circuit
An electronic circuit is composed of individual electronic components, such as resistors, transistors, capacitors, inductors and diodes, connected by conductive wires or traces through which electric current can flow...
is converted into the representation which captures logic operations, arithmetic operations, control flow
Control flow
In computer science, control flow refers to the order in which the individual statements, instructions, or function calls of an imperative or a declarative program are executed or evaluated....
, etc. A common output of this step is RTL description. Logic design is commonly followed by the circuit design
Circuit design
The process of circuit design can cover systems ranging from complex electronic systems all the way down to the individual transistors within an integrated circuit...
step. In modern electronic design automation
Electronic design automation
Electronic design automation is a category of software tools for designing electronic systems such as printed circuit boards and integrated circuits...
parts of the logical design may be automated using high-level synthesis
High-level synthesis
High-level synthesis , sometimes referred to as C synthesis, electronic system level synthesis, algorithmic synthesis, or behavioral synthesis, is an automated design process that interprets an algorithmic description of a desired behavior and creates hardware that implements that behavior. The...
tools based on the behavioral description of the circuit.
Logic operations usually consist of boolean AND, OR, XOR and NAND operations, and are the most basic forms of operations in an electronic circuit. Arithmetic operations are usually implemented with the use of logic operators. Circuits such as a binary multiplier
Binary multiplier
A binary multiplier is an electronic circuit used in digital electronics, such as a computer, to multiply two binary numbers. It is built using binary adders....
or a binary adder are examples of more complex binary operations that can be implemented using basic logic operators.
High-level synthesis or behavioral synthesis
With a goal of increasing designer productivity, research efforts on the synthesis of circuits specified at the behavioral level have led to the emergence of commercial solutions in 2004, which are used for complex ASIC and FPGA design. These tools automatically synthesize circuits specified at C level to a register transfer level (RTL) specification, which can be used as input to a gate-level logic synthesis flow. Today, high-level synthesis, also known as ESL synthesis and behavioral synthesis, essentially refers to circuit synthesis from high level Languages like ANSI C/C++ or SystemC etc., whereas Logic Synthesis refers to synthesis from structural or functional description to RTL.Multi-level logic minimization
Typical practical implementations of a logic function utilize a multi-level network of logic elements.Starting from an RTL description of a design, the synthesis tool constructs a corresponding multilevel Boolean network.
Next, this network is optimized using several technology-independent techniques before technology-dependent optimizations are performed. The typical cost function during technology-independent optimizations is total literal
count of the factored representation of the logic function (which correlates quite well with circuit area).
Finally, technology-dependent optimization transforms the
technology-independent circuit into a network of gates in a given technology. The simple cost estimates are replaced by more concrete, implementation-driven estimates during and after technology mapping. Mapping is constrained by factors such as the available gates (logic functions) in the technology library, the drive sizes for each gate, and the delay, power, and area characteristics of each gate.
Software tools for logic synthesis targeting ASICs
- Design Compiler by SynopsysSynopsysSynopsys, Inc. is one of the largest companies in the Electronic Design Automation industry. Synopsys' first and best-known product is Design Compiler, a logic-synthesis tool. Synopsys offers a wide range of other products used in the design of an application-specific integrated circuit...
- Encounter RTL Compiler by Cadence Design SystemsCadence Design SystemsCadence Design Systems, Inc is an electronic design automation software and engineering services company, founded in 1988 by the merger of SDA Systems and ECAD, Inc...
- BuildGates, an older product by Cadence Design SystemsCadence Design SystemsCadence Design Systems, Inc is an electronic design automation software and engineering services company, founded in 1988 by the merger of SDA Systems and ECAD, Inc...
, humorously named after Bill GatesBill GatesWilliam Henry "Bill" Gates III is an American business magnate, investor, philanthropist, and author. Gates is the former CEO and current chairman of Microsoft, the software company he founded with Paul Allen...
- BuildGates, an older product by Cadence Design Systems
- TalusDesign by Magma Design AutomationMagma Design AutomationMagma Design Automation is a software company in the electronic design automation industry. The company was founded in 1997 and maintains headquarters in San Jose, California, with facilities throughout North America, Europe, Japan, Asia and India....
- RealTime Designer by Oasys Design Systems
- BooleDozer: Logic synthesis tool by IBMIBMInternational Business Machines Corporation or IBM is an American multinational technology and consulting corporation headquartered in Armonk, New York, United States. IBM manufactures and sells computer hardware and software, and it offers infrastructure, hosting and consulting services in areas...
(internal IBM EDA tool)
Software tools for logic synthesis targeting FPGAs
- XSTXilinx ISEXilinx ISE is a software tool produced by Xilinx for synthesis and analysis of HDL designs, which enables the developer to synthesize their designs, perform timing analysis, examine RTL diagrams, simulate a design's reaction to different stimuli, and configure the target device with the...
(delivered within ISEXilinx ISEXilinx ISE is a software tool produced by Xilinx for synthesis and analysis of HDL designs, which enables the developer to synthesize their designs, perform timing analysis, examine RTL diagrams, simulate a design's reaction to different stimuli, and configure the target device with the...
) by XilinxXilinxXilinx, Inc. is a supplier of programmable logic devices. It is known for inventing the field programmable gate array and as the first semiconductor company with a fabless manufacturing model.... - Quartus II integrated Synthesis by AlteraAlteraAltera Corporation is a Silicon Valley manufacturer of PLDs . The company offered its first programmable logic device in 1984. PLDs can be reprogrammed during the design cycle as well as in the field to perform multiple functions, and they support a fairly fast design process...
- IspLever by Lattice SemiconductorLattice SemiconductorLattice Semiconductor Corporation is a United States based manufacturer of high-performance programmable logic devices . Founded in 1983, the company employs about 700 people and has annual revenues of around $300 million, with Darin Billerbeck as the chief executive officer...
- Encounter RTL Compiler by Cadence Design SystemsCadence Design SystemsCadence Design Systems, Inc is an electronic design automation software and engineering services company, founded in 1988 by the merger of SDA Systems and ECAD, Inc...
- LeonardoSpectrum and Precision (RTL / Physical) by Mentor GraphicsMentor GraphicsMentor Graphics, Inc is a US-based multinational corporation dealing in electronic design automation for electrical engineering and electronics, as of 2004, ranked third in the EDA industry it helped create...
- Synplify (PRO / Premier) by SynopsysSynopsysSynopsys, Inc. is one of the largest companies in the Electronic Design Automation industry. Synopsys' first and best-known product is Design Compiler, a logic-synthesis tool. Synopsys offers a wide range of other products used in the design of an application-specific integrated circuit...
- BlastFPGA by Magma Design AutomationMagma Design AutomationMagma Design Automation is a software company in the electronic design automation industry. The company was founded in 1997 and maintains headquarters in San Jose, California, with facilities throughout North America, Europe, Japan, Asia and India....