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

Detalhes bibliográficos
Ano de defesa: 2022
Autor(a) principal: Pavanello, Leticia Leite
Orientador(a): Não Informado pela instituição
Banca de defesa: Não Informado pela instituição
Tipo de documento: Dissertação
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: Universidade Estadual Paulista (Unesp)
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: http://hdl.handle.net/11449/238217
Resumo: 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.