Abstract:
Roteamento é a etapa do fluxo de síntese física de circuito integrados responsável pela geração das conexões do circuito após as células estarem posicionadas. A evolução na tecnologia dos transistores e, consequente evolução dos circuitos, trouxe consigo novos desafios para todas as etapas da síntese física. Rotear um circuito VLSI (Very Large Scale Integration) é uma tarefa de difícil resolução, tanto por possuir um grande volume de dados a ser processado, quanto por se tratar de um problema NP-completo, significando que não existe uma solução ótima que possa ser processada em tempo polinomial. Para resolver o problema, é necessária a utilização de algoritmos gulosos, heurísticas, aprendizado de máquina ou técnicas mais específicas para trabalhar com as estruturas de dados de forma mais intuitiva e obter melhores resultados. Apesar dos roteadores estado-da-arte gerarem resultados satisfatórios, ainda é possível realizar melhorias nestes. Este trabalho explora técnicas de otimização de programação aplicadas a um roteador estado-da-arte de código-fonte aberto. A partir das análises realizadas no roteador NTHU Route, apresentamos melhorias envolvendo parâmetros utilizados nos algoritmos, e aplicação de paralelismo em alguns dos estágios do roteador, buscando uma melhoria no desempenho e na qualidade dos resultados. Com a aplicação das estratégias envolvendo alteração nos parâmetros, mais especificamente com a aplicação de um limiar para aceitação de congestionamento na fase principal do roteador, foi possível diminuir o tempo de execução de todos benchmarks utilizados em média em 9%, sendo no melhor caso observada uma redução de aproximadamente 20% sem grandes impactos no comprimento total de fio. Com a aplicação de paralelismo no estágio de refinamento, foi possível melhorar o tempo tomado nesta fase em até 20%, com uma melhoria média de 10%. Com experimentos aplicando paralelismo na fase principal em conjunto com o aumento da caixa de expansão de busca para ligar dois pinos, o tempo de execução dobrou, devido ao comportamento de busca para achar as soluções nesta fase. Ao juntar as duas modificações, aplicando um limiar para aceitação de congestionamento na fase principal e paralelismo em blocos menores nas duas fases sem o aumento da caixa de expansão de busca, foi possível obter melhorias no tempo de execução de até 20%, sem impacto considerável no comprimento total de fio. Explorar estas técnicas de otimização nos algoritmos de roteamento mostrou bons resultados, que podem ser aplicados a diferentes ferramentas de roteamento e de outras etapas da síntese física.
Routing is the stage of integrated circuits physical synthesis flow responsible for generating the connections of the circuit after the cell placement. The evolution in transistors technology along with circuits growth, brought new challenges for all physical synthesis stages. Routing a VLSI (Very Large Scale Integration) circuit is a hard task to solve, due to the great amount of data to be processed, and the fact that it is a NP-complete problem, meaning that there is not an optimum solution that can be processed in polynomial time. To solve this problem, it is necessary the use of greedy algorithms, heuristics, machine learning or more specific techniques to work along with the data structures in a more intuitive way and obtain better results. Even with the satisfactory results generated by the state-of-the-art global routers, it is still possible to do enhancements in those. This paper explores programming optimization techniques applied to a state-of-the-art open-source global router. From the analysis we made in the NTHU Route, we could present enhancements involving the algorithms parameters, and the application of parallelism in some of the router stages, seeking for improvements in the performance and quality of the results. With the application of the strategies involving parameters, more specific with the application of an overflow threshold for accepting overflowed results at the main phase of the router, it was possible to reduce the runtime of all used benchmarks in average in about 9%, being the best case a reduction of about 20% with no further impacts on the total wirelength. With the application of parallelism strategies at the refinement stage, it was possible to improve the runtime of this phase in 20%, with the average improvement by 10%. With experiments applying parallelism at the main phase together with the increment in the bounding-box expansion for connecting two pins, the execution time doubled, because of the behavior for finding solution on this phase. By mixing both modifications, applying the threshold for overflow acceptance on the main phase, and the parallelism in minor blocks in both phases without the increment of the bounding-box expansion, it was possible to obtain improvements in the general runtime in about 20%, with no considerable impact in the total wirelength. Exploring this techniques of optimization on the routing algorithms showed good results, that can be applied in different routing and other physical synthesis tools.
