Abstract
The routing problem is one of the most widely studied problems in VLSI design. Maze-routing algorithms are used in VLSI routing and robot path planning. Efficiency of the parallel maze routing algorithms which were mostly based on C. Y. Lee's algorithm8is poor. In this paper, we propose time-efficient algorithms to solve the maze-routing problem on a reconfigurable mesh architecture. The constant-time algorithms presented include: (i) testing the existence of specific types of paths between two terminals, and (ii) finding an absolute shortest path (ASP) and a shortest duplex-path (SDP). In addition, a fast algorithm to find the single shortest path (SSP) is presented. The simulation results indicate that a large percentage of the shortest paths that exist between two randomly selected terminals fall into one of the categories studied in this paper. © 1997 Academic Press.
Recommended Citation
F. Ercal and H. C. Lee, "Time-Efficient Maze Routing Algorithms on Reconfigurable Mesh Architectures," Journal of Parallel and Distributed Computing, vol. 44, no. 2, pp. 133 - 140, Elsevier, Aug 1997.
The definitive version is available at https://doi.org/10.1006/jpdc.1997.1353
Department(s)
Computer Science
International Standard Serial Number (ISSN)
0743-7315
Document Type
Article - Journal
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2024 Elsevier, All rights reserved.
Publication Date
01 Aug 1997
