# Principles of Computer Architecture Dr. Mike Frank

Physical Limits of Computing Dr. Mike Frank CIS 6930, Sec. #3753X Spring 2002 Lecture #31 Reversible Processor Architectures Wed., Mar. 27

Administrivia & Overview Dont forget to keep up with homework! We are 10 out of 14 weeks into the course. You should have earned ~71 points by now.

Course outline: Part I&II, Background, Fundamental Limits - done Part III, Future of Semiconductor Technology - done

Part IV, Potential Future Computing Technologies - done Part V, Classical Reversible Computing Fri. 3/22: RevComp theory II: Emulating Irreversible Machines RevComp theory II: Bounds on Space-Time Overheads Mon. 3/25: RevComp scaling analysis I: Cost, energy, area-time.

Wed. 3/27: RevComp scaling analysis II: Spacetime and time. Fri. 3/29: Reversible processor architectures. Mon. 4/1: Reversible programming languages. Wed. 4/3: Reversible algorithms. Part VI, Quantum Computing - starts Fri. 4/5 Part VII, Cosmological Limits, Wrap-Up

Why reversible architectures? What about automatic emulation algorithms? E.g.: Ben73, Ben89, LMT, Frank02. Transform an irreversible alg. to an equiv. revble one. But, these do not yield the most cost-efficient reversible

algorithms for all problems! E.g., log(RE(i./r)/Ron/off) may be only 0.4 rather than 0.5. Finding the best reversible algorithm requires a creative algorithm discovery process! An optimally cost-efficient general-purpose architecture must allow the programmer to specify a custom

reversible algorithm that is specific to his problem. Reversibility Affects All Levels As Ron/off increases & cost of device manuf. declines (while the cost of energy stays high), Maximizing overall cost-efficiency requires an increasingly

large fraction of all bit-ops be done adiabatically. Maximizing the efficiency of the resulting algorithms, in turn, requires reversibility in:

Pro- gramming model

Logic design Functional units Instruction set architectures (unless a perfect emulator is found) Programming languages Increasing requirement High-level algorithms for degree of

reversibility All Known Reversible Architectures Ed Barton (MIT class project, 1978) Conservative logic, w. garbage stack Andrew Ressler (MIT bachelors thesis, 1979; MIT masters thesis, 1981) Like Bartons, but more detailed. Paired branches.

Henry Baker (1992) Reversible pointer automaton machine instructions. J. Storrs JoSH Hall (1994) Retractile-cascade-based PDP-10-like architecture. Carlin Vieri (MIT masters thesis, 1995) Early Pendulum ISA, irrev. impl., full VHDL detail. Frank & Rixner (MIT class project, 1996)

Tick: VLSI schematics & layout of Pendulum subset, w. paired branches Frank & Love (MIT class project, 1996) FlatTop: Adiabatic VLSI impl. of programmable reversible gate array Vieri (MIT Ph.D. thesis, 1999) Fully adiabatic VLSI implementation of Pendulum w. paired branches Reversible Programmable GateArray Architectures

(as of May 99) Photo of packaged FlatTop chip A Bouncing BBMCA Ball

A BBMCA Fredkin Gate Reversible von Neumann Architectures Reversible Architecture Issues Instruction-Set Architecture (ISA) Issues:

How to define irrev. ops (AND, etc.) reversibly? How to do jumps/branches reversibly? What kind of memory interface to have? What about I/O? How to permit efficient reversible algorithms? Should the hardware guarantee reversibility?

Microarchitectural issues: Register file interface

Reversible ALU operations Shared buses Program counter control The Trivial Cases Many typical instructions already reversible:

NOT a Set register a to its bitwise logical complement, a := ~a NEG a Set a to its twos complement negation

a := -a INC a or a := ~a + 1

Increment a by 1 (modulo 2). ADD a b Add register b into register a

(a := (a + b) mod 2) Exclusive-or b into a (a := a b) XOR a b

ROL a b Rotate bits in register a left by # positions given by b. The Nontrivial Cases Other common instructions are not reversible CLR a

Clear register a to 0. LD a b Load register a from addr. pointed to by b.

LDI a 3 Load immediate value 3 into register a. AND a b Set a to the bitwise AND of a and b

JMP a Jump to the instruction pointed to by a. SLL a b

Shift the bits in a left by b bits, filling with 0s on right. Irreversible Data Operations How to do expanding ops reversibly? E.g., AND a b - Prior value of a is lost. Approach #1: Garbage Stack approach.

Based on Landauers embedding. Push all data that would otherwise be destroyed onto a special garbage stack hidden from pgmr. Can unwind computation when finished to recover stack space. (Lecerf 63/Bennett 73 approach)

Problems: Large garbage stack memory needed. Limits computation length. Leaves programmer no opportunity to choose a more efficient reversible algorithm! Illustrating Garbage Stack

Let mean reversible move, mean reversible copy, a reversible uncopy. AND a b Garbage Stack Memory (GSM)

implemented by... 1. t a 2. a t & b 3. t GSM[GSP++] Garbage Stack

Pointer (GSP) 3 230 0 46 1 17 2 0 3

0 4 ... Programmer-Controlled Garbage Put extra data in a programmer-manipulable location.

What if destination location isnt empty? Signal an error, or Use an op that does something reversible anyway Provide undo operations to accomplish unexpanding inverses of expanding ops.

1st method: Errors on non-empty destination: AND A B C -If (A=0) AB&C else error UNAND A B C -If (A=B&C) AB&C else error 2nd method: Use always-reversible store ops.

ANDX A B C - A A (B & C) (self-undoing!) Pendulum - packaged chip photo

## Recently Viewed Presentations

• Can get levels on any anti-seizure medication to assure therapeutic range. CBC, CMP and drug levels every 3 months. Toxicity effects. Marked lethargy/somnolence ... a thorough history needs to be taken before any agent should be started. Heart disease (personal...
• Power Monitoring and Control System for NEPTUNE Ting Chan Advisor: Chen-Ching Liu The Goal The goal of the NEPTUNE project is to establish a regional ocean observatory in the northeast Pacific Ocean.
• The Zener Diode * Zener diode. is designed for operation in the reverse-breakdown region. * The . breakdown voltage. is controlled by the doping level (-1.8 V to -200 V). * The major application of Zener diode is to provide...
• Disclosure Generic drug names are identified in this presentation. Their corresponding Brand name is also identified. This was done to enhance recognition of vaccine information and appeal to a non-pharmacist audience
• in fact, a presentation like a powerpoint is really for the audience, and i am really tired of writing anything down right now. i imagine that most of you will probably have stopped reading this anyway. a presentation should include...
• Memory comparison Type Size Access time Cost per MB CPU registers 256 bytes 1 ns N/A Cache 64 KB 2 ns \$ 20 RAM 512 MB 50 ns \$ 0.20 Disk 200 GB 100,000 ns \$ 0.0002 Numbers are approximate....
• I also changes the way in which we announce WG meetings. From this meeting forward all WG meetings will be submitted to the FGDC.gov/calendar for posting. All attempts will be made to have the posting five days prior to the...
• * Contextual Analysis Contextual Analysis continued Steps for instruction Identify the unknown word Look within the sentence to located possible clues definition, synonym, antonym, example, and general If necessary, look in the sentence just before and just after the sentience...