Barriers

• An important and often used construct in threaded (as well as other parallel) programs is a barrier. A barrier call is used to hold a thread until all other threads participating in the barrier have reached the barrier.
• Barriers can be implemented using a counter, a mutex and a condition variable. (They can also be implemented simply using mutexes; however, such implementations suffer from the overhead of busy-wait.)
• A single integer is used to keep track of the number of threads that have reached the barrier. If the count is less than the total number of threads, the threads execute a condition wait. The last thread entering (and setting the count to the number of threads) wakes up all the threads using a condition broadcast. The code for accomplishing this is as follows:

  1   typedef struct { 
  2       pthread_mutex_t count_lock; 
  3       pthread_cond_t ok_to_proceed; 
  4       int count; 
  5   } mylib_barrier_t; 
  6 
  7   void mylib_init_barrier(mylib_barrier_t *b) { 
  8       b -> count = 0; 
  9       pthread_mutex_init(&(b -> count_lock), NULL); 
  10      pthread_cond_init(&(b -> ok_to_proceed), NULL); 
  11  } 
  12 
  13  void mylib_barrier (mylib_barrier_t *b, int num_threads) { 
  14      pthread_mutex_lock(&(b -> count_lock)); 
  15      b -> count ++; 
  16      if (b -> count == num_threads) { 
  17          b -> count = 0; 
  18          pthread_cond_broadcast(&(b -> ok_to_proceed)); 
  19      } 
  20      else 
  21          while (pthread_cond_wait(&(b -> ok_to_proceed), 
  22              &(b -> count_lock)) != 0); 
  23      pthread_mutex_unlock(&(b -> count_lock)); 
  24  }
  

  In the above implementation of a barrier, threads enter the barrier and stay until the broadcast signal releases them. The threads are released one by one since the mutex count_lock is passed among them one after the other. The trivial lower bound on execution time of this function is therefore $O(n)$ for $n$ threads. This implementation of a barrier can be speeded up using multiple barrier variables.
• Let us consider an alternate barrier implementation in which there are $n/2$ condition variable-mutex pairs for implementing a barrier for $n$ threads.
  • The barrier works as follows: at the first level, threads are paired up and each pair of threads shares a single condition variable-mutex pair.
  • A designated member of the pair waits for both threads to arrive at the pairwise barrier. Once this happens, all the designated members are organized into pairs, and this process continues until there is only one thread.
  • At this point, we know that all threads have reached the barrier point. We must release all threads at this point. However, releasing them requires signaling all $n/2$ condition variables. We use the same hierarchical strategy for doing this. The designated thread in a pair signals the respective condition variables.

  1   typedef struct barrier_node { 
  2       pthread_mutex_t count_lock; 
  3       pthread_cond_t ok_to_proceed_up; 
  4       pthread_cond_t ok_to_proceed_down; 
  5       int count; 
  6   } mylib_barrier_t_internal; 
  7 
  8   typedef struct barrier_node mylog_logbarrier_t[MAX_THREADS]; 
  9   pthread_t p_threads[MAX_THREADS]; 
  10  pthread_attr_t attr; 
  11 
  12  void mylib_init_barrier(mylog_logbarrier_t b) { 
  13      int i; 
  14      for (i = 0; i < MAX_THREADS; i++) { 
  15          b[i].count = 0; 
  16          pthread_mutex_init(&(b[i].count_lock), NULL); 
  17          pthread_cond_init(&(b[i].ok_to_proceed_up), NULL); 
  18          pthread_cond_init(&(b[i].ok_to_proceed_down), NULL); 
  19      } 
  20  } 
  21 
  22  void mylib_logbarrier (mylog_logbarrier_t b, int num_threads, 
  23             int thread_id) { 
  24      int i, base, index; 
  25      i=2; 
  26      base = 0; 
  27 
  28      do { 
  29          index = base + thread_id / i; 
  30          if (thread_id % i == 0) { 
  31              pthread_mutex_lock(&(b[index].count_lock)); 
  32              b[index].count ++; 
  33              while (b[index].count < 2) 
  34                  pthread_cond_wait(&(b[index].ok_to_proceed_up), 
  35                      &(b[index].count_lock)); 
  36                  pthread_mutex_unlock(&(b[index].count_lock)); 
  37              } 
  38              else { 
  39                  pthread_mutex_lock(&(b[index].count_lock)); 
  40                  b[index].count ++; 
  41                  if (b[index].count == 2) 
  42                      pthread_cond_signal(&(b[index].ok_to_proceed_up)); 
  43                  while (pthread_cond_wait(&(b[index].ok_to_proceed_down), 
  44                      &(b[index].count_lock)) != 0); 
  45                  pthread_mutex_unlock(&(b[index].count_lock)); 
  46                  break; 
  47              } 
  48              base = base + num_threads/i; 
  49              i=i*2; 
  50      } while (i <= num_threads); 
  51      i=i/2; 
  52      for (; i > 1; i = i / 2) { 
  53          base = base - num_threads/i; 
  54          index = base + thread_id / i; 
  55          pthread_mutex_lock(&(b[index].count_lock)); 
  56          b[index].count = 0; 
  57          pthread_cond_signal(&(b[index].ok_to_proceed_down)); 
  58          pthread_mutex_unlock(&(b[index].count_lock)); 
  59      } 
  60  }
  

• In this implementation of a barrier, we visualize the barrier as a binary tree. Threads arrive at the leaf nodes of this tree.
• Consider an instance of a barrier with eight threads. Threads 0 and 1 are paired up on a single leaf node. One of these threads is designated as the representative of the pair at the next level in the tree.
• In the above example, thread 0 is considered the representative and it waits on the condition variable $ok\_to\_proceed\_up$ for thread 1 to catch up. All even numbered threads proceed to the next level in the tree. Now thread 0 is paired up with thread 2 and thread 4 with thread 6. Finally thread 0 and 4 are paired. At this point, thread 0 realizes that all threads have reached the desired barrier point and releases threads by signaling the condition $ok\_to\_proceed\_down$. When all threads are released, the barrier is complete.