Browse Prior Art Database

Barrier Synchronization Using Fetch and Add and Broadcast

IP.com Disclosure Number: IPCOM000106898D
Original Publication Date: 1992-Jan-01
Included in the Prior Art Database: 2005-Mar-21
Document File: 2 page(s) / 76K

Publishing Venue

IBM

Related People

Finney, DW: AUTHOR

Abstract

Described is a barrier synchronization method using a fetch-and-add instruction which is followed by a compare instruction and a broadcast message.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Barrier Synchronization Using Fetch and Add and Broadcast

       Described is a barrier synchronization method using a
fetch-and-add instruction which is followed by a compare instruction
and a broadcast message.

      In massively parallel computers, the execution of tasks or
processes may be distributed over many processors where each
processor completes its task separate in time from other processors,
but must wait for all other processors, working on the same problem,
to complete execution.  This wait period is enforced by a barrier.

      If all processors must test a semaphore or similar
synchronization barrier to determine if they can proceed, there will
be a large number of memory accesses that are wasted, while some set
of processors is in a busy wait state retesting the semaphore until
the last processor finishes executing the task.

      If messages are used to indicate the processor has finished its
task, a great deal of extra processing is required when there are a
large number of processors participating in the task execution.  Each
message has to be interpreted by a designated control processor, and
when all processors have finished, the control processor will notify
them to proceed.

      Other architectures have proposed specialized hardware to
determine when all processors have reached the barrier and may
proceed.

      The method of using fetch-and-add followed by a broadcast
greatly simplifies the barrier synchronization task, while making the
system operation much more efficient.

      The method works as follows:
      1.   At run time, the operating system initializes a variable
with the number of processors that will be working together and will
require synchronization at a specific point in the program.
      2.   A specific synchronization (sync) variable will be
assigned for each synchronization and will be initialized t...