6.111 Lecture 161. Power dissipation in CMOSProblem: Energy CapacityDynamic Energy DissipationIntel Pentium 4 Thermal Guidelines2. The Physics of ComputationBilliard ball model of computationThe Fredkin GateThe Fredkin GateThe Fredkin GateThe Fredkin Gate3. Reversible ComputationUncomputingIrreversibility => Energy DissipationIrreversibility => Energy Dissipation4. Fault Tolerant ComputationFault-Tolerant CircuitsFault-Tolerant CircuitsTeramac: “Defect tolerant” FPGA ArrayThe Quantum LimitQuantum BitsQuantum BitsSummary6.111 Fall 2005 Lecture 15, Slide 1Today: Power Dissipation, Reversible Computing, and Quantum Computation1.Power dissipation: CMOS2.Physics of computation3.Reversible computation4.Fault tolerance5.Quantum computation6.111 Lecture 166.111 Fall 2005 Lecture 15, Slide 21. Power dissipation in CMOS• Moore’s law: # of transistors/chip doubles every ~18 months• Exponential rise in power dissipation!6.111 Fall 2005 Lecture 15, Slide 3Problem: Energy Capacity• No Moore’s law for batteries!• Today: Understand where power goes, fundamental limits on power consumption in computation, and frontiers in new approaches to computation6.111 Fall 2005 Lecture 15, Slide 4Dynamic Energy Dissipation6.111 Fall 2005 Lecture 15, Slide 5Intel Pentium 4 Thermal Guidelines6.111 Fall 2005 Lecture 15, Slide 62. The Physics of Computation•Q: What is the minimum energy dissipation necessary for computation?•A: kBTlog 2per operation - J. von Neumann 1949R. Landauer, "Irreversibility and heat generation in the computing process," IBM Journal of Research and Development, vol. 5, pp. 183-191, 1961. J. von Neumann, Theory of Self-Reproducing Automata, Univ. of Illinois Press, 1966.In Out00 001 010 011 1•AND gate:This is irreversible!Landauer’s Principle:Energy Dissipation comes from irreversibility6.111 Fall 2005 Lecture 15, Slide 7Billiard ball model of computation(Feynman, Optics News V11 p11, 1985)(Bennett, IBM J. Research and Dev, V6, p525, 1973)Billiard ball collisions may be used to build logic gates• Billiard balls obey classical Newtonian equations of motion, and thus follow perfectly reversible trajectories.XYXYXYXYXYXYXYXYXYXYXYXYXYXYXYInteraction GateXXYYXXYYXXYYCrossover6.111 Fall 2005 Lecture 15, Slide 11The Fredkin Gate• Without C, A’=A and B’=B• When C is present, A’=B and B’=ACBAC'A'B'A B C0 0 00 0 10 1 01 0 00 1 11 0 11 1 01 1 1A’B’C’0 0 00 0 10 1 01 0 01 0 10 1 11 1 01 1 1IN OUTABCA’B’C’(Ressler, A. L., MIT EECS MS Thesis, Jan. 1981, “The Design of a Conservative Logic Computer and a Graphical Editor Simulator”)6.111 Fall 2005 Lecture 15, Slide 123. Reversible ComputationA B C0 0 00 0 10 1 01 0 00 1 11 0 11 1 01 1 1A’B’C’0 0 00 0 10 1 01 0 01 0 10 1 11 1 01 1 1IN OUTABCA’B’C’Schematic symbol(Fredkin and Toffoli, Int. J. of Theor. Phys., V21 p219, 1982, “Conservative Logic”)• Build an entire computer from Fredkin gates (vs AND/NOT)0XYXYXYY“AND” function0XYXYXYY“AND” function• The Fredkin gate is computationally universal• Its function can be understood as a simple “controlled exchange-bypass switch”• This reversible logic gate is a fundamental building block for a reversible computer01XXXX“NOT” function6.111 Fall 2005 Lecture 15, Slide 13Uncomputing• All functions can be computed reversibly• Reconstruct and erase intermediate results (garbage) by using inverse functions:Copyf1f2f3fnfn-1f1f2f3fnfn-1-1-1-1-1-1OutIn• All computation can be done, in principle, at zero cost in energy!(x,y) → (x,y⊕ f(x))• Q: When is energy dissipation necessary?6.111 Fall 2005 Lecture 15, Slide 15Irreversibility => Energy Dissipation• Consider an error, eg the ball going off trajectory or timingCBAC'A'B'• Correct by expending energy to monitor ball trajectories, and actively correcting errors: erasure of errors costs energyEnergy dissipation is needed only to provide stability & correct errors!6.111 Fall 2005 Lecture 15, Slide 164. Fault Tolerant ComputationReliable computers can be constructed from faulty components• A circuit containing N (error-free) gates can be simulated with probability of error at most ε, using N log(N/ε) faulty gates, which fail with probability p, so long as p<pth.von Neumann (1956)• Instead of constructing perfect digital systems, we can choose adifferent strategy to achieve reliability.6.111 Fall 2005 Lecture 15, Slide 17Fault-Tolerant Circuits6.111 Fall 2005 Lecture 15, Slide 18Fault-Tolerant Circuits6.111 Fall 2005 Lecture 15, Slide 19Ex: Fault Tolerant NANDNAND•Fails with probability p6.111 Fall 2005 Lecture 15, Slide 20Ex: Fault Tolerant NANDMAJMAJMAJNANDNANDNAND•Encode data: 0 → 000, 1 → 111•Assume each gate fails with probability p•Circuit fails only if 2 gates fail (6 possibilities)6.111 Fall 2005 Lecture 15, Slide 21Ex: Fault Tolerant NAND•Recursive construction: 0 → 000000000, 1 → 111111111•Circuit fails only if 2 modules failMMMMMMMMMMMMMMMMMMNNNNNNNNN6.111 Fall 2005 Lecture 15, Slide 22Fault Tolerance: Threshold• Use k recursive levels of error correction:Circuit failure Gate failureThreshold• Error reduction is exponential in resources!6.111 Fall 2005 Lecture 15, Slide 23Teramac: “Defect tolerant” FPGA Array( Heath, Kuekes, Snider, Williams, Science v280, p1716, 1998 )• Modern digital electronics vs fundamental limits:• Intel 4004: 500 additions/Joule• Modern microprocessors: 3× 106additions/Joule• Von Neumann-Landauer limit of kBTlog 2: 1018add./Joule• 864 FPGA’s• 217 defect-free, 647 uncertified• 10% of FPGA logic cells defective• 10% of interconnects unreliable• System made reliable through redundancy• Static, not dynamic faults• Teramac: an experimental digital system using faulty devices:6.111 Fall 2005 Lecture 15, Slide 24The Quantum Limit18791 inchi386i38619861 micrometerWhat happens when 1 bit = atom?20201 nanometer6.111 Fall 2005 Lecture 15, Slide 25?i386i386i386i386MaxwellNewton Schrödinger+ Status9 Factoring: Exponential speedup 9 7-qubit QC demonstrated± Need: new algorithms?1-2Superconding JJ7NMR0-1Quantum dots1-4Trapped IonqubitsSystem1-2Superconding JJ7NMR0-1Quantum dots1-4Trapped IonqubitsSystemShor ’94IBM / MIT 2001Quantum Computation Fundamental Motivations• Quantum physics provides new physical resources• Computer science = new mathematical tools for physics6.111 Fall 2005 Lecture 15, Slide 27Quantum Bits• Arbitrary superposition:1= 0=+1c• Classical
View Full Document
Unlocking...