Optimal buffered routing path constructions for single and multiple clock domain systems

ABSTRACT

Shrinking process geometries and the increasing use of IP components in SoC designs give rise to new problems in routing and buffer insertion. A particular concern is that cross-chip routing will require multiple clock cycles. Another is the integration of independently clocked components. This paper explores simultaneous routing and buffer insertion in the context of single and multiple clock domains. We present optimal and efficient polynomial algorithms that can be used to estimate communication overhead for interconnect and resource planning in single and multi-clock domain systems. Experimental results verify the correctness and practicality of our approach.

REFERENCES

• 1: C. J. Alpert, G. Gandham, J. Hu, S. T. Quay J. L. Neves, and S. S. Saptnekar. "STeiner Tree Optimization for Buffers and Block-ages and Bays". IEEE Transactions on Computer-Aided Design, 20(4):556--562, April 2001.
• 2: Luca P. Carloni , Kenneth L. McMillan , Alexander Saldanha , Alberto L. Sangiovanni-Vincentelli, A methodology for correct-by-construction latency insensitive design, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.309-315, November 07-11, 1999, San Jose, California, United States
• 3: D. Chapiro. Globally Asynchronous Locally Asynchronous Systems. PhD thesis, Stanford University, 1984.
• 4: Tiberiu Chelcea , Steven M. Nowick, Robust interfaces for mixed-timing systems with application to latency-insensitive protocols, Proceedings of the 38th conference on Design automation, p.21-26, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.378256]
• 5: Jason Cong, Timing closure based on physical hierarchy, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA [doi>10.1145/505388.505429]
• 6: Jason Cong , Jie Fang , Kei-Yong Khoo, An implicit connection graph maze routing algorithm for ECO routing, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.163-167, November 07-11, 1999, San Jose, California, United States
• 7: J. Cong and Z. Pan. "Interconnect Performance Estimation Models for Design Planning". IEEE Transactions on Computer-Aided Design, 20(6):739--752, June 2001.
• 8: A. Hemani , T. Meincke , S. Kumar , A. Postula , T. Olsson , P. Nilsson , J. Oberg , P. Ellervee , D. Lundqvist, Lowering power consumption in clock by using globally asynchronous locally synchronous design style, Proceedings of the 36th ACM/IEEE conference on Design automation, p.873-878, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.310091]
• 9: J. Muttersbach, T. Villiger, H. Kaeslin, N. Felber, and W. Fichtner. Globally-asynchronous locally-synchronous architectures to simplify the design of on-chip systems. In Twelfth Annual IEEE International ASIC/SOC Conference, 1999.
• 10: Minghorng Lai , D. F. Wong, Maze routing with buffer insertion and wiresizing, Proceedings of the 37th conference on Design automation, p.374-378, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337500]
• 11: Jan M. Rabaey, Digital integrated circuits: a design perspective, Prentice-Hall, Inc., Upper Saddle River, NJ, 1996
• 12: J-N. Seizovic. "Pipeline Synchronization". In IEEE ASYNC, 1994.
• 13: H. Zhou, D. F. Wong, I.-M. Liu, and A. Aziz. "Simultaneous Routing and Buffer Insertion with Restrictions on Buffer Locations". IEEE Transactions on Computer-Aided Design, 19(7):819--824, July 2000.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Algorithms implemented in hardware

  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

General Terms:
Algorithms, Design, Documentation, Theory