Path: utzoo!mnetor!uunet!lll-winken!lll-lcc!ames!amelia!orville.nas.nasa.gov!fouts
From: fouts@orville.nas.nasa.gov (Marty Fouts)
Newsgroups: comp.arch
Subject: Re: Single tasking the wave of the futu
Message-ID: <44@amelia.nas.nasa.gov>
Date: 19 Dec 87 19:20:16 GMT
References: <3445@hoptoad.uucp> <76700007@uiucdcsp>
Sender: news@amelia.nas.nasa.gov
Reply-To: fouts@orville.nas.nasa.gov (Marty Fouts)
Organization: NASA Ames Research Center, Moffett Field, CA
Lines: 23

In article <76700007@uiucdcsp> johnson@uiucdcsp.cs.uiuc.edu writes:
>
>Even though this is comp.arch, I will argue that the real problem in
>building parallel systems is finding the parallel algorithms to run on them.
>This problem is caused by the fact that we don't have many parallel machines,
>...

I agree.  There is also another problem which has to do with
theoretical understanding of computational complexity.  Algorithm
complexity is studied in the frame work of Turing machines, because of
the knowledge that a TM can compute anything computable, and the
implicit assumption that an algorithm which is optimal on a TM is
optimal on a scalar Von Neumann machine.  There doesn't appear to be a
theoretical framework for studying complexity in machines where
different operations cost different amount or where parallization is
possible.  (Other than taking the plunge into real machine modeling,
but there the level of detail makes it difficult to extrapolate to the
general case.)

It seems to me that some useful work could be done in putting together
an algorithm complexity model which would be useful for dealing with a
multiple processor application. . .

Marty