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

Abstract

The shrink of the devices sizes allows the number of transistors in the integrated circuits to grow, leading to an increase in the leakage power. The discrete gate sizing technique consists in assigning each gate of the circuit to a cell option among the implementation versions available in the cell library. It is a powerful method used in the design flow to carry out optimizations, e.g., timing violations fixing and power and/or area minimization. The Lagrangian relaxation based gate sizer proposed in [Flach et al. 2013] has the best leakage power results published so far for the 2012 ISPD Gate Sizing Contest benchmarks. However, its Lagrangian relaxation phase has some drawbacks. It requires many iterations to converge to a good solution in terms of leakage power. Also, during the initial iterations, the leakage power blows up, so a parcel of the iterations is used to reduce this peak of leakage power. Yet, the Lagrangian relaxation subproblem solver does not rely on any technique to perform cell option candidate filtering, so it can be very timing consuming. Therefore, in this work, the discrete gate sizing flow proposed in [Flach et al. 2013] is extended to tackle the drawbacks aforementioned. It is proposed some enhancements to the Lagrange multiplier update formula that enable the Lagrangian relaxation core to converge faster It is also used a scaling factor to properly scale timing cost and leakage power when evaluating a cell candidate in the Lagrangian relaxation subproblem solver. So, the scaling factor, alongside the new Lagrange multipliers update method, controls the leakage power blow up during the initial Lagrangian relaxation iterations. Moreover, it is applied a cell option candidate filtering strategy to reduce the runtime of each Lagrangian relaxation iteration. Finally, the post-processing timing recovery and power recovery phases of the original work are improved to reduce the overall flow runtime. The new approach achieved leakage power results similar to the baseline work, taking 4:28 fewer iterations and 9:11 fewer cell option candidates evaluation, on average, in the Lagrangian relaxation phase. Also, the leakage power blow up during the initial iterations of the Lagrangian relaxation was reduced from 9:55 the final value, on average, to 2:74 the final value, on average. Finally, compared to [Sharma et al. 2017], which is the fastest gate sizing algorithm published so far, the new approach produced, without using the post-processing power recovery phase, similar leakage power results in general, performing slightly better for the largest benchmark.

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.