Technology Mapping
- PDF / 144,601 Bytes
- 4 Pages / 547.087 x 737.008 pts Page_size
- 83 Downloads / 199 Views
T
Technology Mapping
2. Janson, S.: Large Deviation Inequalities for Sums of Indicator Variables. Technical Report No. 34, Department of Mathematics, Uppsala University (1994) 3. Johnson, N.L., Kotz, S.: Urn Models and Their Applications. Wiley, New York (1977) 4. Kolchin, V.F., Sevastyanov, B.A., Chistyakov, V.P.: Random Allocations. Wiley, New York (1978) 5. Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, New York (1995) 6. Shwartz, A., Weiss, A.: Large Deviations for Performance Analysis. Chapman-Hall, Boca Raton (1994) 7. Weiss, A.: Personal Communication (1993)
Technology Mapping 1987; Keutzer
Technology Mapping, Figure 1 Subject graph (DAG) of a Boolean circuit expressed using NAND2 and INVERTER gates
KURT KEUTZER, KAUSHIK RAVINDRAN Department of Electrical Engineering and Computer Science, University of California at Berkeley, Berkeley, CA, USA Keywords and Synonyms Library-based technology mapping; Technology dependent optimization Problem Definition Technology mapping is the problem of implementing a sequential circuit using the gates of a particular technology library. It is an integral component of any automated VLSI circuit design flow. In the prototypical chip design flow, combinational logic gates and sequential memory elements are composed to form sequential circuits. These circuits are subject to various logic optimizations to minimize area, delay, power and other performance metrics. The resulting optimized circuits still consist of primitive logic functions such as AND and OR gates. The next step is to efficiently realize these circuits in a specific VLSI technology using a library of gates available from the semiconductor vendor. Such a library would typically consist of gates of varying sizes and speeds for primitive logic functions, (AND and OR) and more complex functions (exclusive-OR, multiplexer). However, a naïve translation of generic logic elements to gates in the library will fall short of realistic performance goals. The challenge is to construct a mapping that maximally utilizes the gates in the library to implement the logic function of the circuit and achieve some performance goal—for example, minimum area with the critical path delay less than a target value. This is accomplished by technology mapping. For the sake of simplicity, in the following discussion it is presumed that the sequential memory elements are stripped from the digital circuit and mapped directly into memory
Technology Mapping, Figure 2 Library of pattern graphs (composed of NAND2 and INVERTER gates) and associated costs
elements of the particular technology. Then, only Boolean circuits composed of combinational logic gates remain to be mapped. Further, each remaining Boolean circuit is necessarily a directed acyclic graph (DAG). The technology mapping problem can be restated in a more general graph-theoretic setting: find a minimum cost covering of the subject graph (Boolean circuit) by choosing from the collection of pattern graphs (gates) available in a library. The inputs to the p
Data Loading...
