A preliminary investigation into parallel routing on a hypercube computer

This paper describes an experiment in which parallel routing is performed on a medium grained hypercube parallel proces-sor having 64 processing elements. Each node is a complete 32-bit computer with 128 K-bytes of memory and is con-nected to the other nodes via a direct hypercube interconnec-tion network. A new parallel routing algorithm was devel-oped to exploit this parallel structure. It is a three step algo-rithm 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.