Utilização de hardware reconfigurável para acelerar a satisfação booleana

Iouliia Skliarova, António B. Ferrari

Resumo


Este artigo apresenta um estudo de possibilidade de aceleração da satisfação booleana com a ajuda do hardware reconfigurável. A satisfação booleana (SAT) é um problema importante que tem muitas aplicações em CAD e outras áreas. Neste artigo propomos uma técnica de desenvolvimento orientada a problema em geral para acelerar a resolução de SAT formulado sobre matriz discreta. O algoritmo utilizado requer uma unidade de controlo bastante complexa que é implementada inteiramente em hardware reconfigurável. Por fim, são analisadas diferentes possibilidades de resolução de SAT e argumenta-se que os melhores resultados podem ser obtidos com a ajuda da colaboração de uma aplicação de software executada num computador de uso geral com um circuito de solução de SAT implementado em FPGA.

Palavras-chave


SAT; satisfação booleana; CAD; hardware reconfigurável

Texto Completo:

PDF