SmartDR: algorithms and techniques for fast detailed routing with good design rule handling

Abstract

O roteamento detalhado é uma das etapas mais desafiadoras e demoradas do projeto de circuitos integrados. A solução do roteamento deve obedecer a todas as regras de projeto para que o circuito possa ser corretamente fabricado. No entanto, o tratamento de regras de projeto pode ser muito desafiador, quanto a suas soluções algorítmicas e sua implementação, e pode facilmente levar a tempos de execução inviáveis. Para tornar a resolução do roteamento detalhado mais factível, ele é dividido em duas etapas, onde, na primeira, chamada de roteamento detalhado inicial, uma solução quase completa é obtida mediante a flexibilização das regras de projeto. Na segunda etapa as violações remanescentes de regras de projeto são resolvidas. No entanto, quanto mais o tratamento dessas regras é deixado para a segunda etapa, maior é a chance de elas não serem resolvidas completamente, e isto costuma ocorrer. Assim, é necessário enfrentar o desafio de lidar com o maior número possível de regras na etapa inicial sem comprometer o desempenho do roteamento. Dessa forma, este trabalho propõe um roteador detalhado inicial, chamado SmartDR, para atender essas necessidades, isto é, apresentar uma boa lida com regras de projeto ao mesmo tempo que mantendo um bom desempenho. As principais características do roteador, que atendem a esses objetivos, são técnicas de acesso a pinos e de busca de caminhos. Este trabalho propõe um novo método de acesso a pinos, em que os caminhos de acesso a pinos compartilham os mesmos recursos de roteamento e são legalizados e implementados dinamicamente. Também é proposto um novo algoritmo de busca de caminhos, baseado na busca A* com intervalos, o qual é ciente de várias regras de projeto. É proposto também um novo método para melhorar a função heurística da busca A* levando em consideração peculiaridades do roteamento detalhado, o que leva a um melhor desempenho. Utilizando os benchmarks da competição ISPD 2018, todos os métodos propostos foram avaliados separadamente e em conjunto no roteador proposto, o qual foi comparado com os roteadores estado-da-arte. Os experimentos mostram que as técnicas propostas contribuem para uma melhoria em desempenho e um bom tratamento de regras de projeto, assim como demonstra que o SmartDR é superior aos roteadores estado da arte nesses mesmos quesitos.