Logic Synthesis in Computer Science and Engineering
This content covers topics related to logic synthesis, including Boolean algebra, incomplete Boolean functions, combinational and sequential networks, universal gate sets, and objective functions like power, performance, area, and cost. Detailed explanations and images are provided to enhance understanding of the concepts.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
CSE248 Logic Synthesis CK Cheng Dept. of Computer Science and Engineering University of California, San Diego 1
Outlines Introduction Shannon s Theorems Handy Tools Two Level Logic Synthesis Multilevel Logic Synthesis CMOS Cell Design Format Technology Mapping None Serial Parallel Topology Various Devices 2
Introduction Boolean Algebra Incomplete Boolean Functions Combinational Networks vs. Sequential Networks Universal Gate Sets AOI, {XOR, NAND}, Memory-Logic, Quantum Logic Objective Functions 3
Boolean Algebra Let B be a nonempty set with two 2-input operations, a 1-input operation ` (complement), and two distinct elements 0 and 1. Then B is called a Boolean algebra if the following axioms hold. Associative laws: (a+b)+c=a+(b+c), (a b) c=a (b c) Commutative laws: a+b=b+a, a b=b a Distributive laws: a+(b c)=(a+b) (a+c), a (b+c)=a b+a c Identity laws: a+0=a, a 1=a Complement laws: a+a =1, a a =0 <4>
Incomplete Boolean Functions We focus on binary Boolean functions There are three sets in the range On Set ?, for ? ?,? ? = 1 Don t Care Set ?, for ? ?,? ? can be set either 0 or 1 Off Set ?, for ? ?,? ? = 0. <5>
Combinational Networks Combinational Networks: Function ? ? is independent of previous history, i.e. there is no memory of previous history. Sequential Networks: Function ? ?(?),?(?) depends upon input ? ? at time ?, and the internal state: ? ? = ?(? ? 1 ,? ? 1 ) In this lecture note, we focus on combinational network. 6
Universal Gate Set Definition of Universal Gate Set: A set of gates that can implement any binary Boolean functions. {And, Or, Inverter} {XOR, NAND} {Memtransistors} {Quantum Gates} 7
Objective Functions PPAC: Power, Performance, Area, Cost Power: Number of transistors, frequency of switchings, size of transistors, leakage current (threshold voltages) Performance: Timing Area: Number of gates, size of gates Cost: Production/maintenance cost In this lecture note, we focus on #transistors, #gates, #pins 8
Shannons Theorems: Circuit Complexity Theorem: For sufficiently large n at least |??| 1 2 ?(?) of the |??| functions in ?? , where ? ? = 2?? 1???????, have circuit size at least 2?? 1. In particular, almost all ? ?? have circuit size at least 2?/?. 9
Shannons Theorems: Circuit Complexity ?+?+12?16?? ?! Lemma: At most ? ?,? = ? ?? can be computed by ?2-circuits of size b . Proof : We estimate the number of ?2-circuits of size b. For each gate there are |?2| = 16 possibilities to choose its type and ? + ? + 1 possibilities to choose each of its two predecessors, namely the other ? 1 gates, n var,iables and 2 constants. Each ?2-circuit computes at most b different functions at its gates. Finally, we take into account that each circuit is counted b! times, namely for b! different numberings of its gates. Altogether we obtain the claimed bound. functions 10
Shannons Theorems: Circuit Complexity (Stirling s Formula ?! ???+1/2? ? b!, c constant) ???? ?,? log ?? implies 2???? ? + ? + 1 + 4? + ???? ? +1 ???? 2?. For n sufficiently large, b n + 1 and therefore 2???? + ????? 1 2???? ???? 2? ????? + 6 + ???? ? + If ? 2?? 1, we could conclude 1 2 2?? 1? ???? + 6 + ???? + 2?which for large n is false. Therefore ? ?? 2?/? for sufficiently large n. ? ???? ???? 11
References Claude E. Shannon. The synthesis of two-terminal switching circuits. Bell System Tech. J., 28:59 98, 1949. Oleg B. Lupanov. On the synthesis of switching circuits. Doklady Akademii Nauk SSSR, 119(1):23 26, 1958. English translation in Soviet Mathematics Doklady. 20 Oleg B. Lupanov. Complexity of formula realization of functions of logical algebra. Problemy Kibernetiki, 3:782 811, 1962. https://eccc.weizmann.ac.il/static/books/The_Complexity_of_Boolean_ Functions 12
Shannons Theorems: Circuit Complexity Exercise: Derive the complexity of gates composed by memtransistors. 13
Shannons Theorems: Shannons Expansion Shannon s Expansion of Switch Functions ? ?1,?2, ,??, ,?? = ??? ?1,?2, ,??= 1, ,?? +?? Usage of Shannon s Expansion: Consensus Theorem: ?? + ? ? + ?? = ?? + ? ? ?(?1,?2, ,??= 0, ,??) 14
Handy Tools BDD: Binary Decision Diagrams SAT: Satisfiability Tautology Consensus Theorem Unate Functions DeMorgan s Law 15
Handy Tools: BDD ?3= ?3 ??? ???? ? = ?2?3+ ?2 16
Handy Tools: BDD BDD Reduction 17
Handy Tools: BDD BDD examples 18
Handy Tools: BDD Pairwise Operation using BDD ? ? = ????? ??+ ?? ??? ??? 19
Two Level Logic Synthesis Format: Sum of Products or Product of Sums Obj: Minimize number of terms and number of literals Input: Two of the three sets, ?,?,? Process: Enumerate primes Identify essential primes Select essential primes Select an optimal set of primes to cover the rest of on-set. 20
Two Level Logic Synthesis Primes: Largest cube ? such that ? ? , ? ? = , or ? ? ? = ????????? 21
Multilevel Logic Synthesis Factorization, Decomposition, Division Don t care sets of intermedia nodes in multilevel logic XDC: External don t care set (Given by the spec) SDC: Satisfiability don t care set ODC: Observability don t care set 22
Technology Mapping Dynamic Programming FPGA mapping 23
None Serial Parallel Topology Logic Logic Synthesis Physical Layout 24
Various Devices Quantum Logic Memrestive Logic Threshold Logic 25
