www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - challenge #3 - Parallel for loop

reply janderson <askme me.com> writes:
I would like to be able to run a for loop in parallel, using syntax like:

//example 1
int sum = 0;
foreach_parallel(int a; array)
{
   sum += array[a];   //This could be anything
}

//Example 2
int sum = 0;
for_parallel(int a; a<array.length; ++a) //These could be anything
{
   sum += array[a];   //This could be anything
}

1) The call syntax is a simple generic one statement.
2) It needs to represent a foreach/for-loop as close as possible, 
although it doesn't need to look like a D foreach/for-loop.
3) It needs to handle things like adding all the parts in an array (this 
is the difficult part).
4) Since foreach_parallel always works on an array, you may take some 
concessions for this loop, taking the array of operation into account 
(ie, you may split the array).
5) If we can't do it, what syntax would you recommend to close this gap?

-Joel
Jan 26 2007
next sibling parent Sean Kelly <sean f4.ca> writes:
janderson wrote:
 I would like to be able to run a for loop in parallel, using syntax like:
 
 //example 1
 int sum = 0;
 foreach_parallel(int a; array)
 {
   sum += array[a];   //This could be anything
 }
 
 //Example 2
 int sum = 0;
 for_parallel(int a; a<array.length; ++a) //These could be anything
 {
   sum += array[a];   //This could be anything
 }
 
 1) The call syntax is a simple generic one statement.
 2) It needs to represent a foreach/for-loop as close as possible, 
 although it doesn't need to look like a D foreach/for-loop.
 3) It needs to handle things like adding all the parts in an array (this 
 is the difficult part).
 4) Since foreach_parallel always works on an array, you may take some 
 concessions for this loop, taking the array of operation into account 
 (ie, you may split the array).
 5) If we can't do it, what syntax would you recommend to close this gap?

See: http://www.digitalmars.com/pnews/read.php?server=news.digitalmars.com&group=digitalmars.D.announce&artnum=5015 This could also be done in user code however. The only real danger is that if more than one of the parallel threads throws an exception then the application must terminate. Sean
Jan 26 2007
prev sibling next sibling parent "Andrei Alexandrescu (See Website For Email)" <SeeWebsiteForEmail erdani.org> writes:
janderson wrote:
 I would like to be able to run a for loop in parallel, using syntax like:
 
 //example 1
 int sum = 0;
 foreach_parallel(int a; array)
 {
   sum += array[a];   //This could be anything
 }

This challenge "is not like the others". Unfortunately parallelization like the above is not going to be done soon. Parallelizing arbitrary serial code is an active research topic that has not been settled. In particular, notice that even your simple example requires serious smarts from a compiler, because it features dependencies across the loop: sum can be apparently updated on the n+1'th iteration only after it has been updated on the n'th iteration. Andrei
Jan 26 2007
prev sibling next sibling parent Bill Baxter <dnewsgroup billbaxter.com> writes:
janderson wrote:
 I would like to be able to run a for loop in parallel, using syntax like:
 
 //example 1
 int sum = 0;
 foreach_parallel(int a; array)
 {
   sum += array[a];   //This could be anything
 }
 
 //Example 2
 int sum = 0;
 for_parallel(int a; a<array.length; ++a) //These could be anything
 {
   sum += array[a];   //This could be anything
 }
 
 1) The call syntax is a simple generic one statement.
 2) It needs to represent a foreach/for-loop as close as possible, 
 although it doesn't need to look like a D foreach/for-loop.
 3) It needs to handle things like adding all the parts in an array (this 
 is the difficult part).
 4) Since foreach_parallel always works on an array, you may take some 
 concessions for this loop, taking the array of operation into account 
 (ie, you may split the array).
 5) If we can't do it, what syntax would you recommend to close this gap?
 
 -Joel

That's the kind of thing that OpenMP does (but only for C/C++/Fortran). http://www.openmp.org. The syntax is more like #pragma omp parallel for for(int i=0; i<N; i++) { // operation } But from the FAQ: """ Q8: What if I just want loop-level parallelism? A8: OpenMP fully supports loop-level parallelism. Loop-level parallelism is useful for applications which have lots of coarse loop-level parallelism, especially those that will never be run on large numbers of processors or for which restructuring the source code is either impractical or disallowed. Typically, though, the amount of loop-level parallelism in an application is limited, and this in turn limits the scalability of the application. OpenMP allows you to use loop-level parallelism as a way to start scaling your application for multiple processors, but then move into coarser grain parallelism, while maintaining the value of your earlier investment. This incremental development strategy avoids the all-or-none risks involved in moving to message-passing or other parallel programming models. """ --bb
Jan 27 2007
prev sibling next sibling parent Benji Smith <dlanguage benjismith.net> writes:
janderson wrote:
 I would like to be able to run a for loop in parallel, using syntax like:
 
 //example 1
 int sum = 0;
 foreach_parallel(int a; array)
 {
   sum += array[a];   //This could be anything
 }

Isn't this really just a specialized case of Map/Reduce? It's trivial, as long as the operations inside the loop are completely associative. In other words: A(B + C) == A(B) + A(C) Since a summation satisfies the associativity requirements, then this one is pretty trivial to implement. But, not all operations are associative, and those ones won't be trivially parallizable, without changing the algorithm. Rather than focusing on a foreach_parallel construct, I'd be interested in seeing a competition to implement the most elegant (syntax/semantics) version of Map/Reduce. It'd be especially cool if a library implementation of Map/Reduce could abstract away the details of whether the function was mapped across multiples cores, cpus, or entire machines. More details here: http://labs.google.com/papers/mapreduce.html http://en.wikipedia.org/wiki/MapReduce --benji
Jan 26 2007
prev sibling next sibling parent Mikola Lysenko <mclysenk mtu.edu> writes:
janderson wrote:
 I would like to be able to run a for loop in parallel, using syntax like:
 
 //example 1
 int sum = 0;
 foreach_parallel(int a; array)
 {
   sum += array[a];   //This could be anything
 }
 
 //Example 2
 int sum = 0;
 for_parallel(int a; a<array.length; ++a) //These could be anything
 {
   sum += array[a];   //This could be anything
 }
 
 1) The call syntax is a simple generic one statement.
 2) It needs to represent a foreach/for-loop as close as possible, 
 although it doesn't need to look like a D foreach/for-loop.
 3) It needs to handle things like adding all the parts in an array (this 
 is the difficult part).
 4) Since foreach_parallel always works on an array, you may take some 
 concessions for this loop, taking the array of operation into account 
 (ie, you may split the array).
 5) If we can't do it, what syntax would you recommend to close this gap?
 
 -Joel

http://www.assertfalse.com/downloads/dcsp-alpha0.zip -Mik
Jan 27 2007
prev sibling parent "David B. Held" <dheld codelogicconsulting.com> writes:
janderson wrote:
 I would like to be able to run a for loop in parallel, using syntax like:
 
 //example 1
 int sum = 0;
 foreach_parallel(int a; array)
 {
   sum += array[a];   //This could be anything
 }
 [...]

Of course, for it to be parallelizable at all, your comment "This could be anything" must be false. For instance, if the loop body depends on 50% of the array elements for any given iteration, it may well be worse-performing attempting to do it in parallel (if it's possible at all). If the body mutates the array in any way, parallelization might be impossible. The only sane way to guarantee parallelizability is to demand that the loop body only be a function of the current list item and not mutate the list (including inserting or removing elements). If you impose those requirements, then you end up with something rather familiar: fold. C++ likes to be different, so it spells it "accumulate" (which is much more suggestive of this particular use case). Of course, fold is just what the varargs_reduce() algorithm is, so problem solved. That is, the problem is parallelizable when varargs_reduce() can call varags_reduce_parallel(): when f is associative. In this case, you have to restructure f so that it is pure. State is very bad for both the functional paradigm and parallelism in general. C++ (and mostly D) tend to be very stateful because on a single-threaded processor, mutable state algorithms tend to be fast. But single-threaded processors are soon going the way of the dodo, so get a leg up and throw away that mutable state! Dave
Feb 01 2007