RH and HBO Locks Home Page
Efficient All-Software Synchronization for NUCAs: RH and HBO Locks
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).
Publications and Presentations
- Software Techniques for Distributed Shared Memory by Zoran Radovic. Doctoral Thesis, Department of Information Technology, Uppsala University, November 2005.
- Efficient Synchronization and Coherence for Nonuniform Communication Architectures by Zoran Radovic. Licentiate Thesis 2003-008, Department of Information Technology, Uppsala University, September 2003.
- 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.)
- 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.)
- 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.