Reversible Computer

Sounds like an interesting idea to me, so I spent a few minutes reading Carlin James Vieri's master's thesis, Pendulum: A Reversible Computer Architecture, approved by Thomas F. Knight Jr. the thesis supervisor.

I skimmed quickly through page 23, and I decided this thesis is bullocks.

The idea of reversible computing is that a computer should never have to flip a bit, which causes energy loss. Instead, bits should be exchanged so the total number of 0 and 1 bits are conserved. Chapter 3 of the thesis suggests that load-store instructions should be replaced with exchange. I have a simpler approach.

If you implement a 32-bit machine, use 64-bit words with exactly 32 zero bits and 32 one bits. The 64-bit word is divided into two 32-bit parts, the useful part and the useless part. The idea is that a 32-bit word cannot have more than 32 zeros or 32 ones, so we can freely allocate these zero and ones to the "useful" part of the 64-bit word, and the rest temporarily deposited in the "useless" part of the 64-bit word. Computation is carried out by permuting bits between the useful and useless parts.

My model guarantees that storage requirement compared to a traditional computing machine is bounded by a factor of 2. And existing programs can run unmodified on the new reversible computer.

The thesis goes on to explain reversible and irreversible operations in section 3.2.2. It says that:

Certain datapath functions of two operands, such as XOR, have well defined inverses which allow one operand to be reconstructed unambiguously from the result and the second operand. We call these functions reversible because they may be undone: the inputs may be reconstructed from the outputs. Other functions exhibit data-dependent reversibility.

So far so good. Let's continue.

For example, summing two numbers is reversible unless the sum produces an overflow. Multiplication is also reversible unless an overflow or underflow is produced; multiplying a number by zero is reversible if the result and the non-zero operand are saved.

Now this guy is speaking non-sense. Computers perform finite-domain computation with modulo integer arithmetic. It is well-known (at least to students who studied modern algebra) that addition modulo n has an inverse. Overflow (or underflow) merely means the result "wraps around" because of the modulo. Also, multiplication has inverse only under very specific conditions: (1) the set does not contain zero, and (2) any sequence of multiplication on elements in the set cannot give you multiples of n, which becomes zero after modulo. The unit group U(n) trivially satisfies these two conditions, and it has been shown that any other integer multiplicative groups must be isomorphic to an external product of two or more unit groups U(n₁) × U(n₂) × ... × U(n_k).

The point is, the author does not understand when multiplication is inversible. It then contradicts itself by saying:

And a few operations of interest in traditional programming languages and architectures, such as logical AND, are irreversible in the sense that the result and one operand are never sufficient to determine the second operand.

The thing is, any computer science student knows that logical AND is like multiplying two {0, 1} numbers; logical XOR is like adding {0, 1} modulo 2. Why does the author say that multiplication is reversible and goes on to say that logical AND is not? He fails even basic computer science.

You think MIT kids are smart? This guy writes gibberish on his master's thesis and graduated from MIT. He's smart. Anyway, the rest of the thesis seems to be designing an ALU based on these restricted operations (using exchange as opposed to load-store), something that sophomore year college students are asked to do.

I surely hope Pendulum is not state of the art for reversible computer. The idea surely sounds interesting, but I'd be very worried if these designers of computer architecture can't even grasp basic mathematical facts.