Redução de congestionamento em roteamento global de circuitos VLSI

Abstract

O Roteamento Global é responsável pelo planejamento da distribuição dos meios de interconexão dentro da área do circuito. Dentro da fase do projeto de circuitos conhecida como Síntese Física, essa fase situa-se após a etapa de posicionamento, que define uma posição exata para cada célula do circuito, e antes da etapa de roteamento detalhado que irá definir uma posição para cada meio de interconexão. Os roteadores globais utilizam uma versão abstrata e simplificada do circuito, que agrega uma região e toda a capacidade de fios que esta região comporta, trabalhando com o planejamento dessas capacidades em relação a demanda de interconexão entre as células do circuito. Este trabalho, apresenta um conjunto de técnicas para delimitação e tratamento de áreas que possuem alta demanda por meios de interconexão em circuitos VLSI. As técnicas são aplicadas em duas fases do fluxo de rotamento global: a primeira é executada na fase de pré-roteamento, onde são identificadas as regiões que possuem alta demanda por interconexão, isto é, são destino ou origem de um número elevado fios em relação a sua capacidade de alocar meios de interconexão; a segunda etapa ocorre dentro da fase de roteamento iterativo, identificando e protegendo aquelas que regiões que possuem os níveis mais elevados de congestionamento. Para avaliar os impactos da aplicação das técnicas propostas, foi feita a implementação em um fluxo de roteamento global existente. A avaliação foi partir da extração de quatro métricas de roteamento global comumente utilizadas na literatura de síntese física, para análise de roteamento global: comprimento dos fios, valor total de congestionamento, máximo congestionamento de aresta e tempo de execução. A partir da execução de experimentos utilizando as técnicas, foi possível verificar ganhos de até 11% em redução do congestionamento total no circuito, em benchmarks para os quais ainda não se tem soluções válidas na literatura. Os tempos de execução obtiveram um redução de até 35%, quando comparados com a implementação usada como referência para aplicação das técnicas, o roteador GR-WL. Um dos efeitos colaterais da aplicação de técnicas de calibração de custos é o aumento do comprimento médio dos fios. Os resultados dos experimentos mostram que as técnicas propostas conseguem reduzir este efeito colateral para, no máximo, 1.39% de acordo com os benchmarks executados.

Global routing phase is responsible for the interconnect planning and distribution across the circuit area. During the integrated circuit project flow, the global routing is contained in the Physical Synthesis, after the placement, that is when the position of all circuit cells are defined, and before the detailed routing, when the position of all interonnection wires is realized. A simplified and abstrate version of the circuit routing area is used by the global router, that will agregate in a single vertex, an specific region of the circuit, that represents a bunch of interconnection with their total capacity. This work presents a set of techniques to delimit and threat areas that have high interconnection demand in VLSI circuits. These techniques are applied in two steps of the global routing flow: the first is executed during the initial routing, where the high interconnection demanding regions are identified. the second step is executed during the iterative routing, where the top offender regions are identified and heva their costs pre-allocated. In order to evaluate the impact of the proposed techniques, they are implemented in an existing global routing flow, and four metrics are collected: total wirelenght, execution time, total overflow and maximum overflow. Tha last two metrics will be different from zero just for the circuits that not have a valid solution. After the execution of the experiments it was possible to verify a reduction up to 11% in wirelenght, in some benchmarks that the literature do no have a valid solution. Furthermore, it was possible to verify a reduction up to 35% in the execution time, when compared to the reference implementation. Once we are including constraints in form of cost pre-allocation, it is possible to verify an wirelength increase in some cases. In this work, it was possible to observe a small presence of these side-effects, up to 1.39%, according to the executed benchmarks.