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

Submitted by Aline Batista (alinehb.ufpel@gmail.com) on 2020-08-11T21:36:07Z No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Tese_Stephano_Machado_Moreira.pdf: 3252235 bytes, checksum: 16f91f7fc566bd22ffa09aa59c0d5b72 (MD5) Approved for entry into archive by Aline Batista (alinehb.ufpel@gmail.com) on 2020-08-13T11:59:17Z (GMT) No. of bitstreams: 2 Tese_Stephano_Machado_Moreira.pdf: 3252235 bytes, checksum: 16f91f7fc566bd22ffa09aa59c0d5b72 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Made available in DSpace on 2020-08-13T11:59:30Z (GMT). No. of bitstreams: 2 Tese_Stephano_Machado_Moreira.pdf: 3252235 bytes, checksum: 16f91f7fc566bd22ffa09aa59c0d5b72 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2020-01-15 Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES Detailed routing is one of the most challenging and time-consuming steps of the design of integrated circuits. The routing solution must obey all of the design rules so that the circuit can be properly manufactured. However, design rule handling may be very challenging, regarding its algorithmic solutions and implementation, and may easily lead to unfeasible runtimes. In order to make the detailed routing resolution more feasible, it is divided into two steps, where in the first, called initial detailed routing, an almost complete solution is achieved by relaxing design rules. In the second step the remaining design rule violations are solved. However, the more these rules are left to be handled in the second stage, the greater is the chance that they will not be completely solved, and this usually occurs. Thus, it is necessary to face the challenge of dealing with as many rules as possible in the first step without compromising the runtime. Thus, this work proposes an initial detailed router, called SmartDR, to meet these needs, that is, to provide a good design rule handling while keeping a good runtime. The main features of the router that meet these goals are pin access and path search techniques. This work proposes a novel pin access method, in which the pin access paths share the same routing resources and are dynamically legalized and implemented. It is also proposed a new path search algorithm, based on A *-interval search, which is aware of several design rules. A new method to improve the A * heuristic function is also proposed, taking into account the peculiarities of detailed routing, which leads to a better runtime. Using ISPD 2018 Contest benchmarks, all proposed methods were evaluated separately and altogether in the proposed router, which was compared with state-of-the-art routers. The experiments show that the proposed techniques contribute to runtime and design rule handling improvement, as well as it demonstrates that SmartDR is superior to the state-of-the-art routers in these metrics. 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.