The MIT Reversible Computing Project: Personnel

Present group members: • Tom Knight - PI

• Norm Margolus - physics & computation, cellular automata

• Grad students:

– Carlin Vieri - circuits, reversible RISC

– Michael Frank - algorithms & analysis

– Matt Becker - power supplies

– Josie Ammer - layouts, A/D converter

– Raissa D’Souza - reversible CA models of physics

• Undergraduates:

– Matt DeBergalis - simulators, tools

Past group members: • Saed Younis (now @ Qualcomm) - reversible logic circuit family (SCRL)

Collaborators:

• ISI: Amory Wakefield, Lars Svensson, Bill Athas – Partially reversible circuits for near-term low-energy applications

The MIT Reversible Computing Project: Major Accomplishments to Date

Reversible circuits:

• SCRL circuit technique

• Transmission line power supplies

• Test chips: 4×4 multiplier, systolic array, memory

Full reversible RISC architecture: • Verilog simulation

• Standard CMOS implementation

• ISA simulators

• Assembler, compiler

• Test programs

Theory of reversible computing: • Space/time complexity of reversible algs

• Efficient physical simulations

Engineering analysis:

• Power/speed/cost tradeoffs

• Accounting for leakage

• Scaling laws for reversible 3-D arrays

Motivation for this work

• Efficient computing is valuable for society/economy.

• Important for future of computing:

– Understand physical constraints on computation.

• A goal for theory & engineering:

– Compute as efficiently as possible, within constraints.

• Near-term applications:

– More efficient computing in constrained situations.

• Long-term application:

– Focus engineering to approach limits more quickly/closely.

Reversible computing—The basic story:

• Irreversible computers are thermodynamically crippled.

– Microscopic physics is reversible.

– Information/entropy cannot be destroyed.

– Normal computers constantly “erase” bits.

– Really, discarded bits just become entropy.

– Remove entropy, or computer will melt.

– Entropy removal rates are bounded per area.

– So processing rates are also.

• Reversible computing to the rescue!

– Can compute without discarding bits.

– Instead, can uncompute leftover data.

– Yields arbitrarily lower entropy generation per operation.

– Arbitrarily higher rate of computation per unit area.

– Can pack computing elements more densely in 3-D.

– Communication delays are lower.

– Overheads for reversibility are superseded by benefits.

– Overall: large computers are faster if reversible!

Overview of Contents

• Motivation & History

• Fundamentals – Physical limits on computation

– Reversible computing theory

– Scaling of physical machines

• Engineering – Adiabatic logic circuits

– FlatTop reversible mesh processor – Future device technologies

– Programming reversible machines • Conclusion & Future work

History of Related Research

• Early thermodynamics of computation:

– von Neumann ’49, Landauer ’61.

• Reversible models of computation:

– Lecerf ’63, Bennett ’73, Fredkin and Toffoli (’70’s and ’80’s).

• Efficient reversiblizations:

– Bennett ’89, Levine/Sherman ’90, Lange/McKenzie/Tapp ’94.

• Exotic reversible logic devices:

– Bennett ’73, Fredkin ’82, Likharev ’82, Drexler ’92, Merkle ’96.

• Reversible electronics:

– Watkins ’67, Fredkin/Toffoli ’78, Seitz ’85, Koller/Athas ’92, Younis/Knight ’93, many others …

• Physics and scalability:

– Vitányi ’88, Bilardi/Preparata ’93, Smith ’95.

Physical limits on computation

• Information propagation velocity ≤ c.

• Various theoretical/practical limits on density of entropy/information.

• Information flux limits: follow from above.

• Connectivity limits, due to 3-dimensionality of space.

• Quantum limit on rate of state transitions.

– (Margolus & Levitin ’96)

• Thermodynamic minimum energy dissipation for bit era-

sure.

– (Laundauer ’61)

Reversibility of Physics

• The dynamical equations of mechanics are time-symmetric and forward-deterministic, thus also reverse-deterministic.

• True in classical mechanics, QM, QED, GR, etc.

• Example: Schrödinger equation of quantum mechanics:

−\frac{ℏ^{2}}{2} ∑_{j=0}^{N−1} \frac{1}{m_{j}} \frac{∂^{2}}{∂x_{j}^{2}}Ψ(x⃗, t) + V(x⃗, t)Ψ(x⃗, t) = iℏ\frac{∂}{∂t}Ψ(x⃗, t).

A differential equation determining how Ψ changes with time— in either time direction.

Why entropy increases

9

Venn diagram of types of information/entropy

• Any closed system with finite energy and volume has a finite maximum entropy S_{max}. (Although if volume increases, S_{max} may also.)

• Out of this, the bits that are uncorrelated, or whose correlations have been lost, are entropy. Other bits can be considered “free memory” or negentropy.

• In general some bits of a system are manipulable by us, some not. Some manipulable bits may also be entropy.

Various limits on entropy density for meter-scale objects

Limit

Material  in b/Å^{3} Caveats
Black hole  4.14×10^{39} Need mass ≈ Saturn;

can’t get info. out!

Non-BH  1.53×10^{22} Requires nearly as

much mass.

Normal density ∼ 3×10^{5} May require billion-degree

temperatures.

Atomic matter ∼ 1–10 Hand-waving estimate.

Summary of physical limits on computation

Quantity  Symbol Limit
Info. propagation speed v ≤ c ≈ 3 × 10^{8} m/s
Information density  ρ_{S} ≲ 1–10 b/Å^{3} ??
Information flux  F_{S} ≤ ρ_{S}v
Rate of state change  ν_{⊥} ≤ 4(E − E_{0})/h
Diss. per bit erased  ΔE ≥ k_{B}T ln 2

• Some bound on ρ_{S} exists, but its value is uncertain.

Shor’s algorithm: Initial preparation

• Number to factor is N = 33.

• Range of exponents to compute (mod N) goes up to q = 256 (ideally 2048).

• Register a is put into an equal superposition of all values 0 to q − 1.

• Register b is initially 0.

Shor state after classical exponentiation

14

Shor state after quantum Fourier transform

15

Ordinary CMOS inverter

16

CMOS inverter dynamic behavior

17

Energy dissipation in irreversible switching

Energy supplied: E_{supp} = QV = CV^{2}.

Energy stored: E_{stor} = ∫ dE = ∫ v dq = ∫ \frac{q}{C} dq = \frac{1}{C} ∫_{0}^{Q} q dq

= \frac{1}{C} \frac{1}{2}q^{2}|_{q=0}^{Q} = \frac{1}{2C} Q^{2} = \frac{1}{2C} (CV)^{2} = \frac{1}{2}CV^{2}.

Energy dissipated: E_{diss} = E_{supp} − E_{stor} = CV^{2} − \frac{1}{2}CV^{2} =

\frac{1}{2}CV^{2} .

Reliability bound on CV^{2}

\frac{1}{2}CV^{2} ≥ k_{B}T ln N

where N is desired # ops btw. errors

• Provable from basic thermodynamics.

• Necessary to avoid logic errors due to thermal (“kT/C”) noise.

• Applies to both irreversible & reversible circuits.

• Difference is:

– In reversible circuits, this energy need not be dissipated.

Charging with constant current

E_{diss} = ∫ p dt = ∫ i^{2}R dt = I^{2}RT = (\frac{Q}{t})^{2} Rt
= \frac{Q^{2}}{t}R = \frac{(CV)^{2}}{t}R = CV^{2} \frac{RC}{t} .

Controlled reversible charging in CMOS

• Approximate current source by voltage ramp.

• Replace resistor with a MOSFET (semiconductor transistor).

• Must have V < V_{G} − V_{T}.

• Can be discharged by a similar ramp.

t ≫ RC : E_{diss} → CV^{2} \frac{RC}{t}
t ≪ RC : E_{diss} → \frac{1}{2}CV^{2}

Voltage curves for slow and fast charging

• (a) Slow charging: Load lags behind power supply by a small voltage drop V_{ds} across the transistor, which scales with 1/t_{r}.

• (b) Fast charging: Load approaches supply level in exponentialdecay fashion. Most charge is delivered from a voltage of V_{dd}.

SCRL inverter

23

SCRL generalized inverter

• There may be several input signals.

• Uses complementary pull-up and pull-down networks like standard static CMOS.

• Schematic icon labeled with function computed and clock phase.

SCRL bidirectional latch

25

SCRL pipeline

• Each stage may be many gates in parallel, considered as an n-input, m-output invertible Boolean logic function.

• Reverse stages uncompute the inputs to forward stages.

• Each stage has its own clock phase, until repeat.

• A stage may use 2 nested levels of gates to compute noninverting functions.

• Sequential circuits with feedback fine, if phases aligned properly.

Timing diagram for 3-phase SCRL

27

Simplified SCRL circuit model

28

A problematic case for the original SCRL

• Inner n-FET asked to pass a high voltage.

• Barely turns off as inner node voltage approaches threshold.

• V_{x} crawls up by several ϕ_{T} s over a substantial voltage drop.

• In numerical experiments, dissipation was still ∼ 3000 k_{B}T in this case, when other dissipations were < k_{B}T.

• This dissipation not eliminated unless circuit so slow that leakage dominates.

Fixing the problem case

• Add p-FET to pulldown network, as shown.

• Interior node now tracks all the way to V_{dd}.

• General solution: use dual-rail logic and transmission gates everywhere.

Scaling of energy/op in SCRL with speed, given nonzero leakage

Optimum t_{r} ∝ C_{L}\sqrt{\frac{V_{T0}}{kP_{lk}}}, E_{min} ∝ C_{L}\sqrt{\frac{V_{T0}P_{lk}}{k}}.

The Billiard Ball Model of computation

Idealized “billiard balls” bounce of walls & each other in digitallyprecise trajectories. (Fredkin & Toffoli, ’82)

• Extremely simple.

• Reversible.

• Universal.

– Efficiently simulates arbitrary 2-D reversible cellular automata or reversible circuits.

– Extensible to 3-D.

Flattop analysis

• Estimated room-T minimum energy/op.

• 10 fJ/cycle/cell.

• iCMOS estimated at 20pJ.

• Factor of 2000 energy savings!

• Optimal cycle time: 12μs (83 kHz)

The BBM cellular automaton (Margolus ’88)

• Updated in 2 alternating, overlapping partitionings of array into 2×2 blocks of cells. (“Margolus neighborhood.”)

• Each block updated independently & reversibly.

Boolean logic form of BBMCA update rule

• Simplest logic found to date (in terms of # transistors).

• Computed in two logic levels: first for S, and second for A’,B’,C’,D’.

Grid of FlatTop processing elements

• Each 2×2 block of cells handled by one PE.

• PE visualized at center of each block.

• Cell state passed between diagonally adjacent PEs.

• PE mesh oriented 45^{∘} to cell grid.

• Chip edges chosen parallel to PE mesh.

• Implements two non-interacting BBMCA systems.

Block diagram of a FlatTop processing element

• Note 3 SCRL stages proceeding left to right.

• First stage computes S.

• 2nd stage updates the 4 cells.

• Third stage uncomputes S (and handles initialization).

Icon for a single FlatTop cell

• Mnemonic graphic evoking CA functionality

One corner of an array of FlatTop PEs

• PE icons overlap each other at corners

• Note some edge cells go to pads, others wrap around • Initialization/readout path at upper left.

The full 20×20 array of PEs

40

FlatTop stage 1 logic gate

41

FlatTop stage 2 logic

42

Layout of a FlatTop PE

• 0.5 μm process (HP14)

• ∼ 300 transistors

• ∼ 170 μm × 90 μm

PISA instruction set: simulator/compiler version

Key:
rsd,rt = 5-bit register identifier.
  No-Op if rsd is same reg as rt.
imm,amt = 16 bit signed immediate
  [imm] = imm sign-extended to 32 bits
"Non-expanding" arith./logical operations:
Mnem.   Args.      Forwards behavior
-----   ---------  ---------------------
NEG     rsd        rsd = -rsd
ADD     rsd,rt     rsd += rt (mod 2^32)
ADDI    rsd,imm    rsd += [imm] (mod 2^32)
SUB     rsd,rt     rsd -= rt (mod 2^32)
XOR     rsd,rt     rsd ^= rt
XORI    rsd,imm    rsd ^= [imm]
RL      rsd,amt    rsd = rsd rol amt
RLV     rsd,rt     rsd = rsd rol rt
RR      rsd,amt    rsd = rsd ror amt
RRV     rsd,rt     rsd = rsd ror rt

PISA instruction set, cont’d.

Key:
rd,rs,rt = 5-bit register identifier.
  No-Op if rd is same reg as rs or rt.
imm,amt = 16 bit signed immediate
  [imm] = imm sign-extended to 32 bits
"Expanding" arith./logical operations:
Mnem.   Args.      Forwards behavior
-----   ---------  ---------------------
ANDX    rd,rs,rt   rd ^= rs&rt
ANDIX   rd,rs,imm  rd ^= rs&[imm]
NORX    rd,rs,rt   rd ^= ~(rs|rt)
ORX     rd,rs,rt   rd ^= rs|rt
ORIX    rd,rs,imm  rd ^= rs|[imm]
SLLX    rd,rs,amt  rd ^= rs<<amt
SLLVX   rd,rs,rt   rd ^= rs<<rt
SLTX    rd,rs,rt   rd ^= (rs<rt)?1:0
SLTIX   rd,rs,imm  rd ^= (rs<imm)?1:0
SRAX    rd,rs,amt  rd ^= rs>>amt
SRAVX   rd,rs,rt   rd ^= rs>>rt
SRLX    rd,rs,amt  rd ^= (unsigned)rs>>amt
SRLVX   rd,rs,rt   rd ^= (unsigned)rs>>rt

PISA instruction set, cont’d.

Key:
rd,ra,rb = 5-bit register identifier.
off = 16 bit signed offset
loff = 26 bit signed offset
dir = +1/-1 bit where +1=forward, -1=reverse
BR = internal "branch register"
Branch instructions:
BEQ     ra,rb,off  if ra=rb, BR+=off*dir
BGEZ    rb,off     if rb>=0, BR+=off*dir
BGTZ    rb,off     if rb>0, BR+=off*dir
BLEZ    rb,off     if rb<=0, BR+=off*dir
BLTZ    rb,off     if rb<0, BR+=off*dir
BNE     ra,rb,off  if ra!=rb, BR+=off*dir
BRA     loff       BR+=loff*dir
RBRA    loff       dir=-dir, BR+=loff*dir
SWAPBR  r          r<->BR
PC update between instructions:
  if (BR=0) pc+=dir else pc+=BR*dir
Memory & I/O instructions:
EXCH    rd,ra      rd <-> mem[ra]
READ    ra         ra ^= next word from input str.
TAKE    ra         ra <-> next word on I/O stream
SHOW    ra         Copies ra to output stream.
EMIT    ra         Emit ra to garbage stream.

Reversible and irreversible machine configuration graphs

• Out-degree is always no more than 1 (determinism).

• Reversible in-degree is also no more than 1 (reversibility).

• Reversible configuration graph consists of disjoint loops and chains, which may be infinite (if the configuration space is infinite).

Reversible algorithms

• Sorting n items:

– Generates Θ(log n!) garbage in worst case.

– Hall ’94 reversible insertion sort achieves this in time n^{2}.

– Quicksort & other Θ(n log n) time sorts can be made reversible with no slowdown and Θ(n log n) garbage

– Radix sort (time Θ(n)): no slowdown and Θ(n) garbage.

• Arithmetic on n-bit integers. – Addition or subtraction: time Θ(n), zero garbage.

– Multiplication: Θ(n^{2}) grade-school alg. with no slowdown & no garbage except operands.

∗ Can often eliminate 1 op by division.

∗ Can sometimes eliminate both ops by factoring.

– Naive Θ(n^{3}) matrix multiplication algorithm also w. no slowdown & no garbage.

– Matrix inversion to eliminate 1 operand.

Reversible algorithms, cont’d.

• Search algorithms:

– Breadth-first or depth-first search with no increase in time or space & no garbage.

• Graph problems on n nodes:

– All-pairs shortest path: Floyd-Warshall alg. takes time Θ(n^{3}), space Θ(n^{2}).

– Naive reversible version seems to take space Θ(n^{3}).

– Alternative “matrix squaring” alg.: reversible time Θ(n^{3} log n), space Θ(n^{2} log n). (Leighton)

– Illustrates that the best rev. algs. may have a very different structure from the best irrev. algs

– Algorithm designer must be aware of machine’s reversibility.

• Physical simulations (Margolus, D’Souza, others): – Reversible models of physics have no overhead, good stability.

– Reflect underlying reversibility of physics.

– Example: Schrödinger wave simulation.

Traditional reversible computing theory—Results

Results in the traditional theory context:

• Reversible machines are universal and can sim. irrev. machs.

in linear time. (Save a history.)

– (Landauer ’61)

• History can be uncomputed, leaving no output.

– (Lecerf ’63)

• Desired output can be copied before reversing

– (Bennett ’73)

• Above results extend to parallel models, including cellular

automata and boolean circuits

– (Toffoli ’77, Toffoli & Fredkin, ’80-’82)

• Irrev→rev translation w. polynomial time increase & log-

arithmic space increase.

– (Bennett ’89)

• Linear-space simulation (w. exponential time increase) also

possible.

– (Lange et al. ’97)

• Linear space & time simulation is probably impossible – (Frank & Ammer ’97)

Reversible simulation in linear space

• Lange, McKenzie, Tapp (1997).

• We can reversibly iterate through possible predecessors of an irreversible machine configuration.

• Use this for an “Euler tour” of irreversible machine’s entire configuration tree (above).

• Though tree has branches, traversal around entire tree is reversible.

• Cut off search wherever space limit is exceeded.

• Space requirement: just initial state (O(S)) plus current state (O(S)).

• Time for search is O(2^{S}).

• Correct space limit can be found by successively trying higher and higher bounds until final state is found. (My own contribution.)

Reversible vs. irreversible space-time complexity

Ignoring thermodynamic issues, how efficiently can reversible machines simulate irreversible machines?

• Bennett ’73: Linear time, but polynomially greater space.

• Lange et al. ’97: Linear space, but exponentially greater time.

• Important open question: Is there a single simulation technique that takes only linear space and only linear time? (∀ S, T: RST(S, T) = ST(S, T))?

• Frank & Ammer ’97: Any such technique would fail if you: – Add a (computable) reversible oracle.

– Or, provide input in the form of a reversible ROM

(whose size you don’t count).

• Remember: this negative result is in the context of traditional models of computation, which ignore the potential algorithmic costs of entropy generation.

Elements of Frank-Ammer ’97 proof:

• Initial insight: traversing a singly-linked list seems hard to do reversibly.

• Provide links in the form of an oracle or a ROM, mapping (node) ↔ (node +

successor).

– Individual oracle/ROM calls are reversible & easy to undo.

– Hard part is forgetting nodes previously visited.

– Analogy w. reversible computation of a 1-way cryptographic function (invertible, but hard to invert).

• Choose a chain of nodes that is algorithmically incompressible.

– Can be proven to exist.

– Specified by diagonalization over all possible machines.

• Show that if a reversible machine can traverse this chain (using much less space

than Bennett ’89, and much less time than Lange et al.’97) then:

– You can reconstruct previous nodes in the chain from a given machine state, by running the machine in reverse.

– Provides a way to compress the chain. (Contradiction.)

• Uses Li & Vitányi ’96 result that Bennett ’89 is space-optimal among a certain class of reversible simulation techniques.

Structure of permutation oracles

54

Encoding outdegree-1 directed graphs in permutation oracles Problem graph defined by our oracle

56

Bennett’s optimal reversible pebble game strategy Triangle representation of oracle queries

58

Visualizing the definition of the set of pebbled nodes A worthwhile goal for Computer Science:

Develop & study ultimate models of physical computation

Such a model should: • Be physically realizable.

• Accurately model physical constraints affecting asymptotic scaling behavior (time & space requirements).

• Given that, scale as well as possible.

Benefits of model:

• Basis for designing efficient, scalable computers.

• Unchanging framework for algorithms design.

Physical constraints shape the ultimate model

Constraint  Implications for model
Speed-of-light limit  Locally-connected mesh

(Vitanyi ’88)

3-Dimensionality of space 3-D connectivity

Entropy density limits Finite state per processor / finite information flux

Micro-reversibility / 2^{nd} law of thermo.

Reversible logic / entropy accounting

Reversible logic devices

• Logically reversible:

– Post-state determines pre-state.

• Asymptotically physically reversible:

– Entropy per op typically proportional to speed. S = k_{S}f = k_{S}/t_{op}.

– Entropy rate quadratic in speed. S/t_{op} = k_{S}/t_{op}^{2}.

• Many technologies achieve this behavior. – But entropy coefficient k_{S} varies widely.

– No known fundamental lower bound on k_{S}.

– If k_{S} = 0 is possible, we don’t know how yet.

Spreading things out

• How does performance scale with the number of processors?

• If algorithm requires sufficiently little communication: – Use irreversible processors spread in a 2-D layer.

– Can remove entropy along perpendicular dimension.

– No speed advantage to reversibility.

– Still, reversible machine dissipates less energy.

• If alg. requires local communication,

latency ∝ cycle time, then for an N × N × N array: – Reversible machine still asymptotically faster!

– Irreversible t = Θ(\sqrt[3]{N})

– Reversible t = Θ(\sqrt[4]{N})

– Reversible advantage of Θ( \sqrt[12]{N})

∗ 10^{36}× more processors to increase rev. advantage by 10×!

Best irreversible machine for 3-D array computations A faster reversible machine for 3-D array

simulations “Folding” a column of processors to

minimize volume

Further scaling results

• Fully ballistic machines:

– Full use of 3rd dimension.

– Faster per unit area than irr. by Θ(d).

– Faster in 3-D mesh by Θ(N_{D}^{1/3}).

• Longer communication distances:

– Θ(\sqrt{N_{D}}) distance best for rev. advantage

– Reversible speedup Θ(N_{D}^{1/6}).

• Reversible simulation of irreversible arrays: – Run Bennett alg. for limited #steps.

– Θ(log N_{D}) processor size. (Approximate as Θ(1).)

– Reversible speedup of Θ(N_{D}^{\frac{1}{12}−ϵ}), for any constant ϵ > 0.

∗ Optimal ϵ varies w. N_{D}.

Summary of scaling results

Cost in each model  Advantage factors
Cost  FIA  TPRA  BRA  Reversible  Ballistic
measure  Task type  ($_{i})  ($_{r})  ($_{b})  A_{r} = $_{i}/$_{r}  A_{b} = $_{i}/$_{b}
$ = S  any  N_{ops}  n_{in}  n_{in}  N_{ops}/n_{in}  N_{ops}/n_{in}
$ = T  no comm.  1  1  1  1  1
local comm.  N_{D}^{1/3}  N_{D}^{1/4}  1  N_{D}^{1/12}, $_{r}^{1/3}  N_{D}^{1/3}
\sqrt{N_{D}} comm.  N_{D}^{2/3}  N_{D}^{1/2}  N_{D}^{1/2}  N_{D}^{1/6}, $_{r}^{1/3}  N_{D}^{1/6}, $_{b}^{1/3}
$ = AT  no comm.  N_{ops}  N_{ops}^{5/6}  N_{ops}^{2/3}  N_{ops}^{1/6}, $_{r}^{1/5}  N_{ops}^{1/3}, $_{b}^{1/2}
$ = VT ,  no comm.  N_{D}^{3}  N_{D}^{3}  N_{D}^{3}  1  1
MT ,  local comm.  N_{D}^{3+1/3}  N_{D}^{3+1/4}  N_{D}^{3}  N_{D}^{1/12}, $_{r}^{1/39}  N_{D}^{1/3}, $_{b}^{1/9}
…, $_{c}  \sqrt{N_{D}} comm.  N_{D}^{3+2/3}  N_{D}^{3+1/2}  N_{D}^{3+1/2}  N_{D}^{1/6}, $_{r}^{1/21}  N_{D}^{1/6}, $_{b}^{1/21}

Projections for present & future technologies

Rough estimates based on above scaling results, with actual constant factors included, for several technologies.

• Present/near-future VLSI, w. ordinary cooling:

– Circuits w. ≳ a few hundred layers are faster per area if reversible.

– A 1 m^{3}, 1 MW rev. machine could do ∼ 24 PetaFLOPS (vs. 1 PetaFLOPS in a superconductor-based irrev. design).

– Above a $25 billion cost level, rev. machines become

faster/processor at some problems.

• Various nano-scale reversible technologies, w. aggressive

cooling:

– Faster/area than best possible irrev. tech. if thickness > microns to millimeters.

Entropy transport / cooling technologies

Technology Max entropy

flux F, (\frac{bit}{sec · cm^{2}})

1 Tb/s optic fiber

10 μm thick ∼ 10^{18}

Passive emission 100 W/cm^{2} T ≥ 300K

≤ 3.5 × 10^{22}

Tuckerman microcapillaries ∼ 1 kW/cm^{2}

∼ 3 × 10^{23}

Drexler fractal nano-plumbing ∼ 10 kW/cm^{2}

∼ 3 × 10^{24}
1 bit/Å^{3} @ 1 m/s  10^{26}
1 bit/Å^{3} @ .1 c  3 × 10^{33}

These are also approximately the limits on irreversible processing rates, in bit-ops/sec-cm^{2}.

Entropy generation in irreversible device technologies

Entropy (bits)

Technology  per bit erased
.5μm CMOS @ 300K  ∼ 10^{8}
best CMOS today  ∼ 10^{6}

Likharev RSFQ

10^{−18} J @ 5K 2 × 10^{4}

Lowest possible  1

Entropy coefficients of reversible device technologies

Technology Entropy coefficient k_{S} (bits/GHz)

SCRL today  ∼ 10^{9}

optimistic reversible CMOS

∼ 10^{5}
Merkle Quantum FET  ∼ 1.2
Nano-rod logic  ∼ 0.07

Likharev parametric quantron

∼ 0.025
Helical logic  ∼ 10^{−5}

Scales above which reversible computing wins

Irrev. device / cooling tech.

Reversible Technology CMOS/ passive RSFQ/ capillaries

perfect/ 1 bit/Å^{3} @ 1 m/s

SCRL today 0.2 mm 50 m  4 a.u.
Quantum FET any  any  1 mm
Rod logic  any  any  3 μm
Helical logic  any  any  < 1mm

Summary of major contributions

• Itemization of various physical constraints on computation.

• In models ignoring therodynamics, reversibility seems asymptotically sub-optimal (result with Ammer).

• Proposed the study of ultimate (physically optimal) models of computation.

• Presented the reversible 3-D mesh (with irreversibility at edges).

• Conjectured some form of R3M is an asymptotically optimal model.

• In physically realistic models, TP-reversible machines are faster per unit area, by \sqrt{d}.

• Also, faster per processor by a factor of N_{D}^{1/12} or even N_{D}^{1/6}.

• No logical barriers to designing a reversible mesh processing element using conventional semiconductor tech.

• Future reversible devices projected to be highly advantageous for supercomputing at reasonable scales.

• To attain optimal efficiency, reversibility must be exposed at the algorithms level.

• Reversible instruction sets and programming languages are straightforward.

• Good reversible algorithms are different, but not significantly more difficult to design.