Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

The first stage of over-the-cell routing in the horizontally connected vertically connected (HCVC) model is formulated as followings: Given two rows of terminals, find a planar routing to connect a subset of nets (with weights) on each row of terminals using a fixed number of tracks to maximize the total weight. This problem is called the two row fixed height planar routing (TFPR) problem [CPL93]. The complexity of the TFPR problem was unknown up to now. An approximation algorithm for the TFPR problem was presented in [CPL93]. In this paper we present a O(n2*h2) time algorithm to solve the TFPR problem optimally, where n is the number of terminals and h is the height of the standard cells. Our algorithm can be used to improve the performance of several over-the-cell channel routers including the ones in [CPL93] and [HSS93].

REFERENCES

• CL90: J. Cong and C.L.Liu, "Over-the-cell Channel Routing", IEEE Trans. on CAD, vol.9, no.4, pp.408-418, April 1990.
• CPL93: J.Cong, B. Preas, and C.L. Liu, "Physical Models and Efficient Algorithms for Over-the-cell Routing in Standard Cell Design", IEEE Trans. on CAD, vol. 12, no.5, pp. 723-734, 1993.
• DSMP94: S. Danda, N. Sherwani, S. Madhwapathy, and A. Panyam "An Optimal Algorithm for the Two Row Maximum Planar Subset Problem," Manuscript 1994.
• GN87: G. Gudmundsson, and S. Ntafos, "Channel Routing with Superterminals", Proc. 25th Allerton Conf., pp. 375-376, 1987.
• HSS93: N.D Holmes, N. Sherwani, and M. Sarrafzadeh, "Utilization of Vacant Terminals for Improved over-the-cell channel routing", IEEE Trans. on CAD, vol.12, no.6, pp.780-792, 1993.
• LT94: X. Liu and I.G. Tollis, "Improving Over-The-Cell Channel Routing in Standard Cell Design," Tech. Rep. UTDCS-9-94, Jan. 1994.
• LPHL91: Min-Siang Lin , Hourng-Wern Perng , Chi-Yi Hwang , Youn-Long Lin, Channel density reduction by routing over the cells, Proceedings of the 28th conference on ACM/IEEE design automation, p.120-125, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127640]
• RF82: Ronald L. Rivest , Charles M. Fiduccia, A “greedy” channel router, Proceedings of the 19th conference on Design automation, p.418-424, January 1982
• SS87: Y. Shiraishi and Y. Sakemi, "A Permeation Router", IEEE Trans. on CAD, vol, CAD-6, pp. 462-471, May 1987.

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: Standard cells**

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

General Terms:
Algorithms, Design, Theory