Time-Efficient Maze Routing Algorithms on Reconfigurable Mesh Architectures

✍ Scribed by F Ercal; H.C Lee

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 396 KB
• Volume: 44
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.1997.1353

✦ Synopsis

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 algorithm (1961, IRE Trans. Electron. Comput. (Sept.), 346-365) 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, 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.