Skip to main content

About this book

The LNCS journal Transactions on Computational Science reflects recent developments in the field of Computational Science, conceiving the field not as a mere ancillary science but rather as an innovative approach supporting many other scientific disciplines. The journal focuses on original high-quality research in the realm of computational science in parallel and distributed environments, encompassing the facilitating theoretical foundations and the applications of large-scale computations and massive data processing. It addresses researchers and practitioners in areas ranging from aerospace to biochemistry, from electronics to geosciences, from mathematics to software architecture, presenting verifiable computational methods, findings, and solutions and enabling industrial users to apply techniques of leading-edge, large-scale, high performance computational methods. This, the 24th issue of the Transactions on Computational Science journal, guest edited by Himanshu Thapliyal and Nagarajan Ranganathan, is devoted to the topic of reversible computing. It is comprised of eight selected papers on reversible energy recovery designs, design of reversible logic gates and arithmetic circuits in optical computing, reversible basic linear algebra subprograms, quantum circuit description language, and reversible circuit and logic synthesis.

Table of Contents


Adiabatic CMOS: Limits of Reversible Energy Recovery and First Steps for Design Automation

Standard CMOS technology discards all signal energy during every switching cycle, leading to heat generation that limits the operating speed and the achievable computing performance. Energy-recovery schemes avoid the heat generation, but are often burdened with the cost of significant increase in system complexity and the lack of automated design tools. In this paper, we propose to implement adiabatic CMOS circuits utilizing split-level rails and Bennett clocking, which enable energy-recovery in standard CMOS logic gates with only minor modifications. Using a pessimistic 32 nm bulk MOSFET technology model, a switching energy improvement factor of approximately 10X can be reached over standard CMOS, while we predict that emerging low-leakage transistor technologies potentially enable adiabatic energy improvements up to four orders-of–magnitude over the standard approach. The significant end-result of our method is that we can leverage the huge number of existing standard gate libraries and logic designs for energy-recovery circuits. We outline an approach to integrate the automatic generation of the adiabatic circuits into the standard circuit design flow, including standard gate logic synthesis and place-and-route.
Ismo Hänninen, Gregory L. Snider, Craig S. Lent

Ultrafast All-Optical Reversible Peres and Feynman-Double Logic Gates with Silicon Microring Resonators

We present designs of reversible Peres logic gate and Feynman-Double logic gate based on all-optical switching by two-photon absorption induced free-carrier injection in silicon add-drop microring resonators. The logic gates have been theoretically analyzed using time-domain coupled-mode theory and all-optical switching has been optimized for low-power (25 mW) ultrafast (25 ps) operation with high modulation depth (85 %) to enable logic operations at 40 Gb/s. The advantages of high Q-factor, tunability, compactness, cascadibility, reversibility and reconfigurability make the designs favorable for practical applications.
Purnima Sethi, Sukhdev Roy

Design of Reversible Adder-Subtractor and its Mapping in Optical Computing Domain

Reversible logic has promising applications in dissipation less optical computing, low power computing, quantum computing, etc. Reversible circuits do not lose information, and there is a one-to-one mapping between the input and the output vectors. In recent years, researchers have implemented reversible logic gates in optical domain as it provides high-speed and low-energy computations. Reversible gates can be easily fabricated at the chip level using optical computing. The optical implementation of reversible logic gates are based on semiconductor optical amplifier (SOA)-based Mach-Zehnder interferometer (MZI). The Mach-Zehnder interferometer has advantages such as high speed, low power, easy fabrication, and fast switching time. In this work, we present the optical implementation of an n bit reversible ripple carry adder. The optical reversible adder design is based on two new optical reversible gates referred to as optical reversible gate I (ORG-I) and optical reversible gate II (ORG-II) and the existing optical Feynman gate. The two new reversible gates ORG-I and ORG-II are proposed as they can implement a reversible adder with reduced optical cost which is the measure of number of MZIs switches and the propagation delay, and with zero overhead in terms of the number of ancilla inputs and the garbage outputs. The proposed optical reversible adder design based on the ORG-I and ORG-II reversible gates are compared and shown to be better than the other existing designs of reversible adder proposed in non-optical domain in terms of the number of MZIs, delay, the number of ancilla inputs, and the garbage outputs. A subtraction operation can be defined as \(a-b=\overline{\bar{a}+b}\) and \(a-b=a+\bar{b}+1\), respectively. Next, we propose the design methodologies based on (i) \(a-b=\overline{\bar{a}+b}\), and (ii) \(a-b=a+\bar{b}+1\), to design a reversible adder-subtractor that is controlled by the control signal to perform addition or subtraction operation.
Saurabh Kotiyal, Himanshu Thapliyal, Nagarajan Ranganathan

Towards Reversible Basic Linear Algebra Subprograms: A Performance Study

Problems such as fault tolerance and scalable synchronization can be efficiently solved using reversibility of applications. Making applications reversible by relying on computation rather than on memory is ideal for large scale parallel computing, especially for the next generation of supercomputers in which memory is expensive in terms of latency, energy, and price. In this direction, a case study is presented here in reversing a computational core, namely, Basic Linear Algebra Subprograms (BLAS), which is widely used in scientific applications. A new Reversible BLAS (RBLAS) library interface has been designed, and a prototype has been implemented with two modes: (1) a memory-mode in which reversibility is obtained by checkpointing to memory, and (2) a computational-mode in which nothing is saved, and restoration is done entirely via inverse computation. The article is focused on detailed performance benchmarking to evaluate the runtime dynamics and performance effects, comparing reversible computation with checkpointing on both traditional CPU platforms and recent GPU accelerator platforms. For BLAS Level-1 subprograms, data indicates over an order of magnitude speed up of reversible computation compared to checkpointing. For BLAS Level-2 and Level-3, a more complex tradeoff is observed between reversible computation and checkpointing, depending on computational and memory complexities of the subprograms.
Kalyan S. Perumalla, Srikanth B. Yoginath

Synthesis and Optimization by Quantum Circuit Description Language

This paper describes the infrastructure of synthesizing quantum circuits via a quantum description language and for this purpose a new quantum circuit description language named QCDL is introduced which comprises instructions for quantum unitary operations and high-level structures which are synthesized into quantum logic level architecture. Next to introducing this language, we describe our synthesis approach to build up the quantum circuits out of a QCDL program. Although there are some languages like QCDL that work in the same way, but they lack all required instruction set, optimization step and/or support for distributed quantum circuits like the one in QCDL. More importantly, this paper describes a synthesis method for the specified language which is not completely included in other works in the field.
Mariam Zomorodi-Moghadam, Mohammad-Amin Taherkhani, Keivan Navi

An Approach to Reversible Logic Synthesis Using Input and Output Permutations

The problem of reversible logic synthesis has assumed importance with the growing emphasis on low-power design and its relationship to quantum computation. Many synthesis approaches for reversible logic circuits have been reported over the last two decades. For small functions exact solutions that require minimum number of gates can be computed. Otherwise, heuristics have to be applied that are either based on transformations or a direct mapping from a given data structure. Recently, it was shown that significant reduction in the cost of the synthesized circuits can be obtained, if the ordering of the input (or output) lines is changed. The drawback of the approach was that it can only be applied to smaller sized circuits. In this paper, two alternate approaches for obtaining a good ordering of the variables are presented. Given a reversible specification in the form of a truth table or a permutation, both the methods rely on a properly chosen cost function and try to obtain an ordering of the variables that minimizes the cost. The first method uses an evolutionary algorithm (EA) to arrive at a good ordering of the output variables. To avoid long runtimes the EA does not synthesize the circuit after each evolutionary operation. Both the original and the least cost permutations are synthesized using a standard synthesis tool, and the improvement in cost are compared. Experimental results demonstrate the effectiveness of the scheme. The second method uses an encoded multi-valued truth table as the data structure, and tries to minimize cost by considering both input and output variable orderings. Feasible moves are defined and an iterative approach based on simulated annealing (SA) is used to minimize the cost. Here also explicit synthesis is avoided during the process of looking for a good variable ordering.
Kamalika Datta, Indranil Sengupta, Hafizur Rahaman, Rolf Drechsler

Synthesis of Reversible Circuits Based on EXORs of Products of EXORs

This paper introduces a new concept of reversible circuits based on EXOR-sum of Products-of-EXOR-sums (EPOE). Two algorithms are introduced that synthesize reversible functions using these new EPOE structures. The motivation for this work is to reduce the number of multiple controlled Toffoli gates and their number of inputs. To achieve these reductions the paper generalizes from existing 2-level AND-EXOR structures (ESOP) commonly used in reversible logic to a mixture of 3-level EXOR-AND-EXOR structures and ESOPs. Our approach can be applied to reversible and permutative quantum circuits to synthesize single output functions with one ancilla line. In addition, a variant of the algorithm with garbage lines is presented. A comparison of the ESOP minimizer EXORCISM-4 and variants of the new EPOE minimizer, called EPOEM-1s and EPOEM-1f, is presented. The results show that EPOE circuits do in fact achieve the above-stated cost reductions, in particular when expressed in terms of Maslov’s quantum cost model commonly used in quantum circuit synthesis.
Linh Tran, Ben Schaeffer, Addison Gronquist, Marek Perkowski, Pawel Kerntopf

Improved Cube List Based Cube Pairing Approach for Synthesis of ESOP Based Reversible Logic

This work addresses an ESOP-based reversible logic synthesis technique using paired cube approach. The input specification to this approach is a ‘.spec file’. In this work, initially, the first algorithm generates improved independent ESOP cubes. Next, the second algorithm performs the pairing of these improved ESOP cubes based on their structural similarity. It is observed that the proposed synthesis approach is very efficient mainly for those functions which do not have shared functionality between multiple outputs or have single output. Sharing of cubes between multiple outputs is not considered here. Experimental results show that the proposed approach has a significant impact on reduction of quantum costs of benchmark circuits. As we have mainly focused on the development of the synthesis technique for logic functions which do not have shared functionality between multiple outputs, we have compared our results with existing non shared-cube synthesis methods. Our approach is best fitted in that environment when function does not contain shared data between several outputs. The improved cube list generation algorithm is capable of generating reversible circuits for functions up to 16 input variables within reasonable time as we have taken ‘.spec file’ as input, whereas the cube pairing algorithm constructs reversible circuits for very large functions in negligible execution time.
Chandan Bandyopadhyay, Hafizur Rahaman, Rolf Drechsler


Additional information

Premium Partner

    Image Credits