Fast and Scalable Rendezvousing
A common abstraction in concurrent programming is that of an asymmetric rendezvous mechanism. In this mechanism, there are two types of threads that show up, e.g., producers and consumers. The goal is to match pairs of threads, one of each type, and send them away. Usually the purpose of the pairing is for a producer to hand over a data item (such as a task to perform) to a consumer. The asymmetric rendezvous abstraction encompasses both unfair synchronous queues (or pools) which are a key building block in Java’s thread pool implementation and other message-passing and hand-off designs, and the elimination technique that is used to scale concurrent stacks and queues. We present a highly scalable asymmetric rendezvous algorithm that improves the state of the art in both unfair synchronous queue and elimination algorithms. It is based on a distributed scalable ring structure, unlike Java’s synchronous queue which relies on a non-scalable centralized structure. It is nonblocking, in the following sense: if both producers and consumers keep taking steps, some rendezvous operation is guaranteed to complete. (This is similar to the lock-freedom property, while taking into account the fact that "it takes two to tango", i.e., both types of threads must take steps to successfully rendezvous.)
Fast and Scalable Rendezvousing. Yehuda Afek, Michael Hakimi and Adam Morrison. DISC 2011. Awarded best student paper.
- Synchronous queue (Java) code is available here. This is based on benchmark code used in the Scalable Flat-Combining Based Synchronous Queues paper.
- Stack (C++) code is available here. This is based on the benchmark code used in the Flat combining and the synchronization-parallelism tradeoff paper.