Design of Reversible Computing System Logic, Languages and Circuits

PhD Defense by Michael Kirkedal Carøe. 



This thesis investigates garbage-free reversible computing systems from abstract design to physical gate-level implementation. Arithmetic operations are a basis for many computing systems so the ripple-block carry adder and work towards general multiplication are important contributions in the design of reversible circuits. Such arithmetic circuits have then been used in the design of two larger reversible computing systems. The first is a small von Neumann architecture, called Bob, that can execute programs written in a simple reversible two-address instruction set. A central part of the architecture is a novel design of a reversible arithmetic logic unit. The second system is an implementation of the linear cosine transform used in the H.264/ACV encoding standard.

Designing reversible logic circuits on paper can become very complex, so two reversible functional hardware description languages that can simplify the implementation process are designed. One language is a linear-typed higher-level language, while the other is a gate-level point-free combinator language. These two languages can be used in a garbage-free design flow, where circuits are described in the higher-level language and then translated to the combinator language. From the gate-level language, methods of place-and-route of CMOS gates can be applied. To facilitate this last step, standard cell layouts of the reversible gates in complementary pass-gate CMOS logic are made and, as a test, these cells have been used to fabricate the ALU design.

In total, this thesis has shown that it is possible to design non-trivial reversible computing systems without garbage and that support from languages (computer aided design) can make this process easier. However, there is often still a need to rethink both the problem and the solution to accommodate the no-garbage approach. 

Assessment committee:

  • Chairman: Associate Professor Torben Æ. Mogensen, Department of Computer Science, University of Copenhagen, Denmark
  • Professor Mary Sheeran, Computer Science and Engineering Department, Chalmers University, Sweden
  • Professor Rolf Drechsler, Faculty of Mathematics and Computer Science, University of Bremen, Germany

Academic supervisor:

Associate Professor Robert Glück, Department of Computer Science, University of Copenhagen, Denmark

For an electronic copy of the thesis, please contact Jette Giovanni Møller,