Synthesis of Reversible Cascades from Relational Specifications

Martin Lukac , Marek Perkowski , Michitaka Kameyama , Nouraddin Alhagi , Paweł Kerntopf


So far there are two most common ways of specifying reversible circuits: complete and incomplete. We extend the incomplete function specification by technological constraints and we call it relational specification. We present a parallel programming approach (GPU accelerated) based on dynamical tree search for reversible logic functions specified as relations. The method is based on two search algorithms implemented on a parallel computer using the GPU; on one hand the tree-search synthesizes reversible circuits that are compared with the target circuit and on the other hand a heuristic algorithm searches for such don’t care allocation that would speed up the search. The algorithm showed that correct circuits of up to 5 bits can be obtained for relational specifications without any ancilla bits being added.
Author Martin Lukac
Martin Lukac,,
, Marek Perkowski
Marek Perkowski,,
, Michitaka Kameyama
Michitaka Kameyama,,
, Nouraddin Alhagi
Nouraddin Alhagi,,
, Paweł Kerntopf (FEIT / IN)
Paweł Kerntopf,,
- The Institute of Computer Science
Book De Vos Alexis, Wille Robert (eds.): Proceedings 3rd Workshop on Reversible Computation (RC), 2011, Universitat Bremen, 196 p.
Keywords in EnglishReversible Logic Synthesis, Relational Specifications, Incompletely Specified Functions, Tree Search
ProjectSynthesis of reversible logic circuits – new approaches and algorithms. Project leader: Kerntopf Paweł, , Phone: +48 22 234 7711, start date 17-05-2010, end date 16-11-2012, II/2010/M/2, Completed
WEiTI Projekty finansowane przez MNiSW
Languageen angielski
Score (nominal)0
Citation count*
Share Share

Get link to the record

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Are you sure?