shaffer@crd.GE.COM (Phillip L. Shaffer) (06/28/90)
I have heard discussions on the theoretical limits to the speed
of sequential computation, as one justification for research on
parallel processing (not that I think there are no other
reasons). Such limits might be based on minimum size of
computing elements and the speed of light. In a quick look, I
couldn't find any references on this topic.
Can anyone provide references or original thoughts on this
subject?
On a related topic, I saw a chart of computational speed (MIPS or
some other inadequate measure, but let's not quibble) versus
historical time (log scale for computational speed, linear for
time). The data points represented various real microprocessors,
but the chart was far from complete. A straight line was drawn
through the points, and was not too bad a fit. I didn't see any
curvature in the data, but the author had drawn an extrapolation
(beyond 1990) as leveling off. Has anyone seen or done a serious
study of trends of computing speed versus time, and if so, does
any evidence of leveling off exist, or is this a supposition
based only on the above mentioned theoretical limits to
computational speed?
Thanks for any responses. If anyone e-mails to me, I will post a
summary.
--
Phillip L. Shaffer shaffer@crd.ge.com
GE Corporate Research & Development uunet!crd.ge.com!shaffer
Building KW, Room D211
P.O. Box 8, Schenectady NY 12301dmcmilla@cfctech.cfc.com (Don McMillan CS 50) (06/29/90)
In article <9490@hubcap.clemson.edu>, shaffer@crd.GE.COM (Phillip L. Shaffer) writes: |> I have heard discussions on the theoretical limits to the speed |> of sequential computation, as one justification for research on |> parallel processing (not that I think there are no other |> reasons). Such limits might be based on minimum size of |> computing elements and the speed of light. In a quick look, I |> couldn't find any references on this topic. For a good start, try Seitz's article 'Concurrent VLSI Architectures', IEEE Transactions on Computers, Voc C-33 No 12, Dec 84. Don McMillan __ . . Phone: (313) 986-1436 CS Department / ` |\ /| UUCP: {umich,cfctech}!rphroy!rcsuna!dmcmilla GM Research Labs | ,_ | | | CSNet: mcmillan@gmr.com Warren, MI 48090 USA \__/ | | Internet: dmcmilla%rcsuna.uucp@umich.edu
fineman@ptolemy.arc.nasa.gov (Charles Fineman) (06/29/90)
In article <9490@hubcap.clemson.edu>, shaffer@crd.GE.COM (Phillip L. Shaffer) writes: |> I have heard discussions on the theoretical limits to the speed |> of sequential computation, as one justification for research on |> parallel processing (not that I think there are no other |> reasons). Such limits might be based on minimum size of |> computing elements and the speed of light. In a quick look, I |> couldn't find any references on this topic. |> |> Can anyone provide references or original thoughts on this |> subject? |> |> On a related topic, I saw a chart of computational speed (MIPS or |> some other inadequate measure, but let's not quibble) versus |> historical time (log scale for computational speed, linear for |> time). The data points represented various real microprocessors, |> but the chart was far from complete. A straight line was drawn |> through the points, and was not too bad a fit. I didn't see any |> curvature in the data, but the author had drawn an extrapolation |> (beyond 1990) as leveling off. Has anyone seen or done a serious |> study of trends of computing speed versus time, and if so, does |> any evidence of leveling off exist, or is this a supposition |> based only on the above mentioned theoretical limits to |> computational speed? |> This sounds a lot like an article I saw in Scientific American. If I had to guess, I'd say it was in an issue in the latter part of last decade (not much of a guess, sorry). I think the title was something like "The Fundamental Limits of Computation". I'm not positive, but it may have even been the cover story. Chuck
shaffer@athena.crd.ge.com (Phillip L. Shaffer) (07/07/90)
Here was my original query:
I have heard discussions on the theoretical limits to the speed
of sequential computation, as one justification for research on
parallel processing (not that I think there are no other
reasons). Such limits might be based on minimum size of
computing elements and the speed of light. In a quick look, I
couldn't find any references on this topic.
Can anyone provide references or original thoughts on this
subject?
On a related topic, I saw a chart of computational speed (MIPS or
some other inadequate measure, but let's not quibble) versus
historical time (log scale for computational speed, linear for
time). The data points represented various real microprocessors,
but the chart was far from complete. A straight line was drawn
through the points, and was not too bad a fit. I didn't see any
curvature in the data, but the author had drawn an extrapolation
(beyond 1990) as leveling off. Has anyone seen or done a serious
study of trends of computing speed versus time, and if so, does
any evidence of leveling off exist, or is this a supposition
based only on the above mentioned theoretical limits to
computational speed?
Here are the responses I got:
From: Kallol Kumar Bagchi <kkb@iesd.auc.dk>
Please refer to Dennings article in 1986 Dec.issue of CACM--it is excellent!
[The article is: P. J. Denning, Parallel Computing and Its Evolution,
CACM 29(12):1163-1167, Dec. 1986. Denning argues that the limit to
sequential computation is about 1 GFLOP.]
From: Richard Squier <squier@princeton.edu>
Here's a couple of pointers from stuff I have lying around.
"Communication in Computation," by Robert W. Keyes,
Int'l J. of Theoretical Physics, (1982) p.263
[I don't have the full citation. This article came from a special
(issue, section? I don't remeber which) on physical limits of computation.
Vector Inner Product Evaluation," by Robert J. Meier, Tech. Note CSL-TN-87-316,
Computer Systems Laboratory, Stanford University, October 1986
From: mooij@idca.tds.philips.nl (Wim Mooij)
The following article describes the effect of communication on a
certain computation.
P. Vitanyi
"Locality, Communication and Interconnect Length in Multicomputers"
SIAM Journal on Computing, Vol. 17, pp. 659-672, 1988
From: rphroy!rcsdjm!dmcmilla@cfctech.cfc.com (Don McMillan CS 50)
For a good start, try Seitz's article 'Concurrent VLSI Architectures',
IEEE Transactions on Computers, Voc C-33 No 12, Dec 84.
From: fineman@ptolemy.arc.nasa.gov (Charles Fineman)
This sounds a lot like an article I saw in Scientific American. If
I had to guess, I'd say it was in an issue in the latter part of last
decade (not much of a guess, sorry). I think the title was something
like "The Fundamental Limits of Computation". I'm not positive, but
it may have even been the cover story.
[See the response below.]
From: ayers@hx.lcs.mit.edu (Andy Ayers)
I have a few references which are more directed towards the fundamental
limits on ANY kind of computation, not just sequential, though you can
interpret this stuff with sequential machines in mind.
The classic paper is:
R. W. Keyes
Physical Limits in Digital Electronics
Proc IEEE 63, May 1975, 146-153
You might also find the following interesting:
The Fundamental Physical Limits of Computation
Charles H. Bennett and Rolf Landauer
Scientific American 253(1), 48-56 1985
Is there a fundamental bound on the rate at which information can be
processed?
David Deutsch
Physical Review Letters 48(4), 286-288, Jan 25 1982
Classical and Quantum Limitations on Energy Consumption in Computation
K. K. Likharev
International Journal of Theoretical Physics 21(2/4), 311-326, 1982
Computation and Physics: Wheeler's Meaning Circuit?
Rolf Landauer
Foundations of Physics 16(6), 1986
Introduction to VLSI Systems (chaper 9)
Carver Mead and Lynn Conway
Addison-Wesley, Reading, Mass, 1980
TK7874.M37 // ISBN 0-201-04358-0
I have a bunch of other references on "reversible" computing, but these
are even less relevant to parallel computing.
---------
Many thanks to all those who responded!
--
Phillip L. Shaffer shaffer@crd.ge.com
GE Corporate Research & Development uunet!crd.ge.com!shaffer
Building KW, Room D211
P.O. Box 8, Schenectady NY 12301eugene@wilbur.nas.nasa.gov (Eugene N. Miya) (07/10/90)
In article <9588@hubcap.clemson.edu> shaffer@athena.crd.ge.com (Phillip L. Shaffer) writes: >The classic paper is: >R. W. Keyes >Physical Limits in Digital Electronics >Proc IEEE 63, May 1975, 146-153 There is a RAND Company report on the limits of computation, also a well known report by Ivan Sutherland, Carver Mead, and one other person. Do the literature search and you will find it. --e. nobuo miya, NASA Ames Research Center, eugene@orville.nas.nasa.gov {uunet,mailrus,other gateways}!ames!eugene