Brief announcement: distributed phase synchronization of dynamic set of processes

ABSTRACT

General barrier synchronization is widely used in multiprocessor programming with the introduction of multicore processors. In this paper, we describe a solution for the barrier synchronization of processes (that are not bounded or known a priori) that can dynamically join or drop out of barrier synchronization. A new process can join only in the beginning of each phase along with all the other members; that is, at the beginning of a phase everyone is aware of the other members involved in synchronization. We design a protocol using the above policy that guarantees starvation freedom, i.e., any process wanting to join phase synchronization shall do so within at most two phases.

REFERENCES

• 1: K. Mani Chandy, Parallel program design: a foundation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• 2: John M. Mellor-Crummey , Michael L. Scott, Algorithms for scalable synchronization on shared-memory multiprocessors, ACM Transactions on Computer Systems (TOCS), v.9 n.1, p.21-65, Feb. 1991 [doi>10.1145/103727.103729]
• 3: J. Misra, Phase Synchronization, Notes on Unity, 12-90, UT at Austin, 1990.
• 4: Maurice Herlihy and Nir Shavit, The Art of Multiprocessor Programming, Morgan Kaufmann, 2008. 20(1), Feb. 1991.
• 5: P. Tang and P. C. Yew, Processor Self scheduling for multiple-nested parallel loops, Proc. ICPP, pp. 528-535, August, 1986.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Distributed programming

General Terms:
Algorithms

Keywords:
barriers, phase synchronization, starvation freedom