Pedagogical examples of parallelism
in [General Programming]
|
Prev: SETP-10 Call for papers
Next: Unification Algorithm
From: Jon Harrop on 16 Nov 2009 12:33 There are many competing high-level solutions for parallel programming. For example, Cilk-style wait-free work-stealing task deques. The pedagogical example for this style of parallelism might be a parallel quicksort where subsorts are performed in parallel on different parts of the array. What other high-level solutions for parallel programming exist and what problems are best solved using them? For example, when is nested data parallelism preferable? -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/?u
From: blmblm on 14 Dec 2009 03:20 In article <WoKdnWw3wpQCEZzWnZ2dnUVZ8rCdnZ2d(a)brightview.co.uk>, Jon Harrop <jon(a)ffconsultancy.com> wrote: > > There are many competing high-level solutions for parallel programming. For > example, Cilk-style wait-free work-stealing task deques. The pedagogical > example for this style of parallelism might be a parallel quicksort where > subsorts are performed in parallel on different parts of the array. > > What other high-level solutions for parallel programming exist and what > problems are best solved using them? For example, when is nested data > parallelism preferable? > A very belated reply .... You don't mention the approaches I think would be most familiar to traditional-HPC programmers using MPI and OpenMP, namely splitting the iterations of a loop over a large array. Are those too simple for what you have in mind? -- B. L. Massingill ObDisclaimer: I don't speak for my employers; they return the favor.
From: Jon Harrop on 14 Dec 2009 13:37 blmblm(a)myrealbox.com wrote: > In article <WoKdnWw3wpQCEZzWnZ2dnUVZ8rCdnZ2d(a)brightview.co.uk>, > Jon Harrop <jon(a)ffconsultancy.com> wrote: >> There are many competing high-level solutions for parallel programming. >> For example, Cilk-style wait-free work-stealing task deques. The >> pedagogical example for this style of parallelism might be a parallel >> quicksort where subsorts are performed in parallel on different parts of >> the array. >> >> What other high-level solutions for parallel programming exist and what >> problems are best solved using them? For example, when is nested data >> parallelism preferable? > > A very belated reply .... > > You don't mention the approaches I think would be most familiar to > traditional-HPC programmers using MPI and OpenMP, namely splitting > the iterations of a loop over a large array. Are those too simple > for what you have in mind? The recursive subdivision of an array in quicksort is close enough to be the same thing. You can easily solve it with task parallelism. -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/?u
From: blmblm on 22 Dec 2009 07:56 In article <QKmdncBm7KwK6bvWnZ2dnUVZ8uudnZ2d(a)brightview.co.uk>, Jon Harrop <jon(a)ffconsultancy.com> wrote: > blmblm(a)myrealbox.com wrote: > > In article <WoKdnWw3wpQCEZzWnZ2dnUVZ8rCdnZ2d(a)brightview.co.uk>, > > Jon Harrop <jon(a)ffconsultancy.com> wrote: > >> There are many competing high-level solutions for parallel programming. > >> For example, Cilk-style wait-free work-stealing task deques. The > >> pedagogical example for this style of parallelism might be a parallel > >> quicksort where subsorts are performed in parallel on different parts of > >> the array. > >> > >> What other high-level solutions for parallel programming exist and what > >> problems are best solved using them? For example, when is nested data > >> parallelism preferable? > > > > A very belated reply .... > > > > You don't mention the approaches I think would be most familiar to > > traditional-HPC programmers using MPI and OpenMP, namely splitting > > the iterations of a loop over a large array. Are those too simple > > for what you have in mind? > > The recursive subdivision of an array in quicksort is close enough to be the > same thing. You can easily solve it with task parallelism. You think? Well, probably so, or you wouldn't have said so. But to me these seem like fairly different things -- splitting up the iterations of a loop among processes/threads can be done statically (by which I mean that one can decide before beginning the loop how to assign iterations to processes/threads), while I don't think that's the case for quicksort. Hm. Mileage varies with regard to what counts as "close enough to be the same thing"? Or am I missing some point .... -- B. L. Massingill ObDisclaimer: I don't speak for my employers; they return the favor.
From: Jon Harrop on 24 Dec 2009 19:42
blmblm(a)myrealbox.com wrote: > In article <QKmdncBm7KwK6bvWnZ2dnUVZ8uudnZ2d(a)brightview.co.uk>, > Jon Harrop <jon(a)ffconsultancy.com> wrote: >> The recursive subdivision of an array in quicksort is close enough to be >> the same thing. You can easily solve it with task parallelism. > > You think? Well, probably so, or you wouldn't have said so. > But to me these seem like fairly different things -- splitting > up the iterations of a loop among processes/threads can be done > statically (by which I mean that one can decide before beginning > the loop how to assign iterations to processes/threads), while I > don't think that's the case for quicksort. Hm. Mileage varies > with regard to what counts as "close enough to be the same thing"? > Or am I missing some point .... I see. You can precompute a parallel strategy with nested loops but not arbitrary recursion like quicksort as you say. The former is being reinvented as "nested data parallelism" in the Haskell world today but it has been the pedagogical solution for parallelizing sparse linear algebra on supercomputers for decades. However, a precomputed parallel strategy tends to assume that equal-sized tasks will take equal time to compute which is often not the case on a multicore desktop due to OS scheduling, cache effects and so on. So you really need dynamic load balancing to make efficient use of a modern machine and that is most easily obtained by using the same divide and conquer spawning tasks recursively that you use to parallelize solutions like quicksort. -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/?u |