An algorithm for one and half layer channel routing

ABSTRACT

Channel routing is one of the key problems in the automatic layout design of LSI chips. This paper presents an efficient routing algorithm for one-and-half layer channel model which is based on single layer metal mask and fixed polysilicon crossunders in CMOS gate array. The algorithm makes parallel horizontal routing in each zone by means of ordering and prediction. The nets contend for crossunders in a greedy approach. This results in higher probability of routing success and less crossunders occupied (equally less via holes). Furthermore, by inserting interactive information at the same time of execution if necessary, the router provides more chances of 100% routing success.

REFERENCES

• 1: David N. Deutsch, A “Dogleg” channel router, Proceedings of the 13th conference on Design automation, p.425-433, June 28-30, 1976, San Francisco, California, United States [doi>10.1145/800146.804843]
• 2: T. Yoshimura and E. S. Kuh, "Efficient algorithms for channel routing", IEEE Trans. on CAD/ICAS, vol.CAD-1, no.l, pp.25-35, 1982.
• 3: Ronald L. Rivest , Charles M. Fiduccia, A “greedy” channel router, Proceedings of the 19th conference on Design automation, p.418-424, January 1982
• 4: J. Soukup, "Circuits layout", Proc. IEEE, vol.69, no.10, October 1981.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
      B.4.2 Input/Output Devices
          Subjects: Channels and controllers

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

  J. Computer Applications

General Terms:
Algorithms, Design, Performance, Theory