Is redundancy necessary to reduce delay

ABSTRACT

Logic optimization procedures principally attempt to optimize three criteria: performance, area and testability. The relationship between area optimization and testability has recently been explored. As to the relationship between performance and testability, experience has shown that performance optimizations can, and do in practice, introduce single stuck-at-fault redundancies into designs. Are these redundancies necessary to increase performance or are they only an unnecessary byproduct of performance optimization? In this paper we give a constructive resolution of this question in the form of an algorithm that takes as input a combinational circuit and returns an irredundant circuit that is as fast. We demonstrate the utility of this algorithm on a well known circuit, the carry-skip adder, and present a novel irredundant design of that adder. As our algorithm may either increase or decrease circuit area, we leave unresolved the question as to whether every circuit has an irredundant circuit that is at least as fast and is of equal or lesser area.

REFERENCES

• 1: Paolo Antognetti , Guiseppe Massobrio, Semiconductor Device Modeling with Spice, McGraw-Hill, Inc., New York, NY, 1990
• 2: K. Bartlett, R. Brayton, G. Hachtel, R. Jacoby, C. Morrison, R. Rudell, A. SangiovannioVincentelli, and A. Wang. Multi-level logic minimization using implicit don't c~xes. IEEE Transactions on Ccm~puter-Aided Design, 7(6):723-740, June 1988.
• 3: J. Benkoski, E. Meersch, L. Claesen, and H. De Man. Efficient algorithms for solving the false path probleln in timing verification. In The Proceedings of the International Conference on Computer. AidedDesign, 1987.
• 4: D. Brand. Redundancy and don't cares in logic synthesis. IEEE Transactions on Computers, C32(10), October 1983.
• 5: D. Brand , V. S. Iyengar, Timing Analysis Using Functional Analysis, IEEE Transactions on Computers, v.37 n.10, p.1309-1314, October 1988 [doi>10.1109/12.5996]
• 6: R. Brayton, R. RudeU, A. Sangiovanni-Vincen~elli, and A. Wang. MIS: A multiple-level logic optimization system. IEEE Transactions on Computer.Aided Design, CAD-6(6): 1062-! 081, November 1987.
• 7: D. H. Du , S. H. Yen , S. Ghanta, On the general false path problem in timing analysis, Proceedings of the 26th ACM/IEEE conference on Design automation, p.555-560, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74475]
• 8: L. Fein. Redundancy- a misleading misnomer. In Redundancy Techniques for Computing Systems, pages 1-8. Spartan Books, 1962.
• 9: J. Fishbum and A. Dunlop. TILOS: A posynomial programming approach to transistor sizing. In The Proceedings of the lnterna. tional Conference on Computer-Aided Design, 1985.
• 10: G. Hachtel, R. Jacoby, K. Keutzer, and C. Morrison. On properties of algebraic transformations and the multifault testability of multilevel logic, in The Proceedings of the international Conference on Cootputer-Aided Design, November 1989.
• 11: N. Jouppi. TV: An nMOS timing analyzer. In The Proceedings of the Tlu'rd Caltech VLSI Conference, 1983.
• 12: K. Keutzer and M. Vancura. Timing optimization in a logic synthesis system. In The Proceedings of the International Workshop on Logic Synthesis, Amsterdam. North-Holland, May 1988.
• 13: M. Lehman and N. Burla. Skip techniques for high-speed carrypropagation in binary arithmetic units. IRE Transactions on Electronic Computers, pages 691--698, December 1961.
• 14: R. Lisanke. May 1989. Logic synthesis benchmark circuits for the International Workshop on Logic Synthesis.
• 15: P. C. McGeer , R. K. Brayton, Efficient algorithms for computing the longest viable path in a combinational network, Proceedings of the 26th ACM/IEEE conference on Design automation, p.561-567, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74476]
• 16: Patrick C. McGeer , Robert K. Brayton, Provably correct critical paths, Proceedings of the decennial Caltech conference on VLSI on Advanced research in VLSI, p.119-142, June 1989, Cambridge, Massachusetts, United States
• 17: Patrick C. McGeer , Robert K. Brayton , Richard Rudell , A. Sangiovanni-Vincentelli, Extended stuck-fault testability for combinational networks, Proceedings of the sixth MIT conference on Advanced research in VLSI, p.239-259, March 1990, Boston, Massachusetts, United States
• 18: J. Ousterhout. A switch-level timing veritier for digital MOS circuits. IEEE Transactions on Computer-Aided Design, CAD-4(3), July 1985.
• 19: S. Perremans , L. Claesen , H. De Man, Static timing analysis of dynamically sensitizable paths, Proceedings of the 26th ACM/IEEE conference on Design automation, p.568-573, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74477]
• 20: K. Roy, J. Abraham, K. De, and S. Lusky. Synthesis of delay fault testable combinational logic. In The Proceedings of the International Conference on Computer-Aided Design, pages 418-421, November 1989.
• 21: R. Rudell. Personal communication. June 1989.
• 22: M. Schulz and E. Auth. Advanced autonuttic test pattern generation and redundancy identification techniques. In The Proceedings of the International Fault Tolerant Computing Conference, June 1988.
• 23: K. Singh, A. Wang, R. Brayton, and A. Sangiovanni-Vincentetli. Timing optimization of combinational logic, in The Proceedings of the International Conference on Comp uter-Aided Design, pages 282-285, 1988.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Optimization

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.2 Reliability and Testing**
          Subjects: Testability**

General Terms:
Algorithms, Design, Performance