SyReC: A hardware description language for the specification and synthesis of reversible circuits

Researchers and engineers have focused the investigation of computing machines on a preponderantly irreversible computing paradigm. In fact, most of the established computations are not invertible as a standard logical operation such as an AND illustrates. Although it is possible to obtain the inputs of an AND gate if the output is set to 1 (then, both inputs must be set to 1 as well), it is not possible to uniquely determine the input values if the gate outputs 0. While mainly relying on this conventional way of computation, also its alternative reversible paradigm receives increasing attention.

Reversible computation is a computing paradigm which only allows bijective operations, i.e. reversible n-input n-output functions in which no two input vectors are mapped to the same output pattern. Hence, all computations can be reverted as the inputs can be obtained from the outputs and vice versa.

Although not so well established thus far, reversible computation enables several promising applications and superiors conventional computation paradigms in many domains. Recent accomplishments and experimental validations in these domains made this alternative paradigm also interesting for computer aided design. In particular applications to low-power design and quantum computation accelerated this development.

Low power computation may significantly profit from reversible circuits because, as observed by Landauer [1], power is always dissipated when information is lost during computation. This indeed happens independently from the applied technology. Hence, all computing machines following the conventional paradigm always lose power if irreversible operations (as the above-mentioned AND) are performed. Although the fraction of dissipated power is negligible today, it will become substantial with the expected ongoing miniaturization. Moreover, Gershenfeld has shown that the actual power dissipation corresponds to the amount of energy used to represent the signal [2]. With ongoing miniaturization of circuits, this amount will soon become substantial. Since reversible computations are information loss-less (inputs can always be restored from the outputs and vice versa), this power loss can significantly be reduced or even entirely avoided with the alternative paradigm (e.g. [3], [4]). Recently, this has experimentally been verified in [5].

Quantum computation [6] allows for breaching complexity bounds which are valid for computing devices based on conventional computing by using quantum mechanical phenomena such as superposition and entanglement. Considering that many of the established quantum algorithms include a significant Boolean component (e.g. the oracle transformation in the Deutsch–Jozsa algorithm [7], the database in Grover׳s search algorithm [8], and the modulo exponentiation in Shor׳s algorithm [9]), it is crucial to have efficient methods to synthesize quantum gate realizations of Boolean functions. Since any quantum operation inherently is reversible, reversible circuits can be exploited for this purpose.

Moreover, further promising applications have recently been investigated in the design of low-power encoding and decoding devices for on-chip interconnects in systems-on-a-chip [10], for adiabatic circuits [11], and for circuits employing energy recovery logic [12].

Motivated by these promising developments, design and synthesis of reversible circuits have received significant attention in the last decade. This led to several synthesis techniques following complementary schemes and exploiting different kinds of function representations. Examples include approaches

• •
  relying on a permutation-based [13] or cycle-based [14] representation,
• •
  following a transformation-based scheme [15],
• •
  using functions descriptions such as positive-polarity Reed–Muller expansion [16], Reed–Muller spectra [17], or Exclusive Sum of Products [18], and
• •
  exploiting efficient data-structures such as Binary Decision Diagrams [19] or Quantum Multiple-valued Decision Diagrams [20].

However, all these approaches only allow one to automatically synthesize reversible circuits up to a certain size that is bounded by the underlying function representation. In order to provide an efficient design flow for this kind of computation and its applications, synthesis of reversible logic has to reach a level which allows for the description of circuits at higher levels of abstraction. For this purpose, hardware description languages can be exploited. In conventional synthesis, approaches using languages such as VHDL [21], SystemC [22], or SystemVerilog [23] are used to specify and subsequently synthesize circuits. Even in some of the application domains of reversible logic, namely quantum computation, first programming languages have been proposed (see e.g. Quipper [24] or Scaffold [25] as well as related overviews such as e.g. [26]).

In this work, we provide a comprehensive introduction to and extensions for the hardware description language SyReC.¹ SyReC allows for the specification and automatic synthesis of complex reversible circuits. For this purpose, established concepts from the previously introduced reversible software language Janus [28], [29] are adapted. To the best of our knowledge only two other hardware description languages for reversible logic have been proposed after SyReC has been introduced. In [30] a functional reversible language has been proposed that ensures reversibility using a type system based on linear types. As a consequence, only pure reversible functionality can be addressed, i.e. irreversible operations are not supported. A combinator-style functional language has been presented in [31] which offers the design of reversible circuits at the gate level and therefore focuses on lower levels than SyReC.

In the remainder of this paper, the concepts of the SyReC language as well as the corresponding synthesis methodology are described in detail. After a brief review on the basics of reversible logic and circuits, Section 3 introduces the general concept as well as the precise syntax and the (informal) semantics of the proposed language. It is shown how reversibility in the description is ensured while at the same time a wide range of (also non-reversible) functionality can be provided. The realization of a reversible control flow is also discussed. All concepts are illustrated by means of examples. Section 4 describes how the resulting programs are realized as a reversible circuit. A hierarchical synthesis approach is presented that automatically transforms the respective statements and operations of the new language into a reversible circuit. The respective realizations of the individual statements and expressions as building blocks are presented and discussed. While this allows for the synthesis of complex reversible circuits, the quality of the results can still be improved. Sections 5 and 6 introduce optimization techniques which allow for a reduction of the number of lines or gate costs depending on the individual design needs. Finally, the applicability of the language as well as its synthesizer is demonstrated in Section 7. Here, a fully functional RISC CPU is designed and realized using SyReC. This confirms that even complex logic can easily be realized with this language. Furthermore, the effects of the different optimizations are evaluated and the synthesizer is compared to another solution which is based on a Boolean function representation.

Overall, a comprehensive overview on this new hardware description language for reversible circuit design is provided. This eventually lifts the design of circuits following the reversible computation paradigm from the Boolean level to a higher abstraction.