Logic synthesis
1082894
219263225
2008-06-14T11:09:10Z
MTM
7260262
/* Software tools for logic synthesis targeting ASICs */ space
'''Logic synthesis''' is a process by which an abstract form of desired circuit behavior (typically [[register transfer level]] (RTL) or behavioral) is turned into a design implementation in terms of [[logic gates]]. Common examples of this process include synthesis of [[Hardware Description Language|HDL]]s, including [[VHDL]] and [[Verilog]]. Some tools can generate bitstreams for [[programmable logic device]]s such as [[programmable array logic|PAL]]s or [[Field-programmable gate array|FPGA]]s, while others target the creation of [[ASIC]]s. 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 (logic)|Boolean algebra]]. In 1938, [[Claude Elwood Shannon|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.
== Behavioral synthesis ==
With the goal of increasing designer productivity, there has been a significant amount of research on synthesis of circuits specified at the behavioral level using a hardware description language (HDL). The goal of behavioral synthesis is to transform a
behavioral HDL specification into a register transfer level (RTL) specification, which can be used as input to a gate-level logic synthesis flow.
Behavioral optimization decisions are guided by cost functions that are based on the number of hardware resources and states required. These cost functions provide a coarse estimate of the combinational and sequential circuitry required to implement the design. Today , behavioral logic description and Synthesis essentially refer to Circuit Synthesis from high level Languages like SystemC etc., whereas Logic Synthesis is being restricted for Synthesis from Structural or Functional Description in RTL.
The tasks of scheduling, resource allocation, and
sharing generate the FSM and the datapath of the RTL description of the design.
Scheduling assigns operations to points in time, while allocation assigns each operation or variable to a hardware resource. Given a schedule, the allocation operation optimizes the amount of hardware required to implement the design.
== Multi-level logic minimization ==
Typical practical implementations of a logic function utilize a multilevel 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 tool for logic synthesis ==
=== Software tools for logic synthesis targeting [[ASIC]]s ===
* ''[http://www.synopsys.com/products/logic/design_compiler.html Design Compiler]'' by [[Synopsys]]
* ''[http://www.cadence.com/products/digital_ic/rtl_compiler/index.aspx Encounter RTL Compiler]'' by [[Cadence Design Systems]]
** ''BuildGates'' an older product by [[Cadence Design Systems]] - humorously named after [[Bill Gates]]
*''[http://www.magma-da.com/Pages/BlastCreate.html BlastCreate]'' by [[Magma Design Automation]]
*''[http://domino.research.ibm.com/tchjr/journalindex.nsf/0b9bc46ed06cbac1852565e6006fe1a0/5588d005a20caff385256bfa0067f992?OpenDocument BooleDozer:]'' Logic synthesis tool by [[IBM]] (internal IBM EDA tool)
=== Software tools for logic synthesis targeting [[FPGA]]s ===
* ''Encounter RTL Compiler'' by [[Cadence Design Systems]]
* ''[http://www.mentor.com/products/fpga_pld/synthesis/ LeonardoSpectrum and Precision (RTL / Physical)]'' by [[Mentor Graphics]]
* ''[http://www.synplicity.com/products/synplifypremier/index.html Synplify (PRO / Premier)]'' by [[Synplicity]]
* ''[http://www.magma-da.com/Pages/BlastFPGA.html BlastFPGA]'' by [[Magma Design Automation]]
* ''[[Quartus II]] integrated Synthesis by [[Altera]]
* ''XST (delivered within ISE) by [[Xilinx]]
* ''DesignCompiler Ultra'' and ''IC Compiler'' by [[Synopsys]]
* ''IspLever'' by [[Lattice Semiconductor]]
* [http://www.gepsoft.com/ GeneXproTools - Software for Logic Synthesis]
=== See also ===
*[[Logic optimization]]
== 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.
[[Category:Electronic engineering]]
[[Category:Electronic design]]
[[Category:Digital electronics]]
[[Category:Electronic design automation]]
[[Category:Electronic design automation software]]
[[fi:Logiikkasynteesi]]
[[de:Logiksynthese]]
[[ja:論理合成]]
[[zh:邏輯合成]]