Path: utzoo!utgpu!water!watmath!clyde!att!osu-cis!tut.cis.ohio-state.edu!mailrus!ames!umd5!uflorida!gatech!hubcap!Bjorn
From: lisper-bjorn@YALE.ARPA (Bjorn Lisper)
Newsgroups: comp.parallel
Subject: Re: parallel numerical algorithms.
Message-ID: <1750@hubcap.UUCP>
Date: 26 May 88 12:59:22 GMT
Sender: fpst@hubcap.UUCP
Lines: 66
Approved: parallel@hubcap.clemson.edu

In article <407@m3.mfci.UUCP> colwell@mfci.UUCP (Robert Colwell) writes:
>In article <29851@yale-celray.yale.UUCP> I wrote, on "true parallelism" vs.
"degree of vectorization":
....
>=In my world it is very simple. parallelism is when you do several things at
>=once, at different places. Vector operations are usually executed in a
>=pipeline. When the pipeline is filled every stage in it will execute in
>=parallel. Thus vector operations provide a special form of parallelism.
....
>"Vector ops" are too high a level of abstraction to be of use in
>distinguishing between vectorization and parallelism.  I think we
>have to break down the vector ops into their constituent parts.

The point I wanted to make is that vectorization is a very special form of
parallelism. The limits for "true parallelism" can, if I've got that concept
right, be expressed as data dependencies between "events" where every event
is an application of a "high-level" operator, say "+" in the vector example
above. If we have a multiprocessor system where some processors can perform
"+" and if we have some connections between the processors then a compiler
will have to find a schedule of the events that satisfies three criteria; 1.
communication requirements given by data dependencies must be met by
available connections, 2. "+" events are scheduled only on processors who
can perform "+", 3. no two events are scheduled on the same processor at the
same time. Furthermore the schedule should be "good" which usually means
short completion time.

Vectorization can be described in exactly the same way; in order to do this
"+" must be expressed in terms of suboperations matching the stages of the
pipeline. Every event a(i)+b(i) is now a set of smaller events according to
this, let's call them (i,k) for each vector index i and each stage k. Since
(i,k+1) uses the result from (i,k) as input there is now a data dependency
between each such pair. This new set of events can now be scheduled *in
exactly the same way as above*, where our "multiprocessor system" now
consists of the stages in the pipeline linearly connected stage k -> stage
k+1. 2. transforms to "(i,k) must be scheduled on k" and 1. transforms to
"if (i,k) is scheduled at k for time t, then (i,k+1) must be scheduled at
k+1 for time t+1" (assuming every pipeline stage takes one time step to
complete).

This is a 25 line description of what I tried to say with four lines in my
previous posting.

>Fine-grain parallelism is the principal diet of VLIWs, and we (well,
>I) define it to be one of a small set of things:  memory load or
>store, register-to-register integer or floating operation, and I/O.
>When you've broken down your program into ops at that level, you can
>then schedule them for execution in an optimal way.  Operations that
>are (at that time) unconstrained save for data dependencies exhibit
>what I think of as useful parallelism.
>
>Of course, as soon as we have a decent enough definition, somebody
>will try to apply it to a systolic or connection machine
>and we'll have to start over. ;-)

Yes, you will have to! :-) Have you heard of so-called space-time mapping
methods for synthesizing systolic arrays? These are essentially scheduling
methods that adhere to the three criteria I sketched above. The scheduling
is often concisely expressed as a function from the set of events to
space-time coordinates. So far I've seen no attempts to apply this way of
thinking to the Connection Machine but it is totally clear that it works in
theory. On such a machine the SIMD constraint will replace 2. (the same
operation in time instead of at the same processor) and the communication
requirement 1. will have to be a little more refined and take into account
such things as congestion etc.

Bjorn Lisper