Logic synthesis

In electronics, logic synthesis is a process by which an abstract form of desired circuit behavior, typically at register transfer level (RTL), is turned into a design implementation in terms of logic gates, typically by a computer program called a synthesis tool. Common examples of this process include synthesis of HDLs, including VHDL and Verilog. Some synthesis tools generate bitstreams for programmable logic devices such as PALs or FPGAs, while others target the creation of ASICs. Logic synthesis is one aspect of electronic design automation.

History of logic synthesis

The roots of logic synthesis can be traced to the treatment of logic by George Boole (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 maps. 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 machines (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 arrays (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.

Logic elements

Logic design is a step in the standard design cycle in which the functional design 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.

Various representations of Boolean operations

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.

High-level synthesis or behavioral synthesis

Main article: High-level 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

See also: Logic optimization and Circuit 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.

Commercial tools for logic synthesis

Software tools for logic synthesis targeting ASICs

• Design Compiler by Synopsys
• Encounter RTL Compiler by Cadence Design Systems
  • BuildGates, an older product by Cadence Design Systems, humorously named after Bill Gates
• HDL Designer by Mentor Graphics
• TalusDesign by Magma Design Automation
• RealTime Designer by Oasys Design Systems
• BooleDozer: Logic synthesis tool by IBM (internal IBM EDA tool)

Software tools for logic synthesis targeting FPGAs

• XST (delivered within ISE) by Xilinx
• Quartus II integrated Synthesis by Altera
• IspLever by Lattice Semiconductor
• Encounter RTL Compiler by Cadence Design Systems
• LeonardoSpectrum and Precision (RTL / Physical) by Mentor Graphics
• Synplify (PRO / Premier) by Synopsys
• BlastFPGA by Magma Design Automation

Online tools

• EDA Playground by Doulos (uses Yosys and Verilog-to-Routing synthesis flows)

• BoolEngine

See also

• Binary decision diagram
• Functional verification

References

• Electronic Design Automation For Integrated Circuits Handbook, by Lavagno, Martin, and Scheffer, ISBN 0-8493-3096-3 A survey of the field of Electronic design automation. The above summary was derived, with permission, from Volume 2, Chapter 2, Logic Synthesis by Sunil Khatri and Narendra Shenoy.
• A Consistent Approach in Logic Synthesis for FPGA Architectures, by Burgun Luc, Greiner Alain, and Prado Lopes Eudes, Proceedings of the international Conference on Asic (ASICON), Pekin, October 1994, pp. 104–107.

Further reading

• also as published as softcover ISBN 0-387-31004-5 in 2006