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

• Ano de defesa: 2022
• Autor(a) principal: Pavanello, Leticia Leite
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Estadual Paulista (Unesp)
• Palavras-chave em Português: Problema de empacotamento; Retângulos flexíveis; Matheurística; BRKGA; Floorplanning VLSI; Packaging problem; Soft rectangles; Matheuristics
• Link de acesso: http://hdl.handle.net/11449/238217

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.