pragya sharma pragya sharma - 6 months ago 22
C Question

Openacc: How can I make insertion sort more parallel

Can you please suggest how can I make openacc more parallel. I am making mergesort with insertion sort. Should I use "loop" or "for" for using loop. Also for insertion sort should it be kernel or parallel.

#include <stdlib.h>
#include<stdio.h>
#include <time.h>
#include <openacc.h>
#define THR 1000

//Insertion sort
void isort (int *a, int left, int mid, int right) {

int i,j;
# pragma acc kernels
{
# pragma acc parallel loop num_gangs (1024)
for ( i = mid; i <= right; i++) {
for ( j = i - 1; j >= 0; j--) {
if (a[i] < a [j]) {
int temp = a[j];
a[j] = a[i];
a[i] = temp;
i--;
}
}
}
}
}
void merge(int a[], int left, int right,int left_half[], int right_half[])
{
int i, j, k;
int mid = (left + right + 1) / 2;

i = j = 0;
k = left;

while (i < mid - left && j <= right - mid) {
if (left_half[i] < right_half[j]) {
a[k] = left_half[i];
++i;
} else {
a[k] = right_half[j];
++j;
}

++k;
}

// Copying any leftover elements
#pragma acc data copy(a, right_half)
while (j <= right - mid) {
a[k++] = right_half[j++];//copy remaining elements of the first half

}
#pragma acc data copy(a, left_half)
while (i < mid - left) {
a[k++] = left_half[i++]; //copy remaining elements of the second list
}
}

void mergeSort(int a[], int left, int right)
{
if (left < right) {
int mid = (left + right + 1) / 2;
int left_half[mid - left];
int right_half[right - mid + 1];
int i;
# pragma acc kernels
{
// Copying elements
# pragma acc parallel loop shared (left_half, a)
for (i = left; i < mid; ++i) {
left_half[i - left] = a[i];
}

// Copying elements
# pragma acc parallel loop shared (right_half, a)
for (i = mid; i <= right; ++i) {
right_half[i - mid] = a[i];
}
}
// Recursive call
mergeSort(left_half, 0, mid - left - 1);
mergeSort(right_half, 0, right - mid);
// Merge the two partitions
if ((right - left) > THR){
merge(a, left, right, left_half, right_half);
} else {
isort(a, left,mid, right);
}
}
}


int main()
{
int i, n, *a,c;

printf("Enter the number of elements\n");
scanf("%d",&n);
a = (int *)acc_malloc(sizeof(int) * n);
srand(time(0));
for(i=0;i<n;i++){
a[i]=rand()%1000;
}
printf("\nThe unsorted a is:");
printf("\n");
for(i=0;i<n;i++)
printf("%d ",a[i]);;

mergeSort(a, 0, n-1);
printf("\nSorted a:");
printf("\n");
for(i=0;i<n;i++)
printf("%d ",a[i]);
printf("\n");
}

Answer Source

I don't know the syntax of openacc. As of openmp syntax, if you have larger arrays to loop you can even run each loop of the for loop in parallel while both the for loops run parallel. Take a look at this link1, link2. I don't know if you meant the same by writing # pragma acc parallel loop above for loops or if you have something like this in openacc you can add that.

And you can run both mergesorts parallel, something like this.

# pragma acc kernels
   {
     # pragma acc parallel{mergeSort(left_half, 0, mid - left - 1);}
     # pragma acc parallel{mergeSort(right_half, 0, right - mid);}
   }
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download