Open MPI logo

Open MPI User's Mailing List Archives

  |   Home   |   Support   |   FAQ   |   all Open MPI User's mailing list

From: Harakiri (harakiri_23_at_[hidden])
Date: 2006-12-19 15:33:11


Hello,

i need some input on the parallelisation of quicksort.
If anyone knows a more appropriate forum/list than
this, please tell me =)

I've written 2 different approaches to the quicksort
parallelisation.

1. The "master" server splits the array of numbers
into N seperate parts, where N is the number of
available clients or slave servers. Each slave then
does a quicksort on its own subarray - finally all
slaves sent their subarray to the master. The master
then does a quicksort on the presorted list.
*This was done for the assumption that presorted list
sort faster with quicksort than very unordered/random
numbers lists.

2. The "master" server finds out the MIN and MAX value
from the to sorting array (iterates through all
numbers). Then it will assign boundaries to each slave
starting from MIN for the first slave, to MAX for the
last slave (i.e. for 2 slaves it would be from MIN ->
MAX/2 and MAX/2+1 -> MAX).
The master then sends the whole array to each slave,
each slave filters through the whole array all numbers
within their own boundary (slave 1 for example would
find all numbers between MIN -> MAX/2), after that it
would quicksort the resulting array. Finally each
slave server would sent the resulting subarrays to the
master in the correct sequence - meaning that the
master server would not be needed to do any sorting at
all - only append the results i.e. slave1 starts
first, then slave2...

This has the advantage that only minimum network
"messages" are sent (not traffic).

Anyone has any different ideas ? I've read a few
papers about it - the basic approach would be to
parallel the divide and conquer part - which would
result in ALOT of network messages...

Thank you

__________________________________________________
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com