C.H. Bennett July ’02BrownianComputingCharles H. Bennett IBM Research Yorktown MIT 10 May 06and thethermo-dynamicsof computing1 Freeman Dyson2 Gregory Chaitin3 James Crutchfield4 Norman Packard5 Panos Ligomenides6 Jerome Rothstein7 _ Hewitt?8 Norman Hardy9 Edward Fredkin10 Tom Toffoli11 Rolf Landuaer12 J. Wallmark13 Frederick Kantor14 David Leinweber15 Konrad Zuse16 Bernard Zeigler17 Carl Adam Petri18 Anatol Holt19 Roland Vollmar20 Hans Bremerman21 Donald Greenspan22 Markus Buettiker23 Otto Floberth24 Robert Lewis25 Robert Suaya26 _ Kugell27 Bill Gosper28 Lutz Priese39 Madhu Gupta30 Paul Benioff31 Hans Moravec32 Ian Richards33 Marian Pour-El34 Danny Hillis35 Arthur Burks36 John Cocke37 George Michael38 Richard Feynman39 Laurie Lingham40 _ Thiagarajan41 ?42 Gerard Vichniac43 Leonid Levin44 Lev Levitin45 Peter Gacs46 Dan Greenberger1981 Conference on Physics of Information (MIT Endicott House)Practical Theoretical CosmicMy level of ExpertiseHeat managementin real computersLandauer’s PrincipleReversible ComputationBrownian ComputersAsymptotic scalability of computing, Thermodynamics and complexity in the Universe Heat generation is a serious problem in today’s computers, limiting packing density and therefore performance. Combat it by:• Making gates less dissipative, even if slower, can sometimes increase performance FLOPS/watt, while reduced clock speed is offset by increased parallelism (e.g. BlueGene/L)• Dynamic Power Management—switching off clock where not needed or to let a hot region cool down. • Resonant clock to reduce ½ CV2 losses from non-adiabatic switching (see Michael Frank’s talk)• Thicker gates to reduce gate leakage current• More conductive materials to reduce I2R resistive lossesƒƒIR images clearly indicate significant reduction in IR images clearly indicate significant reduction in power consumption and temperature rise due to DPM.power consumption and temperature rise due to DPM.Dynamic Power Management Dynamic Power Management in IBM Power5 (GR) microprocessor, in IBM Power5 (GR) microprocessor, ƒƒA random test generator and exerciser program is A random test generator and exerciser program is run in Single Thread (ST) and Simultaneous Multiple run in Single Thread (ST) and Simultaneous Multiple Thread (SMT) mode with and without Dynamic Power Thread (SMT) mode with and without Dynamic Power Management (DPM).Management (DPM).see demo this afternoon by Maurice McGlashan-Powell1 GHzSMT_noDPM1v05, 42.9A, 77C1GHzSMT_DPM1v05, 28.4A, 54C1 GHzST_noDPM1v05, 42.2A, 73.5C1 GHzST_DPM1v05, 26.7A, 51C"Information is Physical" Rolf Landauer "It from bit" John Archibald WheelerWhen Turing, Shannon, von Neumann and their contemporaries formalized the notions of information and computation, they left out notions of reversibility and quantum superposition reversibility => thermodynamics of computationsuperposition => quantum information/computation theory. MathematicsPhysical WorldComputational resources required to simulate physical states and evolutions(It from Bit: Involvement of information in the very origin of physical reality.) Physical (e.g. thermodynamic) resources required for computation and communicationabaa XOR baabbcc XOR(a AND b)XOR gateToffoli gateConventional computer logic uses irreversible gates, eg NAND, but these can be simulated by reversible gates. Toffoli gate is universal. Reversible logic was used to show that computation is thermodynamically reversible in principle. Later needed forQuantum Computationself-inverseNAND gateabNOT(a AND b)no inverseaFanoutThermodynamics of Computation• Landauer’s Principle: each erasure of a bit, or other logical 2:1 mapping of the state of a physical computer, increases the entropy of its environment by k log 2.• Reversible computers, which by their hardware and programming avoid these logically irreversible operations, can in principle operate with arbitrarily little energy dissipation per step. Avatars of the Second Law of ThermodynamicsNo physical process has as its sole result is the conversion of heat into work.It is impossible to extract work from a gas at constant volume if all parts are initially at the same temperature and pressure.It is impossible to see anything inside a uniformly hot furnace by the light of its own glow.No physical process has as its sole result the erasure of information.Looking inside apottery kilnby its own glowby external lightOrdinary irreversible computation can be viewed as an approximation or idealization, often quite justified, in which one considers only the evolution of the computational degrees of freedom and thus neglects the cost of exporting entropy to the environment.• Practice for quantum computing• Improving the thermodynamic efficiency of computing at the practical ½ CV2level (rather than the kT level)• Understanding ultimate limits and scaling of computation and, by extension, self-organizationWhy study reversible classical computing, when Landauer erasure cost is negligible compared to other sources of dissipation in today’s computers?Classification of Computers from thermodynamic viewpointA. Irreversible (eg. PC, Mac…)B. Reversible1. Ballistic (e.g. Billiard ball model) dynamical trajectory isomorphic to desired computation 2. Brownian (e.g. RNA polymerase) random walk in a low-energy labyrinth in configuration space, isomorphic to desired computation 3. Intermediate, like walk on a 1d lattice with mean free path >1 (e.g. Feynman’s quantum computer)aba AND ba AND NOT ba AND bb AND NOT aThe chaotic world of Brownian motion, illustrated by a molecular dynamics movie of a synthetic lipid bilayer (middle) in water (left and right)dilauryl phosphatidyl ethanolamine in waterhttp://www.pc.chemie.tu-darmstadt.de/research/molcad/movie.shtmlKinds of computation graph for Brownian computersForward direction ofIntended computationExtraneous predecessorsPotential Energy Landscape for Brownian ComputerInitial state Intended successorExtraneous (error) stateE0EeError probability per step is approx. exp [ (E0 -Ee) / kT]Error correction is logically many-to-one, so it has a thermodynamic cost, by Landauer’s principle. Conversely, and less obviously, a system’s “desire” to make errors is itself a thermodynamic driving force that can be partly harnessed to reduce the cost of correcting the errors. Proofreading in DNA ReplicationPolymerase (1) tries to insert