You are here: Home projects ed-tree

Elimination-Diffraction Trees

Producer-consumer pools, that is, collections of unordered objects or tasks, are a fundamental element of modern multiprocessor software and a target of extensive research and development. For example, there are three common ways to implement such pools in the Java JDK6.0: the SynchronousQueue, the LinkedBlockingQueue, and the ConcurrentLinkedQueue. Unfortunately, most pool implementations, including the ones in the JDK, are based on centralized structures like a queue or a stack, and thus are limited in their scalability.  The ED-Tree is a distributed pool structure based on a combination of the elimination-tree and diffracting-tree paradigms, allowing high degrees of parallelism with reduced contention. We use the ED-Tree to provide new pool implementations that compete with those of the JDK.


Scalable Producer-Consumer Pools Based on Elimination-Diffraction Trees.  Yehuda Afek, Guy Korland, Maria Natanzon, Nir Shavit.  EuroPar 2010.

Source code

Available here.