Análise de aproximações da MRST para o problema de roteamento de componentes de circuitos com obstáculos

Abstract

Hen designing VLSIs, it is necessary to connect several components avoiding to collide with obstacles and using the smallest set of connections. To solve this problem, it is necessary to find the Minimum Rectilinear Steiner Tree (MRST) between the components, but to find the same is a NP-complete problem, being necessary to do the use of approximations to the MRST. A simple approach is to find the Minimal Spanning Tree (MST), but as the circuits can be very large, it becomes impracticable to carry out the search in all the space to connect the components, being necessary to reduce the search space. Generating the Hanan grid, in addition to reducing the search space, ensures that the MRST is contained in it, but since most cases involve very large circuits, even using the Hanan grid, it becomes unfeasible in memory resource, once the number of points generated is still very large. Thus, starting from the approximation of the MST using the Hanan grid, this work makes the comparison with another approach, analyzing the results obtained when applying to the circuit routing problem, making estimations in order to decide which approach best applies to the case.