Avaliação do Impacto de Reconvergências na Qualidade da Solução de Gate Sizing Discreto Baseado em Programação Dinâmica

Abstract

O problema de gate sizing consiste em dimensionar as portas lógicas de um circuito digital com o objetivo de minimizar a potência por este consumida, sem violar restrições de atraso. Este é um problema que tem recebido atenção recentemente devido à demanda crescente de sistemas embarcados que exigem um baixo consumo de energia. Trabalhos recentes mostraram que a formulação desse problema utilizando Relaxação Lagrangeana leva a bons resultados, sendo sua resolução viabilizada através de diferentes técnicas como programação dinâmica, heurísticas gulosas, etc. Seria de se esperar que a resolução do problema com programação dinâmica levasse a melhores resultados do que em heurísticas gulosas (pois o primeiro método toma decisões globais no espaço de soluções). Entretanto, os resultados da literatura que utilizam heurísticas gulosas são melhores do que os que utilizam programação dinâmica. Este trabalho investiga o motivo dessa redução da qualidade. A hipótese de pesquisa levantada é a de que as estratégias utilizadas por algoritmos de programação dinâmica para contornar as limitações resultantes da presença de reconvergências de caminhos em circuitos reais degradam a qualidade da solução de tais algoritmos. Para isso, foram gerados circuitos artificiais a partir dos parâmetros dos circuitos da infraestrutura do ISPD 2012 Discrete Gate Sizing Contest e variando o número de reconvergências. Estes circuitos foram utilizados para comparar um algoritmo de cada classe. Para circuitos sem reconvergências, o algoritmo de programação dinâmica atingiu um leakage médio 28% menor do que a heurística gulosa para os circuitos com a configuração fast e 37% menor para os circuitos com a configuração slow, ao custo de um tempo de execução em média 85 vezes maior. Para circuitos com 100% das reconvergências do circuito real cujos parâmetros foram extraídos, o algoritmo de programação dinâmica atingiu um consumo de energia em média 63% superior para os circuitos com a configuração fast e 13% superior para os circuitos com a configuração slow. Portanto, os resultados obtidos sugerem que a hipótese de pesquisa levantada é válida.