Multicore Programming in the face of Metamorphosis: Union-Find as an Example
A crucial question facing today’s multicore programmers is which programming methodology to use for coordination and data structure design: fine grained locking, lock-free or wait-free synchronization, or perhaps transactional memory.X delivering a given level of scalability, how costly is it, in terms of both performance and ease of programming, to use methodology X to add new features to this existing algorithm.
One aspect of this question that has received little attention is the tradeoff between performance and flexibility. In other words, given a data structure implemented using methodology
This work studies the flexibility question in the context of the union-find problem, a problem that is a unique fit for our quest in that it has a known efficient wait-free concurrent solution for implementing the union and find methods, but only a complex sequential solution if one wishes to allow delete methods. Based on union find, we are able to make interesting observations about the relative benefits of using locks, non-blocking algorithms, and state-of-the-art software transactional memory systems.
Moreover, based on our new understandings, we present highly efficient and flexible algorithms for the union-find and union-find-delete problems that we believe are of independent interest.
The source code is available here.