TIME-EFFICIENT MAZE ROUTING ALGORITHMS ON RECONFIGURABLE MESH ARCHITECTURES

The routing problem is one of the most widely studied problems in VLSI design, Maze-routing algorithms are used in VLSI routing and robot pa th 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-eff icient algorithms to solve the maze-routing problem on a reconfigurabl e mesh architecture. The constant-time algorithms presented include: ( i) testing the existence of specific types of paths between two termin als, and (ii) finding an absolute shortest path (ASP) and a shortest d uplex-path (SDP), In addition, a fast algorithm to find the single sho rtest 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 pa per. (C) 1997 Academic Press.