Department of Information Technology

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

Publications and Presentations

Updated  2005-12-15 16:51:05 by Zoran Radovic.