Synthesis of Reversible Cascades from Relational Specifications
Martin Lukac , Marek Perkowski , Michitaka Kameyama , Nouraddin Alhagi , Paweł Kerntopf
AbstractSo 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.
|Book||De Vos Alexis, Wille Robert (eds.): Proceedings 3rd Workshop on Reversible Computation (RC), 2011, Universitat Bremen, 196 p.|
|Keywords in English||Reversible Logic Synthesis, Relational Specifications, Incompletely Specified Functions, Tree Search|
|Project||Synthesis 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
* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.