Title :
A Parallel Adaptable Routing Algorithm and its Implementation on a Two-Dimensional Array Processor
Author :
Watanabe, Toshio ; Kitazawa, Hitoshi ; Sugiyama, Yoshi
Author_Institution :
Atsugi Electrical Communications Laboratories, NTT, Kanagawa, Japan
fDate :
3/1/1987 12:00:00 AM
Abstract :
A new parallel-processing wire-routing algorithm is presented and implemented on a parallel processor. The two main features of the parallel algorithm are the control of the path quality and the finding of a quasi-minimum Steiner tree. Both Lee´s maze algorithm and the proposed algorithm are implemented on an AAP-1 two-dimensional array processor, and the performance is compared to that of software programming on a general-purpose computer. It is shown experimentally that routing by the proposed algorithm implemented on the AAP-1 is 230 times faster than a software maze router run on a 1-MIPS computer for a three-pin/net circuit on a 256 X 256 grid.
Keywords :
Adaptive arrays; Computer architecture; Design automation; Grid computing; Hardware; Parallel algorithms; Routing; Software algorithms; Software performance; Very large scale integration;
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
DOI :
10.1109/TCAD.1987.1270268
