Otimização pós-síntese de circuitos reversíveis utilizando métodos heurísticos

Abstract

Neste trabalho foram programados dois algoritmos descritos na literatura denominados de XOR e MDM que realizam a síntese de circuitos reversíveis a partir da tabela verdade. Programou-se também algoritmos relacionados com a otimização pós-síntese, denominados Greedy, Simulated Annealing e Variable Neighbourhood Descent, que empregam métodos heurísticos e regras de reescrita, cujo objetivo é reduzir a quantidade de portas lógicas reversíveis do circuito sintetizado. A contribuição deste trabalho foi o emprego do método Divisão que divide o circuito sintetizado em vizinhanças e aplica o método Simulated Annealing ou Variable Neighbourhood Descent nas partes do circuito. Os métodos de otimização implementados foram comparados utilizando como testes 42 circuitos. Constatou-se que os métodos Simulated Annealing e Variable Neighbourhood Descent em conjunto com o método Divisão geraram circuitos menores. Além disso, o algoritmo que aplica a meta-heurística Simulated Annealing comparado ao Variable Neighbourhood Descent obteve menor quantidade de portas em 7 dos 42 circuitos, mesmo custo em 29 circuitos e pior custo em 6.

In this work, two algorithms described in the literature denominated of XOR and MDM are programmes that realize the synthesis of reversible circuits from the truth table. It has been programmed also algorithms related to the post-synthesis optimization, called Greedy, Simulated Annealing and Variable Neighbourhood Descent, which use heuristic methods and rewriting rules, whose objective is to reduce the number of reversible logic gates of the synthesized circuit. The contribution of this work was the use of the Division method that divides the synthesized circuit into neighborhoods and applies the Simulated Annealing or Variable Neighbourhood Descent method in the circuit parts. The implemented optimization methods were compared using 42 circuits as a test. It was found that the Simulated Annealing and Variable Neighborhood Descent methods together with the Division method generated smaller circuits. Furthermore, the algorithm that applies the Simulated Annealing meta-heuristic compared to the Variable Neighbourhood Descent obtained the lowest number of gates in 7 of the 42 circuits, even cost in 29 circuits and the worst cost in 6.