Um novo algoritmo de busca de caminhos em grade.

Abstract

The process of circuit synthesis has an enormous complexity involved, requiring the use of algorithms to automate the procedures. One of the stages of this long process is the routing, which aims to determine the wiring routes connecting the circuit components. The routing step is divided in global and detailed routing. In detailed routing, path-search algorithms on grids are used to determine the wiring routes. However, it is expected that these algorithms are able to handle at least the most basic design rules. Thus, considering that routing is very time consuming, this paper proposes a new generic path-search algorithm on three-dimensional grids, called SG-Router, able to handle some of the simpler design rules. The goal of the proposal is to perform a comparison, regarding runtime and path quality, with Hetzel’s algorithm, which is the state of the art of the generic path-search algorithms on grid, used in detailed routing. The paper also presents some proposals of optimizations, regarding time and search quality of the already existing version of the algorithm, which works only in two-dimensional scope. Most of these optimizations were reused in the SG-Router. The experiments performed on the improved two-dimensional version of the algorithm showed that the algorithm obtained the optimal path in all searches. The algorithm was faster than Hetzel’s algorithm, adapted to 2D space, presenting a speedup between 2,68 and 7522. The experiments with the SG-Router in random search scenarios showed a speedup of at least 11, for scenarios with more obstacles, and up to 1857, for average scenarios. The algorithm presented a deficiency to handle scenarios similar to labyrinths, since in these cases the algorithm can easily cause memory overflow. This problem prevented the use of the algorithm in detailed routing. However, the drawback is not final and can be bypassed. This work also suggests future improvements to the SG-Router, making it a promising algorithm for the detailed routing and more generic search scenarios.