A preliminary investigation into parallel routing on a hypercube computer

ABSTRACT

This paper describes an experiment in which parallel routing is performed on a medium grained hypercube parallel processor having 64 processing elements. Each node is a complete 32-bit computer with 128 K-bytes of memory and is connected to the other nodes via a direct hypercube interconnection network. A new parallel routing algorithm was developed to exploit this parallel structure. It is a three step algorithm consisting of a global routing step, a boundary crossing placement step, and a detailed routing step. All steps can be performed in parallel. When applied to a standard benchmark it was able to route 95 % of the wires. The algorithm was also executed on a large mainframe computer using the same benchmark. The execution time was compared to that for the hypercube. The hypercube was about three times as fast.

REFERENCES

• 1: C. Y. Lee, "An algorithm for path connections and its applicatJions," IRE Tran. on Electronic Com outers, vol. EC-10, Sep. 961, pp. 346--358, 1961.
• 2: R. A. Rutenbar, T. N. Mudge and D. E. A~:ins, "A class of cellular architectures to support physical design automation," IEEE Tran. CAD of IC's and Systems, vol. CAD-3, no. 4, pp. 264-278, Oct. 1 !)84.
• 3: M. A. Breuer and K. Shamsa, "A hardware router," Jour. of Digital Systems, vol. IV, issue 4, pp. 393- 408, 1981.
• 4: Tom Blank , Mark Stefik , Willem vanCleemput, A parallel bit map processor architecture for DA algorithms, Proceedings of the 18th conference on Design automation, p.837-845, June 29-July 01, 1981, Nashville, Tennessee, United States
• 5: S. J. Hong and R. Nair,"Wire routing machines--- New tools for VLSI physical design," Proc. of the IEEE, vol. 71, no. 1 pp. 57-65, Jan 1983.
• 6: J.P. Hayes, T. N. Mudge, Q. F. Stout, S. Colley and J. Palmer, "Architecture of a Hypercube Supercomputer," Proc. of lnt. Conf. on Parallel Processing, pp. 653-660, Aug. 1986.
• 7: Robin Arthur Rutenbar, A class of cellular computer architectures to support physical design automation (vlsi layout, integrated circuit, routing), 1984
• 8: R. A. Rutenbar, "Systolic routing Hardware: performance evaluation and optimization," submitted to IEEE Tran. CAD of iC's and Systems.
• 9: Ronald L. Rivest, The “PI” (placement and interconnect) system, Proceedings of the 19th conference on Design automation, p.475-481, January 1982
• 10: J. H. Hoel "Some variations of Lee's algorithm," IEEE Trans. Computers, vol. C-25, pp. 19-24, Jan. 1976.
• 11: William Thomas Blank, A bit map architecture and algorithms for design automation, 1982

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

General Terms:
Algorithms, Design, Experimentation, Theory