EEL 4930§06 / 5930§05, Spring 2006
Special Topics:  Physical Limits of Computing

Course Syllabus

 

Class hours:               MWF 9:40-10:30 am

Class location:            Engineering bldg. A, rm. 337

 

Instructor:                  Dr. Michael P. Frank, rm. A342, 410-6463, mpf@eng.fsu.edu

Office hours:              MWF 2:00-4:00 pm

 

Prerequisites:             EEL 3300 – Introduction to Electronics

                                    EEL 3705 – Digital Logic Design

 

Course description:    This is a research survey course of a current research area that is becoming increasingly important as computer technology approaches the nanoscale:  the study of the fundamental physics of computing, with an emphasis on general physical limits that impact the maximum speed, memory density, and energy efficiency that any computer technology can ever possibly attain, based on the known laws of physics. 

Known physics suggests that the historical “Moore’s Law” trends of decreasing transistor size and increasing computer performance per unit cost may plateau within only a few years, and will definitely reach firm physical limits within the next few decades (i.e., within the careers of today’s students).  When this happens, it will have a major impact on the growth of the technology industry, and perhaps even on the entire world economy.

This course will educate students about the nature of the various physical limits that threaten to halt the future improvement of computing technology, and expose students to various new emerging and proposed computing technologies (such as quantum dots, carbon nanotubes, spintronics, and superconductive logics) which have been suggested to help keep computer efficiency improving for as long as possible, circumventing the near-term limits, and approaching the ultimate limits as closely as possible.  The most ambitious of the proposed new technologies involve radical new fundamental paradigms for computing, namely reversible computing and quantum computing.

Reversible computing aims to circumvent all known limits to computer energy efficiency by designing new mechanisms for digital logic that are almost perfectly physically reversible and highly ballistic, so that the machine essentially “coasts” through a long computation with minimal frictional losses.  Ideal reversible devices could run faster and be packed together more densely without overheating than any possible technology based on the traditional irreversible logic paradigm. 

Quantum computing aims to improve algorithmic efficiency on certain specialized problems by taking drastic “short-cuts” along carefully-crafted trajectories through the large space of quantum states “in between” traditional digital states.  The course will cover the basics of theory and implementation for both reversible and quantum computing.

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

Textbook:       There are three recommended textbooks for this course in the bookstore:  the Feynman Lectures on Computation, Maxwell’s Demon 2, and Quantum Information and Quantum Computation.  You must buy at least one, and use it as the basis for a homework assignment, presentation, or report.  However, I recommend that you buy all three if possible, since they are all seminal references in this field.  Additional online lecture notes and scanned or photocopied readings will be provided as needed.

Topics:  This is a comprehensive list of topics that ought to be addressed in an ideal version of this course.  However, due to time constraints, some of the below topics may have to be skipped.

  1. Introduction:  Moore’s Law vs. Modern Physics
  2. Background in the theory of information and computation:
    1. Probability and statistics:  Basic concepts
    2. Information theory:  Information, entropy, channel capacity theorems, informational complexity.
    3. Theory of computing:  Computation universality, computational complexity, models of computation.
  3. Background in required physics:
    1. Classical mechanics:  Basic concepts, quantities, units, and constants; Planck units; Hamiltonian and Lagrangian dynamics.
    2. Relativity:  Lorentz transformations, energy-mass equivalence, simple facts about general relativity and black holes.
    3. Quantum mechanics:  Basic quantum theory, Schrödinger equation, basic elements of quantum field theory.
    4. Thermodynamics and statistical mechanics: Modern understanding of heat, free energy, temperature, entropy, some quantum statistics.
    5. Solid-state physics:  Basics of Fermi levels, band structure, etc.
  4. Interpreting physics as computation:
    1. Entropy as information:  From Boltzmann to Zurek
    2. Physical action as computational effort
    3. Energy as rate of computing:  Margolus-Levitin theorem
    4. Temperature as clock speed
    5. Momentum as spatial density of computation
    6. Relations between gravity and information density.  Holographic bound, Lloyd-Ng relations
  5. Fundamental physical limits on computation:
    1. Information propagation velocity limits:  Speed-of-light limit
    2. Information density limits:  Smith, Bekenstein, Lloyd-Ng  bounds
    3. Information bandwidth limits:  Shannon’s and Smith’s
    4. Computation speed limits:  Parallel and serial performance limits
    5. Energy dissipation limits:  Landauer’s principle, other limits
    6. Reliability limits:  Thermal noise limit on bit energy
  6. Limits of semiconductor technology:
    1. Semiconductor technology basics:  Bandgaps, P/N junctions, MOSFETs
    2. Semiconductor technology trends:  Moore’s Law, constant-field scaling, ITRS roadmap
    3. Semiconductor technology limits: Oxide breakdown, punch-through, leakage.
  7. Reversible computing
    1. Reversible device principles:  Energy and entropy coefficients, leakage
    2. Reversible logic gates:  Fully vs. conditionally reversible primitives
    3. Reversible circuits:  Combinational, sequential, pipelined
    4. Reversible hardware description languages:  Required features
    5. Reversible functional units:  Adders, multipliers, memories
    6. Reversible architectures:  Flattop, Pendulum, others
    7. Reversible programming languages: Ψ-Lisp, R, others
    8. Reversible algorithms:  Complexity issues, algorithm examples
    9. Reversible systems:  Systems engineering and scaling issues
  8. Quantum computing
    1. Quantum gates:  1-bit, 2-bit, n-bit
    2. Quantum circuits:  Quantum logic network formalism
    3. Quantum algorithms:  Grover’s, Shor’s, etc.
    4. Quantum error correction:  Fault-tolerance, etc.
  9. Candidate post-MOSFET device technologies:
    1. Novel FET fabrication techniques & materials: silicon nanowire FETs, carbon nanotube FETs,
    2. Non-field-effect transistors: Interband tunneling transistors, quantum interference transistors
    3. Other nanoelectronic devices: Quantum dots, resonant tunneling diodes, resonant tunneling transistors
    4. Molecular electronic devices
    5. Superconducting electronic devices
    6. Nanomechanical and nano-electromechanical devices
    7. Chemical devices (DNA computing, etc.)
    8. Magnetic and spintronic devices
    9. Quantum computing implementations

Course instructional objectives:

            Upon completion of this course, students should be able to:

1.      Identify and explain the relationships between key physical and computational concepts.

2.      Identify and explain the key short-term and long-term physical barriers that threaten to prevent continued improvement in the low-level efficiency of digital devices.

3.      Explain the motivation for the new computing paradigms of reversible computing and quantum computing.

4.      Explain the basic principles of reversible and quantum computing.

5.      Explain and design simple examples of reversible and/or quantum circuits and algorithms.

6.      Perform important analytical calculations in the physics of computing.

Course grade components:

            The course grade will be computed on the basis of the following components:

Attendance/participation:                              25%   
Assessed via roll-taking, in-class assignments.

                        Written reports on readings:             25%   

                                    Short papers assigned and due approximately weekly.

                        Written homework:                                        25%

                                    Problem sets of an analytical or technical nature.

                        Term project, paper or presentation:            25%   

Longer project, research paper or in-class presentation

There will also be opportunities for optional programming projects presented occasionally throughout the semester.  If completed, these will count as extra credit towards your overall course grade.

Grading scale:  I use a strict grading scale of 90% A, 80% B, 70% C, 60% D.  There will be NO rounding of grades; e.g., even 89.99% is still only a B.  You have sole responsibility for making sure that your grade is over the bar.

Class policies:

1.      No absences or late submission of assignments will be accepted, except with a valid excuse letter signed by Dr. Harvey.

2.      You are bound by the academic honor code, described at http://www.fsu.edu/‌~‌dof‌/‌‌academics.htm.  Violations will be reported, and penalties may include a failing grade in an assignment or in the course.

Students with Disabilities:     Students with disabilities needing academic accommodations should: (1) Register with and provide documentation to the Student Disability Resource Center (SDRC, see http://www.fsu.edu/~staffair/­dean/‌StudentDisability/ ); and (2) Bring a letter to the instructor from the SDRC indicating you need accommodations.  This should be done within the first week of class.  This syllabus and other class materials are available in alternative format upon request.

Special first day instructions:

1.   You must attend the first class or you will be dropped from the course.     

2.   You are required to sign and turn in the form declaring that you have satisfied the course prerequisites within the first week of classes.  If you do not turn in the form, or if later you are found not to have satisfied the prerequisites, you may be dropped from the course.

3.   Please make sure right away that you are enrolled in the course’s Blackboard website.  We will use this website to communicate with you regarding the course.  You should check it frequently for new announcements.

More details:  A course web page is available under the FSU Blackboard System at http://campus.fsu.edu.  All FSU students registered for the class are automatically enrolled on the web page.  FSU students: log in using your Garnet account ID and password.  FAMU students log in using your engineering account user name appended with “_eng”, and your engineering password (Example: If your engineering email address is JDoe@eng.fsu.edu and your engineering password is "eestudent", then login in as "JDoe_eng" with password "eestudent").  FAMU students must then select the course and use the enrollment button to add their names to the course web page roll.  IT IS REQUIRED FOR ALL FAMU STUDENTS TO ENROLL, AND ALL FSU STUDENTS TO VERIFY ENROLLMENT IN THE COURSE WEB PAGE.