Department of Information Technology
Department of Information Technology
Uppsala UniversityInformation TechnologySearch for staffHome
Listen

Scalable Producer Consumer Pools based on Elimination-Diffracting Trees (EuroPar'10)

Description

Abstract.
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.

This paper presents the ED-Tree, 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. In experiments on a 128 way Sun Maramba multicore machine, we show that ED-Tree based pools scale well, outperforming the corresponding algorithms in the JDK6.0 by a factor of 10 or more at high concurrency levels, while providing similar performance at low levels.

Link to the paper

You can find related materials in Papers subpage.

Questions

Question 1:
Consider the balancer binary-tree in Figure 1. Current state of the toggle bits in this tree is '110'b reading the tree nodes from left to right and top to bottom. If the initial state of these bits has been '000'b, list the other states in between when tokens 1-5 entered into the tree and placed in queues.


Bits state Token No.
000 --
1
2
3
4
110 5


Question 2:

The ED-Tree in Figure 2, can be used for
a) FIFO access to tokens entered into the tree
b) LIFO access to tokens entered into the tree
c) object pool with no order in access to tokens entered into the tree


Kjell

Q1:

Bits state Token No.
000 --
110 1
011 2
101 3
000 4
110 5

Q2:

C
Magnus

Q1:

Bits state Token No.
000 --
110 1
011 2
101 3
000 4
110 5

Q2:
C. Without elimination of pushes and pops, the queue will behave in a FIFO-manner.
Stavros

Q1:

Bits state Token No.
000 --
110 1
011 2
101 3
000 4
110 5

Q2:
C. By keeping separate producer and consumer toggle bits we would normally have consumer i popping from the same queue that the producer i pushed. This would maintain FIFO behaviour on the overall queue. However, requests are allowed to eliminate each other earlier, therefore FIFO is not guaranteed.
Martin

Q1:

Bits state Token No.
000 --
110 1
011 2
101 3
000 4
110 5

Q2: C, due to elimination. And since the eliminations dominate (Fig. 7), the order will not be "almost FIFO" as one may expect. Instead, newly inserted elements are more likely returned. This is interesting, as the purpose of adding a separate pop bit appears to be to get FIFO-like behavior rather than to reduce contention. Maybe it's not needed?
Fred

Q1:

Bits state Token No.
000 --
110 1
011 2
101 3
000 4
110 5

Q2: c
Andreas

Q1:

Bits state Token No.
000 --
110 1
011 2
101 3
000 4
110 5

Q2:
C (FIFO without elimination)
Jonatan

Q1:

Bits state Token No.
000 --
110 1
011 2
101 3
000 4
110 5

Q2:
C
Pavol

Q1:

Bits state Token No.
000 --
110 1
011 2
101 3
000 4
110 5

Q2:
C (no elimination)
Pan

Q1:

Bits state Token No.
000 initial
110 1
011 2
101 3
000 4
110 5

Q2:

C
Sofia

Q1:

Bits state Token No.
000 --
110 1
011 2
101 3
000 4
110 5

Q2:
C, but will behave like FIFO w/out elimination
Yunyun

Q1:

Bits state Token No.
000 --
110 1
011 2
101 3
000 4
110 5

Q2:
C

Updated  2013-05-15 12:31:57 by Yunyun Zhu.