With the advent of battery operated computers and hand held digital electronic devices, circuit designers have become more conscious of the need to reduce power consumed by the integrated circuits (ICs) used in their designs.
Various techniques for reducing the power consumed in electronic circuits have been applied at all levels of design. For a survey of generally applicable techniques, attention is directed to "Hyper-LP: A System For Power Minimization Using Architectural Transformations", by A. P. Chandrakasan, M. Potkonjak, J. Rabaey, and R. W. Broderson, Proceedings of the International Conference on Computer-Aided Design, pp.300-303, (November 1992), [IEEE 0-8186-3010-8/92].
Logic-Optimization techniques modify well known algorithms for logic optimization such as node simplification and partial collapsing, which are well known in the art. Other works of interest are "On Average Power Dissipation and Random Pattern Testability of CMOS Combinational Logic Circuits", by A. Shen, A. Ghosh, S. Devadas, and K. Keutzer, Proceedings of the International Conference on Computer-Aided Design, pp. 402-407, (November 1992), [IEEE 0-8186-3010-8/92], discussing the logic-optimization technique of disjoint cover realization; "Decomposition for Minimum Transition Activity", by R. Murgai, R. K. Brayton, and A. Sangiovanni-Vincentelli, Proceedings of the Low-Power Workshop, pp. 1-10, Napa, Calif., (April 1994) [Dept. EECS, Univ. of Cal. Berkeley], discussing the technique of node decomposition; and "Technology Mapping for Low Power", by V. Tiwari, P. Ashar, and S. Malik, Proceedings of the 30th ACM/IEEE Design Automation Conference, pp. 74-79, (June 1993), [ACM 0-89791-577-1/93/0006-0074], and in "Technology Decomposition and Mapping Targeting Low Power Dissipation", by C. Y. Tsui, M. Pedram, and A. M. Despain, Proceedings of the 30th ACM/IEEE Design Automation Conference, pp. 68-73, (June 1993), [ACM 0-89791-577-1/93/0006/0068], both discussing technology mapping to obtain circuits with reduced switching activity.
A problem with logic-optimization techniques is that circuit switching time and propagation delays are often not accounted for in these standard logic optimization algorithms. All of the above techniques are based on a zero-delay model, where only the final stable value on each gate is considered. It remains unclear whether results obtained using the above techniques are related to the actual power consumed in the circuit. As a result, none of these techniques have reported results with an actual significant power reduction.
The State-Encoding approach is based on the observation that a sizable fraction of logic in most circuits is devoted to computing the next state function, as discussed in "State Assignment for Low Power Dissipation", by L. Benini, G. DeMicheli, Proceedings of EDAC'94, (1994). As a result, it is reasoned that if neighboring states in the state transition graph differ in very few bits, few transitions will be required on most input-vector changes. Re-encoding of sequential logic circuits to minimize transition activity is described in the paper, "Re-encoding Sequential Circuits to Reduce Power Dissipation", by G. D. Hachtel, M. Hermida, A. Pardo, M. Poncino, and F. Somenzi, Proceedings of the International Conference on Computer-Aided Design, pp. 70-73, (November 1994), [ACM 0-89791-690-5/94/0011/0070]. A basic problem with state-encoding approaches is that it is often difficult to make strong statements about the transition activity in a circuit when the input-output function and the state code is known but the actual implementation of the Combinational logic circuit is not yet known. This is not to say that this technique cannot be usefully applied in conjunction with the techniques disclosed and claimed herein.
The Pre-Computation technique attempts to reduce power consumption by selectively pre-computing some of the output logic values one clock cycle in advance. The pre-computed values are then used to reduce the transition activity in the next clock cycle. While a few pre-computation architectures have been explored, for instance, "Precomputation-Based Sequential Logic Optimization for Low Power", by M. Alidina, J. Monteiro, S. Devadas, A. Ghosh, and M. Papaefthymiou, Proceedings of the International Conference on Computer-Aided Design, pp. 74-81, (November 1994), [ACM 0-89791-690-5/94/0011/0074], it appears that for effective power reduction a specific pre-computation architecture must be designed for each circuit class. The technique appears to be more effective on data path circuits with a regular logic structure, e.g., arithmetic. However, the technique is not as effective on control circuits that do not have regular logic structures, also called random logic.
A general objection to these approaches is that it is often difficult to estimate either a peak or an average power consumption of a circuit, which are complex functions of both the logical and timing properties of the circuit. Given a delay model based upon timing properties, efficiently determining the logical behavior of circuits over time, under all possible input vectors is a very difficult problem. Thus, one is often forced to rely on timing simulation. However, there is neither a guarantee that the set of input test vectors chosen for simulation is representative of the whole input space nor that the set of input test vectors contains the worst-case vector.
FIG. 1a and 1b illustrate typical Shannon graphs. The Shannon graph in FIG. 1a includes a set of nodes, also called switching nodes, each having one or more input edges and two output edges. In the example, the Shannon graph labeled f, 20, has a root node 10 labeled X.sub.1 and output edges 30 and 40, labeled x.sub.1 and x,.sub.'1, respectively. Note: x' as used herein is equivalent to x, the logical complement to x.
A drawback with current circuits is that certain nodes in a circuit may not affect the eventual output state of the circuit. This drawback is illustrated below in the following example. In this example, three nodes are labeled A, B and C, having input states denoted X, Y and Z: EQU A=X AND Y EQU B=Z AND Y EQU C=A OR B
In the case where X=0, Y=1 and Z=1, the output state of A, B and C are as follows: A=0, B=1 and C=1. Now if the input states changes from X=0, Y=1 and Z=1 to X=1, Y=1 and Z=1, assuming a unit delay, node A changes from 0 to 1, node B remains at 1, and node C remains at 1. Since the output for B did not change, the output state of C was independent of the value of A. The final state of A was not needed to determine the correct output of the circuit with respect to node C, because the result of the transition of A from 0 to 1 did not propagate to the node C. Because node A switched without having an impact on node C, the power consumed by the switching of A could have been saved. In larger circuits containing even greater number of nodes in multiple pathways, many transitions do not eventually propagate to the output. Thus, eliminating those components whose transitions do not propagate to the output in a circuit is important.
What is needed in this art is a method for deriving a low power circuit from a Shannon graph. Since transitions depend not only upon logical properties, but also upon timing properties of circuit components, it is desirable in this art to reduce the number of 0 to 1 transitions on switching nodes. In a circuit derived from a Shannon graph, most of the power consumed is due to the charging of gate inputs by primary inputs leads, i.e. input capacitance. Reducing the amount of input capacitance on the primary input leads is thus important.