Path: utzoo!mnetor!uunet!lll-winken!lll-lcc!ames!ucbcad!ucbvax!cbosgd!cbdkc1!jap
From: jap@cbdkc1.ATT.COM
Newsgroups: comp.arch
Subject: Re: Single tasking the wave of the futu
Message-ID: <2642@cbdkc1.ATT.COM>
Date: 23 Dec 87 22:39:54 GMT
References: <3445@hoptoad.uucp> <76700007@uiucdcsp> <44@amelia.nas.nasa.gov>
Reply-To: jap@cbdkc1.UUCP (James A. Parker CB 3S308W x5250)
Organization: AT&T Bell Laboratories, Columbus
Lines: 39

In article <44@amelia.nas.nasa.gov> fouts@orville.nas.nasa.gov (Marty Fouts) writes:
>...
>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. . .

Actually there are some formal models for parallelism (including their
relationship to sequential models).  I just completed a course in
Computational Complexity at Ohio State, and in it we studied two
such models:  Parallel Random Access Machines (PRAMs), and Uniform Families
of Circuits.  The area seems to be pretty fluid yet (e.g., the professor used
a textbook he is in the process of writing, since he wasn't aware of any
existing general treatment of the subject), but it is indeed there.

[mini-diatribe]
Who, pray tell, is the person who made the decision to electronically enforce
a limit on the size of quoted material?  Somewhere out there, someone made
such a conscious decision, making life miserable for those who post.  Whoever
made this decision owes a public apology to the net, and an immediate
retraction of said "feature" from the software.

Note that this diatribe was added simply to allow me to post the real message
above.
[end of diatribe]
-------------------------------------------------------------------------------
James A. Parker       | This message is both brought to you and disavowed by
...!cbosgd!cbdkc1!jap | AT&T Bell Laboratories
-------------------------------------------------------------------------------