Finding placement-relevant clustersWith fast modularity-based clustering

Abstract

In advanced technology nodes, IC implementation faces an increasing design complexity as well as ever-more demanding design schedule requirements. This raises the need for new decomposition approaches that can help reduce problem complexity, in conjunction with new predictive methodologies that can help to avoid bottlenecks and loops in the physical implementation flow. Notably, with modern design methodologies it would be very valuable to better predict the final placement of the gate-level netlist: this would enable more accurate early assessment of performance, congestion and floorplan viability in the SOC floorplanning/RTL planning stages of design. In this work, we study a new criterion for the classic challenge of VLSI netlist clustering: how well netlist clusters “stay together” through final implementation. We propose the use of several evaluators of this criterion. We also explore the use of modularity-driven clustering to identify natural clusters in a given graph without the tuning of parameters and size balance constraints typically required by VLSI CAD partitioning methods. We find that the netlist hypergraph-to-graph mapping can significantly affect quality of results. Further, we empirically demonstrate that modularity-based clustering achieves better correlation to actual netlist placements than traditional VLSI CAD methods (our method is also 2 faster than use of hMetis for our largest testcases). Finally, we propose a flow with fast “blob placement” of clusters. The “blob placement” is used as a seed for a global placement tool that performs placement of the flat netlist. With this flow we achieve 20% speedup on the placement of a netlist with 4.9M instances with less than 3% difference in routed wirelength.

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.