Graph-based algorithms for transistor count minimization in VLSI circuit EDA tools

Abstract

This master’s thesis introduces a set of graph-based algorithms for obtaining reduced transistor count VLSI circuits using simple cells. These algorithms are mainly focused on minimizing node count in AIG representations and mapping this optimized AIG using simple cells (NAND2 and NOR2) with a minimal number of inverters. Due to the AIG node count minimization, the logic sharing is probably highly present in the optimized AIG, what may derive intermediate circuits containing cells with unfeasible fanout in current technology nodes. In order to fix these occurrences, this intermediate circuit is subjected to an algorithm for fanout limitation. The proposed algorithms were applied over a set of benchmark circuits and the obtained results have shown the usefulness of the method. The circuits generated by the methods proposed herein have, in average, 32% less transistor than the previous reference on transistor count using simple cells. Additionally, when comparing the presented results in terms of transistor count against works advocating for complex cells, our results have demonstrated that previous approaches are sometimes far from the minimum transistor count that can be obtained with the efficient use of a reduced cell library composed by only a few number of simple cells. The simple-cells-based circuits obtained after applying the algorithms proposed herein have presented a lower transistor count in many cases when compared to previously published results using complex (static CMOS and PTL) cells.

Esta dissertação de mestrado introduz um conjunto de algoritmos baseados em grafos para a obtenção de circuitos VLSI com um número reduzido de transistores utilziando células simples. Esses algoritmos têm um foco principal na minimização do número de nodos em representações AIG e mapear essa estrutura otimizada utilizando células simples (NAND2 e NOR2) com um número mínimo de inversores. Devido à minimização de nodos, o AIG tem um alto compartilhamento lógico, o que pode derivar circuitos intermediários contendo células com fanouts infactíveis para os nodos tecnológicos atuais. De forma a resolver essas ocorrências, o circuito intermediário é submetido a um algoritmo para limitação de fanout. Os algoritmos propostos foram aplicados num conjunto de circuitos de benchmark e os resultados obtidos mostram a utilidade do método. Os circuitos resultantes tiveram, em média, 32% menos transistores do que as referências anteriores em números de transistores utilizando células simples. Adicionalmente, quando comparando esses resultados com trabalhos que utilizam células complexas, nossos números demonstraram que abordagens anteriores estão algumas vezes longe do número mínimo de transistores que pode ser obtido com o uso eficiente de uma biblioteca reduzida de células, composta por poucas células simples. Os circuitos baseados em células simples obtidos com a aplicação dos algoritmos proposto neste trabalho apresentam um menor número de transistores em muitos casos quando comparados aos resultados previamente publicados utilizando células complexas (CMOS estático e PTL).