DocumentCode
914696
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
Volume
6
Issue
2
fYear
1987
fDate
3/1/1987 12:00:00 AM
Firstpage
241
Lastpage
250
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;
fLanguage
English
Journal_Title
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
Publisher
ieee
ISSN
0278-0070
Type
jour
DOI
10.1109/TCAD.1987.1270268
Filename
1270268
Link To Document