Sunday, August 26, 2007

Parallel QuickSort in COSA

The day before yesterday, I did a search on the web looking for a parallel quicksort algorithm in Erlang. I could not find any. I was somewhat surprised (although not entirely) given that Erlang is promoted as one of the best concurrent languages that will make it easy to take advantage of the parallelism of our new fancy multicore processors. I must admit that Erlang's creators never claimed that it was a parallel programming language, just concurrent with light weight processes. So I decided to design a parallel quicksort component based on the COSA software model. COSA is ideal for this sort of thing because it was designed for super fine-grain parallelism.

PS. Please write me a note if you know of a parallel quicksort in Erlang or some other functional/concurrent language.


Dan said...

I must say that I don't believe I'll fully understand the COSA model without having an actual implementation so I can start coding.
Experimenting is an important part of the way I learn .
However , I've thought of a
reasonably elegant sincrounous version of the lee algorithm .In most programing languages existent today , Lee's algorithm would require an additional stack-like structure . I hope you can understand my pseudocode :

//we call array[][] the array for which we execute the algorithm , 0
representing an empty space , and -1 a wall .

int length;
int height;
int number; ) {

//do nothing
make-a-lee-cell(length+1 ,height number+1);
make-a-lee-cell(length ,height+1 number+1);
make-a-lee-cell(length-1 ,height number+1);
make-a-lee-cell(length ,height-1 number+1);}

Of course , I could not represent
the truly synchronous solution as I have it in my head with pseudocode,
but I hope you understand my idea .
I look forward to the day when I will be able to implement it in COSA .

Nicholas said...

Check out the homepage of the NESL project. Their main sample is a Parallel-Quicksort, which they say takes well under 100 lines to effeciently implement in NESL, and over 1000 lines in C++/MPI. I think they did this many years ago.