Heurísticas para o floorplanning de circuitos VLSI como um problema de empacotamento de retângulos flexíveis

Abstract

O problema de planejamento de layout de um circuito VLSI (Very Large Scale Integration), chamado de floorplanning, consiste no processo de determinar a localização física de módulos retangulares e interconectá-los dentro dos limites do chip, otimizando recursos. Com forte característica geométrica, este problema pode ser abordado como um problema de empacotamento de retângulos flexíveis. Neste problema, é preciso definir as posições de módulos em uma área de alocação sem que haja sobreposição, além de decidir as dimensões de cada módulo, que podem ser ajustadas dentro de uma proporção predefinida, e de modo a minimizar o comprimento de fio utilizado para conectar os módulos entre si. Devido ao grande número de variáveis envolvidas, este problema é difícil de ser solucionado e, obter soluções exatas, implica em alta complexidade computacional. Desta forma, métodos heurísticos são comumente utilizados na tentativa de obter boas soluções em tempos viáveis. Para resolver o problema de planejamento de circuitos VLSI de maneira eficiente, um modelo matemático, uma abordagem matheurística e uma meta-heurística BRKGA (Biased Random-Key Genetic Algorithm) são propostos neste trabalho. O modelo matemático é utilizado em ambas as abordagens heurísticas de forma iterativa e com uma estratégia de janela deslizante, resolvendo o problema parcialmente para reduzir a dificuldade computacional do problema original. O desempenho dos métodos propostos foi avaliado a partir de testes computacionais com instâncias MCNC (Microelectronics Center of North Carolina) na linguagem de programação C++ com o solver CPLEX. Resultados dos experimentos computacionais demonstraram grande potencial de obtenção de soluções satisfatórias pelos métodos, principalmente na abordagem BRKGA combinada com o procedimento de janela deslizante.

The floorplanning problem of a VLSI (Very Large Scale Integration) circuit is the process of determining the physical location of rectangular modules and interconnecting them within the chip limits, optimizing resources. With strong geometric characteristics, this problem can be approached as a flexible rectangle packing problem. In this problem, it is necessary to define the positions of modules in an allocation area without overlapping, in addition to deciding the dimensions of each module, which can be adjusted within a predefined proportion, in order to minimize the wire length used for connecting the modules together. Due to the large number of variables involved, this problem is difficult to solve, and obtaining exact solutions implies high computational complexity. In this way, heuristic methods are commonly used in an attempt to obtain good solutions in feasible times. To efficiently solve the VLSI circuit planning problem, a mathematical model, a matheuristic approach, and a BRKGA (Biased Random-Key Genetic Algorithm) are proposed in this work. The mathematical model is used in both heuristic approaches in an iterative way and with a sliding window strategy, solving the problem partially to reduce the computational difficulty of the original problem. The performance of the proposed methods was evaluated from computational tests with MCNC instances (Microelectronics Center of North Carolina) in the C++ programming language with the CPLEX solver. Results of computational experiments showed great potential for obtaining satisfactory solutions by the methods, mainly in the BRKGA approach combined with the sliding window procedure.