Algorithms to improve area density utilization, routability and timing during detailed placement and legalization of VLSI circuits

• Ano de defesa: 2019
• Autor(a) principal: Monteiro, Jucemar Luis
• Orientador(a): Johann, Marcelo de Oliveira
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Palavras-chave em Português: Microeletrônica; Vlsi
• Palavras-chave em Inglês: Placement Optimization; Network Flow; Branch and Cut
• Link de acesso: http://hdl.handle.net/10183/197078

O posicionamento é um estágio desafiante no fluxo de projeto físico para integrar circuitos VLSI (sigla do inglês Very Large-Scale Integration (VLSI)). Em projetos modernos de circuitos VLSI, diversas restrições de projeto são impostas para visar a complexidade dos avançados nodos de fabricação CMOS (sigla do inglês). As restrições de projeto têm uma considerável influência em obter soluções otimizadas de circuitos. A qualidade do posicionamento tem uma significativa influência no desempenho do circuito. No posicionamento, obter os requisitos do circuito em tempo de propagação e rotabilidade é uma tarefa desafiante. Requerimentos de tempo de propagação e rotabilidade são especialmente difíceis de obter em circuitos que tem regiões com alta densidade de utilização de área. Além disso, a qualidade do posicionamento tem influência direta na qualidade do circuito e no esforço de otimização dos algoritmos de síntese da árvore de relógio (sigla do inglês CTS), roteamento e pós-posicionamento otimização. A primeira contribuição apresentada nessa tese é um algoritmo incremental de posicionamento para otimizar violações no tempo de propagação sujeito a rotabilidade. O algoritmo proposto é baseado em características das redes e dos caminhos de dados para computar posições otimizadas para as células. Continua) Posições otimizadas são aceitas somente se elas estão dentro de regiões livres de violações de roteamento. A segunda contribuição apresentada nessa tese é um algoritmo de espalhamento de células. O objetivo é mover células fora de regiões com alta densidade de área considerando efeitos adversos nas células movidas. O algoritmo proposto é baseado em técnicas de network flow e branch and cut para minimizar regiões com alta densidade de área. Fluxos de área são movidos de regiões com alta densidade de área para regiões com baixa densidade de área com caminhos com custo otimizado. Assim sendo, a concentração de células é reduzida e espaços são abertos em regiões com alta densidade de área com minimizado efeitos adversos nas células movidas. Algoritmos de legalização, posicionamento detalhado e pós-posicionamento podem utilizar esses espaços abertos para otimizar mais a solução de posicionamento. Em regiões com alta densidade de área, espaços são recursos limitados. No fluxo de posicionamento tradicional (posicionamento global, legalização e posicionamento detalhado), a otimização do posicionamento é limitada pelo fluxo tradicional. O algoritmo proposto de espalhamento de células pode ser integrado em um fluxo misto de posicionamento que é composto de algoritmos intercalados de legalização e posicionamento detalhado. Nesse fluxo de posicionamento misto, a restrição para otimizar posicionamento detalhado em uma netlist legalizada pode ser relaxada. Algoritmos de posicionamento detalhado podem obter melhor posicionamento com uma formulação de posicionamento menos restrita. O foco dos algoritmos de legalização pode ser somente remover sobreposição de células com efeitos adversos minimizados no posicionamento ao invés de também minimizar violações de densidade de utilização de área. O algoritmo proposto de espalhamento de células é aplicado nos estágios de legalização e posicionamento detalhado para otimizar densidade de utilização de área. O algoritmo proposto de legalização obteve melhoria no espalhamento médio (30%) e máximo (350%) de células comparado com algoritmos de legalização estado da arte. No posicionamento detalhado, o algoritmo proposto foi avaliado em fluxos de posicionamento industrial e acadêmico. No fluxo de posicionamento industrial, o algoritmo proposto melhorou espalhamento de células, potência dissipada e tempo de propagação. O algoritmo proposto de espalhamento de células pode melhorar a qualidade do posicionamento em fluxos de posicionamento mistos em ambiente industrial e acadêmico. O algoritmo proposto fornece posicionamento com distribuição uniforme de células em projetos limitados com efeitos adversos minimizados nas células movidas.