Ultimate Theoretical Models
of Nanocomputers
Massechusetts
Institute of Technology AI Lab
545 Technology Square, Room 747
Cambridge MA 02139
telephone: (617) 253-4175
fax: (617) 253-5060
[email protected]
http://www.ai.mit.edu/~mpf
©1997 Michael P. Frank
This is an abstract for
a talk to be given at the
Fifth
Foresight Conference on Molecular Nanotechnology.
This abstract is also available at
http://www.ai.mit.edu/~mpf/Nano97/abstract.html
The full paper is available at
http://www.ai.mit.edu/~mpf/Nano97/paper.html.
The article is partially based on previous work by the author
and co-workers, namely an existing unpublished memo
and a draft manuscript submitted to UMC '98.
Although a complete nanotechnology does not yet exist, we can
already foresee some new directions in theoretical computer
science that will be required to help us design maximally
efficient computers using nano-scale components. In particular,
we can devise novel theoretical models of computation that are
intended to faithfully reflect the computational capabilities of
physics at the nano-scale, in order to serve as a basis for the
most powerful possible future nanocomputer architectures.
In this paper we
present arguments that a reversible 3-D mesh of processors is an
optimal physically-realistic model for scalable computers. We
show that any physical architecture based on irreversible logic
devices would be asymptotically slower than realizations of our
model, and we argue that no physical realization of computation
aside from quantum
computation could be asymptotically faster.
We also calculate, using parameters from a variety of
different existing and hypothetical technologies, how large a
reversible computer would need to be in order to be faster than
an irreversible machine. We find that using current technology, a
reversible machine containing only a few hundred layers of
circuits could outperform any conventional machine, and that a
reversible computer based on nanotechnology would only need to be
a few microns across in order to outperform any possible
irreversible technology.
We argue that a silicon implementation of the reversible 3-D
mesh could be valuable today for speeding up certain scientific
and engineering computations, and propose that the model should
become a focus of future study in the theory of parallel
algorithms for a wide range of problems.
*Corresponding Address:
Massachusetts Institute of
Technology, AI Lab, 545 Technology Square, Room 747,
Cambridge, MA 02139, ph: 617-253-4175, fax: 617-253-5060, email: [email protected]
|