Efficient global fanout optimization algorithms

ABSTRACT

Fanout optimization is a fundamental problem in timing optimization. Most of the research has focused on the fanout optimization problem for a single net (or the local fanout optimization problem - LFO). The real goal, however, is to optimize the delay through the entire circuit by fanout optimization incurring minimum area penalty and without violating the pin loading constraints. This is known as the global fanout optimization (GFO) problem. In this paper, we show that the techniques proposed so far in the literature are either impractical or ineffective for large designs. We propose simple yet efficient and effective schemes for GFO and show that they outperform the "nearly-optimum" reverse topological (RT) algorithm [9] on large industrial designs. One of these schemes yields only 0.3% worse circuit delay on average, but incurs only 18.5% of the area penalty as compared to the RT algorithm and is about 3 times faster. A popularly used mincut-based strategy [7] was not found to be effective.

REFERENCES

• 1: C. Leonard Berman , J. Lawrence Carter , Ken F. Day, The fanout problem: from theory to practice, Proceedings of the decennial Caltech conference on VLSI on Advanced research in VLSI, p.69-99, June 1989, Cambridge, Massachusetts, United States
• 2: G. De Micheli. Performance-Oriented Synthesis fo Large-Scale Domino CMOS Circuits. IEEE Transactions on Computer-Aided Design, CAD-6(5):751-765, 1987.
• 3: H. J. Hoover , M. M. Klawe , N. J. Pippenger, Bounding Fan-out in Logical Networks, Journal of the ACM (JACM), v.31 n.1, p.13-18, Jan. 1984 [doi>10.1145/2422.322412]
• 4: Rajeev Murgai, On the global fanout optimization problem, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.511-515, November 07-11, 1999, San Jose, California, United States
• 5: Lukas P. P. P. van Ginneken. Buffer Placement in Distributed RC-tree Networks for Minimum Elmore DElay. In ISCAS, pages 865-868, 1990.
• 6: Kanwar Jit Singh, Performance optimization of digital circuits, University of California at Berkeley, Berkeley, CA, 1992
• 7: Kanwar Jit Singh , Alberto Sangiovanni-Vincentelli, A heuristic algorithm for the fanout problem, Proceedings of the 27th ACM/IEEE conference on Design automation, p.357-360, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123303]
• 8: K. J. Singh, a. R. Wang, R. K. Brayton, and A. Sangiovanni-Vincentelli. Timing Optimization of Combinational Logic. In ICCAD, pages 282-285. IEEE, 1988.
• 9: Herve Jacques Touati, Performance-oriented technology mapping, University of California at Berkeley, Berkeley, CA, 1991

INDEX TERMS

Primary Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.4 Microprogram Design Aids
          Subjects: Optimization

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS

  C. Computer Systems Organization

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Electronics

General Terms:
Algorithms, Design, Measurement, Performance, Theory