PHIGURE: a parallel hierarchical global router

ABSTRACT

A new Parallel HIerarchical algorithm for Global Routing (PHIGURE) is presented in this paper. The router is based on the work of Burstein and Pelavin [1], but has many extensions for general global routing and parallel execution. Main features of the algorithm include structured hierarchical decomposition into separate independent tasks which are suitable for parallel execution and adaptive simplex solution for adding feedthroughs and adjusting channel heights for row-based layout. The algorithm is described and results are presented for a shared-memory multiprocessor implementation.

REFERENCES

• 1: M. Burstoin and R, Pelavin, "Hierarchical Wire Routing," IEEE Trans. CAD, v ol. CAD-2, No. 4, pp. 223-234, Oct. 1983.
• 2: P. Banerjee, "The Use of Parallel Processing in VLSI Computer-Aided Design Applications," ICCAD-88 Tutorial, also Tech. Report No. CSG-104, Coordinated Science Laboratory, Univ. of Illinois, Urbana, IL, May 1988.
• 3: K.W. Lee and C. Sechen, "A New Global Router for Row-Based Layout," Proc. Int. Conf. Comt~uter-Aided Design, pp. 180-183, Nov. 1988.
• 4: J. Cong and B. Preas, "A New Algorithm for Standard Cell Global Routing," Proc. Int. Conf. Computer-Aided Design, pp. 176-179, Nov. 1988.
• 5: O. A. Olukotun , T. N. Mudge, A preliminary investigation into parallel routing on a hypercube computer, Proceedings of the 24th ACM/IEEE conference on Design automation, p.814-820, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.38016]
• 6: Y. Won and S. Sahni, "Maze Routing On A Hypercube Multiprocessor Computer," Proc. Int. Conf. on Parallel Processing, pp. 630-637, Aug. 1987.
• 7: M. Marek-Sadowska, "Global Router for Gate Array," Proc. lnt. Conf. Computer Design, pp. 332-337, Oct. 1984.
• 8: W. K. Luk , D. T. Tang , C. K. Wong, Hierarchial global wiring for custom chip design, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.481-489, July 1986, Las Vegas, Nevada, United States
• 9: P.S. Tzeng and C. H. Sequin, "Codar: A Congestion- Directed General Area Router," Proc. Int. Conf. Computer-Aided Design, pp. 30-33, Nov. 1988.
• 10: Ravi Nair , Se June Hong , Sandy Liles , Ray Villani, Global wiring on a wire routing machine, Proceedings of the 19th conference on Design automation, p.224-231, January 1982
• 11: T. Watanabe, H. Kitazawa, and Y. Sugiyama, "A Parallel Adaptable Routing Algorithm and its Implementation on a Two-Dimensional Array Processor," IEEE Transactions Computer-Aided Design, vol. CAD-6, No 2, pp. 241-250, March 1987.
• 12: Jonathan Rose, LocusRoute: a parallel global router for standard cells, Proceedings of the 25th ACM/IEEE conference on Design automation, p.189-195, June 12-15, 1988, Atlantic City, New Jersey, United States

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

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

General Terms:
Algorithms, Design