Thursday, 14 May 2015

OpenMP program for n-ary search algorithm

Introduction:
            n-ary search algorithm is for searching a number from the given sorted array by dividing the array into n equal parts recursively until we get the required position of required number. Binary search is also a n-ary search with value of n=2.
             In this program, I have used multi-threading to find the n parts of array. Break-up points which separates these parts, I called them 'separators' and their indices are saved in the array 'sep'.

Watch following video to know basics of OpenMP Programming:


             Go through the following program and check the output which I have provided at the end of this post. For this program, I have used gcc compiler on Linux. gcc and g++ compilers, they are consisted of OpenMP library.


Program(openmpnarysearch.c):
#include<stdio.h>
#include<math.h>
#include<omp.h>

void main()
{
 int sep[20],array[20],key,i,j,n,left,right,size,interval,index,break_value=0,tid;
 printf("Enter the size of array\n");
 scanf("%d",&size);
 printf("Enter the elements of array in ascending order\n");
 for(i=0;i<size;i++)
  {
   scanf("%d",&array[i]);
  }
 printf("Enter the key to be searched\n");
 scanf("%d",&key);
 printf("Enter the value of n for n-ary search algorithm\n");
 scanf("%d",&n);

 left=0;
 right=size-1;

 if(key>=array[left] && key<=array[right])
  {
   while(left!=right)
   {
     // (start) code to find seperators
     printf("left=%d, right=%d, size=%d\n",left,right,size);
     if(size<=n)
      {
       #pragma omp parallel for num_threads(size)
       for(i=0;i<size;i++)
        {
         sep[i]=left+i;
         tid=omp_get_thread_num();
         printf("Thread %d allocated sep[%d]=%d\n",tid,i,sep[i]);
        }
      }

     else
      {
       sep[0]=left;
       interval=ceil((float)size/(float)n);
     
       #pragma omp parallel for num_threads(n-1)
       for(i=1;i<=n-1;i++)
        {
         sep[i]=left+interval*i-1;
         tid=omp_get_thread_num();
         printf("Thread %d allocated sep[%d]=%d\n",tid,i,sep[i]);
        }

        sep[n]=right;
       }
      // (end) Code to find seperators

      // (start) Code for comparison

      for(i=0;i<=n;i++)
       {
         if(key==array[sep[i]])
          {
            index=sep[i];
            printf("Element found at position %d\n",index+1);
            break_value=1;
            break;
          }
         if(key<array[sep[i]])
          {
            right=sep[i];
            if(i!=0)
              left=1+sep[i-1];
            size=right-left+1;
            break;
          }
       }

      // (end) Code for comparison

      if(break_value==1)
        break;
   } //End of 'while' loop
  } //End of 'if'

if(left==right || !(key>=array[left] && key<=array[right]))
  printf("Element does not present in the list\n");

} //End of main()



Instructions to run:
For compilation:
gcc -fopenmp program_name.c -lm
(Note: -fopenmp is used to use "OpenMP" library while -lm is used to use "math.h").

To run:
./a.out

Output: 

For Element present in the sorted array






For Element NOT present in the sorted array








Next: Common Lisp Programming Tutorial with Examples

Previous: OpenMP Program for Merge Sort





7 comments:

  1. Very Nice Post Parag...

    ReplyDelete
  2. It is failing for the following input:
    No. of elements: 8
    Array elements:
    2 5 9 15 16 19 30 48
    Element to be searched: 30
    Value of n for n-ary search: 4

    ReplyDelete
    Replies
    1. Kaustubh, sorry for late reply.
      I have made respective changes in program and also added your example into the output.
      Thanks for your suggestion.

      Delete
    2. Can u tell me how this algo works.And what is sep and why to use.

      Delete
    3. Value for n in nsearch means the n should be available in the input list

      Delete
    4. n-ary search means searching any particular element from the given n sorted elements. Binary Search is 2-ary search algorithm.

      Delete
    5. Separators are the elements which separate the Sub groups of numbers. For example, in binary Search, middle element is the separator.

      Delete