Path: utzoo!utgpu!water!watmath!clyde!att!osu-cis!tut.cis.ohio-state.edu!mailrus!ames!vsi1!altnet!uunet!munnari!murdu!pal
From: pal@murdu.OZ (Philip Leverton)
Newsgroups: comp.arch
Subject: Re: memory speed & futurology
Message-ID: <1443@murdu.OZ>
Date: 27 Aug 88 03:17:42 GMT
References: <2179@ditmela.oz> <11978@steinmetz.ge.com>
Reply-To: pal@murdu.UUCP (Philip Leverton)
Organization: Computing Services, Melb. Uni.
Lines: 95

In article <11978@steinmetz.ge.com> davidsen@crdos1.UUCP (bill davidsen) writes:
[deleted]
>  It can be proven that there is a limit to how fast a computer may be,
>independent of the techniques used. There was an article by a physicist
>several years ago on this, and he quoted the limit. The problem is the speed
>of light. To reduce delays induced by the SOL requires making devices
>smaller. When wires becode extremely small they become statistical problems
>rather than conductors. If a wire is a few molecules in diameter (he quoted
>the values), putting an electron in one end does not insure that an electron
>comes out the other.
>
>  Add to this having to use lower voltage to keep power down so the whole
>thing won't melt, and you hit a firm lower limit on size, and thereby
>performance. This does not preclude parallel processing for problems which
>have the right characteristics.
>
>  The good news is that we are currently about 21 orders of magnitude from
>the limit. I can't guess what reducing the size of a CPU/memory system by
>that level would do for performance, but if you put one on my desk I'll
>report the benchmarks.
>
>  Anyone who can find a copy of the original article, please supply more
>details.

I think the article that you're referring to is "Quantum Mechanical Computers"
by the late Prof. Richard Feynman. A copy arrived as a Caltech preprint at the
University of Melbourne Physics Dept in 1984. The preprint says that is is
a "Plenary Talk presented to IQEC-CLEO Meeting, Anaheim,June 19, 1984."
What follows is essentially a paraphrase of a several sections of Feynman's
original article, which I have. I also have no idea what IQEC-CLEO stands
for, either. :-)

Feynman considered the problem of the determining the physical limitations
imposed on the future development of computers due to quantum mechanics
and the uncertainty principle. His formulated a Hamiltonial to describle
an ideal computing system (ignoring the effect of small imperfections).
His conclusion was that "the laws of physics present no barrier to reducing
the size of computers until bits are the size of atoms, and quantum
behaviour holds dominant sway."

The minimum free enery that must be expended to operate a computer composed
of the ideal primitives AND, NOT, [could be combined into NAND], 
FAN OUT(2 "wires" -> 1 "wire") and EXCHANGE (crossed "wires") was thought 
to be kT ln(2) [from the AND case]. At the present with a transistor
system the heat dissipation is 10**10 kT because to change the voltage
of a wire it is dumped to ground through a resistance; and to build up the
voltage we feed it charge again through a resistance. Nature in her DNA
copying machine, dissipates about 100 kT per bit copied. Feynman goes on to
say that "Being, at present so very far from this kT ln(2) figure, it seems
ridiculous to argue that even this is too high and the minimum is essentially
zero. But, we are going to be even more ridiculous later and consider bits
written on one atom instead of the present 10**11 atoms. Such nonsense is
very entertaining to professors like me. I hope you will find it interesting
and entertaining also." Bennet showed that the kT ln(2) limit was wrong
because you don't have to use irreversible (in the thermodynamic sense)
primitives. You can use reversible machines that contain only reversible
primitives. Then the minimum free energy required is *independent* of the
complexity or number of logical steps in the calculation. The energy would
probably be kT per bit of the output answer! 

"The time needed to make a step in a calculation in such a machine depends on
the strength or the energy of the interactions in the term of the Hamiltonian.
If each of the terms in the Hamiltonial is supposed to be of the order of
0.1 eletron volts, then it appears that the time for the "cursor" to make
each step, if done in a ballistic fashion, is of the order 6.0E-15 sec.
This does not represent an enormous improvement, perhaps only about four
orders of magnitude, over the present values of the time delays in
transistors, and is not much shorter that the very short times possible to
achieve in many optical systems."

The article goes on to consider the Hamiltonian of quantum mechanical
computer, state representation in such a machine, imperfections and 
irreversible free energy losses, and simplifying the implementation.

Here are the references of the article:
1. Bennet, C.H. "Logical Reversibility of Computation," IBM Journal of
Research and Development, *6* (1979) 525-532.
2. Fredkin, E. and Toffoli, T. "Conservative Logic," Int. Journal of
Theoretical Physics, *21* (1982) 219-253.
3. Bennet, C.H. "Thermodynamics of Computation - A Review," Int. Journal of
Theoretical Physics, *21* (1982) 905-940.
4. Toffoli, T. "Bicontinuous Extensions of Irreversible Combinatorial
Functions," Mathematical Systems Theory, *14* (1981) 13-23.
5. Priese, L. "On a Simple Combinatorial Structure Sufficient for Sublying
Non-Trivial Self Reproduction," Journal of Cybernetics, *6* (1976) 101-137.

Of course, all this work dates from 1984; no doubt further research has been
done since then. The 10**11 figure for the size of a transistor might
have been reduced by a bit too!

Phil Leverton, University Computing Services, University of Melbourne.
A once and future physics student.
ACSnet: pal@murdu 	CSNET: pal%murdu.oz@australia
ARPA: pal%murdu.oz@uunet.css.gov
UUCP: {uunet,hplabs,mcvax,ukc,nttlab}!munnari!murdu.oz!pal