Finding placement-relevant clustersWith fast modularity-based clustering

• Ano de defesa: 2020
• Autor(a) principal: Fogaça, Mateus Paiva
• Orientador(a): Reis, Ricardo Augusto da Luz
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Palavras-chave em Português: Microeletrônica; Planta baixa : Circuitos integrados; Particionamento; Arquitetura de computadores
• Palavras-chave em Inglês: EDA; Physical design; Placement; Modularity-based clustering
• Link de acesso: http://hdl.handle.net/10183/215350

Em nodos tecnológicos avançados, a implementação de circuitos integrados deve lidar com o aumento da complexidade dos projetos e também com cronogramas mais restritos. Portanto, cria-se a necessidade de novas abordagens de decomposição que ajudem a reduzir a complexidade do problema e novas metodologias preditivas para evitar gargalos e iterações no fluxo de implementação. Em metodologias de projeto modernas, seria útil predizer o posicionamento do circuito em nível de portas lógicas. Essa habilidade tornaria possível avaliar com maior precisão a planta baixa de um circuito em termos de desempenho e congestionamento ainda nas etapas de projeto da planta baixa e planejamento da descrição do circuito em nível de transferências de registradores de sistemas em chip. Este trabalho apresenta um novo critério de avaliação do problema clássico de agrupamento do circuito em nível de portas lógicas: avaliar se as portas lógicas de um grupo “permanecem próximas” ao longo do fluxo de implementação. Métodos para a avaliação desse critério são propostos. Além disso, o trabalho utiliza uma classe de técnicas de agrupamento chamada de agrupamento baseado em modularidade para identificar “grupos naturais” em um grafo, dispensando a necessidade de ajustes de parâmetros do algoritmo ou restrições de balanceamento de tamanho dos grupos, tradicionalmente necessários em técnicas de particionamento utilizadas por ferramentas de CAD (do inglês, computer-aided design). Os experimentos realizados mostram que o mapeamento do circuito de hipergrafo para um grafo afeta significativamente a qualidade dos resultados. Também demonstra-se empiricamente que grupos obtidos com técnicas de agrupamento baseadas em modularidade possuem uma maior correlação com o posicionamento quando comparadas com técnicas de particionamento tradicionalmente empregadas por ferramentas de CAD (A técnica utilizada neste trabalho também é 2 mais rápida que a ferramenta de particionamento tradicional hMetis nos maiores casos de teste). Por fim, é proposto um fluxo no qual se realiza posicionamento de grupos (“posicionamento de bolhas”). O “posicionamento de bolhas” é utilizado com ponto de partida (“semente”) para uma ferramenta de posicionamento global. A ferramenta de posicionamento global utiliza a semente para realizar o posicionamento das portas lógicas do circuito. O fluxo proposto permite reduzir em 20% o tempo do posicionamento do circuito e a diferença nos resultados é menor que 3% em termos de comprimento de fios.