Announcements

Course Info:

Instructor: Dr. Michael P. Frank. Office: CSE E442. Email: mpf@cise.ufl.edu. Office phone: 392-6888. Office hours: M7,T8,R9. Additional time can be scheduled upon request.

Course Description:

Computing pioneer and visionary Ed Fredkin (formerly of MIT) has argued, from core principles of fundamental physics, that Moore's Law (which forecasts ever-increasing computer power over time) must come to a halt (or at least slow down) sometime in the coming millenium.

But we'd like to guess more precisely how long it will be before the first plateau of Moore's Law is reached (10 years? 100?), and what paths future computing technology (and computer science theory) might need to follow in order to forestall the eventual slowdown for as long as possible. In this course, we will study what is currently known in the physics of computing research community in relation to these issues.

Course Format:

1. Frequent reading assignments from the primary research literature
2. Lectures introducing each topic & reviewing the readings,
3. Open-discussion and question-and-answer sessions, and
4. Short written homework assignments to encourage & verify participation

List of Topics:

• Fundamental physical constraints on computation:
• Speed of light limit and its implications
• Quantum limits on information density and processing rates
• The second law of thermodynamics
• Long-term impact of general relativity
• Chaos and analog computation
• The future of semiconductor technology:
• Semiconductor technology trends
• The National Semiconductor Roadmap
• Constraints on voltage/capacitance scaling
• Fundamental limits to energy efficiency
• Energy-efficient "adiabatic" reversible logic:
• Principles of adiabatic electronics
• Pipelined, sequential, fully-reversible logic circuits
• Power supply issues
• Potential future computing technologies:
• Superconductor electronics
• Quantum computing
• DNA computing
• Nanomechanical logic
• Molecular electronics
• Physics-based models of computation:
• Need for physics-based models
• The form of an optimal model
• Benefits of full and partial reversibility
• Reversible computer science
• General irreversible-to-reversible conversions
• Reversible serial and parallel architectures
• Reversible programming languages and algorithms

How to Enroll:

There is a cap on enrollment of ~25 undergrads and ~25 graduate students, which is presently about full. If it's full when you try to add, come anyway on the first day, and keep trying to add it during the first week. I may increase the enrollment limit, or alternatively, some students may drop it.

Reading Material:

1. Part Ia / Week 1: Moore's Law, and some basic physical limits.
2. Part Ib / Week 2: Thermodynamic limits, other misc. physics issues.
3. Part IIa / Week 3: Semiconductor technology scaling.
4. Part IIb / Week 4: Alternative nano-scale semiconductor devices.
5. Part III / Weeks 5-6: Reversible adiabatic circuits.
6. Part IV / Weeks 7-8: Misc. Future Computing Technologies
7. Part V / Weeks 9-10: Quantum Computing
8. Part VI / Weeks 11-12: Reversibility in Computer Science
9. Part VII /Weeks 13-14: Physical Models of Computation

Required readings:

The primary source of reading material will be photocopied research articles which will be generally be made available as optically-scanned PDF files on the course reserve web site of the Marston science library. Some of these will also be available in electronic form from the web. These readings are still being selected and assembled. See the first homework assignment for the list of readings for the first week.

One thing that will definitely also be required is my own working manuscript "Reversibility for Efficient Computing", which contains chapters on many areas of the course: physical limits of computing, quantum computing, adiabatic circuits, and future computing technologies. You can either download it from the web and print chapters as needed, using your own resources, or you can buy it at the UF bookstore; I will have them print it up. (You will only be paying for their printing costs: no profit to me.)

Recommended readings:

The following books are also recommended, and over the course of the semester we will refer to them to some extent, so you are advised to purchase as many of them as you can reasonably afford. However, they are not required. I am trying to get the UF bookstore to stock them, but in the meantime, you could order them online from the following Amazon links:

Feynman Lectures on Computation

In the early eighties, famous physicist Richard Feynman, with help from colleagues, taught a course on "The Potentialities and Limitations of Computing Machines" at Caltech. This book encapsulates Feynman's lecture notes from that course.

 

The first part of this book is basically an introduction to and summary of much of basic computer science, which will be very helpful to those students (most of you who are not CS graduate students) who do not have so much background in that area. However, we will not cover this material in class (except as needed to answer student questions that might arise). You should, nevertheless, read it on your own if you start to feel lost with the computer science part of the course.

 

Then, the later part of this book really hits at the core of what this course is about: the thermodynamics and other physical aspects of computation. We may copy excerpts of the most important sections for the course packet, but if you buy the book, you will have the maximum information.

Feynman and Computation : Exploring the Limits of Computers

Companion volume to the above, this book collects old and recent articles on the physics of computing by Feynman and his colleagues in physics, electrical engineering, and computer science who were guest lecturers in his course. (If we're lucky, we may even get one or two of them as guest lecturers in our course!) Most of the articles are excellent, and make for interesting and very relevant reading for our course.

 

We will ask you to read some of these articles. We may provide photocopies for students who don't want to buy the full book, but if you do buy the book, you will be sure to have a clean, fresh copy, and the complete set of articles.

Explorations in Quantum Computing

We will be handing out some introductory articles and tutorials on quantum computing (plus the "Feynman and Computation" book above also contains one), but I thought I'd supplement this with an entire book on quantum computing, for those students who are particularly interested in this topic.

 

This book comes with software which we will try to set you up to be able to run at CIRCA, which allows you to simulate and experiment with a quantum computer and run some quantum algorithms.

 

However, I haven't yet seen this book myself, so I'm not yet certain about how good it is. So, this is somewhat of an experiment.

Warren Smith, of the NEC Research Institute, taught a similar course on "Computing and the Laws of Physics" at the Princeton Applied Math department in Fall of 1998. His course notes may be found at http://external.nj.nec.com/homepages/wds/pu-course.html; we may use some of them as well. I recommend you familarize yourself with his site, and download, print, and read his material as needed.

Course Calendar: (tentative)

Each week's assignment will be linked to from the week number when available. Lecture notes will be linked to from the lecture title when available.

Week 1:         I. FUNDAMENTAL PHYSICAL CONSTRAINTS
     M 1/10        L1. Course intro: Moore's law vs. known physics.
     W 1/12        L2. Physical locality and the speed-of-light limit.
     F 1/14        L3. Quantum limits on information density.
Week 2:
     M 1/17            (MLK Day off)
     W 1/19        L4. (HW1 due)
                       Finish information density limits.
                       Quantum limits on info. flux and processing rates.
     F 1/21        L5. Reversibility & 2nd law of thermo.
                       (Skipping chaos, analog, general relativity.)

Week 3:         II. FUTURE SEMICONDUCTOR TECHNOLOGY
     M 1/24        L6. (HW2 due)
                       Semiconductor technology basics.
     W 1/26        L7. Semiconductor scaling laws.
     F 1/28        L8. Thermal concerns in semiconductor scaling.
Week 4:
     M 1/31        L9.  short lecture - survey to pick topics for rest of week
     W 2/2         L10. (HW3 on week 3 due)
                        Advanced devices: Quantum dots, single-electron transistors, etc.
     F 2/4         L11. Advanced devices cont.: Quantum-Dot Cellular Automata

Week 5:         III. ADIABATIC CIRCUITS (slides on reserve)
     M 2/7         L12. Basic principles of adiabatic circuits
     W 2/9         L13. Split-level charge recovery logic
     F 2/11        L14. (HW4 on week 4 due)
                        Accomodating reversibility in logic designs
Week 6:
     M 2/14        L15. More on adiabatic circuits
     W 2/16        L16. Issues in designing efficient resonant power supplies
     F 2/18        L17. Adiabatic circuits: Wrap-up

At this point I stopped writing detailed lecture notes, but slides for most
of the subsequent lectures are available on reserve.

Week 7:         IV. MISC FUTURE COMPUTING TECHNOLOGIES
     M 2/21        L18. Superconducting electronics (HW5 on part III due) 
     W 2/23        L19. (cont.)
     F 2/25        L20. DNA computing
Week 8:         
     M 2/28        L21. (cont.) 
     W 3/1         L22. Nanomechanical logic
     F 3/3         L23. Molecular electronics

     M 3/6         \
     W 3/8          | SPRING BREAK 
     F 3/10        /

Week 9:         V. QUANTUM COMPUTING
     M 3/13        L24. Intro, basic principles & formalism. (HW6 on part IV due) 
     W 3/15        L25. Quantum logic gates and circuits.
     F 3/17        L26. Shor's algorithm.
Week 10:        
     M 3/20        L27. Grover's algorithm, physics simulations.
     W 3/22        L28. Error-correcting codes.  Quantum cryptography.
     F 3/24        L29. Implementation approaches.

Week 11:        VI. REVERSIBILITY IN COMPUTER SCIENCE
     M 3/27        L30. Interconversions: Bennett's, Lange-McKenzie-Tapp's (HW7 on part V due)
     W 3/29        L31. (cont.) Interconversions: Minimum overheads (1st third).
     F 3/31        L32. Reversible architectures: Instruction set architectures. (uarch?)
Week 12:        
     M 4/3         L33. Reversible languages: Janus, Psi-Lisp, The R language 
     W 4/5         L34. Reversible algorithms: misc. algs, quantum simulator.
                VII. PHYSICS-BASED MODELS OF COMPUTATION
     F 4/7         L35. Rationale for physics-based models, problems with
                        existing models, proposed structure of optimal models.

Week 13:        
     M 4/10        L36. (HW8 due) Scaling of reversible vs. irreversible models.
     W 4/12        L--  (Dr. Frank at Sandia.  Class canceled.)
     F 4/14        L37. Ed Fredkin's guest lecture on "Digital Mechanics".
Week 14:
     M 4/17        L38. Discuss Fredkin, Sandia labs, scaling cont.
     W 4/19        L39. Finish scaling. Bonus topic: Classical crypto.
                VIII. WRAP-UP OF COURSE
     F 4/21        L40. Course evals.  Bonus topics cont. Extra credit assignment due. 
                        Retrospective on course.
Week 15:
     M 4/24        L41. (HW9 due) Reserved for extra-credit student presentations.
     W 4/26        L42. This class probably will be canceled.

Exam week:
  There is no final exam in this course, and there is no class meeting planned
  during the exam period.  Have a nice summer break!

Course Flyers