Realistic Theoretical Models of Nanocomputers
Proposal/abstract for NanoInvestor 2002 conference

Michael P. Frank
U. of Fla., CISE Dept.

Regardless of the precise physical mechanisms used in future nano-scale logic technologies, certain fundamental physical principles will constrain their performance, and dictate the form of the scaling laws involved in any realistic engineering and economic analysis of future nanocomputer architectures composed of large numbers of such devices.  Paramount among these fundamental principles are certain inexorable constraints such as the second law of thermodynamics, and the speed-of-light limit.

In our research in the Reversible Computing Group at University of Florida (evolved from our earlier Ph.D. work at M.I.T.), we are investigating realistic, technology-independent models of nano-scale computation devices and architectures that take into account all of the relevant fundamental physical constraints, as well as generic kinds of device limitations, while also respecting system design constraints imposed by even the best known machine architectures and algorithms.

In our 1997 paper, "Ultimate theoretical models of nanocomputers," presented at a Foresight conference and archived in the journal Nanotechnology [1], and in our subsequent (1999) Ph.D. thesis [4], we considered the relative scalability of adiabatic (i.e., thermodynamically reversible, compared with irreversible) models of computation, in a somewhat idealized model where we assumed that certain device parameters (namely, leakage rates, and the Qs of fixed-size resonators) could be made as favorable as needed, given sufficient engineering effort.  We found that under these assumptions, we could prove an unboundedly increasing cost-efficiency advantage for reversible versus irreversible computing (by small polynomial factors), as a system is scaled to larger numbers of processors [1,2,4].

In our work since 1999, we have been refining our former models to be increasingly comprehensive and realistic, encompassing a broader range of important device and algorithmic limitations.  Significant advantages for reversibility remain in these more realistic models, and moreover, we now can accurately describe how these advantages vary as a function of many relevant device technology parameters.  Our new models are useful for guiding both device engineering, and nanocomputer architecture.  As an example of the latter, our work incorporates a simple (and patent pending) logic synthesis technique for transforming an arbitrary irreversible logic circuit into an equivalent reversible one that is optimized to be as efficient as one can expect from any such general transformation, modulo any major new breakthroughs in reversible computing theory (apparently rendered unlikely by [5]).  This technique ought to be commercializable for improving circuit efficiency in sufficiently energy-limited applications in the near future, using present-day adiabatic CMOS VLSI technologies (such as we used in [3]).

Attachment: Photograph of the four reversible/adiabatic chips that were developed in connection with our previous work on the MIT reversible computing project.  These important proof-of-concept chips demonstrated that there are no fundamental architectural barriers to implementing efficiently scalable, parallel computing using traditional programming abstractions within an arbitrarily fully-reversible framework.  The next generation of chips, currently under development at UF, will reduce these insights to practice, producing highly-optimized adiabatic microprocessors and DSPs, which can be commercialized today, while also serving as prototypes for future nanocomputer architectures.

[1] Michael P. Frank and Tom Knight, ``Ultimate theoretical models of nanocomputers,'' Nanotechnology 9(3):162-176, Sep. 1998. Also presented at the Fifth Foresight Conference on Molecular Nanotechnology, Palo Alto, CA, Nov. 1997.

[2] Michael P. Frank, Tom Knight, Norm Margolus, ``Reversibility in optimal scalable computer architectures,'' in Calude, Casti, Dineen, eds., Unconventional Models of Computation (proceedings of the First International Conference on Unconventional Models of Computation, Jan. 1998), pages 165-182, Springer, 1998.

[3] Michael P. Frank, Carlin Vieri, M. Josephine Ammer, Nicole Love, Norman H. Margolus, Thomas F. Knight, Jr., ``A scalable reversible computer in silicon,'' in ibid., pages 183-200.

[4] Michael P. Frank, ``Reversibility for Efficient Computing,'' Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, Massachusetts, May 1999.

[5] Michael P. Frank and M. Josephine Ammer, ``Relativized separation of reversible and irreversible space-time complexity classes,'' Information and Computation, submitted May 2001.