Abstract
The routing problem is one of the most widely studied problems in VLSI design. Mazerouting algorithms are used in VLSI routing and robot path planning. Efficiency of the parallel maze routing algorithms which were mostly based on Lee's algorithm is 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, (ii) finding an absolute shortest path (ASP) and a shortest duplex-path (SDP). In addition, fast algorithms are presented for finding the shortest triplex-path (STP) and the single shortest path (SSP). 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.
Recommended Citation
Ercal, Fikret and Lee, H. C., "Fast Algorithms for Maze Routing on an RMESH" (1996). Computer Science Technical Reports. 193.
https://scholarsmine.mst.edu/comsci_techreports/193
Department(s)
Computer Science
Report Number
CSc-96-05
Document Type
Technical Report
Document Version
Final Version
File Type
text
Language(s)
English
Rights
© 1996 University of Missouri - Rolla, All rights reserved
Publication Date
1996-07-01
