Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!rice!uw-beaver!Teknowledge.COM!unix!garth!fouts@bozeman.ingr.com (Martin Fouts)
From: fouts@bozeman.ingr.com (Martin Fouts)
Newsgroups: comp.sys.super
Subject: Re: Cray tidbits
Message-ID: <522@garth.UUCP>
Date: 28 Jun 90 16:32:56 GMT
References: <354@garth.UUCP> <1990May23.041119.4359@ux1.cso.uiuc.edu> <390@garth.UUCP> <58230@bu.edu.bu.edu> <470@garth.UUCP> <58992@bu.edu.bu.edu>
Sender: fouts@garth.UUCP
Distribution: comp
Organization: INTERGRAPH (APD) -- Palo Alto, CA
Lines: 83
In-reply-to: art@cs.bu.edu's message of 17 Jun 90 21:00:46 GMT

In article <58992@bu.edu.bu.edu> art@cs.bu.edu (Al Thompson) writes:

   In article <470@garth.UUCP> fouts@bozeman.ingr.com (Martin Fouts) writes:
   |In article <58230@bu.edu.bu.edu> art@cs.bu.edu (Al Thompson) writes:
   |   In article <390@garth.UUCP> fouts@bozeman.ingr.com (Martin Fouts) writes:
   [...]

   |I'm not quite as optimistic.  I will not quite equate scientific
   |problem with easy, although I will certainly agree that they embody a
   |wide range of easy problems.  But I still agree.  In fact, let me now
   |introduce a term which I didn't invent: (though wish I had)

   I didn't mean "easy" in the sense of a snap, I meant it in the sense of
   "easy parallelism".  That's not necessarily an easy problem.  In fact many
   scientific problems consist of calculations that are inherently simple but
   must be replicated over a large number of cases.  Geofry Fox has done a
   lot of work on this.

Actually, I also meant easy in the sense of "easy parallelism."  I'm
familiar with Fox's work.  I'm also familiar with several classes of
scientific problems which are not easy to parallelize.  To me, QCD is
easy to parallelize but hard to understand, (I'm no quantum physicist)
while estimation of population dynamics is easy to understand but hard
to parallelize.  (I'm no biologist either, but the arguments are
"intuitive", and the problem is partial order dependent, rendering it
intractable as a parallelizable problem.)

   [...]

   |
   |"Functional Multiprocessing (tm?)"  == Decomposing the processors to
   |match the problem and then optimizing each processing element to its
   |task.  I predict that this will be a more important contribution then
   |vectorization.

   This is probably correct.  It is a compelling idea and one we are working
   on here, although not quite in the form as stated.

   |
   |   [...]
   |   |
   |   |CRI could possibly build a SIMD implementation of the Y/MP; that is a
   |   |Y/MP instruction set driven data parallel processor.

   [...]

   |
   |   I can't imagine such a machine being SIMD.  The Cray instruction set, if
   |   implemented on each processor, contains data dependent jumps.  The first
   |   time one of these is executed, poof you're off in MIMD land.
   |
   |Actually, there are ways to make those jumps which would work in a
   |SIMD architecture and would support the itteration to a fixed point
   |method of parallelization described by Chandy and Misra, but I
   |wouldn't want to program one of them (;-)

   My point was turning MIMD to SIMD.  Not the other way around.  In fact I
   have done the fixed the fixed point Chandy Misra problem and it's not
   quite.  Perhaps the reason I say this is because I had it solved before I
   knew it (I wasn't really looking for a solution, but a light went on and
   sure enough, there it was).

   Turing SIMD to MIMD is not so terribly difficult.  To do so with any
   reasonable degree of efficiency on the other is not so easy.

Agreed.  Now think about my statement as an attempt to cast an MIMD
machine to a SIMD machine using an N to 1 jump processor:  When a data
dependent jump occurs, all processors go nondeterministically to the
same next instruction.  You still have lock step instruction
execution, but now you have nondeterminism.  The only way I can think
to write correct programs for this beast is through fixed point
itteration.

Marty
--
Martin Fouts

 UUCP:  ...!pyramid!garth!fouts  ARPA:  apd!fouts@ingr.com
PHONE:  (415) 852-2310            FAX:  (415) 856-9224
 MAIL:  2400 Geng Road, Palo Alto, CA, 94303

If you can find an opinion in my posting, please let me know.
I don't have opinions, only misconceptions.