[OpenMP] Solution 10 : Binary Search

This material is part of the course Practical Introduction to Parallel Programming and meant for educational purposes only.

Task

Implement a program that uses tasks to execute a binary search algorithm in parallel. Use the sequential implementation below as the basis of your program. Print the number of the thread that has found the value in the tree.

Hints

The binary tree is not sorted; a value can be located in the left or right sub-tree of a node. You must search both sub-trees.

Do not forget to indicate which variables are private and which are shared.

Can you verify that the search operation is executed in parallel?

What happens if you vary the maximum number of threads through the environment variable OMP_NUM_THREADS?

Paste this command into your terminal:

The password to connect is

Question 1: Binary Search

#include <stdio.h>
#include <stdlib.h>

#ifdef _OPENMP
#include <omp.h>
#else
#define omp_get_num_threads() 1
#define omp_get_max_threads() 1
#define omp_get_thread_num()  0
#endif

/* ---------------------------------------------------------------------
 * types
 * ------------------------------------------------------------------ */

struct                    node
{
  int                       value;
  struct node*              left;
  struct node*              right;
};

typedef struct node       node_t;

/* ---------------------------------------------------------------------
 * build_tree()
 *
 *   Builds a binary tree. The entries are NOT sorted.
 * ------------------------------------------------------------------ */

node_t*                   build_tree

  ( int                     count )

{
  node_t*  root = NULL;
  int      i;

  if ( count )
  {
    root = (node_t*) calloc ( 1, sizeof(node_t) );

    if ( ! root )
    {
      fprintf ( stderr, "Failed to allocate memory.\n" );
      exit    ( 1 );
    }
  }

  for ( i = 1; i < count; i++ )
  {
    node_t*  node = (node_t*) calloc ( 1, sizeof(node_t) );
    node_t*  top  = root;

    if ( ! node )
    {
      fprintf ( stderr, "Failed to allocate memory.\n" );
      exit    ( 1 );
    }

    node->value = i;

    while ( 1 )
    {
      node_t**  next = NULL;

      if ( rand() % 2 )
      {
        next = &top->left;
      }
      else
      {
        next = &top->right;
      }

      if ( ! (*next) )
      {
        *next = node;
        break;
      }
      else
      {
        top = *next;
      }
    }
  }

  return root;
}

/* ---------------------------------------------------------------------
 * kill_tree()
 *
 *   Destroys a binary tree.
 * ------------------------------------------------------------------ */

void                      kill_tree

  ( node_t*                 root )

{
  if ( root->left )
  {
    kill_tree ( root->left );
  }

  if ( root->right )
  {
    kill_tree ( root->right );
  }

  free ( root );
}

/* ---------------------------------------------------------------------
 * find_value()
 *
 *   Returns a pointer to a node containing a specified value, or
 *   NULL if there is no such node.
 * ------------------------------------------------------------------ */

node_t*                   find_value

  ( node_t*                 root,
    int                     value )

{
  node_t*  node1 = NULL;
  node_t*  node2 = NULL;

  if ( root )
  {
    if ( root->value == value )
    {
      printf ( "Thread %d found the value.\n",
               (int) omp_get_thread_num() );

      return root;
    }

#pragma omp taskgroup
    {
#pragma omp task shared(node1,root)
      if ( root->right )
      {
        node1 = find_value ( root->right, value );
      }

#pragma omp task shared(node2,root)
      if ( root->left )
      {
        node2 = find_value ( root->left,  value );
      }
    }
  }

  if ( node1 )
  {
    return node1;
  }
  else
  {
    return node2;
  }
}

/* ---------------------------------------------------------------------
 * main()
 * ------------------------------------------------------------------ */

int main ( int argc, char** argv )
{
  node_t*  root = build_tree ( 100 );
  node_t*  node = NULL;

  omp_set_nested ( 1 );

  double t0 = omp_get_wtime();

#pragma omp parallel
  {
#pragma omp single
    {
      int  value = 42;
      if (argc>1)
        value = atoi(argv[1]);

      node = find_value ( root, value );

      if ( node )
      {
        printf ( "Value found: %d\n", node->value );
      }
      else
      {
        printf ( "Value not found.\n" );
      }
    }
  }

  double t1 = omp_get_wtime();
  printf ( "In %g seconds\n", t1-t0);

  kill_tree ( root );

  return 0;
}

Question 2: OpenMP environment variables

Specify the OpenMP environment variables that should be used for running your program (export OMP_NUM_THREADS=1 ...). Use semicolons to separate multiple variables

Question 3: Command Line Argument

Specify the command line arguments that should be passed to your program when it is run. Arguments must be given in quotes and separated by commas. Leave this filed empty if you do not want to specify command line arguments.

Example: "1","int","arg=2" is interpreted as three arguments 1, int, and arg=2.

Author(s)	Erik-Jan Lingen, Matthias Möller
Deadline	Geen deadline
Submission limit	No limitation

Information

Sign in