Fast extract with cube hashing

Abstract

The fast-extract algorithm is a well-known algebraic method for factoring and decomposing Boolean expressions. Since it uses pairwise comparisons between cubes to find factors, the run-time is degraded for networks whose primary outputs are expressed in terms of primary inputs and have Boolean functions with thousands of cubes. This work describes a new implementation of the fast-extract algorithm, fxch, having complexity linear in the number of cubes. The reduction in complexity is achieved by hashing sub-cubes and using the hash table to find good factors to extract. Experimental results on industrial benchmarks show better run-time and scalability of the proposed algorithm, compared to the available solutions.

O algoritmo fast-extract é um método algébrico bem conhecido para a fatoração e decomposição de expressões booleanas. Entretanto, seu método de busca por divisores, que utiliza a comparação de pares de cubos, o torna demasiadamente lento para redes cujas saídas primárias são expressas em termos de entradas primárias e que tenham funções booleanas com milhares de cubos. Este trabalho descreve uma nova implementação do algoritmo fast-extract, fxch, com complexidade linear no número de cubos. A redução na complexidade é atingida com a utilização de uma tabela hash, utilizada para encontrar bons divisores. Os resultados experimentais em benchmarks industriais mostram tempo de execução e escalabilidade superiores, em comparação com as soluções disponíveis.