Biblioteca de BDDs baseada em inteiros

Abstract

Diagramas de decisão binária (BDDs) são um tipo de estrutura de dados muito usada no projeto de circuitos integrados digitais. Este trabalho apresenta uma contribuição para a obtenção de estruturas de dados mais eficientes para BDDs através da proposta de uma chave única baseada em um só inteiro. Para operações lógicas de oito entradas ou mais, esta implementação foi de duas a treze vezes mais rápida do que uma implementação de referência onde a chave única é baseada em cadeias de caracteres. Para circuitos aritméticos cujas entradas possuem três bits ou mais, o resultado obtido foi um ganho de velocidade de 2,5 à 9,4 vezes.

BDDs are a type of data structure widely used in the design of digital integrated circuits. This work presents a contribution to obtain more efficient BDD data structures through using a unique key based on a single integer. For logic operations of eight inputs or more, this implementation was two to thirteen times faster compared to a reference implementation where the unique key is based in a string of characters. For arithmetic circuits of two three or more bits inputs, the result obtained was a 2.5 to 9.4 times gain in speed.