Thread: Parallel merge sort

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);
    }
}

So you want a process tree which looks like this, where M is a merging parent, and S is a sorting child.

Code:

     M
    / \
   M   S
  / \
 S   S

Seems like an ideal case for recursion to me.

So forget about sorting and merging for the moment, and focus on getting something to print out all the steps, like

sorting from 0 to 999
sorting from 1000 to 1999
merging 0 to 1999

and so on through all the steps you need.

When that looks good, you can replace the relevant steps with fork() and wait(), and perform the actual sort and merge as needed.

I dunno, did you use the recursive approach and get 32 leaves printed out?

If it's printing out the list of sorts and merges OK, then just replace them with fork() calls and see what happens.