Universidade Estadual Paulista “Júlio de Mesquita Filho” Faculdade de Engenharia – Câmpus de Bauru Programa de Pós-graduação em Engenharia de Produção Heurísticas para o floorplanning de circuitos VLSI como um problema de empacotamento de retângulos flexíveis Letícia Leite Pavanello Bauru 2022 Letícia Leite Pavanello Heurísticas para o floorplanning de circuitos VLSI como um problema de empacotamento de retângulos flexíveis Dissertação apresentada ao Curso de Pós-graduação em Engenharia de Produção da Universidade Estadual Paulista “Júlio de Mesquita Filho” como parte dos requisitos necessários para a obtenção do título de Mestre em Engenharia de Produção. Orientador: Profa. Dra. Adriana Cristina Cherri Coorientador: Prof. Dr. Carlos Diego Rodrigues Bauru 2022 P337h Pavanello, Leticia Leite Heurísticas para o floorplanning de circuitos VLSI como um problema de empacotamento de retângulos flexíveis / Leticia Leite Pavanello. -- Bauru, 2022 56 f. Dissertação (mestrado) - Universidade Estadual Paulista (Unesp), Faculdade de Engenharia, Bauru Orientadora: Adriana Cristina Cherri Coorientador: Carlos Diego Rodrigues 1. Pesquisa Operacional. 2. Problema de Empacotamento. 3. Retângulos flexíveis. 4. Matheurística. 5. BRKGA. I. Título. Sistema de geração automática de fichas catalográficas da Unesp. Biblioteca da Faculdade de Engenharia, Bauru. Dados fornecidos pelo autor(a). Essa ficha não pode ser modificada. UNIVERSIDADE ESTADUAL PAULISTA Câmpus de Bauru ATA DA DEFESA PÚBLICA DA DISSERTAÇÃO DE MESTRADO DE LETÍCIA LEITE PAVANELLO, DISCENTE DO PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA DE PRODUÇÃO, DA FACULDADE DE ENGENHARIA - CÂMPUS DE BAURU. Aos 27 dias do mês de outubro do ano de 2022, às 14:00 horas, por meio de Videoconferência, realizou-se a defesa de DISSERTAÇÃO DE MESTRADO de LETÍCIA LEITE PAVANELLO, intitulada Heurísticas para o floorplanning de circuitos VLSI como um problema de empacotamento de retângulos flexíveis. A Comissão Examinadora foi constituida pelos seguintes membros: Profª. Drª. ADRIANA CRISTINA CHERRI NICOLA (Orientador(a) - Participação Virtual) do(a) Departamento de Matematica / Faculdade de Ciencias de Bauru UNESP, Prof. Dr. FLAVIO KEIDI MIYAZAWA (Participação Virtual) do(a) Instituto de Computação / Universidade Estadual de Campinas, Prof. Dr. PEDRO AUGUSTO MUNARI JUNIOR (Participação Virtual) do(a) Departamento de Engenharia de Produção / Universidade Federal de São Carlos. Após a exposição pela mestranda e arguição pelos membros da Comissão Examinadora que participaram do ato, de forma presencial e/ou virtual, a discente recebeu o conceito final:_ _ _ _ _ _ _ _ _ _ _ _ _ . Nada mais havendo, foi lavrada a presente ata, que após lida e aprovada, foi assinada pelo(a) Presidente(a) da Comissão Examinadora. Profª. Drª. ADRIANA CRISTINA CHERRI NICOLA Faculdade de Engenharia - Câmpus de Bauru - Av. Engenheiro Luiz Edmundo Carrijo Coube, , 14-01, 17033360 http://www.feb.unesp.br/posgrad_prod/index.phpCNPJ: 48.031.918/0030-69. aprovada À minha mãe Márcia e minha irmã Alícia, testemunhas da minha dedicação... Agradecimentos Agradeço à Deus, por ter sempre me sustentado, principalmente em meio ao contexto desafiador de pandemia, no qual este trabalho foi realizado. Aos meus orientadores Adriana Cherri e Diego Rodrigues, pela orientação, amizade, confiança e todo o suporte dado durante o desenvolvimento deste trabalho. À minha mãe Márcia, pelo amor incondicional, cuidado, incentivo e dedicação. À minha irmã Alícia, pelo amor, compreensão e carinho. Obrigada por estarem sempre ao meu lado. Ao meu querido Raphael Bueno, pelo amor, apoio e todos os momentos que me fizeram mais feliz e motivada. Fico feliz em compartilhar esta etapa da minha vida com você. Aos meus amigos Arthur Medeiros e Guilherme Calvo, pela amizade, apoio e companhia nos mais diversos momentos. Aos professores Pedro Munari e Flávio Miyazawa pelas sugestões e dicas que enriquece- ram esta dissertação. À CAPES pela credibilidade e apoio financeiro. Agradeço a todos que me ajudaram, direta ou indiretamente, a concluir esta etapa. Para sempre, obrigada. 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 carac- terí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 compri- mento 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 expe- rimentos 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. Palavras-chave: Problema de Empacotamento. Retângulos flexíveis. Matheurística. BRKGA. Abstract 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. Themathematical 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. Keywords: Floorplanning VLSI. Packaging Problem. Soft rectangles. Matheuristics. BRKGA. Lista de figuras Figura 1 – Circuito integrado VLSI. . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Figura 2 – Representação de um problema de empacotamento de retângulos. . . . . . . 6 Figura 3 – Dimensões de um item i com exemplos e possíveis variações de dimensão, mantendo a área inicial ou respeitando uma proporção pré-definida. . . . . . 8 Figura 4 – Representação de possíveis empacotamentos com retângulos flexíveis. . . . 8 Figura 5 – Casos possíveis de posicionamento entre dois módulos i e j. . . . . . . . . . 20 Figura 6 – Comprimento de fio HPWL entre dois itens (dx + dy). . . . . . . . . . . . . 22 Figura 7 – Exemplo 1 de distância HPWL = 11. . . . . . . . . . . . . . . . . . . . . . 22 Figura 8 – Exemplo 2 de distância HPWL = 7,5. . . . . . . . . . . . . . . . . . . . . . 23 Figura 9 – Representação horizontal de posicionamento relativo fixado do item i (módulo fixo) com inserção do item k (módulo livre) à direita ou à esquerda de j (módulo livre). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 Figura 10 – Etapas da abordagem heurística SW. . . . . . . . . . . . . . . . . . . . . . 28 Figura 11 – Exemplo de janela deslizante a cada iteração (sw = 4). . . . . . . . . . . . 29 Figura 12 – Exemplo de layout a cada iteração (sw = 4). . . . . . . . . . . . . . . . . . 30 Figura 13 – Estrutura da abordagem heurística SW. . . . . . . . . . . . . . . . . . . . . 31 Figura 14 – Esquema geral de processo evolutivo do BRKGA. . . . . . . . . . . . . . . 32 Figura 15 – Alocações (layouts) obtidas para as instâncias APTE, AMI49, AMI33 e HP. 35 Figura 16 – Alocações obtidas para AMI33: itens ordenados por menor conectividade (sw = 3 e sw = 5, respectivamente). . . . . . . . . . . . . . . . . . . . . . 38 Figura 17 – Alocações obtidas para AMI33: itens ordenados por maior conectividade (sw = 1, sw = 3 e sw = 5, respectivamente). . . . . . . . . . . . . . . . . 39 Figura 18 – GAP de soluções entre instâncias por critério de ordenação. . . . . . . . . . 39 Figura 19 – Comprimento de fio por ordenação para a instância AMI33. . . . . . . . . . 40 Figura 20 – Solução para AMI49. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 Figura 21 – Solução para HP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 Figura 22 – Solução para APTE. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 Figura 23 – Solução para XEROX. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 Figura 24 – GAP de soluções obtidas entre instâncias por tamanho de janela deslizante sw. 42 Figura 25 – GAP de valores de tempo computacional registrado entre instâncias por tama- nho de janela deslizante sw. . . . . . . . . . . . . . . . . . . . . . . . . . . 42 Figura 26 – Soluções dos BRKGAs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 Figura 27 – Tempo dos BRKGAs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 Figura 28 – Melhor solução de cada método nas instância. . . . . . . . . . . . . . . . . 45 Figura 29 – Tempo computacional da melhor solução de cada método nas instâncias. . . 45 Lista de tabelas Tabela 1 – Casos possíveis de posicionamento de dois módulos i e j, com i < j. . . . . 17 Tabela 2 – Valores das variáveis binárias ao posicionar dois módulos i e j, com i < j . 21 Tabela 3 – Soluções obtidas pelo modelo matemático com tempo limite de 15 horas. . . 35 Tabela 4 – Comprimento de fio obtido por ordenação para a instância AMI33. . . . . . 36 Tabela 5 – Tempo computacional obtido por ordenação para a instância AMI33. . . . . 36 Tabela 6 – Comprimento de fio por ordenação para a instância AMI49. . . . . . . . . . 37 Tabela 7 – Tempo computacional obtido por ordenação para a instância AMI49. . . . . 37 Tabela 8 – Comprimento de fio por ordenação para a instância APTE. . . . . . . . . . 37 Tabela 9 – Tempo computacional por ordenação para a instância APTE. . . . . . . . . 37 Tabela 10 – Comprimento de fio por ordenação para a instância HP. . . . . . . . . . . . 37 Tabela 11 – Tempo computacional por ordenação para a instância HP. . . . . . . . . . . 37 Tabela 12 – Comprimento de fio por ordenação para a instância XEROX. . . . . . . . . 38 Tabela 13 – Tempo computacional por ordenação para a instância XEROX. . . . . . . . 38 Tabela 14 – Soluções BRKGA com tempo limite de execução (critério de parada) de 1 hora. 43 Tabela 15 – Soluções BRKGA-SW e tempo limite de execução (critério de parada) de 1 hora. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 Tabela 16 – Melhor solução e tempo computacional obtida por cada método proposto. . 44 Tabela 17 – Descrição de itens da instância APTE. . . . . . . . . . . . . . . . . . . . . 53 Tabela 18 – Descrição de itens da instância XEROX. . . . . . . . . . . . . . . . . . . . 53 Tabela 19 – Descrição de itens da instância HP. . . . . . . . . . . . . . . . . . . . . . . 54 Tabela 20 – Descrição de itens da instância AMI33. . . . . . . . . . . . . . . . . . . . . 55 Tabela 21 – Descrição de itens da instância AMI49. . . . . . . . . . . . . . . . . . . . . 56 Lista de abreviaturas e siglas BRKGA Biased Random-Key Genetic Algorithm BRKGA-SW BRKGA - Sliding Window BRKGA-CLP BRKGA - single Container Loading Problem GAOSPF Genetic Algorithm for Open Shortest Path First routing HSA Hybrid Simulated Annealing HPWL Half Perimeter Wire Length LOA Lion Optimization Algorithm MCNC Microelectronics Center of North Carolina RKGA Random-Key Genetic Algorithm PCE Problemas de Corte e Empacotamento SW Sliding Window VLSI Very Large Scale Integration Sumário 1 INTRODUÇÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 FUNDAMENTAÇÃO TEÓRICA . . . . . . . . . . . . . . . . . . . . . . 4 2.1 Problemas de planejamento de circuitos VLSI . . . . . . . . . . . 4 2.2 Problemas de empacotamento de retângulos . . . . . . . . . . . . 6 2.2.1 Característica do problema . . . . . . . . . . . . . . . . . . . . 6 2.2.2 Retângulos flexíveis . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2.3 Dificuldade de resolução . . . . . . . . . . . . . . . . . . . . . . 8 3 REVISÃO DE LITERATURA . . . . . . . . . . . . . . . . . . . . . . . . 10 3.1 Problemas de empacotamento . . . . . . . . . . . . . . . . . . . . 10 3.1.1 Modelos matemáticos . . . . . . . . . . . . . . . . . . . . . . . 10 3.1.2 Abordagens heurísticas e meta-heurísticas . . . . . . . . . . . . 11 3.1.3 Algoritmo genético BRKGA . . . . . . . . . . . . . . . . . . . . 12 3.2 Circuitos integrados VLSI . . . . . . . . . . . . . . . . . . . . . . 14 3.3 Modelo de Chen e Chang (2009) . . . . . . . . . . . . . . . . . . . 17 4 MODELO MATEMÁTICO . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.1 Contextualização . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.2 Representação de posicionamento . . . . . . . . . . . . . . . . . . 20 4.3 Cálculo do comprimento de fio . . . . . . . . . . . . . . . . . . . 21 4.4 Modelo Matemático . . . . . . . . . . . . . . . . . . . . . . . . . 23 5 ABORDAGENS HEURÍSTICAS . . . . . . . . . . . . . . . . . . . . . . 26 5.1 Heurística SW . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 5.2 Mateurística BRKGA-SW . . . . . . . . . . . . . . . . . . . . . . 31 6 EXPERIMENTOS COMPUTACIONAIS . . . . . . . . . . . . . . . . . 34 6.1 Modelo Matemático . . . . . . . . . . . . . . . . . . . . . . . . . 34 6.2 Heurística SW . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 6.3 BRKGA-SW . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 7 CONCLUSÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 Apêndices 52 APÊNDICE A – DESCRIÇÃO DE ITENS DE CADA INSTÂNCIA . . . . . 53 A.1 APTE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 A.2 XEROX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 A.3 HP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 A.4 AMI33 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 A.5 AMI49 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 1 1 Introdução O VLSI (Very Large Scale Integration) é uma tecnologia de microeletrônica que integra uma grande quantidade de módulos em um chip. A construção de um circuito integrado é feita de forma sequencial, devido à sua complexidade, e o floorplanning, processo de determinar a localização física dos módulos e interconectá-los dentro dos limites do chip do melhor modo possível, é uma etapa essencial no projeto físico de um VLSI. Nas abordagens modernas deste processo, os módulos são essencialmente flexíveis (CHEN; CHANG, 2009; SINGH; BAGHEL; AGARWAL, 2016), assim as dimensões de cada módulo pode ser ajustada dentro de um intervalo de proporção entre altura e largura pré-definida no projeto. O floorplanning permite que a complexidade do projeto do circuito seja gerenciada de modo eficaz, dado que a planta de alocação resultante (layout) afeta todas os estágios subsequen- tes no projeto, como colocação e roteamento. Este planejamento envolve determinar os locais e tamanhos dos módulos no chip, além de estimar a área total necessária, o atraso e o congestiona- mento da fiação, fornecendo, assim, uma base para o layout. Este processo de planejamento físico de um circuito pode ser interpretado como um problema de empacotamento com retângulos flexíveis. Computacionalmente, ele é um problema NP-difícil (KAHNG et al., 2011). Os problemas de empacotamento são estudados há décadas como uma ferramenta de apoio na tomada de decisão em diversos setores. Com uma forte característica geométrica, os problemas de empacotamento bidimensionais consistem em empacotar retângulos menores (itens) com dimensões predefinidas em regiões retangulares maiores, utilizando os recursos disponíveis da melhor forma possível e sem que haja sobreposição. Apesar de ser um problema difícil de otimização combinatória, diversos trabalhos foram publicados. Abordagens exatas para o problema foram propostas por Fekete e Schepers (2000), Chen e Chang (2009) e Martello e Monaci (2015). Entretanto, devido à resolução custosa deste problema, muitas abordagens de resolução são heurísticas. A heurística mais antiga e famosa é a bottom-left (BL), proposta por Baker, Coffman Jr e Rivest (1980). Outras abordagens foram propostas por Wu et al. (2002), Huang, Chen e Xu (2007), Wei, Zhang e Chen (2009), Wei et al. (2011), Bortfeldt (2013), He, Ji e Li (2015), Wang e Chen (2015), Venkatraman e Sundhararajan (2019), entre outros. Uma variação para o problema de empacotamento bidimensional ocorre quando os retângulos a serem empacotados possuem dimensões flexíveis. Neste caso, as dimensões de cada item podem variar em um determinado intervalo, respeitando uma proporção entre suas Capítulo 1. Introdução 2 respectivas alturas e larguras. Os problemas de empacotamento de retângulos flexíveis são problemas de otimização combinatória difíceis de serem resolvidos, pois é necessário definir como os retângulos de um conjunto predefinido serão empacotados na região e, ainda, decidir quais as suas dimensões, respeitando as suas limitações geométricas e a não-sobreposição dos itens. Além de sua importância teórica, este problema surge em várias situações práticas, incluindo a determinação do layout de circuitos integrados de grande escala. Os problemas de empacotamento de módulos (retângulos) flexíveis em circuitos VLSI costumam considerar a otimização da área do chip e o comprimento do fio de metal semi-condutor, usado para conectar os módulos entre si. Para minimizar o comprimento do fio das interconexões do circuito, é preciso identificar quais itens devem ser colocados próximos uns aos outros e alocá-los de forma a atender metas, muitas vezes conflitantes, de comprimento de fio utilizado, espaço disponível no chip e desempenho necessário. Com os módulos posicionados de acordo com uma descrição detalhada de conectividade do circuito, obtém-se distâncias de interconexão mais curtas, que utilizam menos recursos de roteamento, e consequentemente circuitos mais eficientes. Devido ao grande número de variáveis envolvidas no problema, o floorplanning é difícil de ser solucionado, apesar de ser representado facilmente através de modelos matemáticos. Con- sequentemente, obter soluções exatas torna-se inviável, principalmente para grandes instâncias. Desta forma, métodos heurísticos podem ser eficientes para encontrar boas soluções em tempos computacionais viáveis. Em Chen, Zhu e Ali (2011), Anand, Saravanasankar e Subbaraj (2013), Chan, Hsu e Lin (2013), He, Ji e Li (2015), Wu et al. (2016), Venkatraman e Sundhararajan (2019) e Shunmugathammal, Columbus e Anand (2020), os autores sugeriram e exploraram diferentes técnicas heurísticas e meta-heurísticas para o floorplanning, sendo o algoritmo genético utilizado em várias das abordagens. O algoritmo genético é uma meta-heurística em que cada indivíduo da população re- presenta uma solução viável para o problema abordado. Através de operações de cruzamento e mutação, os indivíduos encontrados sofrem modificações com o objetivo de evoluir a população e possivelmente obter soluções melhores a cada iteração. O BRKGA (Biased Random-Key Genetic Algorithm) é um algoritmo genético de chave tendenciosa amplamente utilizado em problemas de natureza combinatória, devido à sua estrutura de fácil adaptação. Os trabalhos Ericsson, Resende e Pardalos (2002), Gonçalves, Mendes e Resende (2005), Noronha, Resende e Ribeiro (2011), Mainieri (2014), Mönch e Roob (2018), Mauri et al. (2021), entre outros, apresentaram o BRKGA, aplicados em diferentes contextos e obtendo bons resultados. Não foram encontrados trabalhos de BRKGA para empacotar retângulos flexíveis ou aplicado ao floorplanning de circuitos. Apesar dos trabalhos existentes e dos diversos métodos que abordam o floorplanning de circuitos VLSI, as soluções ótimas não são conhecidas e abordagens não-exatas mais eficientes podem ser exploradas. Ainda, a maioria dos autores adota como objetivo principal a minimização da área do chip, deixando o comprimento de fio como objetivo secundário, quando considerado. Capítulo 1. Introdução 3 Devido à sua importância para garantia de qualidade e eficiência em um circuito VLSI, o comprimento de fio deve ser minimizado no processo de alocação e, com distâncias mais curtas para as interconexões, é esperado que a área do chip seja consequentemente reduzida. Neste trabalho, o floorplanning é abordado como um problema de empacotamento de retângulos flexíveis com o objetivo de minimizar o comprimento de fio utilizado nas interconexões. Para resolver o problema de planejamento de circuitos VLSI de maneira eficiente, são propostos um modelo matemático, uma heurística de janela deslizante e uma meta-heurística BRKGA adaptada. Simultaneamente são exploradas as vantagens da programação matemática e do método heurístico. Para ambos os procedimentos propostos, estratégias de inicialização e de janela deslizante são definidas. Desta forma, a resolução do problema de alocação é realizada de forma parcial em relação ao problema original. Ao determinar o tamanho da janela deslizante, uma quantidade menor e fixa de variáveis com posicionamento livre são consideradas, diminuindo significativamente a dificuldade envolvida na resolução modelo. Além da característica de flexibilidade dos itens, a influência de diferentes tamanhos de janela deslizante e critérios na ordenação inicial sobre o resultado final das abordagens é analisada. A implementação dos métodos foi realizada na linguagem computacional C++ com o solver IBM CPLEX Optimization Studio versão 22.1. Os testes foram realizados com instâncias da literatura e layouts de circuitos VLSI com valores de comprimento de fio em diferentes tempos computacionais são apresentados. Uma comparação entre os resultados dos métodos propostos é realizada. O Capítulo 2 deste trabalho é composto pela fundamentação teórica para o estudo desen- volvido e o Capítulo 3 contém uma revisão de literatura que contempla problemas de empacota- mento em geral e, principalmente, abordados para o resolver o floorplanning, além de métodos heurísticos conhecidos. Conceitos fundamentais e o modelo matemático proposto são detalhados no Capítulo 4, seguido do procedimento heurístico desenvolvido e algoritmo genético adaptado (BRKGA-SW) apresentados no Capítulo 5. No Capítulo 6, resultados de testes computacionais com instâncias da literatura são apresentados, e o Capítulo 7 destina-se às conclusões e melhorias sugeridas para a continuidade do trabalho. 4 2 Fundamentação Teórica Neste capítulo, são apresentadas definições detalhadas que fundamentam o floorplanning de circuitos VLSI e os problemas de empacotamento de retângulos. Além disso, são mencionados possíveis métodos de resolução propostos ao longo deste trabalho. 2.1 Problemas de planejamento de circuitos VLSI O VLSI é uma tecnologia de microeletrônica que integra uma grande quantidade de módulos eletrônicos numa pastilha de silício, conhecida como chip. Com o avanço da tecnologia de circuito integrado e a sua presença crescente na composição de produtos de uso específico, tais como automóveis, eletrodomésticos e dispositivos de comunicação em geral, torna-se necessário planejar detalhadamente cada etapa do projeto de fabricação, geralmente dividas em duas fases: projeto lógico e projeto físico. A Figura 1 apresenta um circuito integrado VLSI. Figura 1 – Circuito integrado VLSI. Fonte: Iaroslav Neliubov/Shutterstock O projeto físico é essencial no VLSI. Nesta etapa, as representações de circuito dos mó- dulos do projeto são convertidas em representações geométricas de forma que, quando fabricadas nas camadas de materiais correspondentes, garantirão o funcionamento necessário do circuito. Os principais passos que compõe o projeto físico são o planejamento topológico, posicionamento e roteamento, assim um conjunto de módulos e um netlist, isto é, uma descrição detalhada de conectividade do circuito, são determinados para serem posicionados e conectados no chip. Capítulo 2. Fundamentação Teórica 5 Um dos grandes desafios no design de um VLSI é o problema de planejamento de layout (floorplanning), isto é, o processo de determinar a localização física dos módulos e interconectá- los dentro dos limites da placa (chip), utilizando os recursos disponíveis da melhor forma possível. Um layout, também chamado de planta baixa ou floorplan, é uma dissecção de uma região retilínea em um conjunto de retângulos, em que cada um destes retângulos representa um módulo. Para o floorplanning de circuitos VLSI é dado um conjunto de módulos retangulares e algumas redes, sendo cada rede um subconjunto de módulos que deverão ser conectados por fios semicondutores no passo de roteamento. É chamado de comprimento de fio a distância utilizada para interconectar os módulos que pertencem a umamesma rede nos circuitos integrados. Conectar os módulos com longas distâncias de comprimento de fio resulta em chips maiores, mais lentos e com menor confiabilidade. Ainda, quando a medida do comprimento total de todas as interconexões é muito grande ou quando as conexões são muito densas em uma determinada região, pode não haver recursos de roteamento suficientes, afetando o custo de fabricação. Deste modo, busca-se determinar o posicionamento dos módulos de forma a minimizar o comprimento de fio utilizado nas conexões para obter circuitos com maior nível de desempenho. Com módulos posicionados de acordo com a descrição de conectividade do circuito, detalhada na netlist, obtém-se distâncias de interconexões mais curtas, que utilizam menos recursos, com os caminhos de sinal ponta a ponta mais rápidos e tempos de rota mais consistentes. Ainda, dado o aumento da complexidade do projeto e as novas propriedades e requisitos do circuito, o floorplanning tem sido abordado de modo reformulado. As novas considerações e desafios tornam o problema mais difícil. Ao contrário do floorplanning clássico, que geralmente lida apenas com a área dos módulos para minimizar a região do chip, o floorplanning moderno é formulado considerando como crucial a possibilidade de redimensionar as dimensões dos módulos retangulares dentro de um intervalo de proporção e considerando restrições de contorno fixo (CHEN; CHANG, 2009). Os limites da proporção são pré-definidos para cada módulo. O floorplanning moderno do VLSI pode ser modelado como um problema de empacota- mento com retângulos flexíveis de grande porte. Neste problema, os módulos são flexíveis e devem ser alocados e conectados uns aos outros respeitando restrições de espaço. Além de determinar as posições dos módulos, suas dimensões também são decisões que devem ser consideradas, minimizando o comprimento do fio usado em suas interconexões. Desta forma, acrescenta-se ao problema de empacotamento de retângulos flexíveis, o problema de minimizar o comprimento de fio utilizado para interconectar os módulos. Posicionar os módulos nos circuitos VLSI é uma tarefa complexa, assim como a imple- mentação de algoritmos que produzam boas soluções para o problema, em tempo de execução viável. O floorplanning é um problema difícil de ser solucionado, devido ao grande número de variáveis envolvidas. Computacionalmente, é um problema NP-difícil (KAHNG et al., 2011). Capítulo 2. Fundamentação Teórica 6 2.2 Problemas de empacotamento de retângulos Os problemas de empacotamento de retângulos consistem em encontrar uma configuração para alocar retângulos menores (itens) em retângulos maiores (objetos ou recipientes), de forma que os itens estejam completamente contidos no recipiente e sem sobreposições entre si. O objetivo deste problema é posicionar os itens no recipiente do melhor modo possível, otimizando os espaços ou materiais disponíveis. Na Figura 2 é representada uma solução possível de um problema de empacotamento que contém itens retangulares e cujo objetivo é minimizar a área do retângulo exterior envolvente que contém os itens disponíveis para o posicionamento. Figura 2 – Representação de um problema de empacotamento de retângulos. Os problemas de empacotamento são similares ao problema de corte de estoque bidi- mensional (BEZERRA, 2018). Enquanto o problema de empacotamento busca determinar a melhor configuração para posicionar os itens, o problema de corte consiste em determinar a melhor maneira de produzir os itens através de cortes efetuados nos objetos (placas). Assim, empacotar itens pode ser visto como cortes de espaços, sendo estes espaços ocupados por itens, e vice-versa. Além de sua importância teórica, os Problemas de Corte e Empacotamento (PCE) estão presentes em diversas situações práticas em processos industriais de planejamento de produção, armazenagem e transporte. 2.2.1 Característica do problema Para especificar um PCE dentre os vários contextos nos quais ele pode surgir, é estabe- lecida uma tipologia utilizada na literatura para classificar a estrutura de um problema e suas variações (WÄSCHER; HAUβNER; SCHUMANN, 2007). Esta estrutura inclui características suficientes para definir um problema de empacotamento, sendo elas o tipo de atribuição, tipo e forma de itens, tipo de objetos e os critérios de dimensionalidade. Um PCE pode ser unidimensional, bidimensional, tridimensional ou n-dimensional. O tipo de atribuição de um problema de empacotamento define o objetivo de otimização adotado no posicionamento dos itens no objeto, que pode ser a minimização dos recursos disponíveis ou a maximização da produção, por exemplo. Os itens podem possuir dimensões fixas ou flexíveis, variando altura e largura de modo que a área seja preservada ou com altura e largura que variam Capítulo 2. Fundamentação Teórica 7 de modo a respeitar uma proporção pré-definida entre elas. Ainda, cada item pode ser regular ou irregular, com posicionamento ortogonal ou não-ortogonal. Sobre os objetos, um problema pode considerar um único objeto, múltiplos objetos idênticos ou múltiplos objetos heterogêneos, disponíveis para alocar os itens. A forma como um conjunto de itens é cortado ou empacotado no objeto pode ser chamada de padrão de corte, assim a solução de um PCE é representada por uma sequência de padrões que resultam em um layout sem sobreposições. Além das características sobre os itens e objetos, a categoria dos padrões de cortes possíveis deve ser considerada para definir o problema. Um padrão pode ser categorizado em guilhotinado ou não-guilhotinado. O corte guilhotinado é feito por toda a extensão do objeto, paralelamente à um dos lados, produzindo dois novos retângulos, isto é, o corte vai de um extremo ao outro do retângulo original. Um padrão é chamado de guilhotinado quando é formado por sucessivos cortes guilhotinados. Caso contrário, assume-se que o padrão é não-guilhotinado. Com o objetivo de minimizar recursos durante o processo de planejamento de layout de circuitos VLSI, o problema de empacotamento ortogonal bidimensional com retângulos flexíveis, alocados em um único objeto de modo não-guilhotinado, é considerado neste trabalho. 2.2.2 Retângulos flexíveis Uma variação para o problema de empacotamento bidimensional ocorre quando os retân- gulos a serem empacotados possuem dimensões flexíveis (soft rectangles), conforme supracitado. Nesse caso, uma região retangular com comprimento e altura pré-definidos deve ser preenchida por um conjunto de retângulos menores com dimensões flexíveis, que podem variar em um inter- valo, respeitando a proporção (aspect ratio) entre suas respectivas alturas e larguras. Selecionar quais retângulos flexíveis de um conjunto pré-definido serão empacotados na região e quais suas dimensões, respeitando as suas limitações geométricas e a não-sobreposição dos itens escolhidos, consiste em um desafio adicional na resolução deste problema. Na Figura 3, as dimensões de um item i são ilustradas, assim como as dimensões x e y da área de alocação. Cada item pode variar mantendo sua área ou variar livremente dentro de um intervalo pré-definido de proporção entre sua altura e largura. Para o objeto (chip), é possível determinar dimensões fixas ou considerar como dimensão a altura e largura do menor retângulo envolvente que contém todos os itens empacotados. Assim, as dimensões do objeto podem ser alteradas durante o processo de posicionamento dos itens. Para exemplificar o problema de empacotamento com retângulos flexíveis em área fixa, considere uma região retangular inicial com dimensões 140 × 140. Três modos possíveis de alocação são apresentados na Figura 4. Retângulos com as mesmas cores entre as figuras, possuem a mesma área. Nos três casos, as dimensões dos retângulos alocados variam sem que área seja alterada. É possível notar que a alocação da região no segundo recipiente ficou mais concentrada Capítulo 2. Fundamentação Teórica 8 iy x (xi, yi) hi wi (W, H) ÁREA PRÉ-DEFINIDA: Variação de dimensões com área fixa = 600 20 × 30 25 × 24 PROPORÇÃO DEFINIDA: Variação de dimensões com 0.5 ≤ h w ≤ 1.5 20 × 30 20 × 20 Figura 3 – Dimensões de um item i com exemplos e possíveis variações de dimensão, mantendo a área inicial ou respeitando uma proporção pré-definida. e, consequentemente, com melhor aproveitamento da região. Ainda, as duas primeiras situações apresenta objetos com dimensões fixas, enquanto a terceira situações assume, como dimensões do objeto, o menor retângulo envolvente que contém todos os itens alocados. 40 × 40 50 × 40 60 × 40 40 × 60 60 × 50 20 × 80 40 × 40 40 × 50 50 × 32 50 × 60 50 × 48 50 × 48 AJUSTE DE ITENS: 40 × 40 40 × 50 50 × 32 50 × 60 50 × 48 50 × 48 AJUSTE DE ITENS E OBJETO: Figura 4 – Representação de possíveis empacotamentos com retângulos flexíveis. Este problema apresenta inúmeras aplicações, sendo uma das principais, o problema de planejamento e alocação de módulos flexíveis para conexões entre redes em circuitos integrados VLSI (Seção 2.1). Nesta aplicação, cada item, também chamados de módulo, pode ser ajustado de diferentes formas, variando suas dimensões dentro de um intervalo definido de proporção entre altura e largura. Os módulos devem ser alocados em um chip que, neste trabalho, assume as dimensões do menor retângulo envolvente possível. 2.2.3 Dificuldade de resolução Os PCE pertencem à classe de problema NP-difícil, isto é, não se conhece algoritmo exato que resolva estes problemas em tempo polinomial. Devido sua característica combinatória, existe um número exorbitante de arranjos possíveis quando o objetivo é determinar o posicionamento ótimo de corte ou empacotamento, inviabilizando o processo. Assim, o uso de métodos exatos para otimização de um problema de empacotamento é altamente custoso, pois exige um longo tempo de processamento, sem que sequer sejam gerados resultados práticos. Capítulo 2. Fundamentação Teórica 9 Com o intuito de viabilizar o processo de resolução de PCE, métodos heurísticos são comumente utilizados para solucionar o problema de empacotamento em tempos computacionais razoáveis. Tais métodos não garantem a obtenção de uma solução ótima, mas podem obter boas aproximações com baixo esforço computacional, isto é, menor tempo de processamento, quando comparado à utilização de métodos exatos. Diferentes métodos foram propostos na literatura para resolver, de modo exato ou aproximado, vários problemas de empacotamento e podem ser agrupados, de forma simplificada, em heurísticas, meta-heurísticas e métodos exatos. Uma breve revisão sobre cada método de resolução é apresentada no Capítulo 3. 10 3 Revisão de literatura O problema abordado neste trabalho trata o floorplanning de circuitos VLSI como um problema de empacotamento de retângulos flexíveis. Neste capítulo, é apresentada uma revisão de literatura que contempla trabalhos relevantes sobre problemas de empacotamento de modo geral, abordados por meio de diferentes técnicas de resolução, e trabalhos com métodos aplicados especificamente no contexto de planejamento de circuitos integrados. 3.1 Problemas de empacotamento A literatura sobre problemas de corte e empacotamento ortogonal bidimensional tem crescido consideravelmente nos últimos anos (IORI et al., 2021). Nesta seção são descritos mo- delos matemáticos propostos para resolver problemas de empacotamento em diversas aplicações, além de heurísticas e meta-heurísticas, comumente utilizadas para obter soluções em tempo computacional viável. 3.1.1 Modelos matemáticos Para empacotar um conjunto de itens retangulares mistos flexíveis, Murata e Kuh (1998) propuseram um modelo matemático que trata as variáveis de posição relativa dos itens como dados de entrada. A abordagem dos autores é baseada na representação de posicionamento dos itens por pares de sequência (Sequence Pair). Um par de sequência é um par de permutações entre dois retângulos e especifica qual das condições de posição é válida: é possível que um módulo esteja à direita ou à esquerda de outro módulo, horizontalmente posicionado, ou que um módulo esteja acima ou abaixo de outro módulo, verticalmente posicionado. A representação adotada pelos autores é a mais utilizada para representar padrões ao longo do tempo. Em Lodi e Monaci (2003) foi abordado um modelo que executa o empacotamento bidimensional de itens formando níveis. Os itens são inseridos da esquerda para a direita no primeiro nível, que tem sua altura determinada pela altura do item mais alto, e tem como objetivo minimizar a altura utilizada no retângulo envolvente da alocação. Ibaraki e Nakamura (2006) abordaram o problema de empacotamento de retângulos, cujas formas poderiam ser ajustáveis, dentro de determinadas restrições de perímetro e área. Os autores utilizaram pares de sequência Capítulo 3. Revisão de literatura 11 para especificar posições relativas entre cada par de retângulos. Para determinar o tamanho exato e a localização de todos os retângulos, uma formulação matemática foi proposta e para encontrar bons pares de sequências, técnicas de busca local foram utilizadas. Considerando características de flexibilidade, Bui, Vidal e Hà (2019) propuseram um modelo de programação inteira mista para representar o problema de corte guilhotinado dois- estágios quando os retângulos a serem cortados possuem área fixa, porém, perímetro flexível. Uma abordagem baseada em busca binária também foi proposta. O estudo desenvolvido teve como referência a reforma agrária no Vietnã. 3.1.2 Abordagens heurísticas e meta-heurísticas Heurísticas são métodos baseados em argumentos intuitivos que geram boas soluções sob certas condições, mas que não garantem a otimalidade. Meta-heurísticas são métodos de otimização flexíveis com estrutura de algorítimos genéricos, que coordenam heurísticas simples e podem ser aplicados a diferentes tipos de problemas com relativamente poucas modificações a serem feitas para adaptá-los (CHERRI, 2009). Muitas meta-heurísticas foram introduzidas na literatura. Entre estas, encontramos simulated annealing (recozimento simulado), busca de vizinhança variável, busca de dispersão, busca local iterada, otimização de colônia de formigas, otimização de enxame e algoritmos genéticos. Imahori, Yagiura e Ibaraki (2003) propuseram meta-heurísticas de busca local com geração de várias soluções iniciais, busca local iterativa e busca aleatória, para otimizar os custos de um empacotamento com retângulos rígidos. Em Imahori, Yagiura e Ibaraki (2005) os autores desenvolveram técnicas para avaliar soluções obtidas por meio da representação de pares de sequência. Bortfeldt (2006) sugeriu um algoritmo genético para resolver o problema de minimização da área no empacotamento de retângulos, abordando o empacotamento em tiras (strip packing) bidimensionais, que consiste em alocar um conjunto de itens retangulares de dimensões fixas em um retângulo maior de largura fixa e largura variável, de modo que a largura total do layout seja minimizada. Em Bortfeldt (2013), o mesmo autor apresentou uma abordagem genérica que é baseada em dois algoritmos: uma heurística construtiva e um algoritmo que alterna método de busca e algoritmo genético com restrições que consideram padrões guilhotináveis. Existe uma vasta literatura sobre heurísticas para problemas de empacotamento bidimen- sional. Em Ortmann e Vuuren (2010) os autores abordaram dois problemas de empacotamento, o problema de empacotamento em tiras e o problema de empacotamento em caixas de tamanho variável. Além disso, compararam computacionalmente um total de 252 heurísticas e variantes para problemas de empacotamento em tiras bidimensionais. Em Iori et al. (2021), os autores revisam mais de 180 artigos relacionados a problemas de corte e empacotamento ortogonal bidimensional, com cerca de metade das referências trabalhos Capítulo 3. Revisão de literatura 12 publicados nos últimos dez anos e apenas 20% antes de 2000. Na revisão proposta, foram descritos os principais métodos de pré-processamento e relaxamento, além de alguns algoritmos heurísticos e de aproximação. Os autores discutiram modelos matemáticos e apresentaram estatísticas sobre os métodos exatos para problemas bidimensionais considerados. 3.1.3 Algoritmo genético BRKGA O algoritmo genético é uma meta-heurística introduzida por Holland (1975) aplicando o princípio de seleção natural de Darwin. Em um algoritmo genético cada indivíduo da população representa uma solução viável para o problema abordado e, dada uma série de gerações produzidas pelo algoritmo, o indivíduo mais apto da última geração é adotado como solução. Em geral, dois tipos de operadores são utilizados: o cruzamento e a mutação. O cruzamento (crossover) é uma operação realizada para definir novos indivíduos que tenham as características genéticas de seus pais. Essa operação intensifica a busca ao procurar obter uma boa solução através da combinação de duas soluções da população. A mutação é uma operação utilizada para perturbar a convergência de uma população e diversificar a busca da solução, procurando gerar indivíduos distintos dos demais indivíduos da população através de uma modificação aleatória. Geralmente, a taxa de mutação é baixa para evitar discrepâncias. Algoritmos genéticos com chaves aleatórias (RKGA, Random-Key Genetic Algorithm) foram propostos pela primeira vez por Bean (1994) para resolver problemas de otimização combinatória envolvendo sequenciamento. Em um RKGA, uma população é representada por vetores de chaves reais geradas aleatoriamente no intervalo contínuo [0,1), sendo chamada de geração a população desenvolvida a cada iteração. Um algoritmo determinístico, chamado de decodificador, recebe um vetor de chaves aleatórias como entrada e gera uma solução viável do problema de otimização com valor associado da função objetivo. Com esses valores calculados pelo decodificador na geração atual, a população é dividida em dois grupos de indivíduos: um pequeno grupo de elite com os melhores resultados obtidos e o conjunto restante de indivíduos não-elite. Para evoluir a população, uma nova geração de indivíduos deve ser produzida. Uma nova geração é composta pelos indivíduos de elite da geração anterior, novos vetores gerados aleatoriamente na operação de mutação e indivíduos descendentes, produzidos através do processo de cruzamento de quaisquer dois indivíduos da população. Os descendentes inseridos correspondem sempre às soluções discretas do problema de otimização combinatória, com viabilidade garantida pelo decodificador. O algoritmo genético de chave aleatória tendenciosa (BRKGA, Biased Random-Key Genetic Algorithm) é um RKGA, com algumas particularidades. Assim como o RKGA, as meta-heurísticas BRKGA obtém uma solução viável para um problema de otimização através da decodificação de uma solução codificada, como um vetor de chaves aleatórias geradas no intervalo Capítulo 3. Revisão de literatura 13 real [0, 1). Após o cálculo da função objetivo realizado pelo decodificador e o particionamento dos indivíduos em dois grupos (elite e não-elite), cria-se uma nova geração. De modo semelhante, uma estratégia elitista garante que as melhores soluções obtidas sejam passadas sem alterações de uma geração para a próxima, enquanto a mutação de indivíduos desempenha o papel de perturbar a convergência da população esquivando de valores ótimos locais. Diferentemente do RKGA, o BRKGA seleciona os indivíduos para a operação de cruza- mento de modo tendencioso. Neste método, determina-se que o cruzamento de indivíduos (pais) no algoritmo seja necessariamente feito com um indivíduo de elite e um indivíduo não-elite, ao invés de escolher ambos a partir da população toda. A repetição na seleção de um indivíduo para cruzamento é permitida e, portanto, um pai pode gerar mais de um descendente na mesma geração. Ainda, admite-se que a probabilidade do indivíduo descendente herdar a chave do pai elite é sempre maior em relação ao pai não-elite. Diversos trabalhos propõem abordagens BRGKA para diferentes tipos de problemas de otimização. Em Ericsson, Resende e Pardalos (2002) foram propostos algoritmos genéticos para resolver o problema de configuração de peso do protocolo de roteamento de internet intra-domínio. O método BRKGA dos autores, denominado por GAOSPF (Genetic Algorithm for Open Shortest Path First routing) trata o problema de roteirização em redes com o objetivo de minimizar o custo total na distribuição do fluxo de dados. Um BRKGA foi comparado com algoritmos genéticos da literatura em Gonçalves e Resende (2004). A meta-heurística para projetar células de manufatura, apresentada pelos autores, obteve os melhores resultados na comparação realizada. No ano seguinte, em Gonçalves, Mendes e Resende (2005), foi proposto pelos autores um BRKGA para o problema de programação de tarefas no ambiente job shop com o objetivo de minimizar o makespan, isto é, obter o menor tempo de processamento de todas as tarefas. Em Gonçalves (2007) foi proposto um algoritmo genético para o problema de empacotamento bidimensional com objetivo de reduzir a área não ocupada na solução geométrica. O algoritmo proposto pelo autor é uma abordagem híbrida composto por um procedimento de colocação e um BRKGA. Para resolver o problema de congestionamento em redes rodoviárias, um BRKGA foi proposto em Buriol et al. (2010) com o objetivo de otimizar o desempenho da rede de transportes através da alocação estratégica de pedágios. O BRKGA também foi utilizado em Valente et al. (2011), porém em outro contexto. Os autores propuseram um BRKGA para o problema de programação de tarefas no ambiente de uma máquina com objetivo de minimizar atrasos. Já em Noronha, Resende e Ribeiro (2011), utilizou-se o BRKGA para o problema de roteirização e atribuição de comprimentos de onda, minimizando a quantidade total de comprimentos. Um tutorial para a implementação do BRKGA foi estruturado em Gonçalves e Resende (2011). No ano seguinte, um algoritmo para o empacotamento tridimensional, denominado por BRKGA-CLP (single Container Loading Problem), foi proposto pelos autores em Resende et al. (2012), com o objetivo de otimizar o volume de contêineres. Em Mainieri (2014) foi utilizado um Capítulo 3. Revisão de literatura 14 BRKGA em um ambiente de trabalho sequencial em estágio, conhecido pelo termo Flowshop híbrido, em que cada estágio deve ser executado apenas uma vez e por uma máquina. O método foi proposto para minimizar o atraso de todos os trabalhos realizados no ambiente dado. Também com o objetivo de minimização, porém em uma aplicação completamente distinta, em Stefanello (2015) um BRKGA foi proposto para resolver o problema de tráfego em redes de transporte e de telecomunicações com o objetivo de controlar o fluxo na rede, minimizando o congestionamento. Prasetyo et al. (2016) realizaram uma revisão o desenvolvimento de BRKGAs para resolver diversos problemas de otimização. O trabalho teve como objetivo fornecer uma contex- tualização do desenvolvimento dos algoritmos e áreas de aplicação encontradas na literatura. Os autores destacaram a tendência de aumento do uso do BRKGA para melhorar o desempenho de outros procedimentos quando combinados. Em Mönch e Roob (2018) foi proposta uma estrutura matheurística para problemas de escalonamento com máquinas de processamento em lote pa- ralelo, com atribuição de lotes às máquinas e sequenciamento realizados por uma abordagem BRKGA. Apesar das limitações indicadas no trabalho, a estrutura proposta foi capaz de fornecer soluções de alta qualidade em um curto período de tempo computacional. Em Mauri et al. (2021) um BRKGA foi proposto, juntamente com outra meta-heurística híbrida, para resolver um problema de localização de instalações de multiprodutos, com o objetivo de minimizar o custo relacionado a fábricas e depósitos abertos mais o custo de transporte dos produtos das fábricas até os clientes. O BRKGA também foi considerado em publicações ainda mais recentes, como em Lima et al. (2021) e Guimarães et al. (2022). Em todos os trabalhos supracitados, o uso do BRKGA gerou bons resultados, obtendo melhor desempenho frente a outros algoritmos genéticos encontrados na literatura, indicando o alto potencial do método. Além de sua qualidade e facilidade de adaptação para abranger diversos problemas, o BRKGA tem garantia de viabilidade de soluções (GONÇALVES; RESENDE, 2011) e possui tutoriais disponíveis que facilitam sua implementação. Deste modo, um BRKGA para o problema de planejamento de circuitos VLSI é proposto e detalhado no Capítulo 5 deste trabalho. 3.2 Circuitos integrados VLSI Zhan, Feng e Sapatnekar (2006) apresentaram um algoritmo analítico sofisticado de planejamento de layout de circuitos VLSI que pode ser usado para empacotar eficientemente módulos flexíveis em uma matriz fixa. A localização e o dimensionamento dos módulos são otimizados para que seja alcançado valor reduzido de comprimento total de fio. Primeiramente, as posições de cada módulo são determinadas de forma aproximada. Em seguida, as sobreposições são gradualmente removidas no segundo estágio para obter a alocação final. Apesar da abordagem lidar bem com projetos de grande escala, ela não pode garantir uma solução sem sobreposição. Young et al. (2001) utilizaram relaxação lagrangeana para resolver o problema de alocação de módulos retangulares flexíveis. O método desenvolvido teve por objetivo minimizar a área Capítulo 3. Revisão de literatura 15 total de empacotamento dos módulos, e foi implementado em um simulated annealing framework utilizando a representação por pares de sequência. Com uma abordagem semelhante, Chi e Chi (2002) propuseram um algoritmo floorplanning com módulos flexíveis para otimizar a área utilizada no design de um circuito VLSI. Chen et al. (2007) estudaram o problema no floorplannig com contorno fixo. Um algoritmo baseado em uma busca evolutiva robusta foi desenvolvido, juntamente com uma nova abordagem para flexibilizar os módulos alocados e, assim, ajustar o layout reduzindo o contorno fixo no chip. Chen e Chang (2009) propuseram uma abordagem analítica exata tratando as posições relativas dos módulos retangulares como variáveis binárias do problema no floorplanning. Para minimizar a área de forma linear, a largura do retângulo envolvente foi fixada e a altura necessária para a alocação dos módulos minimizada na função objetivo, respeitando limites pré-definidos. O modelo matemático formalizado pelos autores apresentou resultados satisfatórios, podendo considerar módulos flexíveis e gerar soluções exatas. Apesar disso, a formulação é um problema linear inteiro misto e seu tempo de execução se torna bastante elevado para médias e grandes instâncias. Mais detalhes sobre esta abordagem é apresentada na Seção 3.3, dado que a abordagem dos autores Chen e Chang (2009) foi uma forte referência para o desenvolvimento do modelo proposto na Capítulo 4 deste trabalho. Chen, Zhu e Ali (2011) sugeriram um algoritmo híbrido de simulated annealing (HSA) para o planejamento de alocação na etapa física de circuitos VLSI. O HSA usa um método guloso para construir uma árvore B* inicial, uma operação em árvore B* para explorar o espaço de busca e uma estratégia de busca para aprimorar os resultados da exploração feita. Para reduzir a medida de área de empacotamento, além do comprimento de fio na alocação de módulos rígidos, Anand, Saravanasankar e Subbaraj (2013) implementaram uma técnica de otimização multiobjetivo chamada AMOSA (Archived Multiobjective Simulated Annealing Algorithm), um algoritmo baseado em simulated annealing. Chan, Hsu e Lin (2013) adotaram uma abordagem de dois estágios para o floorplanning de um conjunto de módulos de tamanhos variados. O primeiro estágio consiste na distribuição dos módulos em um contorno fixo otimizando o comprimento de fio utilizado. No segundo estágio, é realizada uma abordagem baseada em partição para obter uma solução viável sem prejudicar o bom resultado atingido no estágio inicial. He, Ji e Li (2015) apresentaram uma heurística de redução dinâmica para o problema de minimização da área de empacotamento de retângulos flexíveis em circuitos. A abordagem proposta transforma a instância do problema original em uma série de instâncias menores, determinando dinamicamente as dimensões do retângulo envolvente. Com o mesmo objetivo de estudo, Gracia e Rajaram (2015) adotaram uma estratégia de busca híbrida e algoritmo genético para otimizar o floorplanning VLSI. Laskar et al. (2015) apresentaram um estudo e comparação dos diferentes algoritmos de otimização e as representações envolvidas no problema de layout do VLSI. Dentre os algoritmos, a maior parte do trabalho foi realizada para otimização de minimização de área. Singh, Baghel Capítulo 3. Revisão de literatura 16 e Agarwal (2016) reuniram e revisaram heurísticas e algoritmos meta-heurísticos de trabalhos que consideram o problema de otimização no floorplanning de VLSI. Comparações entre os procedimentos reunidos foram incluídas neste estudo e mesmo a representação mais eficaz apresentada indicou limitações de flexibilidade. Wu et al. (2016) propuseram um procedimento heurístico para resolver o problema de minimização da área de empacotamento de retângulos quando o layout final deveria conter um retângulo central, com flexibilidade nas dimensões, as quais poderiam ser alteradas dentro de limites razoáveis. Estratégias de preenchimento do espaço interno foram propostas para melhorar a taxa de preenchimento do layout final. Jenifer, Anand e Levingstan (2016) propuseram uma abordagem para a determinação do design físico do VLSI. Com o objetivo de obter a área mínima do floorplanning remodelando os blocos presentes, o trabalho proposto redefine o problema com uma meta-heurística baseada em simulated annealing. Singh, Baghel e Agarwal (2016) usaram um algoritmo de simulated anneling otimizar a área do problema de planejamento do floorplanning de VLSI, reduzindo o espaço interno não utilizado na alocação dos módulos. Para resolver o problema de empacotamento de retângulos flexíveis, Ji et al. (2017) propuseram um algoritmo que funde todos os retângulos em um retângulo final composto. Os autores mostraram que o algoritmo proposto pode garantir um layout viável sob algumas condições. Com o objetivo final de reduzir a área total de alocação de módulos no planejamento de layouts de circuitos VLSI de contorno fixo, Venkatraman e Sundhararajan (2019) propuseram uma abordagem híbrida que combina um algoritmo genético com o algoritmo Harmony Search (HS). Laudis e Ramadass (2020) apresentaram um algoritmo multiobjetivo bioinspirado que explora um conjunto de soluções chamado de geração. A cada geração parte da população sofre mutações e cruzamentos, procurando atingir uma nova solução melhor que as anteriores. Shunmugathammal, Columbus e Anand (2020) propuseram um método para resolver o problema de otimização de floorplanning usando algoritmo genético que é chamado Lion Optimization Algorithm (LOA) e tem como objetivo minimizar a área utilizada na alocação. O LOA foi desenvolvido para layouts não-guilhotinados de itens com restrição de contorno fixo. Apesar dos diversos trabalhos abordando o problema de empacotamento de retângulos, métodos de solução mais eficientes podem ser explorados, garantindo que muitos estudos ainda sejam desenvolvidos e possibilitando o uso de instâncias mais próximas do ponto de vista prático, principalmente no contexto do posicionamento de módulos flexíveis em circuitos VLSI. Para resolver este problema, abordagens exata, matheurística e meta-heurística baseadas na literatura serão estudadas neste trabalho. Capítulo 3. Revisão de literatura 17 3.3 Modelo de Chen e Chang (2009) Para solucionar o problema de empacotamento de módulos retangulares, fixos ou flexíveis, Chen e Chang (2009) propuseram uma abordagem analítica exata tratando as posições relativas de itens retangulares como variáveis binárias do problema. Sua formulação inclui uma função objetivo e considera dois conjuntos de restrições básicas: restrições de não sobreposição do item e restrições de dimensão. Assim, garante-se que os módulos (itens retangulares) alocados não estejam sobrepostos entre si e estejam completamente contidos no retângulo envolvente. Com duas variáveis binárias (pij e qij) introduzidas, dois módulos i e j são considerados não sobrepostos, se pelo menos um dos casos apresentados na Tabela 1 for satisfeito. Na formu- lação, (xi, yi) é o par ordenado que indica a posição do canto inferior esquerdo do item i, wi a largura e hi a altura do item i. Analogamente, para o item j. Tabela 1 – Casos possíveis de posicionamento de dois módulos i e j, com i < j. pij qij i está à esquerda de j xi + wi ≤ xj 0 0 i está abaixo de j yi + hi ≤ yj 0 1 i está à direita de j xi − wi ≥ xj 1 0 i está acima de j yi − hi ≥ yj 1 1 Fonte: Traduzido de Chen e Chang (2009). O modelo matemático apresentado por Chen e Chang (2009), tem como objetivo mini- mizar a função não linear definida pela área do layout, A = x · y, em que x é a largura e y a altura do retângulo envolvente resultante após a alocação dos itens. O valor de x e y deve ser obtido, respeitando limites superiores pré-definidos de largura e altura do retângulo envolvente do layout, respectivamente,W e H . Para transformar a função objetivo em linear, diminuindo a complexidade do sistema e possibilitando tratar o problema como linear inteiro misto, uma aproximação para o problema foi feita. Assim, fixou-se a largura x = W , minimizando apenas y, e consequentemente, reduzindo a área total utilizada na alocação. Tal modelo é definido por: Parâmetros: • n: número de itens; • J = {1, . . . , n}: conjunto de itens i; • wi, hi: dimensões do item i; • W, H: dimensões máximas do retângulo envolvente (largura e altura do chip). Variáveis: Capítulo 3. Revisão de literatura 18 • xi, yi: coordenadas do item i (variável de posição); • pij, qij: relação horizontal e vertical de posição, para todo i < j. Modelo: minimizar y (3.1) sujeito a : xi + wi ≤ W ∀i ∈ J (3.2) yi + hi ≤ y ∀i ∈ J (3.3) xi + wi ≤ xj + W (pij + qij) i < j, ∀i ∈ J (3.4) yi + hi ≤ yj + H(1 + pij − qij) i < j, ∀i ∈ J (3.5) xi − wj ≥ xj − W (1 − pij + qij) i < j, ∀i ∈ J (3.6) yi − hj ≥ yj − H(2 − pij − qij) i < j, ∀i ∈ J (3.7) xi, yi ≥ 0 ∀i ∈ J (3.8) pij, qij ∈ {0, 1} i < j, ∀i ∈ J (3.9) No modelo (3.1)-(3.9), a função objetivo (3.1) minimiza a altura do retângulo envolvente do layout. As restrições (3.2) e (3.3) garantem que as dimensões dos itens alocados estejam dentro dos limites de largura e altura, respectivamente. As restrições (3.4)-(3.7) asseguram que os módulos, tomados dois a dois, não fiquem sobrepostos e que uma das desigualdades exibidas na Tabela 1 seja aplicada. Quando pij = 1 e qij = 0, por exemplo, a restrição (3.6) é dada por xi − wj ≥ xj − W (1 − 1 + 0) e a inequação xi − wj ≥ xj é aplicada, no caso em que i está à direita de j. A restrição (3.8) garante a não-negatividade das variáveis xi, yi e a restrição (3.9) define o domínio das variáveis pij e qij . O modelo (3.1)-(3.9) não envolve objetivo ou restrições específicas do floorplanning. Desta forma, pode ser utilizado genericamente para problemas de empacotamento que buscam minimizar altura ou largura do retângulo envolvente. Com base na formulação de Chen e Chang (2009), que considera apenas a otimização da área, adaptações podem ser realizadas com a finalidade de melhor representar o problema de planejamento de layouts em circuitos integrados VLSI. Um modelo matemático é proposto e detalhado no Capítulo 4. 19 4 Modelo Matemático Neste capítulo, conceitos essenciais e um modelo matemático são propostos para resol- ver o floorplanning em circuitos VLSI, abordado como um problema de empacotamento de retângulos flexíveis. Este problema considera como variáveis de decisão as posições ideais para um determinado conjunto de módulos retangulares flexíveis alocados em uma área de chip, de modo que não haja sobreposição, além de decidir quais as dimensões mais adequadas para cada retângulo, respeitando proporções pré-estabelecidas (aspect radio) entre sua altura e largura. 4.1 Contextualização Com o avanço da tecnologia, o número de módulos em um chip aumenta. Com o aumento da complexidade do floorplanning e dos requisitos do circuito, novas considerações podem ser agregadas ao problema, entre elas a possibilidade dos módulos alocados serem flexíveis. Para considerar esta possibilidade, no modelo proposto por Chen e Chang (2009) deve-se incluir as restrições (4.1) e (4.2): wmin i ≤ wi ≤ wmax i ∀i ∈ J (4.1) hmin i ≤ hi ≤ hmax i ∀i ∈ J (4.2) Os módulos flexíveis podem alterar suas alturas e larguras, ao contrário dos módulos rígidos com alturas e larguras fixas, mantendo a mesma área do módulo. Neste caso, as dimensões wi e hi passam a ser tratadas como variáveis nomodelo e novos parâmetros são considerados:wmin i e wmax i indicam, respectivamente, o limite mínimo e máximo da largura do item i. Analogamente, hmin i e hmax i indicam, respectivamente, o limite mínimo e máximo da altura do item i. Com módulos ajustáveis, configurações de layout mais eficientes são obtidas, possibilitando um melhor uso da área do chip e encaixe na alocação dos itens. Além da área utilizada na alocação, o comprimento de fio utilizado para conectar os módulos no circuito também deve ser considerado. Uma medida de comprimento total de in- terconexões muito grande resulta em chips maiores e mais lentos, afetando o desempenho e o custo de fabricação do circuito. Ao reduzir a quantidade de fio utilizado, obtém-se circuitos que Capítulo 4. Modelo Matemático 20 utilizam menos recursos de roteamento, com tempos de rota mais consistentes e com maior nível de desempenho (KAHNG et al., 2011; CHAN; HSU; LIN, 2013). 4.2 Representação de posicionamento Para representar a configuração geométrica dos módulos no layout, as posições dos itens podem ser especificadas por coordenadas definidas em relação a um sistema de eixos ou através de um conjunto de relações topológicas entres os itens, definindo as posições relativas entre eles. Neste trabalho, foi utilizada uma representação derivada da ferramenta padrão, conhecida como par de sequência (MURATA et al., 1996), para especificar a posição relativa entre cada par de módulos e obter um empacotamento sem sobreposição. As posições relativas atribuídas aos itens podem ser escritas como inequações e facilmente inseridas em um modelo matemático. Assim como em Chen e Chang (2009), dado dois módulos i e j, as variáveis binárias de posicionamento lij e bij , horizontal e vertical, respectivamente, são introduzidas para denotar a posição que o item i ocupa em relação ao item j. Apenas uma das variáveis binárias associadas ao par de itens assume valor não nulo, assim, os módulos i e j são considerados não sobrepostos se uma das condições apresentadas na Tabela 2 é válida. Possíveis casos de posicionamento de itens são ilustrados na Figura 5. i j i está à esquerda de j (lij = 1) j i j está à esquerda de i (lji = 1) j i i está abaixo de j (bij = 1) i j j está abaixo de i (bji = 1) Figura 5 – Casos possíveis de posicionamento entre dois módulos i e j. Dado que a ferramenta de Murata et al. (1996) é a mais utilizada para representar padrões de posicionamento ao longo da literatura, a representação de posicionamento descrita acima foi adotada neste trabalho por se relacionar fortemente com pares de sequência. Desta forma, é Capítulo 4. Modelo Matemático 21 Tabela 2 – Valores das variáveis binárias ao posicionar dois módulos i e j, com i < j lij bij lji bji i está acima de j 0 0 0 1 i está à direita de j 0 0 1 0 i está abaixo de j 0 1 0 0 i está à esquerda de j 1 0 0 0 possível adaptar ou incrementar os métodos aqui propostos, combinando-os com outros trabalhos existentes sem grandes complicações na representação de posicionamento dos itens, também chamados de módulos. 4.3 Cálculo do comprimento de fio Nos circuitos integrados, uma rede r é um conjunto de módulos (itens retangulares flexíveis) interconectados pré-definidos na instância. Para calcular o comprimento do fio gasto para fazer essas conexões, recorre-se à aproximação, dado que as informações reais de roteamento não estão disponíveis no estágio do floorplanning. Uma aproximação de comprimento de fio comumente usada para uma rede é medir seu comprimento de fio de meio-perímetro ponderado (HPWL). O método HPWL é razoavelmente preciso, calculado com eficiência e adota como distância o comprimento de meio perímetro da menor caixa delimitadora (retângulo) que inclui todos os pontos de conexão do circuito integrado, também chamados de pinos. Quando as posições dos pinos não são fornecidas, pode-se calcular o HPWL usando os centros dos módulos flexíveis (CHEN; CHANG, 2009; KAHNG et al., 2011). Neste trabalho, o cálculo do HPWL é obtido a partir do comprimento de meio perímetro do retângulo exterior com arestas que contém o centro dos módulos que estão ligados entre si, isto é, a distância entre os dois pontos centrais dos módulos é dada pela soma das diferenças absolutas de suas coordenadas, utilizando apenas retas verticais e horizontais. Este formato não-euclidiano de obter distâncias dx e dy é conhecido como Geometria do Táxi ou Distância de Manhattan (KAHNG et al., 2011; JENIFER; ANAND; LEVINGSTAN, 2016), ilustrado na Figura 6. O comprimento de fio entre dois itens i, j ∈ J é dado por d = dx + dy, sendo: dx = |xj − xi| (4.3) dy = |yj − yi| (4.4) Para obter as dimensões Wr e Hr, respectivamente, largura e altura de uma rede r, calcula-se a soma da distância central de todos os módulos interconectados. O modelo matemático proposto otimiza as estimativas dessasmétricas de comprimento de fio,minimizando as dimensões das redes do circuito integrado VLSI. Capítulo 4. Modelo Matemático 22 (xi, yi) (xj , yj)dy dx Figura 6 – Comprimento de fio HPWL entre dois itens (dx + dy). Nas Figuras 7 e 8, um conjunto de itens alocados são ilustrados para exemplificar como a distância de HPWL é, geometricamente, obtida em uma rede. Cada item possui seu ponto central destacado e duas redes distintas são apresentadas. Na Figura 7, o retângulo envolvente que contém os itens 1, 2 e 4 representa uma possível rede (Rede 1) e espera-se que todos os itens contidos nela sejam interconectados. As dimensõesW1 = 7 eH1 = 4, largura e altura da Rede 1, respectivamente, também são apresentadas. H 1 = 4 W1 = 7 Rede 1 4 1 2 3 Figura 7 – Exemplo 1 de distância HPWL = 11. O comprimento de fio, ou distância HPWL, da rede é dado pela soma de suas dimensões, nesse caso, o comprimento de fio da Rede 1 é igual a 11 unidades de medida. Na Figura 8, a rede apresentada (Rede 2) contém os itens 3 e 4, conectados entre si com comprimento de fio em destaque. As métricas associadas à Rede 2 são obtidas de forma análoga à Rede 1, com comprimento de fio igual à 7,5 unidades de medida. Sabendo que o comprimento de fio, utilizado nas interconexões, tem grande influência nos custos e desempenho de um circuito, busca-se minimizar as distâncias associadas ao problema de empacotamento de retângulos flexíveis abordado. Ao adotar uma função objetivo que reduz a distância HPWL do circuito VLSI, espera-se obter layouts compactos e eficientes. Capítulo 4. Modelo Matemático 23 H 2 = 0, 5 W2 = 7 Rede 2 4 1 2 3 Figura 8 – Exemplo 2 de distância HPWL = 7,5. 4.4 Modelo Matemático A formulação proposta tem como objetivo minimizar as distâncias do comprimento de fio HPWL entre subconjuntos especificados dos itens, isto é, reduzir a medida da quantidade de metal necessária para interconectar os módulos de forma a garantir a funcionalidade do chip. Os parâmetros e variáveis do modelo matemático são definidos por: Parâmetros: • n: número de itens flexíveis (módulos); • m: número de redes; • J = {1, . . . , n}: conjunto de itens i; • R = {1, . . . , m} ⊆ J : conjunto de redes r; • wmin i , hmin i : dimensões mínimas do item i; • wmax i , hmax i : dimensões máximas do item i; • amin i , amax i : proporção mínima e máxima entre altura e largura do item i (aspect ratio); • W max, Hmax: dimensões máximas do retângulo envolvente (largura e altura do chip). Variáveis: • xi: abcissa do item i (variável de posição); • yi: ordenada do item i (variável de posição); • wi: largura do item i; Capítulo 4. Modelo Matemático 24 • hi: altura do item i; • Wr: largura da rede r; • Hr: altura da rede r; • lij e bij: relação horizontal (left) e vertical (below) de posição, respectivamente; lij = ⎧⎨ ⎩ 1, se i está à esquerda de j; 0, caso contrário. bij = ⎧⎨ ⎩ 1, se i está abaixo de j; 0, caso contrário. Modelo: minimize ∑ r∈R Wr + Hr (4.5) sujeito a : wmin i ≤ wi ≤ wmax i ∀i ∈ J (4.6) hmin i ≤ hi ≤ hmax i ∀i ∈ J (4.7) amin i · hi ≤ wi ≤ amax i · hi ∀i ∈ J (4.8) xj ≥ xi + wi − (1 − lij) · W max ∀i �= j ∈ J (4.9) yj ≥ yi + hi − (1 − bij) · Hmax ∀i �= j ∈ J (4.10) lij + bij + lji + bji = 1 ∀i < j ∈ J (4.11) Wr ≥ |(xi + wi 2 ) − (xj + wj 2 )| ∀r ⊆ R, ∀i, j ∈ r (4.12) Hr ≥ |(yi + hi 2 ) − (yj + hj 2 )| ∀r ⊆ R, ∀i, j ∈ r (4.13) lij, bij ∈ {0, 1} ∀i �= j ∈ J (4.14) No modelo (4.5)-(4.14), a função objetivo (4.5) minimiza o comprimento de fio utilizado nas interconexões dos itens, de todas redes, adotando a simplificação de distância entre dois módulos que, neste caso, é sempre calculada entre os centros geométricos dos módulos. As restri- ções (4.6) e (4.7) garantem que as dimensões dos módulos flexíveis estejam dentro do intervalo permitido. Com dimensões variáveis, é preciso que a largura (wi) de cada item i seja limitada inferior e superiormente, respeitando os parâmetros pré-estabelecidos. Analogamente, a altura (hi) possui valor mínimo e máximo. As restrições (4.8) estabelecem que cada módulo retangular deve respeitar uma proporção altura-largura (ai = hi/wi) para manter seu funcionamento e eficiência ao ser flexibilizado. As restrições (4.9) e (4.10), referentes às relações de posicionamento entre os itens, garantem que não haja sobreposição entre dois módulos e que ambos estejam contidos no retângulo envolvente do layout, isto é, estejam inteiramente alocados na região do chip. No caso Capítulo 4. Modelo Matemático 25 de lij = 1, temos que xj ≥ xi + wi, portanto, a abcissa de j deve assumir um valor igual ou superior a abcissa do ponto inferior esquerdo do item i, sem que haja sobreposição horizontal dos itens. Caso lij = 0, xj ≥ xi + wi − Wmax garante que o item j está horizontalmente contido no retângulo envolvente. De modo análogo, as restrições (4.10) tratam as posições dos itens verticalmente. As restrições (4.11) asseguram que uma, e apenas uma, das variáveis binárias de po- sicionamento referentes a i e j assuma valor não nulo. Desta forma, é possível que o item i esteja à esquerda e abaixo de j simultaneamente, porém este caso é indicado somente através da transitividade entre ambos os itens e os demais. Por exemplo, dados os itens i, j e k, é possível inferir que, se i está abaixo de k (bik = 1) e k está abaixo de j (bkj = 1), certamente i também está abaixo de j, ainda que bij = 0 e lij = 1. Assim, i e j aparecem relacionados verticalmente por transitividade e horizontalmente através de uma das variáveis binárias de posicionamento que assume valor não nulo. As restrições (4.12) e (4.13) são referentes às dimensões de rede, calculadas, rede a rede, para todos os itens contidos nela. A largura da rede assume o valor da maior diferença das abcissas dos pontos centrais dos módulos pertencentes à ela. Da mesma forma, a altura da rede é obtida em função das ordenadas dos pontos centrais de cada par de itens. Cada um desses grupos de restrições obtém as dimensões do semi-perímetro do retângulo que contém os pontos centrais dos módulos na rede. As restrições (4.14) definem lij e bij o domínio das variáveis de decisão. O modelo proposto foi baseado em Chen e Chang (2009). As formulações diferem na função objetivo, além das restrições de dimensão de rede (4.12) e (4.13) que foram acrescentadas para considerar a minimização do comprimento de fios ao invés de otimizar a área do retângulo envolvente. Adequações também foram feitas nas restrições (4.9), (4.10) e (4.11) de posiciona- mento entre os módulos para melhor atender a finalidade do problema considerado neste trabalho, dado que as variáveis binárias assumem características distintas na formulação proposta. 26 5 Abordagens heurísticas O problema de empacotamento de retângulos flexíveis pode ser facilmente representado através de modelos matemáticos, porém é difícil de ser solucionado devido ao grande número de variáveis envolvidas. Obter soluções exatas implica em alta complexidade computacional, principalmente para problemas com grandes dimensões. Assim, métodos heurísticos são frequen- temente utilizados para explorar o espaço de soluções com um baixo esforço computacional e garantia de boas soluções (SINGH; BAGHEL; AGARWAL, 2016; WU et al., 2016). Neste capítulo, uma abordagem heurística de janela deslizante (SW, Sliding Window) e uma mateurística BRKGA são propostas para resolver de maneira eficiente o problema de empacotamento de retângulos flexíveis no contexto do floorplanning de circuitos VLSI. Usada em ambos os métodos heurísticos, a estratégia de janela deslizante consiste em pegar, sob condições específicas, um subconjunto de uma lista dada. A cada iteração um elemento é substituído no subconjunto, criando um efeito de deslizamento da janela sobre o conjunto. 5.1 Heurística SW Combinando programação matemática e um método heurístico para reduzir a dificuldade de resolução do problema, a heurística proposta é um procedimento iterativo que conta com uma estratégia de inicialização, estabelecida utilizando critérios de ordenação para os itens que se deseja alocar. Desta forma, é possível definir quais módulos serão priorizados no planejamento do circuito e resolver um problema parcial, com apenas alguns dos módulos a serem alocados, ao invés de buscar uma solução exata para o problema. A cada iteração, um novo item não-alocado é selecionado para ser inserido no layout e um sub-modelo (4.5)-(4.14) é criado com tamanho fixo e reduzido em relação ao modelo do problema original. Para formalizar a heurística SW, novos parâmetros foram adotados: • sw: tamanho da janela deslizante, sw ∈ {1, · · · , n − 1}; • coni: conectividade do item i, coni ∈ {0, · · · , m}; • it: índice de iteração, it ∈ {0, · · · , n − sw}. Capítulo 5. Abordagens heurísticas 27 O tamanho da janela deslizante sw indica a quantidade de itens com posições livres, e suas variáveis de decisão correspondentes, considerados na resolução do sub-modelo, isto é, o número de módulos que podem ser posicionados, reposicionados ou ajustados em suas dimensões a cada iteração. O parâmetro sw pode assumir valor entre 1 e n − 1, sendo n a quantidade total de itens do problema. A conectividade coni de um item i indica o número de redes r que o contém, calculado no momento de inicialização do algoritmo e limitado no intervalo de 0 a m, sendo m o número total de redes do problema. Os valores sw e coni são constantes durante todo o processamento da heurística. Na primeira etapa da heurística SW, é utilizada uma estratégia de inicialização que consiste em ordenar os módulos flexíveis seguindo um critério de ordenação, dentre os critérios: • área de forma não-decrescente; • área de forma não-crescente; • conectividade de forma não-decrescente; • conectividade de forma não-crescente. Na etapa seguinte, um sub-modelo é criado para resolver a alocação de parte dos itens do problema original na primeira iteração (it = 0). Este sub-modelo é criado utilizando (4.5)-(4.14). Apenas os sw primeiros itens da lista ordenada são considerados na resolução, diminuindo significativamente a dificuldade computacional do problema. O sub-modelo é resolvido e, a partir da sub-solução obtida, fixam-se as posições relativas do primeiro item da alocação feita, isto é, as variáveis l e b associadas ao item passam a ser parâmetros no sub-modelo. Após acrescentar o próximo item não-alocado da lista ordenada ao sub-modelo, inicia-se uma nova iteração (it = 1). O sub-modelo é resolvido e, a partir da sub-solução obtida, fixam-se as posições relativas l e b do segundo item da lista ordenada. MÓDULO FIXO i i j POSIÇÃO FIXADA: i está à esquerda de j (lij = 1) CASO 1: k à direita de j i j k i fixo à esquerda de j módulo k é inserido: (lij = 1) (ljk = 1) ou CASO 2: k à esquerda de j i k j i fixo à esquerda de j módulo k é inserido: (lij = 1) (lkj = 1) Figura 9 – Representação horizontal de posicionamento relativo fixado do item i (módulo fixo) com inserção do item k (módulo livre) à direita ou à esquerda de j (módulo livre). Capítulo 5. Abordagens heurísticas 28 Para facilitar a notação, assume-se que um módulo livre é um item que tem suas posições relativas livres (lij, lji, bij e bji), assim, pode ser posicionado de forma independente no layout. Por outro lado, chama-se de módulo fixo o item que tem suas posições relativas fixadas, isto é, caso o módulo fixo i esteja à esquerda de um módulo j, é necessário que essa relação seja mantida em todas as iterações futuras. Na fixação das posições relativas associadas ao item i com lij = 1, por exemplo, ainda que um novo item k seja acrescentado ao layout à direita de i, a relação entre i e j deve ser mantida. Observe o esquema na Figura 9 com a representação da relação horizontal entre os módulos i, j e k, com lij = 1 fixo e variação entre lkj = 1 e ljk = 1. O sub-modelo é atualizado, acrescentando o terceiro item não-alocado, e resolvido. A partir da sub-solução obtida, fixam-se as posições relativas referentes ao item it + 1, sendo it o índice da iteração presente, e atualiza-se o sub-modelo inserindo o próximo item não-alocado da lista. O sub-modelo é resolvido novamente. Estes passos são realizados de modo iterativo até que a quantidade de itens do sub-modelo seja igual à quantidade de itens do modelo inicial. Adota-se como solução do modelo a solução obtida para o sub-modelo na última iteração realizada. A Figura 10 apresenta brevemente as etapas da abordagem heurística SW. Modelo com n módulos livres ETAPA 1 Ordenação: 1, 2, 3, 4, · · · , n ETAPA 2 Sub-modelo com sw módulos livres A cada iteração it: um módulo alocado é fixado e um não-alocado é acrescentado. Figura 10 – Etapas da abordagem heurística SW. Nas Figuras 11 e 12, a abordagem proposta é ilustrada. Na Figura 11, o comportamento do método a cada iteração (it = 0, · · · , 4) é representado visualmente. No exemplo, um conjunto de módulos retangulares, ordenados de 1 a 8, e tamanho da janela deslizante sw igual a 4 são considerados. A cada iteração, o primeiro módulo livre listado tem suas posições relativas fixadas (itens cinzas) e a janela de módulos livres é deslizada para a direita, incluindo o próximo módulo ao sub-problema. Se (sw + it) = 8, todos os itens já foram posicionados e então uma solução final é obtida. O layout resultante de cada iteração é apresentado na Figura 12. Vale observar, na representação visual de cada iteração na Figura 12, que o retângulo envolvente é ajustado de acordo com a necessidade da alocação feita, assumindo sempre a menor dimensão necessária para conter todos os itens no chip. Ainda, cada módulo livre pode ser incluído entre dois módulos fixos, como visto na Iteração 4, em que o item 8 é posicionado entre os itens 1 e 3. A Figura 13 apresenta a estrutura geral da abordagem iterativa desenvolvida. As iterações acontecem enquanto existem módulos (itens) não alocados. Caso (sw + it) = n, todos os n itens foram considerados e então uma solução final para o modelo original (4.5)-(4.14) é encontrada. Capítulo 5. Abordagens heurísticas 29 Janela Deslizante 1 2 3 4 5 6 7 8 ITERAÇÃO 0 Janela Deslizante 1 2 3 4 5 6 7 8 ITERAÇÃO 1 Janela Deslizante 1 2 3 4 5 6 7 8 ITERAÇÃO 2 Janela Deslizante 1 2 3 4 5 6 7 8 ITERAÇÃO 3 Janela Deslizante 1 2 3 4 5 6 7 8 ITERAÇÃO 4 Figura 11 – Exemplo de janela deslizante a cada iteração (sw = 4). Capítulo 5. Abordagens heurísticas 30 ITERAÇÃO 0 Itens livres: {1, 2, 3, 4} Itens fixados: {} 1 2 3 4 ITERAÇÃO 1 Itens livres: {2, 3, 4, 5} Itens fixados: {1} 1 2 3 45 ITERAÇÃO 2 Itens livres: {3, 4, 5, 6} Itens fixados: {1, 2} 1 2 3 4 5 6 ITERAÇÃO 3 Itens livres: {4, 5, 6, 7} Itens fixados: {1, 2, 3} 1 2 3 4 5 6 7 ITERAÇÃO 4 Itens livres: {5, 6, 7, 8} Itens fixados: {1, 2, 3, 4} 1 2 3 4 5 6 7 8 LAYOUT FINAL Todos os itens alocados J = {1, 2, 3, 4} ∪ {5, 6, 7, 8} 1 2 3 4 5 6 7 8 Figura 12 – Exemplo de layout a cada iteração (sw = 4). Capítulo 5. Abordagens heurísticas 31 Criar sub-modelo (4.5-4.14) Inicialização: ordenação dos módulos Resolver o sub-modelo com sw módulos livres Fixar as posições relativas l e b do módulo (it + 1) n módulos alocados? Acrescentar módulo (sw + it) Solução final encontrada Não (it++)Sim Figura 13 – Estrutura da abordagem heurística SW. 5.2 Mateurística BRKGA-SW Nesta seção é descrito o algoritmo genético de chave-aleatória tendenciosa (BRKGA) adaptado para o problema de empacotamento de módulos flexíveis em circuitos VLSI. Uma mateurística é um algoritmo de otimização que surge pela integração de meta-heurísticas e programação matemática, assim uma mateurística BRKGA-SW é apresentada nesta Seção. A estrutura geral da mateurística foi revisada no Capítulo 3. Os valores adotados para cada parâmetro são especificados no Capítulo 6. Em um BRKGA, os indivíduos consistem em um vetor de números reais aleatórios no intervalo de [0, 1), sendo estes números também chamados de chaves. Um decodificador tem como entrada uma população de p indivíduos e retorna uma solução viável para o problema, de modo que seja possível avaliar a função objetivo desta solução. Para descrever um BRKGA para um problema de otimização combinatória específico, basta mostrar como as soluções são codificadas como vetores de chaves aleatórias e como esses vetores são decodificados para soluções viáveis do problema de otimização. São parâmetros essenciais para a compressão do algoritmo neste trabalho: • p: tamanho da população; • pe: tamanho da população considerada elite; Capítulo 5. Abordagens heurísticas 32 • p − pe: tamanho da população não-elite; • pm: tamanho da população de indivíduos mutantes; • pb: probabilidade de herança de um pai elite no cruzamento; • Critério de parada: tempo computacional ou taxa mínima de melhoria de uma população para outra. No BRKGA adaptado para o problema de empacotamento de módulos flexíveis em circuitos VLSI, um indivíduo é uma solução do floorplanning representada por um vetor de chaves aleatórias que possuem uma relação biunívoca com os módulos a serem posicionados e suas variáveis de posicionamento. Uma população é um conjunto de indivíduos e cada indivíduo tem sua aptidão determinada pela função objetivo (4.5) do modelo proposto na Seção 4. Os indivíduos com valores de função objetivo menores são mais aptos do que aqueles com valores maiores, uma vez que o problema abordado é de minimização. Os indivíduos de maior aptidão, isto é, as soluções com os menores valores de comprimento de fio utilizado nas interconexões dos módulos, compõem o grupo de elite da população. GERAÇÃO k 20% 80%Po pu la çã o INDIVÍDUOS ELITE INDIVÍDUOS NÃO-ELITE Cruzamento combinação de pai elite e não-elite Elitismo indivíduos copiados sem alterações Mutação indivíduos aleatórios GERANDO k + 1 20% 70% 10% ELITE ANTERIOR INDIVÍDUOS FILHOS MUTANTES GERAÇÃO k + 1 M ai sa pt o A pt id ão ,o rd en aç ão e pa rti ci on am en to INDIVÍDUOS ELITE INDIVÍDUOS NÃO-ELITE Figura 14 – Esquema geral de processo evolutivo do BRKGA. O esquema na Figura 14 apresenta parte do processo do BRKGA. O algoritmo começa com a geração inicial k, composta por uma população de p vetores aleatórios de tamanho n ou 2n, sendo n o número de módulos flexíveis considerados no floorplanning. A população é particionada em elite e não-elite de acordo com a aptidão dos indivíduos. A cada iteração uma nova geração é formada com uma nova população, composta pelos pe indivíduos elite da geração anterior, pm indivíduos mutantes gerados através da operação de mutação e p − pe − pm indivíduos descendentes gerados através da combinação de duas soluções, um pai elite e um pai não-elite. Na iteração seguinte, a população é particionada novamente e todo o processo se repete até que o critério de parada seja atingindo. O algoritmo retorna o indivíduo mais apto Capítulo 5. Abordagens heurísticas 33 encontrado durante toda a execução, isto é, a solução que assume o menor comprimento de fio na busca realizada. Além da decodificação feita para adaptar o BRKGA ao problema abordado neste trabalho, uma combinação entre as formulações foi proposta. O BRKGA-SW agrega a janela deslizante ao algoritmo genético na etapa evolutiva de uma geração para a geração seguinte. Ao calcular a aptidão de cada indivíduo da população, o modelo (4.5)-(4.14) é executado através da heurística SW (Seção 5.1) que estrutura a resolução do floorplanning utilizando janela deslizante para reduzir a dificuldade e tempo do algoritmo a cada iteração inicialização. Como inicialização, adota-se o padrão do BRKGA de ordenação não-decrescente do vetor real gerado aleatoriamente. Os resultados obtidos pela heurística SW e pela mateurística BRKGA-SW, para diferentes instâncias testadas, são apresentados no Capítulo 6. 34 6 Experimentos computacionais Para avaliar o desempenho dos procedimentos propostos, testes computacionais foram realizados na linguagem de programação C++ com o solver IBM CPLEX Optimization Studio versão 22.1 e executados em um computador com processador Intel Core i7-2600 com 16GB de memória RAM. Foram utilizadas cinco instâncias do conjunto de referência arquivado no Microelectronics Center of North Carolina (MCNC)1 com origem no projeto de circuitos VLSI, no qual todos os itens têm forma retangular flexível e o número de itens a serem posicionados não ultrapassa os 50. Cada instância contém um número de redes, sendo cada rede um conjunto de módulos (itens) interconectados com composição pré-definida. São elas: • APTE: 9 itens flexíveis e 97 redes; • XEROX: 10 itens flexíveis e 203 redes; • HP: 11 itens flexíveis e 83 redes; • AMI33: 33 itens flexíveis e 123 redes; • AMI49: 49 itens flexíveis e 408 redes. Neste capítulo, são apresentadas as configurações específicas adotadas em cada etapa dos testes e os resultados obtidos na execução do modelo matemático proposto, da abordagem heurística SW e da mateurística BRKGA-SW. Por fim, a solução e tempo computacional de cada um dos métodos é resumida e comparadas entre eles. 6.1 Modelo Matemático Com o objetivo de minimizar as distâncias do comprimento de fio utilizado para inter- conectar os módulos no chip, o modelo matemático (4.5)-(4.14) foi implementado com tempo de execução limitado à 15 horas, devido à sua alta complexidade. Sem esta limitação, seria necessário um período de tempo impraticável para atingir uma solução exata, inviabilizando o uso do modelo de forma independente. 1 http://vlsicad.eecs.umich.edu/BK/MCNCbench/SOFT/ Capítulo 6. Experimentos computacionais 35 Os resultados obtidos são apresentados na Tabela 3, juntamente com a área total do layout resultante da alocação, limitante inferior e GAP para cada instância considerada. Instância Valor da solução Área LB GAP AMI33 27478 842625 11124,7 59,52% AMI49 442221 33406576 202890,0 54,12% APTE 157715 28901632 156138,0 1,00% HP 36407 2159136 30888,5 15,16% XEROX 357932 14081873 345928,0 3,35% Tabela 3 – Soluções obtidas pelo modelo matemático com tempo limite de 15 horas. O modelo matemático, proposto no Capítulo 4, tem como resultado as posições possivel- mente ideais para o conjunto de módulos alocados, suas dimensões, o comprimento de fio HPWL utilizado para interconectá-los de acordo com as redes e o tempo computacional do procedimento. Através dos resultados obtidos, uma solução geométrica pode ser ilustrada para cada alocação obtida. Na Figura 15, por exemplo, é possível visualizar as alocações geradas para as instâncias APTE, AMI49, AMI33 e HP, correspondentes aos dados supracitados na Tabela 3. Figura 15 – Alocações (layouts) obtidas para as instâncias APTE, AMI49, AMI33 e HP. Capítulo 6. Experimentos computacionais 36 6.2 Heurística SW Nesta seção, os resultados obtidos pela heurística SW são apresentados. As instâncias foram testadas para diferentes valores do parâmetro sw, que corresponde ao tamanho da janela deslizante no modelo e indica a quantidade de variáveis livres a serem consideradas por iteração, variando nos valores sw = [1, 2, 3, 4, 5], sendo 1 o menor valor possível para sw, e os demais valores escolhidos arbitrariamente. Ainda, quatro critérios de ordenação foram considerados na inicialização dos módulos, também chamados de itens: (a) área de modo não-decrescente, (b) área de modo não-crescente, (c) conectividade não-decrescente e (d) conectividade não-crescente. Foi estipulado o limite de tempo de 15 minutos para a obtenção de cada solução no sub-modelo, isto é, cada iteração. Nas Tabelas 4 a 13 são apresentados os valores de comprimento de fio e tempo computa- cional, em segundos, obtidos pela heurística para cada instância, combinando diferentes critérios de ordenação inicial e tamanhos de janela. Destaca-se o melhor resultado obtido para a instância e o tempo computacional correspondente. AMI33 sw = 1 sw = 2 sw = 3 sw = 4 sw = 5 Menor área (a) 30184 27696 27937 25865 25445 Maior área (b) 29694 26334 27346 24973 25347 Menor conectividade (c) 30468 28007 29488 25326 26404 Maior conectividade (d) 27048 25319 26354 25354 24658 Tabela 4 – Comprimento de fio obtido por ordenação para a instância AMI33. AMI33 sw = 1 sw = 2 sw = 3 sw = 4 sw = 5 Menor área (a) 7682 2524 7218 1652 19742 Maior área (b) 2739 1079 2421 6330 15733 Menor conectividade (c) 2834 1968 1419 8537 15629 Maior conectividade (d) 2297 1898 5421 7741 10532 Tabela 5 – Tempo computacional obtido por ordenação para a instância AMI33. Os valores obtidos pelo modelo matemático (4.5)-(4.14), com tempo de execução de 15 horas, foram rapidamente superados pelos resultados encontrados pela heurística SW. Para a instância AMI33, a função objetivo do modelo exato obteve como resultado 27478 em 15 horas, enquanto a heurística SW obteve o resultado 24658, em um tempo computacional de aproximadamente 3 horas. Esses valores indicam que através da abordagem herística proposta é possível atingir boas soluções em um tempo muito menor. Para a instância AMI49 (Tabela 6), o melhor resultado obtido considerou como o critério de inicialização a conectividade de itens de modo não-crescente, característica que se manteve para as demais instâncias: AMI33 e APTE. Nas Tabelas 10 e 13, observa-se que a melhor solução encontrada para a instância HP foi obtida ao adotar o critério de ordenação por área de modo não-crescente, considerando uma janela deslizante de tamanho 5. Capítulo 6. Experimentos computacionais 37 AMI49 sw = 1 sw = 2 sw = 3 sw = 4 sw = 5 Menor área (a) 472657 462784 444773 442852 436985 Maior área (b) 626015 620124 645093 521928 498833 Menor conectividade (c) 550140 597468 528251 518566 510881 Maior conectividade (d) 469879 441883 440818 413738 423920 Tabela 6 – Comprimento de fio por ordenação para a instância AMI49. AMI49 sw = 1 sw = 2 sw = 3 sw = 4 sw = 5 Menor área (a) 8638 13475 8282 20022 25196 Maior área (b) 17929 4957 7528 19489 48636 Menor conectividade (c) 42394 11350 2402 4931 10717 Maior conectividade (d) 32351 8307 3458 7541 20483 Tabela 7 – Tempo computacional obtido por ordenação para a instância AMI49. APTE sw = 1 sw = 2 sw = 3 sw = 4 sw = 5 Menor área (a) 159344 173529 172347 165792 158001 Maior área (b) 162859 163930 159134 159134 157718 Menor conectividade (c) 183876 169328 170968 159141 159252 Maior conectividade (d) 162860 164610 157739 159245 157718 Tabela 8 – Comprimento de fio por ordenação para a instância APTE. APTE sw = 1 sw = 2 sw = 3 sw = 4 sw = 5 Menor área (a) 819 319 221 127 156 Maior área (b) 110 246 713 315 115 Menor conectividade (c) 600 261 638 211 100 Maior conectividade (d) 598 262 399 277 923 Tabela 9 – Tempo computacional por ordenação para a instância APTE. HP sw = 1 sw = 2 sw = 3 sw = 4 sw = 5 Menor área (a) 41010 41259 38553 37588 37083 Maior área (b) 42034 41194 36681 36681 36659 Menor conectividade (c) 43383 40018 39228 39017 37692 Maior conectividade (d) 38847 37252 36832 36832 36832 Tabela 10 – Comprimento de fio por ordenação para a instância HP. HP sw = 1 sw = 2 sw = 3 sw = 4 sw = 5 Menor área (a) 1303 3595 1376 392 767 Maior área (b) 1317 2518 631 2190 1904 Menor conectividade (c) 1414 4083 1205 1491 3235 Maior conectividade (d) 1397 3544 1713 795 986 Tabela 11 – Tempo computacional por ordenação para a instância HP. Capítulo 6. Experimentos computacionais 38 XEROX sw = 1 sw = 2 sw = 3 sw = 4 sw = 5 Menor área (a) 374661 386350 377546 375599 360550 Maior área (b) 367020 359104 357935 357932 357924 Menor conectividade (c) 385671 386482 380994 367024 372432 Maior conectividade (d) 412978 373382 375104 371501 362655 Tabela 12 – Comprimento de fio por ordenação para a instância XEROX. XEROX sw = 1 sw = 2 sw = 3 sw = 4 sw = 5 Menor área (a) 130 438 234 182 605 Maior área (b) 140 373 91 329 224 Menor conectividade (c) 712 353 127 86 1040 Maior conectividade (d) 706 492 115 106 423 Tabela 13 – Tempo computacional por ordenação para a instância XEROX. Ao definir um critério de ordenação inicial é possível estabelecer quais itens serão priorizados na alocação feita e, com isso, melhorar o processo iterativo realizado. De acordo com os dados supracitados nas Tabelas 4 a 13, para todas as instâncias testadas, os melhores resultados foram obtidos ao utilizar ordenações não-crescentes como estratégia inicial e, na maioria dos casos, ordenações baseadas nas características da descrição detalhada da conectividade do VLSI. As soluções obtidas indicam grande influência do critério de ordenação no resultado final do problema. Com tendência a obter o melhor resultado, ordenar os itens pela conectividade de modo não-crescente garante que o processo de alocação seja iniciado fixando primeiramente os itens que possuem maior conectividade e flexibilizando o posicionamento dos itens que aparecem em um número menor de conexões. Nas Figuras 16 e 17 é possível visualizar a solução geométrica (layouts) de algumas alocações obtidas para a instância AMI33 com diferentes tamanhos de janela e ordenações por conectividade. Figura 16 – Alocações obtidas para AMI33: itens ordenados por menor conectividade (sw = 3 e sw = 5, respectivamente). Com as soluções geométricas dadas, nota-se que os layouts possuem espaço não utilizado (espaço morto) no interior do retângulo envolvente e os módulos flexíveis foram ajustados Capítulo 6. Experimentos computacionais 39 predominantemente em formato quadrangular, em que wi = hi e si = 1. Em nenhum dos testes considerados para as cinco instâncias, o número de itens flexionados com si �= 1 atinge valor maior que 30%. Este resultado indica que a característica de flexibilidade dos itens foi pouco explorada no espaço de soluções. A tendência é que alocações com itens flexíveis sejam mais compactas, isto é, tenham espaço morto reduzido, além de menores valores de comprimento de fio utilizado nas interconexões, objetivo principal do problema. Figura 17 – Alocações obtidas para AMI33: itens ordenados por maior conectividade (sw = 1, sw = 3 e sw = 5, respectivamente). Na Figura 18 a comparação de soluções entre as instâncias para cada critério de ordenação é ilustrada graficamente. No eixo vertical, é expresso o percentual que indica a distância da solução em relação à melhor solução obtida para aquela instância. No eixo horizontal, cada instância é indicada pelo seu nome seguindo, respectivamente, o tamanho de janela sw = [1, 2, 3, 4, 5]. O critério que prioriza itens com maior conectividade fica em destaque, com valores inferiores aos demais critérios nas instâncias AMI33, AMI49, APTE e HP. Figura 18 – GAP de soluções entre instâncias por critério de ordenação. Capítulo 6. Experimentos computacionais 40 Figura 19 – Comprimento de fio por ordenação para a instância AMI33. Figura 20 – Solução para AMI49. Figura 21 – Solução para HP. Figura 22 – Solução para APTE. Figura 23 – Solução para XEROX. Capítulo 6. Experimentos computacionais 41 Ainda, vale observar a relação entre o tempo computacional e o tamanho de janela adotado. Como proposto na abordagem, ao criar sub-modelos com uma quantidade limitada de variáveis que podem ser posicionadas livremente, a dificuldade de resolução é reduzida e o tempo de execução diminui consid