CODEWITHSUNDEEP
copenmpmergesort
singleton
singleton

Reputation: 1

Mergesort using openmp

I am learning parallel programming and I'm trying to parallelize mergesort such that the number of threads equals the number of levels of recursion. Divide the array into 8 subarrays and use each thread to each subarray. I do not want to use pthreads. I am posting the sequential code. Please tell me steps on how I can use #pragma commands and parallelize the algo.

#include <stdlib.h>

#include "omp.h"

void mergesort(int a[],int i,int j);
void merge(int a[],int i1,int j1,int i2,int j2);

int main()
{
    int *a, num, i;
    scanf("%d",&num);

   a = (int *)malloc(sizeof(int) * num);
    for(i=0;i<num;i++)
        scanf("%d",&a[i]);
        
    mergesort(a, 0, num-1);
    
    printf("\nSorted array :\n");
    for(i=0;i<num;i++)
        printf("%d ",a[i]);
        
    return 0;
}

void mergesort(int a[],int i,int j)
{
    int mid;
      int tid;  
    if(i<j)
    {
        mid=(i+j)/2;
         //tid=omp_get_thread_num;
        #pragma omp parallel sections 
        ct=omp_get_num_threads(3);
        {

       //printf("%d",tid);
            #pragma omp section
            {
                mergesort(a,i,mid);        //left recursion
            }

            #pragma omp section
            {
                mergesort(a,mid+1,j);    //right recursion
            }
        }

        merge(a,i,mid,mid+1,j);    //merging of two sorted sub-arrays
    }
}
 
void merge(int a[],int i1,int j1,int i2,int j2)
{
    int temp[1000];    //array used for merging
    int i,j,k;
    i=i1;    //beginning of the first list
    j=i2;    //beginning of the second list
    k=0;
    
    while(i<=j1 && j<=j2)    //while elements in both lists
    {
        if(a[i]<a[j])
            temp[k++]=a[i++];
        else
            temp[k++]=a[j++];
    }
    
    while(i<=j1)    //copy remaining elements of the first list
        temp[k++]=a[i++];
        
    while(j<=j2)    //copy remaining elements of the second list
        temp[k++]=a[j++];
        
    //Transfer elements from temp[] back to a[]
    for(i=i1,j=0;i<=j2;i++,j++)
        a[i]=temp[j];
}

Upvotes: 0

Views: 340

Answers (1)

J&#233;r&#244;me Richard
J&#233;r&#244;me Richard

Reputation: 50808

First of all, move the #pragma omp parallel in the main since multiple parallel section must not be nested (for sake of performance since it will create a new parallel section for each thread).

Then, do not use sections/section since it is not done for such a use. Use tasks instead. Tasks can be submitted recursively like what you want to do. You can wait for the tasks to be executed using a taskwait (typically before the merge).

Since tasks are expensive, you should consider not creating too much tasks. You can control either you want to create task or not using a if clause.

Do not forget to free the allocated data in the main function.

Upvotes: 1

Related Questions