Understanding and addressing the impact of wiring congestion during technology mapping

ABSTRACT

Traditionally, interconnect effects are taken into account during logic synthesis via wireload models, but their ineffectiveness for DSM technologies has been demonstrated and various physical synthesis approaches have been spawned to address the problem. Of particular interest is that logic block size is no longer dictated exclusively by total cell area, yet synthesis optimization objectives are aimed specifically at minimizing the number and size of cells. Methodologies that incorporate congestion within the logic synthesis objective function have been proposed in [9][10][11] and [15]; however, as we will demonstrate, predicting the true congestion prior to layout is not possible, and the efficacy of any approach can only be evaluated after routing is completed within the fixed die size. In this paper we propose a practical, complete methodology which first performs congestion-aware technology mapping using a global weighting factor for the cost function [15], and then applies incremental localized unmapping and remapping on congested areas. This complete approach addresses the problem that one global factor is not ideally suited for all regions of the designs. Most importantly, through the application of this methodology to industrial examples we will show that any attempt at a purely top-down single-pass congestion-aware technology mapping is merely wishful thinking.

REFERENCES

• 1: H. B. Bakoglu. "Circuits, Interconnections and Packaging". Addison Wesley, Reading, MA, 1990.
• 2: Dennis Sylvester , Kurt Keutzer, Getting to the bottom of deep submicron, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.203-211, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.288614]
• 3: An integrated placement and synthesis approach for timing closure of PowerPC/sup TM/ microprocessors, Proceedings of the 1997 International Conference on Computer Design (ICCD '97), p.206, October 12-15, 1997
• 4: Padmini Gopalakrishnan , Altan Odabasioglu , Lawrence Pileggi , Salil Raje, Overcoming wireload model uncertainty during physical design, Proceedings of the 2001 international symposium on Physical design, p.182-189, April 01-04, 2001, Sonoma, California, United States [doi>10.1145/369691.369769]
• 5: K. Keutzer, DAGON: technology binding and local optimization by DAG matching, Proceedings of the 24th ACM/IEEE conference on Design automation, p.341-347, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37940]
• 6: E. Detjens, G. Gannot, R. Rudell, A. Sangiovanni-Vincentelli, and A. Wang. "Technology Mapping in MIS". In Proc. ACM/IEEE Intl. Conf. on Computer-Aided Design, pages 116--119, Nov. 1987.
• 7: Massoud Pedram , Narasimha Bhat, Layout driven technology mapping, Proceedings of the 28th conference on ACM/IEEE design automation, p.99-105, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127635]
• 8: A. H. Salek, J. Lou, and M. Pedram. "An Integrated Logical and Physical Design Flow for Deep Submicron Circuits". IEEE Transac¿tions on CAD, vol. 18, no. 9, pages 1305--1315, Sept. 1999.
• 9: M. Pedram, and N. Bhat. "Layout Driven Logic Restructuring/Decomposition". In Proc. ACM/IEEE Intl. Conf. on Computer-Aided Design, pages 134--137, Nov. 1991.
• 10: Hirendu Vaishnav , Massoud Pedram, Minimizing the routing cost during logic extraction, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.70-75, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217509]
• 11: Thomas Kutzschebauch , Leon Stok, Congestion aware layout driven logic synthesis, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 12: G. Meixner, and U. Lauther. "Congestion-Driven Placement Using a New Multi-Partitioning Heuristic". In Proc. ACM/IEEE Intl. Conf. on Comp. Aided Design, pages 332--335, Nov. 1990.
• 13: Phiroze N. Parakh , Richard B. Brown , Karem A. Sakallah, Congestion driven quadratic placement, Proceedings of the 35th annual conference on Design automation, p.275-278, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277121]
• 14: Lalgudi N. Kannan , Peter R. Suaris , Hong-Gee Fang, A methodology and algorithms for post-placement delay optimization, Proceedings of the 31st annual conference on Design automation, p.327-332, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196399]
• 15: D. Pandini , L. Pileggi , A. Strojwas, Congestion-Aware Logic Synthesis, Proceedings of the conference on Design, automation and test in Europe, p.664, March 04-08, 2002
• 16: M. Borgatti, F. Lertora, B. Foiret, and L. Cali'. "A Reconfigurable System featuring Dynamically Extensible Embedded Microprocessor, FPGA and Customisable I/O". In Proc. IEEE CICC, May 2002.

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Layout; Placement and routing

General Terms:
Algorithms, Design, Performance