Trace driven logic synthesis—application to power minimization

ABSTRACT

A trace driven methodology for logic synthesis and optimization is proposed. Given a logic description of a digital circuit C and an expected trace of input vectors T an implementation of C that optimizes a cost function under application of T is derived. This approach is effective in capturing and utilizing the correlations that exist between input signals on an application specific design. The idea is novel since it propose synthesis and optimization at the logic level where the goal is to optimize the average case rather than the worst case for a chosen cost metric. This paper focuses on the development of algorithms for trace driven optimization to minimize the switching power in multi-level networks. The average net power reduction (internal plus I/O power) obtained on a set of benchmark FSMs is 14%, while the average reduction in internal power is 25%. We also demonstrate that the I/O transition activity provides an upper bound on the power reduction that can be achieved by combinational logic synthesis.

References

1. 1.R. K. Brayton, G. D. Hachtel, C. T. McMullen, and A. L. Sangiovanni-Vincentelli. Logic Minimization Algorithms for VLSI Synthesis. Kluwer Academic Publishers, 1984.
2. 2.O. Coudert. On Solving Covering Problems. In Proc. of the Design Automation Conf., pages 197-202, June 1996.
3. 3.O. Coudert and R. Haddad. Integrated Resynthesis for Low Power. In ISLPED Digest of Technical Papers, pages 169-174, August 1996.
4. 4.G. D. Hachel, M. Hermida, A. Pardo, M. Poncino, and E Somenzi. Re-Encoding Sequential Circuits to Reduce Power Dissipation. In Proceedings of the Design Automation Conference, pages 70-73, June 1994.
5. 5.S. Iman and M. Pedram. Logic Extraction and Factorization for Low Power. In Proceedings of the Design Automation Conference, pages 248-253, June 1995.
6. 6.S. Iman and M. Pedram. Two-Level Logic Minimization for Low Power. In Proceedings of the International Conference on Computer- Aided Design, pages 433-438, November 1995.
7. 7.R. Marculescu, D. Marculescu, and M. Pedram. Efficient Power Estimation for Higly Correlated Input Streams. In Proceedings of the Design Automation Conference, pages 628-634, June 1994.
8. 8.R. Murgai, R. K. Brayton, and A. L. Sangiovanni-Vincentelli. Decomposition for Minimum Transition Activity. In Proceedings of the Low Power Workshop - Napa Valley, April 1994.
9. 9.E N. Najm. A Survey of Power Estimation Techniques in VLSI Circuits. IEEE Transactions on VLSI Systems, 2:446-455,1994.
10. 10.E N. Najm. Feedback, Correlation, and Delay Concerns in the Power Estimation of VLSI Circuits. In Proceedings of the 32tn Design Automation Conference, pages 612-617, June 1995.
11. 11.J. Rajski and J. Vasudevamurthy. The Testability-Preserving Concurrent Decomposition and Factorization of Boolean Espression. IEEE Transactions on Computer-Aided Design, 11:778-793,1992.
12. 12.K. Roy and S.C. Prasad. Circuit Activity Based Logic Synthesis for Low Power Reliable Operations. IEEE Transactions on VLSI Systems, 1:503-513,1993.
13. 13.Richard L. Rudell. Logic Synthesis for VLSI Design. PhD thesis, University of California Berkeley, Electronics Research Laboratory, College of Engineering, University of California, Berkeley, CA 94720, April 1989. Memorandum No. UCB/ERL M89/49.
14. 14.C-Y. Tsui, R. Marculescu, D. Marculescu, and M. Pedram. Improving the Efficiency of Power Simulators by Input Vector Compaction. In Proceedings of the Design Automation Conference, pages 165- 168, June 1996.
15. 15.C-Y. Tsui, M. Pedram, and A. M. Despain. Efficient Estimation of Dynamic Power Consumption under a Real Delay Model. In Proceedings of the International Conference on Computer-Aided Design, pages 224-228, Nov 1993.
16. 16.C-Y. Tsui, M. Pedram, and A. M. Despain. Exact and Approximate Methods for Calculating Signal and Transition Probabilities in FSMs. In Proceedings of the 29th Design Automation Conference, pages 18-23, June 1994.
17. 17.A. Wang. Algorithms for Multi-Level Logic Optimization. PhD thesis, University of California Berkeley, Electronics Research Laboratory, College of Engineering, University of California, Berkeley, CA 94720, April 1989.

Index Terms

• Applied computing

  • Physical sciences and engineering

    • Engineering

• Hardware

  • Electronic design automation

    • High-level and register-transfer level synthesis

  • Hardware validation

    • Functional verification

      • Simulation and emulation

  • Integrated circuits

    • Logic circuits