Path: utzoo!attcan!uunet!snorkelwacker!usc!zaphod.mps.ohio-state.edu!swrinde!emory!hubcap!art
From: art@cs.bu.edu (Al Thompson)
Newsgroups: comp.parallel
Subject: Re: fine->medium->coarse
Message-ID: <9173@hubcap.clemson.edu>
Date: 31 May 90 12:40:52 GMT
Sender: fpst@hubcap.clemson.edu
Lines: 28
Approved: parallel@hubcap.clemson.edu

In article <9166@hubcap.clemson.edu> george%avocet@cs.utah.edu (Lal George) writes:
|I would like clarification regarding the proper meaning of 
|the terms fined grained, medium grained and coarse grained 
|parallelism. I have seen the latter two being used 
|interchangeably. Where does one typically draw the line between
|medium and coarse grained parallelism. 

I don't have the reference handy, but it's in C. Gordon Bell, "Multis a
new class of computer" or something close to that.  It's in Science in
1985.

Bell defines "grain" as the number of machine instructions executed
between synchronization events.  Fine grained <20, medium 20-200, coarse
200-2000 and very coarse >2000.

Stone, in "High-Performance Computer Architecture 2nd ed.", Addison-Wesley
p 309 in a discussion of parallel performance, says, "This section shows
that performance benefits strongly depend on the ratio R/C, where R is the
length of a run-time quantum and C is the length of communications
overhead produced by that quantum.  The ratio expresses how much overhead
is incurred per unit of computation."..."The ratio R/C is a measure of
\{em task granularity}.  In \{em coarse-grain} parallelism, R/C is
relatively high, so each unit of computation produces a relatively small
amount of communication.  In {\em fine-grained} parallelism, R/C is very
low, so there is a relatively large amount of communication and other
overhead per unit of computation."  Stone does not attach any particular
numbers to "fine", "coarse" etc. but it is clear his thinking is in the
same ballpark as Bell's.