RH and HBO Locks Home Page

Efficient All-Software Synchronization for NUCAs: RH and HBO Locks

Project Overview

Scalable architectures with nonuniform memory access time (CC-NUMAs) have gained increased popularity in recent years. The increased scalability has increased the demand for scalable lock implementations, such as the queue-based locks of Mellor-Crummey and Scott (MCS lock), and of Craig, Landin and Hagersten (CLH lock).

This project demonstrates that the first come, first served nature of queue-based locks makes them less suitable for non-uniform communication architectures (NUCAs), such as CC-NUMAs built from a few large nodes or from chip multiprocessors (CMPs). In contrast, the simpler test-and-set spin locks give an unfair advantage to neighboring processors when a lock is released, which will create a fast lock handover time as well as more locality for the data accessed in the critical region.

We propose RH lock and a set of simple software-based hierarchical backoff locks (HBO) that create node affinity in NUCAs.

This project is supported in part by Sun Microsystems, Inc., and the Parallel and Scientific Computing Institute (PSCI).

Project Members

• Erik Hagersten (Professor)
• Zoran Radovic (PhD Student)

Publications and Presentations

• Software Techniques for Distributed Shared Memory by Zoran Radovic. Doctoral Thesis, Department of Information Technology, Uppsala University, November 2005.
  • PowerPoint presentation

• Efficient Synchronization and Coherence for Nonuniform Communication Architectures by Zoran Radovic. Licentiate Thesis 2003-008, Department of Information Technology, Uppsala University, September 2003.
  • PowerPoint presentation

• Hierarchical Backoff Locks for Nonuniform Communication Architectures by Zoran Radovic and Erik Hagersten. In Proceedings of the Ninth International Symposium on High Performance Computer Architecture (HPCA-9), Anaheim, California, USA, February 2003. (The original HBO locks paper.)
  • PowerPoint presentation

• Efficient Synchronization for Nonuniform Communication Architectures by Zoran Radovic and Erik Hagersten. In Proceedings of Supercomputing 2002 (SC2002), Baltimore, Maryland, USA, November 2002. (The original RH lock paper.)
  • PowerPoint presentation

• RH Lock: A Scalable Hierarchical Spin Lock by Zoran Radovic and Erik Hagersten. In Proceedings of the 2nd Annual Workshop on Memory Performance Issues (WMPI 2002), held in conjunction with the 29th International Symposium on Computer Architecture (ISCA29), Anchorage, Alaska, USA, May 2002.
  • PowerPoint presentation