Simultaneous signal and power routing under K model

ABSTRACT

In this paper, we study the min-area simultaneous signal and power routing problem under a given noise bound (i.e., the SPR/NB problem). The resulting SPR/NB solution is free of capacitive noise and satisfies a given inductive noise bound under the $K_{eff}$ model. We first develop the pre-routing area estimation techniques for the min-area simultaneous shield insertion and net ordering (SINO) solutions. We then propose a two-phase approach to solve the min-area SPR/NB problem: in the first phase, we define a regular power/ground (P/G) structure according to the above area estimation; and in the second phase, we carry out SINO procedures to search for the best solution in a very limited neighborhood of the pre-defined P/G structure. Experimental results show that our approach is able to achieve the min-area SPR/NB solution efficiently by searching only the first-order neighborhood of the pre-defined P/G structure. Our ongoing work extends the interconnect estimation and two-phase algorithm to an explicit RLC noise model.

REFERENCES

• 1: Jason Cong , Lei He , Cheng-Kok Koh , Patrick H. Madden, Performance optimization of VLSI interconnect layout, Integration, the VLSI Journal, v.21 n.1-2, p.1-94, Nov. 1996 [doi>10.1016/S0167-9260(96)00008-9]
• 2: J. Cong. Challenges and opportunities for design innovations in nanometer technologies. SRC Design Sciences Concept Paper, 1997.
• 3: Kevin M. Lepak , Irwan Luwandi , Lei He, Simultaneous shield insertion and net ordering under explicit RLC noise constraint, Proceedings of the 38th conference on Design automation, p.199-202, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.378463]
• 4: Lei He , Kevin M. Lepak, Simultaneous shield insertion and net ordering for capacitive and inductive coupling minimization, Proceedings of the 2000 international symposium on Physical design, p.55-60, May 2000, San Diego, California, United States [doi>10.1145/332357.332374]
• 5: Guoan Zhong , Cheng Kok Koh , Kaushik Roy, A twisted-bundle layout structure for minimizing inductive coupling noise, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 6: A. Ruehli. Equivalent circuit models for three-dimensional multiconductor systems. IEEE Trans. on MIT, 1974.
• 7: L. He, N. Chang, S. Lin, and O. S. Nakagawa. An efficient inductance modeling for on-chip interconnects. In Proc. IEEE Custom Integrated Circuits Conference, pages 457-460, May 1999.
• 8: Shen Lin , Norman Chang , Sam Nakagawa, Quick On-Chip Self- and Mutual-Inductance Screen, Proceedings of the 1st International Symposium on Quality of Electronic Design, p.513, March 20-22, 2000
• 9: Jason Cong , Lei He , Andrew B. Kahng , David Noice , Nagesh Shirali , Steve H.-C. Yen, Analysis and justification of a simple, practical 2 1/2-D capacitance extraction methodology, Proceedings of the 34th annual conference on Design automation, p.627-632, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266303]
• 10: K. M. Lepak, M. Xu, and L. He. Simultaneous shield insertion and net ordering for capacitive and inductive coupling minimization. submission to IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 2000.
• 11: L. He and M. Xu. Characteristics and modeling for on-chip interconnects. In University of Wisconsin, Technical Report, ECE-00-001, 2000.
• 12: Cuthbert Daniel , Fred S. Wood, Fitting Equations to Data: Computer Analysis of Multifactor Data, John Wiley & Sons, Inc., New York, NY, 1980
• 13: P. Sherrod. Nonlinear Regression Analysis Program, 1997.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Interconnection architectures (e.g., common bus, multiport memory, crossbar switch)

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

  C. Computer Systems Organization

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

Keywords:
interconnect design, interconnect estimation, net ordering, on-chip inductance, shield insertion