Barrier (computer science)

From Wikipedia, the free encyclopedia

In parallel computing, a barrier is a type of synchronization method. A barrier for a group of threads or processes in the source code means any thread/process must stop at this point and cannot proceed until all other threads/processes reach this barrier.[1]

Many collective routines and directive-based parallel languages impose implicit barriers. For example, a parallel do loop in Fortran with OpenMP will not be allowed to continue on any thread until the last iteration is completed. This is in case the program relies on the result of the loop immediately after its completion. In message passing, any global communication (such as reduction or scatter) may imply a barrier.

In concurrent computing, a barrier may be in a raised or lowered state. The term latch is sometimes used to refer to a barrier that starts in the raised state and cannot be re-raised once it is in the lowered state. The term count-down latch is sometimes used to refer to a latch that is automatically lowered once a pre-determined number of threads/processes have arrived.

Implementation[edit]

The basic barrier has mainly two variables, one of which records the pass/stop state of the barrier, the other of which keeps the total number of threads that have entered in the barrier. The barrier state was initialized to be "stop" by the first threads coming into the barrier. Whenever a thread enters, based on the number of threads already in the barrier, only if it is the last one, the thread sets the barrier state to be "pass" so that all the threads can get out of the barrier. On the other hand, when the incoming thread is not the last one, it is trapped in the barrier and keeps testing if the barrier state has changed from "stop" to "pass", and it gets out only when the barrier state changes to "pass". The following C++ code demonstrates this procedure.[2][3]

struct barrier_type
{
    // how many processors have entered the barrier
    // initialize to 0
    int arrive_counter;
    // how many processors have exited the barrier
    // initialize to p
    int leave_counter;
    int flag;
    std::mutex lock;
};

// barrier for p processors
void barrier(barrier_type* b, int p)
{
    b->lock.lock();
    if (b->arrive_counter == 0)
    {
        if (b->leave_counter == p) { // no other threads in barrier
            b->flag = 0;             // first arriver clears flag
        } else {
            b->lock.unlock();
            while (b->leave_counter != p); // wait for all to leave before clearing
            b->lock.lock();
            b->flag = 0;
        }
    }
    int arrived = ++(b->arrive_counter);
    unlock(b->lock);
    if (b->arrive_counter == p) { //last arriver sets flag
        b->arrive_counter = 0;
        b->leave_counter = 1;
        b->flag = 1;
    } else {
        while (b->flag == 0); // wait for flag
        lock(b->lock);
        b->leave_counter++;
        unlock(b->lock);
    }
}

The potential problem is:

  1. Due to all the threads repeatedly accessing the global variable for pass/stop, the communication traffic is rather high, which decreases the scalability.

This problem can be resolved by regrouping the threads and using multi-level barrier, e.g. Combining Tree Barrier. Also hardware implementations may have the advantage of higher scalability.

Sense-Reversal Centralized Barrier[edit]

Instead of using the same value to represent pass/stop, sequential barriers use opposite values for pass/stop state. For example, if barrier 1 uses 0 to stop the threads, barrier 2 will use 1 to stop threads and barrier 3 will use 0 to stop threads again and so on.[4] The following C++ code demonstrates this.[2][5][3]

struct barrier_type
{
    int counter; // initialize to 0
    int flag; // initialize to 0
    std::mutex lock;
};

int local_sense = 0; // private per processor

// barrier for p processors
void barrier(barrier_type* b, int p)
{
    local_sense = 1 - local_sense;
    b->lock.lock();
    b->counter++;
    int arrived = b->counter;
    if (arrived == p) // last arriver sets flag
    {
        b->lock.unlock();
        b->counter = 0;
        // memory fence to ensure that the change to counter
        // is seen before the change to flag
        b->flag = local_sense;
    }
    else
    {
        b->lock.unlock();
        while (b->flag != local_sense); // wait for flag
    }
}

Combining Tree Barrier[edit]

A Combining Tree Barrier is a hierarchical way of implementing barrier to resolve the scalability by avoiding the case that all threads are spinning at the same location.[4]

In k-Tree Barrier, all threads are equally divided into subgroups of k threads and a first-round synchronizations are done within these subgroups. Once all subgroups have done their synchronizations, the first thread in each subgroup enters the second level for further synchronization. In the second level, like in the first level, the threads form new subgroups of k threads and synchronize within groups, sending out one thread in each subgroup to next level and so on. Eventually, in the final level there is only one subgroup to be synchronized. After the final-level synchronization, the releasing signal is transmitted to upper levels and all threads get past the barrier.[5][6]

Hardware Barrier Implementation[edit]

The hardware barrier uses hardware to implement the above basic barrier model.[2]

The simplest hardware implementation uses dedicated wires to transmit signal to implement barrier. This dedicated wire performs OR/AND operation to act as the pass/block flags and thread counter. For small systems, such a model works and communication speed is not a major concern. In large multiprocessor systems this hardware design can make barrier implementation have high latency. The network connection among processors is one implementation to lower the latency, which is analogous to Combining Tree Barrier.[7]

Thread barrier[edit]

POSIX Threads standard supports thread barrier which can be used to block the specified threads or the whole process at the barrier until other threads to reach that barrier.[1] 3 main API supports by POSIX to implement thread barriers are:

pthread_barrier_init()
Init the thread barrier with the number of threads needed to wait at the barrier in order to lift it[8]
pthread_barrier_destroy()
Destroy the thread barrier to release back the resource[8]
pthread_barrier_wait()
Calling this function will block the current thread until the number of threads specified by ; pthread_barrier_init() call pthread_barrier_wait() to lift the barrier.[9]

The following example (implemented in C with pthread API) will use thread barrier to block all the threads of the main process and therefore block the whole process:

#include <stdio.h>
#include <pthread.h>

#define TOTAL_THREADS           2
#define THREAD_BARRIERS_NUMBER  3
#define PTHREAD_BARRIER_ATTR    NULL // pthread barrier attribute

pthread_barrier_t barrier;

void *thread_func(void *ptr){
    printf("Waiting at the barrier as not enough %d threads are running ...\n", THREAD_BARRIERS_NUMBER);
    pthread_barrier_wait(&barrier);
    printf("The barrier is lifted, thread id %ld is running now\n", pthread_self());
}

int main()
{  
	pthread_t thread_id[TOTAL_THREADS];

    pthread_barrier_init(&barrier, PTHREAD_BARRIER_ATTR, THREAD_BARRIERS_NUMBER);
    for (int i = 0; i < TOTAL_THREADS; i++){
        pthread_create(&thread_id[i], NULL, thread_func, NULL);
    }

    // As pthread_join() will block the process until all the threads it specifies are finished, 
    // and there is not enough thread to wait at the barrier, so this process is blocked
    for (int i = 0; i < TOTAL_THREADS; i++){
        pthread_join(thread_id[i], NULL);
    }
    pthread_barrier_destroy(&barrier);
    printf("Thread barrier is lifted\n"); // This line won't be called as TOTAL_THREADS < THREAD_BARRIERS_NUMBER
}

The result of that source code is:

Waiting at the barrier as not enough 3 threads are running ...
Waiting at the barrier as not enough 3 threads are running ...
// (main process is blocked as not having enough 3 threads)
// Line printf("Thread barrier is lifted\n") won't be reached

As we can see from the source code, there are just only two threads are created. Those 2 thread both have thread_func(), as the thread function handler, which call pthread_barrier_wait(&barrier), while thread barrier expected 3 threads to call pthread_barrier_wait (THREAD_BARRIERS_NUMBER = 3) in order to be lifted. Change TOTAL_THREADS to 3 and the thread barrier is lifted:

Waiting at the barrier as not enough 3 threads are running ...
Waiting at the barrier as not enough 3 threads are running ...
Waiting at the barrier as not enough 3 threads are running ...
The barrier is lifted, thread id 140643372406528 is running now
The barrier is lifted, thread id 140643380799232 is running now
The barrier is lifted, thread id 140643389191936 is running now
Thread barrier is lifted

As main() is treated as a thread, i.e the "main" thread of the process,[10] calling pthread_barrier_wait() inside main() will block the whole process until other threads reach the barrier. The following example will use thread barrier, with pthread_barrier_wait() inside main(), to block the process/main thread for 5 seconds as waiting the 2 "newly created" thread to reach the thread barrier:

#define TOTAL_THREADS           2
#define THREAD_BARRIERS_NUMBER  3
#define PTHREAD_BARRIER_ATTR    NULL // pthread barrier attribute

pthread_barrier_t barrier;

void *thread_func(void *ptr){
    printf("Waiting at the barrier as not enough %d threads are running ...\n", THREAD_BARRIERS_NUMBER);
	sleep(5);
    pthread_barrier_wait(&barrier);
    printf("The barrier is lifted, thread id %ld is running now\n", pthread_self());
}

int main()
{  
	pthread_t thread_id[TOTAL_THREADS];

    pthread_barrier_init(&barrier, PTHREAD_BARRIER_ATTR, THREAD_BARRIERS_NUMBER);
    for (int i = 0; i < TOTAL_THREADS; i++){
        pthread_create(&thread_id[i], NULL, thread_func, NULL);
    }

	pthread_barrier_wait(&barrier);

    printf("Thread barrier is lifted\n"); // This line won't be called as TOTAL_THREADS < THREAD_BARRIERS_NUMBER
	pthread_barrier_destroy(&barrier);
}

This example doesn't use pthread_join() to wait for 2 "newly created" threads to complete. It calls pthread_barrier_wait() inside main(), in order to block the main thread, so that the process will be blocked until 2 threads finish its operation after 5 seconds wait (line 9 - sleep(5)).

See also[edit]

References[edit]

  1. ^ a b GNU Operating System. "Implementation of pthread_barrier". gnu.org. Retrieved 2024-03-02.
  2. ^ a b c Solihin, Yan (2015-01-01). Fundamentals of Parallel Multicore Architecture (1st ed.). Chapman & Hall/CRC. ISBN 978-1482211184.
  3. ^ a b "Implementing Barriers". Carnegie Mellon University.
  4. ^ a b Culler, David (1998). Parallel Computer Architecture, A Hardware/Software Approach. Gulf Professional. ISBN 978-1558603431.
  5. ^ a b Nanjegowda, Ramachandra; Hernandez, Oscar; Chapman, Barbara; Jin, Haoqiang H. (2009-06-03). Müller, Matthias S.; Supinski, Bronis R. de; Chapman, Barbara M. (eds.). Evolving OpenMP in an Age of Extreme Parallelism. Lecture Notes in Computer Science. Springer Berlin Heidelberg. pp. 42–52. doi:10.1007/978-3-642-02303-3_4. ISBN 9783642022845.
  6. ^ Nikolopoulos, Dimitrios S.; Papatheodorou, Theodore S. (1999-01-01). "A quantitative architectural evaluation of synchronization algorithms and disciplines on ccNUMA systems". Proceedings of the 13th international conference on Supercomputing. ICS '99. New York, NY, USA: ACM. pp. 319–328. doi:10.1145/305138.305209. ISBN 978-1581131642. S2CID 6097544. Archived from the original on 2017-07-25. Retrieved 2019-01-18.
  7. ^ N.R. Adiga, et al. An Overview of the BlueGene/L Supercomputer. Proceedings of the Conference on High Performance Networking and Computing, 2002.
  8. ^ a b "pthread_barrier_init(), pthread_barrier_destroy()". Linux man page. Retrieved 2024-03-16.
  9. ^ "pthread_barrier_wait()". Linux man page. Retrieved 2024-03-16.
  10. ^ "How to get number of processes and threads in a C program?". stackoverflow. Retrieved 2024-03-16.

External links[edit]

"Parallel Programming with Barrier Synchronization". sourceallies.com. March 2012.