Parallel merge sort

[stud91]

Hey everyone! So I wanted to implement parallel merge sort in C using fork(), mmap(...) and waitpid() system calls only.....The program should create processes until the problem size is less than 1000...I need to sort an int array..
The algorithm that i have in mind is...

(Suppose i create 4 processes, 1 parent and 3 children)

Use mmap() to share data b/w processes..
Parent P divides the array into 2 parts. fork() creates a child C1. Assign sorting of 2nd half of array to C1 and first half to P. P calls fork() again and creates another child C2. C2 will sort the second half of P's array. Simultaneously C1 calls fork() and creates another child C3 and C3 will sort the second half of C1's array. Meanwhile C1 and P will wait for the sorting to complete (i.e. wait for C3 and C2 to terminate respectively). Then C1 will merge with C3 and P with C2 and P will wait for C1 and so on...until the array is sorted...

What i need to know is how to call a fork() within a fork() in this particular case...
e.g.
For two 4 processes i.e. when n = 2 can i implement like this..If yes, then actually i want to make at most 32 processes i.e. when n=5....So I cannot possibly use so many if statements and i don't think i can use for loop here..

<code>
pid = fork();

if(pid == 0) //child1 process
{
if(n == 2){

pid2 = fork();
if (pid2 == 0) //child3 process
{
msort(numbers,(3*size)/4,size,buffer);
}
else if (pid2 > 0) //child 1 process -- parent of child3
{
msort(numbers,size/2,(3*size)/4,buffer);
waitpid(pid2,NULL,0);
merge(numbers,size/2,(3*size)/4,size,buffer);
}
}
else{
msort(numbers,size/2,size,buffer);
}
}

else if (pid > 0) //parent process
{
if(n == 2){
pid2 = fork();
if (pid2 == 0) //child2 process
{
msort(numbers,0,size/4,buffer);
}
else if (pid2 > 0) //parent process
{
msort(numbers,size/4,size/2,buffer);
waitpid(pid2,NULL,0);
merge(numbers,0,size/4,size/2,buffer);
}
}
else{
msort(numbers,0,size/2,buffer);
waitpid(pid,NULL,0);
merge(numbers,0,size/2,size,buffer);
}
}
</code>

 

[GeekyDeaks]

Hi Stud,

This lends itself to a recursive solution. Forgive my paranoia, but this looks like course work to me, so I'll just give some pointers to begin with:

You want a function which will check if the size is small enough for a direct sort, or if it needs to fork new processes, each new process calling itself with a smaller array.

i.e.

function rsort(numbers, size, buffer.... ) {


  if(size < 1000) {
     // just sort the numbers now
     msort(.....);
     return;
  }

  pid1 = fork();
  if(!pid1) {
    rsort(// first half of numbers)
    return;
  }

  pid2 = fork();
  if(!pid2) {
    rsort(// second half of numbers)
    return;
  }

  // wait for both child process to finish and then merge

}

You could also stick the forks() in a quick for(i = 0; i< 2; i++) loop if you want and use an array for the pid's. You could then calculate the split from i and allow 2+ child processes per recursion.

HTH,
Scott