© P.Prinetto - all rights reserved Version 2.0 6.4.16.4 – Tackling circuit complexity (1)ECE 465Tackling circuit complexity (1)Paolo PRINETTOPolitecnico di Torino (Italy)University of Illinois at Chicago, IL (USA)[email protected]@uic.eduwww.testgroup.polito.itLecture 6.426.4 Goal• This lecture is the former part of a group of 2 lectures aiming at presenting methods used in manual combinational synthesis to overcome the limitations of the purely manual approach presented in lectures 6.1-6.3• It eventually shows how minimization tools can be used to exploit circuit complexity.36.4 Prerequisites • Lectures 5.2 and 6.346.4 Homework• Students are warmly encouraged to solve the proposed exercises56.4 Further readings • No particular suggestion66.4 Outline• Tackling the complexity• ROM-based synthesis• K-map partitioning• Partially automated approach.© P.Prinetto - all rights reserved Version 2.0 6.4.26.4 – Tackling circuit complexity (1)ECE 46576.4 Tackling the complexityPurely manual synthesis can be applied when the # of PIs is very limited, only.To overcome such a very strong limitation, several approaches are possible, characterized by different applicability – cost trade-offs.86.4 Tackling the complexityWe shall consider the following ones:• ROM-based synthesis• K-map partitioning• Partitioning based techniques• RT level minimizations• Synthesis by iterating basic cells.96.4 Outline• Tackling the complexity⇒ROM-based synthesis• K-map partitioning • Partially automated approachRom-based SynthesisAny n-inputs / m-outputs combinational circuit can easily be implemented resorting to a (2nx m) ROM.PInmPOROM2n× mPInmPOaddroutcombinationalcircuitRom-based SynthesisThe value that the m-outputs of the target circuit get when the value j is applied at the circuit’s n-inputs must be stored in the m bits of the j-thcell of the ROM.PInmPOROM2n× mPInmPOaddrout≡combinationalcircuit126.4 ExamplesFor sake of clarity, we shall consider some of the examples already seen in lecture 6.3.© P.Prinetto - all rights reserved Version 2.0 6.4.36.4 – Tackling circuit complexity (1)ECE 465136.4 Exercise #6.3.1Design a combinational circuit with 1 output Uand an input X (3 downto 0) that, when it receives on X an unsigned hexadecimal digit X, provides, on U, a logical value 1 iff:X < 4 or X > 8.x16U146.4 0000 10001 10010 10011 10100 00101 00110 00111 0Solution(ROM 16x1)1000 01001 11010 11011 11100 11101 11110 11111 1x(16)UAddress Content Address Content156.4 Design a combinational circuit with a 4-bit input and a 3-bit output such that, when it receives on its input a hexadecimal digit X, provides, on its output:sqrt (X) Exercise #6.3.2√166.4 0000 0000001 0010010 0100011 0100100 0100101 0110110 0110111 011Solution(ROM 16x3)1000 0111001 1001010 1001011 1001100 1001101 1001110 1001111 100Address Content Address Content√176.4 Look-up tablesROM-based synthesis is particularly suited for combinational circuits acting as look-up table, i.e., tables storing values to be randomly read.186.4 Outline• Tackling the complexity• ROM-based synthesis⇒K-map partitioning• Partially automated approach© P.Prinetto - all rights reserved Version 2.0 6.4.46.4 – Tackling circuit complexity (1)ECE 465196.4 K-map partitioning orMUX-based synthesisSuch an approach stems from the Boole’s expansion theorem (slide # 55 of lecture 3.1):every Boolean function f : Bn → B : f (x1, x2, …, xn) can be expressed as: f (x1, x2, …, xn) = = x1’ · f0(0, x2, …, xn) + x1· f1(1, x2, …, xn) ∀ (x1, x2, …, xn) ∈ B206.4 Basic ideaThe expressionf (x1, x2, …, xn) = x1’ · f0+ x1· f1can obviously by interpreted as:If x1 = 0 (i.e., x1’ = 1) then f = f0else f = f1which leads to the following implementation:216.4 x101Combinationalnetworkimplementingf0Combinationalnetworkimplementingf1x2, …, xnx2, …, xnfIf x1 = 0 (i.e., x1’ = 1) then f = f0else f = f1226.4 ... and so on ... The process can be easily iterated...236.4 x3x2x1...246.4 ExampleConsider the following map:abc00 01 11 100 11001 1001U© P.Prinetto - all rights reserved Version 2.0 6.4.56.4 – Tackling circuit complexity (1)ECE 465256.4 ExampleConsider the following map:It can be partitioned as follows:abc00 01 11 100 11001 1001U266.4 ExampleConsider the following map:It can be partitioned as follows:abc00 01 11 100 11001 1001UabcIf c=0 then00 01 11 100 1100If c=1 then:00 01 11 101 1001UabcU276.4 ExampleConsider the following map:It can be partitioned as follows:abc00 01 11 100 11001 1001UabcIf c=0 then00 01 11 100 1100If c=1 then:00 01 11 101 1001UabcUa’b’286.4 ExampleConsider the following map:It can be partitioned as follows:abc00 01 11 100 11001 1001UIf c=0 then U = a’if c=1 then U = b’296.4 ExampleConsider the following map:It can be partitioned as follows:abc00 01 11 100 11001 1001UIf c=0 then U = a’if c=1 then U = b’a’b’c0 1U306.4 Alternative implementationabcU00 01 11 100 1 1 0 01 1 0 0 1© P.Prinetto - all rights reserved Version 2.0 6.4.66.4 – Tackling circuit complexity (1)ECE 465316.4 Alternative implementationabcU00 01 11 100 1 1 0 01 1 0 0 1326.4 Alternative implementationabc00 01 10 11UU1c’0c1c’c 0s1as0b00 01 11 100 1 1 0 01 1 0 0 1336.4 Exercise #6.3.4Design a comparator which, receiving in input:• A(1 downto 0) and B(1 downto 0)• a signal 2C/~UM specifying the coding used for A and B (1=2's complement, 0=unsigned magnitude)provides 3 outputs A_GT_B, A_EQ_B and A_LT_Bsuch that:• A_GT_B = 1 iff A > B• A_EQ_B = 1 iff A = B• A_LT_B = 1 iff A < B.>=<346.4 Solution00 01 11 1000011110A1A0B1B000 01 11 102C/~UM =0> = <(2C)> = <(UM)2C/~UM =1>=<356.4 UM2CA_GT_BAB>=<>=<2C/~UMA_EQ_BA_LT_B>=<366.4 Outline• Tackling the complexity• ROM-based synthesis• K-map partitioning⇒Partially automated approach© P.Prinetto - all rights reserved Version 2.0 6.4.76.4 – Tackling circuit complexity (1)ECE 465376.4 Partially automated approachLogic level refinement and optimization can be easily performed resorting to the logic minimizer Espresso, developed at U.C. Berkeley (USA).386.4 behavior structure physicalStep #3.1.1: Logic level refinementssystemRTlogicSpecsRepresentation of POs in Espresso format396.4 Espresso Format.i 3.o 100- 11-0 111- 1.e# of inputs# of outputsinput_cube output_valueinput_cube