David A. Bader
IEEE Fellow
AAAS Fellow
College of Computing
Georgia Tech
Atlanta, GA 30332



Designing Irregular Parallel Algorithms With Mutual Exclusion and Lock-free Protocols

Lock-free shared data structures in the setting of distributed computing have received a fair amount of attention. Major motivations of lock-free data structures include increasing fault tolerance of a (possibly heterogeneous) system and getting rid of the problems associated with critical sections such as priority inversion and deadlock. For parallel computers with closely-coupled processors and shared memory, these issues are no longer major concerns. While many of the results are applicable especially when the model used is shared memory multiprocessors, no prior studies have considered improving the performance of a parallel implementation by way of lock-free programming. As a matter of fact, often times in practice lock free data structures in a distributed setting do not perform as well as those that use locks. As the data structures and algorithms for parallel computing are often drastically different from those in distributed computing, it is possible that lock-free programs perform better. In this paper we compare the similarity and difference of lock-free programming in both distributed and parallel computing environments and explore the possibility of adapting lock-free programming to parallel computing to improve performances. Lock-free programming also provides a new way of simulating PRAM and asynchronous PRAM algorithms on current parallel machines.

Publication History

Versions of this paper appeared as:
  1. G. Cong and D.A. Bader, ``Lock-free Parallel Algorithms: An Experimental Study,'' The 11th International Conference on High Performance Computing (HiPC 2004), L. Bougé and V.K. Prasanna, (eds.), Springer-Verlag LNCS 3296, 516-527, Bangalore, India, December 2004.
  2. G. Cong and D. A. Bader, ``Designing Irregular Parallel Algorithms With Mutual Exclusion and Lock-free Protocols,'' Journal of Parallel and Distributed Computing, 66(6):854-866, 2006.

Download this report in Adobe PDF


Last updated: May 10, 2006


Computational Biology

Parallel Computing