Nary Search Using OpenMP

It's been quite a while since I last posted. This post shows how conduct a nary search on an array using OpenMP.

OpenMP

Allows to create threads in C by simple pragma directives, this is one of the easiest ways to get threading done. In case you like the way threading is done here you might want to take a look at the various directives offered by OpenMP for parallel processing.

N-ary Search

You might have worked earlier with maybe ternary, or at least binary search. In this kind of a search we divide the sorted array into n parts at each stage and then perform the search.

Compilation using GCC

gcc -o outfilename -fopenmp omp_code.c

Code

//Code by Abhishek Munagekar to implement  nary search
#include "iostream"
#include "omp.h"
int newar[100];
using namespace std;

int nary(int l,int r, int key,int n){
 int index = -1;
 int size=(r-l+1)/n;
 if(size==0 || n==1){
  #pragma omp parallel for
  for(int i=l;i<=r;i++){
   if(newar[i]==key) index=i;  
  }
 return index; 
 }
 int left=l;
 int right=r;
 omp_set_num_threads(n);
 omp_set_nested(1);
 # pragma omp parallel
 {
  int id=omp_get_thread_num();
  int lt=l+id*size;
  int rt=lt+size-1;
  if (id==n-1) rt=r;
  
  if(newar[lt]<=key && newar[rt]>=key){
   left=lt;
   right=rt;
  }  
 }
 if (left==l && right ==r) return -1;
 return nary(left,right,key,n);

}

int main(){
 
 
 
 cout<<"Program for nary search"<<endl; 
 int nos;
 int nthread;
 cout<<"Enter the number of numbers\t"<<endl;
 cin>>nos;
 cout<<"Please enter numbers one after the other\n";
 for(int i=0;i<nos;i++) cin>>newar[i];
 cout<<"Enter the number of theads\t";
 cin>>nthread;
 cout<<"Enter the key\t";
 int key;
 cin>>key;
 cout<<endl;
 cout<<nary(0,nos-1,key,nthread)<<endl;
 
 
  
}

Conclusion

This article just demonstrates the capabilities of OpenMP. One of the best parts of OpenMP is that there is minimal amount of code written for threading. Even if the library is not available these directives could be ignored, so the compiler would treat it like serial code.