Subject: some comments on parallel decomp.

From: Saleh Elmohamed <[email-masked]>
Date: Sat, 3 Jul 1999 20:53:24 -0400

Hi Doug,

Sorry for not getting the chance to sent you comments, etc.
on the parallel programming chapter. I've quickly gone over it
and sort of few things came to mind... I'll try to send more on 
the rest of the chapter, and particularly on Cilk later... 
If none of these make sense, let me know :)

Comments:

On the aspect of "availability"; when dealing with parallel/dist
computing on, say a platform of clusters, "availability" is seeking 
to minimize downtime of large critical systems, such as important 
on-line DBs and TPS. Structurely, these kind of systems have much in 
common with multiprogramming clusters, etc...

One general question(s) to ask is that: if you have portability
and 'generality', how do you achieve 'efficiency'? and how do you
measure it? ... that is, what is the metric used here?

Task-based parallelism:

On the design steps stated; from a conventional parallel computing
point of view the job of creating a parallel program out of a
sequential one is roughly as follows:

1. Decomposition of the computation into tasks ...
2. Assignment of tasks to processes...
3. Orchestration of necessary data access, communication, and
synch among processes...
4. Mapping or binding of processes to processors...

'Decomposition' and 'assignment' together are called 'partitioning',
since they divide the work done by the program among the cooperating
processes.

On the issue of load-balancing...  Its problems are much
more common where 'problems' are decomposed into different functions,
rather than splitting one function across processors. It is usually
nearly impossible to evenly balance the processing requirements of
different functions... So, yes, as you pointed out, load balancing
gets better when there are more blocks (or tasks) available to do in
parallel. On the other hand, with many small blocks you could end up
with more serialization overhead and degradation of cache
efficiency. In most cases, there is no perfect solution to this
problem. The user just have to find a hunck of work that is big enough 
to overcome serialization and cache effects, yet small enough not
to suffer dramatically from load-balancing problems. From experience,
such intermediate sizes quite often exist. When they don't, the
problem is simply not efficiently parallelizable, at least not in the
representation or form being investigated. Perhaps, other
representation will work.

... In message-passing paradigms, load-balancing is explicit which is
a function of how data is distributed, except for really large-sized
granularity parallelism. The reason is that it takes much longer to
transmit the data required from node (i.e. SMP) to another, than
within a single node. I'd say tens or hundred of megabits per sec
vs. gigabytes per sec, respectively.

On contention:

It is a particularly insidious performance problem. The most troubling 
thing about it, of course among others, is that the cause of it may be
difficult to identify since the effects might be felt at very different
points in the program than the original cause (all the more so if
communication is implicit).
A couple of programming principles to somewhat alleviate it :
1. avoid having too many processes communicating with the same
process, and 
2. stagger messages to the same destination in time so as not to
overwhelm the destination or resources along the way.

...

On Fork/Join:

One of the steps mentioned above, involved in creating a parallel
program is the concept of orchestration.... It also involves things 
such as creating processes, managing dynamic tasking, etc. So, due to the
high cost of creation, processes are created once up front and have them
execute till the program terminates, rather than creating and
terminating processes as parallel sections of the code are entered
and exited by a single main thread of computation. This is a fork-join 
approach which is sometimes used with lightweight threads instead of
processes...

-----------------

More comments/questions to come ...

best wishes,
Saleh

---

From: Doug Lea <[email-masked]>
Date: Wed, 14 Jul 1999 21:05:10 -0400 (EDT)

(Sorry for the delay!)

Thanks for the comments! I'm in midst of revamping some of this for
second edition of CPJ. I'm trying to maintain focus on shared-memory
multiprocessors using a single JVM, which accounts for total disregard
for a lot of classic parallel processing stuff! :-) But it is still
fun to have someone critique from a more classic perspective.

-- 
Doug Lea, Computer Science Department, SUNY Oswego, Oswego, NY 13126 USA
[email-masked] 315-341-2688 FAX:315-341-5424 http://gee.cs.oswego.edu/