george%avocet@cs.utah.edu (Lal George) (05/31/90)
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. Thanks. Lal.
art@cs.bu.edu (Al Thompson) (05/31/90)
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.
jones@pyrite.cs.uiowa.edu (Douglas W. Jones) (05/31/90)
>From article <9166@hubcap.clemson.edu>, by george%avocet@cs.utah.edu (Lal George): > I would like clarification regarding the proper meaning of > the terms fined grained, medium grained and coarse grained > parallelism. These terms are poorly standardized, if at all. One definition I've seen said that systolic, pipelined and SIMD architectures are fine-grained, in the sense that critical sections and synchronization take place at the level of single machine instructions. Medium grained synchronization was defined as that involving critical sections or synchronization delays of 10 to 100 instructions, and coarse grained was defined as that involving critical sections or synchronization delays of thousands of instructions. This is all quite arbitrary. What is important is that the relative granularity of two parallel algorithms can be compared using such things as critical section size or the duration of an acceptable synchronization delay. I would describe my work on shared priority queues (CACM Vol 32 No 1) as involving medium grained parallelism in an MIMD shared memory environment. Doug Jones jones@herky.cs.uiowa.edu
gkj@doc.imperial.ac.uk (Guido K Jouret) (06/01/90)
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. fine =< medium =< coarse. The formal way to proceed is to find some suitably personal metric (i.e. the number of assembly language instructions in a task whose opcodes end in L) and use that to divide your metric space in three. The first part is the light-grained tasks, the middle corresponds to medium granularity, etc. Guido...
jayasim@cis.ohio-state.edu (D Jayasimha) (06/08/90)
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. > >Thanks. > >Lal. As others have pointed out, there is no standard defintion to say what a "grain" is. But, I find the following to be a useful guide- a "grain" is the smallest scheduling unit on a processor- the "definition" is biased towards scheduling of processes and one could poke holes at the definition (for example, there is also an implicit language model assumed) - nevertheless, I find it to be useful: Fine grained parallelism- exploits parallelism at the "basic operation level" (e.g., addition, multiplication) Medium grained parallelism- exploits parallelism at the loop level, i.e., an iteration of a loop level is the scheduling unit; Coarse grained paralleism- exploits parallelism at the subprogram level, i.e., a subprogram or a procedure is the scheduling unit. d n jayasimha (jayasim@cis.ohio-state.edu) Dept of Comp & Inf Sc The Ohio State Univ Columbus, OH 43210.
fouts@bozeman.ingr.com (Martin Fouts) (06/08/90)
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. Hmm. A good indication of the problem which arises in making this distinction is your "fine->medium->coarse" notation. The way I think of granularity is as a graduated scale moving from fine on the left to coarse on the right. There are three problems with this. There is no standard calibration for the scale. The ranges overlap. Marketing people have gotten their hands on the definitions. Before marketing, the range might have looked like: +-- As fine grained as possible | As coarse grained as possible --+ | | v v |---- fine ----| |---- medium ----| |---- coarse ----| Now it might look like +-- As fine grained as possible | As coarse grained as possible --+ | | v v |---- fine --------------| ( I claim I do fine grained) |---- medium ----| ( I claim you do medium grained) |-------------- coarse ----| ( or, I claim coarse is good enough) The whole thing is further complicated by measuring different kinds of granularity with the same adjectives. For instance, pipelined machines are sometimes said to be fine grained because of the locality of overlap, while simd systems are sometimes said to be fine grained because of the huge number of parallel operations that can be performed simultaneously. Arg. Another futile exercise in attempting to use English as a precise language. 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.
narayan@atanasoff.cs.iastate.edu (Pankaj Narayan) (06/09/90)
Almasi and Gottlieb's book : Higly Parallel Computing QA76.5 A385 Page 15: The *granularity* or *grain size* is the average subtask SIZE, measured in instructions executed (on some agreed-on serial computer) The *degree* or *extent* of parallelism is the NUMBER of subtasks available *Level* (as in 'procedure-level parallelism, expression-level parallelism' etc., refers to the SOURCE of the parallelism in what was originally a serial program. ---- Hope this helps. -- Pankaj Narayan narayan@atanasoff.cs.iastate.edu 246 North Hyland Ave, Apt. 306 ,Ames, IA 50010 Ph: (515) 292-5535