CIS 6930.3753X, Spr. '02
Physical Limits of Computing
http://www.cise.ufl.edu/~mpf/physlim

Course Info:

Instructor: Dr. Michael P. Frank. Office: CSE E442. Email: mpf@cise.ufl.edu. Office phone: 392-6888. Office hours: Thursdays, 7th-9th periods (2-5 pm).  Additional time can be scheduled upon request, given several days' notice by email.  Also, feel free to drop in whenever my door is open.

Teaching assistants: Jeff King <jeffking@ufl.edu> Office hours: MWF8 CSE-468, and Murshed Chowdhury <mchowdhu@ecel.ufl.edu> Office hours: Thursday and Friday, 5th-6th periods (Office : CSE 445F).

Course Description:

Current knowledge of physics seems to suggest that the Moore's Law trends of decreasing transistor size, and increasing computer performance per cost, will come to a halt (or at least slow down) within the next few decades, i.e., within the careers of students today.  When this happens it will have a major impact on society (not to mention our own future career paths), so it is useful to take look ahead at these limits, and learn about some technologies that are currently being explored that may help us, at least, to continue improving computer performance steadily for as long as possible, before running into the inevitable eventual limits.

We will study the frontier of current research in this exciting topic area, and gain a working familiarilty with the (physical, engineering, and analytical) concepts, tools,  and methodologies that will be needed for industry to eventually push the boundaries of computing as near as possible to their ultimate limits.

Prerequisites:

There are no formal course prerequisites.  However, if you have had any courses in physics (especially quantum mechanics), electrical engineering, or theoretical computer science, they will be quite helpful..

Course Format:

• Frequent reading assignments from the primary research literature and some useful books.
• Lectures introducing each topic & giving summaries of the important points in the readings.
• Questions from the class & open discussion are encouraged.
• Biweekly assignments will be of a variety of types, selected at the students' individual option:
• Sets of written problems to exercise students' ability to apply the technical concepts covered in the material.
• Computer-based projects to explore specific topics in more depth.
• Open-ended research papers on topics' of the students' choice relating to the course.

The detailed course grading policy, and descriptions of the different types of assignments, can be found here.

The course is intended for graduate students, but will be open to interested undergraduates who are bright and motivated to learn this material.  Enrollment is limited to 100 students.  (Last year it was limited to 50 and filled quickly.)

List of Topics for Spring '02

• Background
• Basic physics concepts you'll need
• Basic computer science concepts you'll need
• Basic systems engineering concepts you'll need
• Fundamental physical constraints on computation:
• Speed of light limit and its implications
• Quantum limits on information density and processing rates
• Fundamental limits of communication bandwidth & latency
• Thermodynamic limits on energy dissipation
• Long-term impact of general relativity
• Chaos and analog computation
• The future of semiconductor technology:
• Semiconductor technology trends, the National Semiconductor Roadmap
• Fundamental & engineering constraints & limits to semiconductor scaling.
• Fundamental limits to energy efficiency of electronics.
• Potential future computing technologies:
• Mesoscale bulk electronics: Quantum Dots, Single-Electron Transistors, etc.
• Superconducting electronic logic
• Molecular electronics: Buckytubes, Tour wires, etc.
• Other: Nanomechanical rod logic, biochemical/DNA computing.
• New models of computing - next year move this topic earlier
• Classical reversible computing:
• Fundamentals of adiabatic processes
• Adiabatic electronic devices & CMOS logic families
• Scaling advantages of reversibility
• Reversible microprocessor architectures, programming languages, algorithms
• Quantum computing:
• Quantum logic gates & circuits
• Algorithms
• Quantum information & communication
• Physical implementations
• Cosmological limits of computing:
• Dyson & Krauss-Starkman models & their implications

How to Enroll:

Reading Lists & Assignments: (Being updated for Spring '02)

• Part I: Course Introduction & Background
• Part II: Fundamental Physical Constraints on Computation
• Part III: The Future of Semiconductor Technology
• Part IV: Potential Future Computing Technologies
• Part V: Classical Reversible Computing
• Part VI: Quantum Computing
• Part VII: Wrap-Up of Course

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 in our password-protected directory, or 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 above for the detailed reading lists.

One thing that is also strongly recommended  is my own working manuscript "Reversibility for Efficient Computing", which contains chapters about 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 in printed & bound form (the green course packet) at the UF bookstore. Also, for convenience, last year's lecture notes and slides are available in printed form, as a blue course packet at the UF bookstore.  Or you can access them online below (but not quite all of the slides in the printed packet are online yet).  (With the course packets, you will only be paying for the printing costs: No profit to me.)

Strongly recommended textbooks:
These books are very helpful and I strongly recommend that you buy as many of them as you can afford.  However, you are not required to buy any specific book because of the flexible structure of the assignments.  At minimum, you should skim all these books at the bookstore, and buy whichever one you think you will find most helpful.

Feynman Lectures on Computation

In the early eighties, famous physicist Richard Feynman, with help from colleagues (including some of my own advisors), taught a course on "The Potentialities and Limitations of Computing Machines" at Caltech, similar in spirit to our own course. 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 on reserve at the library 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.

Quantum Computation and Quantum Information

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:

The Physics of Quantum Information 

Explorations in Quantum Computing

This book does not always have the best explanations of things, but it comes with Mathematica-based software which we will set you up to be able to run at CISE, which allows you to simulate and experiment with a quantum computer and run some quantum algorithms.

Quantum Computing by Mika Hirvensalo

Other resources:

• 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.
• Spring 2000 Course Homepage, for reference