Technology mapping

Page 1

Exercise 1: GST Given the following circuit: apply the GST transformation to the input C. Solution draft This transformation can improve the circuit when, for example, input C is delayed with respect the other ones. The SOP of the circuit is: ܥܤ Thus Shannon’s decomposition is exploited for variable C, in particular: 1 2 Thus the two netlists are created and the two results are the inputs of a multiplexer selected by signal C: f1 0 OUT f2 1 C Exercise 2: technology mapping Given the following subject graph: and the following technology library descriptions: XNOR2(5) and NAND4(4) determine the formulation of the binate covering problem. Consider the convention PORTNAME(COST). Solution draft The following steps have to be perform: 1. use a variable mi for each match of a pattern graph in the subject graph, (mi =1 if match is chosen); 2. write a clause for each node of the subject graph indicating which matches cover this node. For example, if a subject node is covered by matches {m2, m5, m10 }, then the clause would be (m2 + m5 + m10). Remember that each node has to be covered. 3. Repeat for each subject node and take the product over all subject nodes For example, consider the port 1. It can be covered by inv, having b as input and generating g1. It will be represented by the variable m1. Port 2 can be also covered by inv, having a as input and generating g2. It will be represented by the variable m2. Then, port 3 can be covered by nand with g1 and g2 as inputs, generating g3. In this way you can generate variables for all the nodes. Moreover, consider for example ports 4, 6 and 7. They can be all covered just by port nand3, as well as ports 7,8 and 9. The resulting table is: Suppose that gi represents the port i as well as its output. For example, to cover the port 1…