Tackling the drawbacks of a lagrangian relaxation based discrete gate sizing algorithm

• Ano de defesa: 2018
• Autor(a) principal: Plácido, Henrique
• Orientador(a): Reis, Ricardo Augusto da Luz
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Palavras-chave em Português: Microeletrônica; Circuitos integrados
• Palavras-chave em Inglês: Leakage power minimization; Timing constraints; Lagrangian relaxation; Cell selection; Physical design; EDA; Microelectronics
• Link de acesso: http://hdl.handle.net/10183/193469

A redução das dimensões dos dispositivos permite que o número de transistores nos circuitos integrados aumente, levando ao aumento da potência estática do circuito. A técnica de dimensionamento discreto de portas lógicas consiste em atribuir a cada porta lógica do circuito uma célula dentre todas as opções de implementação disponíveis na biblioteca de células. É uma poderosa técnica empregada no fluxo de síntese de circuitos integrados para realizar otimizações, como, por exemplo, remoção de violações de timing e minimização de potência e/ou área do circuito. O algoritmo de dimensionamento discreto de portas lógicas baseado em relaxação Lagrangiana proposto em [Flach et al. 2013] apresenta os melhores resultados em termos de potência estática publicados até então para os benchmarks da competição de dimensionamento discreto de portas lógicas do ISPD que ocorreu em 2012 [Ozdal, Burns and Hu 2012]. Contudo, a fase de relaxação Lagrangiana desse algoritmo possui algumas desvantagens. São necessárias muitas iterações para o algoritmo convergir para uma boa solução em termos de potência estática. Também, durante as iterações iniciais, a potência estática aumenta consideravelmente, assim, uma parcela das iterações é utilizada para reduzir o pico de potência estática Ainda, o resolvedor do subproblema Lagrangiano não utiliza nenhuma técnica de filtragem de células candidatas, então, o algoritmo pode ser muito lento. Então, nesse trabalho, o fluxo de dimensionamento discreto de portas lógicas proposto em [Flach et al. 2013] é estendido para tratar as desvantagens citadas. São propostas algumas melhorias para a fórmula de atualização dos multiplicadores de Lagrange que permitem a fase de relaxação Lagrangiana convergir mais rapidamente. Também é utilizado um fator de escala para balancear adequadamente o custo de timing e a potência estática quando uma célula candidata é avaliada pelo resolvedor do subproblema Lagrangiano. Assim, o fator de escala, juntamente com o novo método de atualização dos multiplicadores de Lagrange, controla a explosão de potência estática durante as iterações inicias da fase de relaxação Lagrangiana. Ainda, é utilizada uma estratégia de filtragem de células candidatas para reduzir o tempo de execução das iterações do algoritmo de relaxação Lagrangiana. Finalmente, as etapas de pós-processamento timing recovery e power recovery foram modificadas para reduzir o tempo de execução do fluxo. A nova abordagem atingiu resultados em termos de potência estática similares ao algoritmo original, tendo 4,28 vezes menos iterações, em média, e 9,11 vezes menos testes de células candidatas, em média, na fase de relaxação Lagrangiana Também, o grande aumento de potência estática durante as iterações iniciais da relaxação Lagrangiana foi reduzido de 9,55 vezes a potência final obtida, em média, para 2,74 vezes a potência final obtida, em média. Finalmente, comparado ao algoritmo de dimensionamento discreto de células proposto em [Sharma et al. 2017], que é o mais rápido publicado até então, a ferramenta desenvolvida nesse trabalho produziu, mesmo não utilizando a fase de pós processamento power recovery, resultados muito próximos em termos de potência estática, tendo resultados levemente melhores para o maior benchmark.