TY - JOUR
T1 - A Hardware Maze Router with Application to Interactive Rip-Up and Reroute
AU - Suzuki, Kei
AU - Matsunaga, Yusuke
AU - Tachibana, Masayoshi
AU - Ohtsuki, Tatsuo
PY - 1986/10
Y1 - 1986/10
N2 - This paper presents a new parallel-processing architecture for hardware routers based on the Lee algorithm. Unlike the existing machines, which require N2 processors to implement the Lee algorithm on an N x N grid plane, the proposed architecture requires only O(N) processors to find a path in O(N) time. A prototype machine with 64 processors has been developed to deal with a 128 × 128 grid plane. The architecture of the machine is discussed, together with its experimental performance data. Further, it is reported that the parallel-processed Lee algorithm is most useful and powerful when applied to interactive rip-up and reroute.
AB - This paper presents a new parallel-processing architecture for hardware routers based on the Lee algorithm. Unlike the existing machines, which require N2 processors to implement the Lee algorithm on an N x N grid plane, the proposed architecture requires only O(N) processors to find a path in O(N) time. A prototype machine with 64 processors has been developed to deal with a 128 × 128 grid plane. The architecture of the machine is discussed, together with its experimental performance data. Further, it is reported that the parallel-processed Lee algorithm is most useful and powerful when applied to interactive rip-up and reroute.
UR - http://www.scopus.com/inward/record.url?scp=84934027087&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84934027087&partnerID=8YFLogxK
U2 - 10.1109/TCAD.1986.1270218
DO - 10.1109/TCAD.1986.1270218
M3 - Article
AN - SCOPUS:84934027087
SN - 0278-0070
VL - 5
SP - 466
EP - 476
JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
IS - 4
ER -