Preliminary results on nb-feb, a synchronization primitive for parallel programming

ABSTRACT

We introduce a non-blocking full/empty bit primitive, or NB-FEB for short, as a promising synchronization primitive for parallel programming on may-core architectures. We show that the NB-FEB primitive is universal, scalable and feasible. NB-FEB, together with registers, can solve the consensus problem for an arbitrary number of processes (universality). NB-FEB is combinable, namely its memory requests to the same memory location can be combined into only one memory request, which consequently mitigates performance degradation due to synchronization "hot spots" (scalability). Since NB-FEB is a variant of the original full/empty bit that always returns a value instead of waiting for a conditional flag, it is as feasible as the original full/empty bit, which has been implemented in many computer systems (feasibility).

REFERENCES

• 1: Krste Asanovic et al. The landscape of parallel computing research: A view from berkeley. Technical Report No. UCB/EECS-2006-183, University of California, Berkeley, 2006.
• 2: Guy E. Blelloch , Phillip B. Gibbons , S. Harsha Vardhan, Combinable memory-block transactions, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany [doi>10.1145/1378533.1378537]
• 3: David E. Culler , Anoop Gupta , Jaswinder Pal Singh, Parallel Computer Architecture: A Hardware/Software Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
• 4: Maurice Herlihy, Wait-free synchronization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.1, p.124-149, Jan. 1991 [doi>10.1145/114005.102808]
• 5: Clyde P. Kruskal , Larry Rudolph , Marc Snir, Efficient synchronization of multiprocessors with shared memory, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.4, p.579-601, Oct. 1988 [doi>10.1145/48022.48024]
• 6: M. M. Michael and M. L. Scott. Implementation of atomic primitives on distributed shared memory multiprocessors. In Proc. of the IEEE Symp. on High-Performance Computer Architecture, pages 222--231, 1995.
• 7: Srinivas Sridharan , Arun Rodrigues , Peter Kogge, Evaluating synchronization techniques for light-weight multithreaded/multicore architectures, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA [doi>10.1145/1248377.1248388]

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Shared memory

  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Hardware/software interfaces

General Terms:
Algorithms, Reliability, Theory

Keywords:
combinability, full/empty bit, many-core architectures, non-blocking synchronization, universal primitives