RACES 2012
image/svg+xml
RACES 2012
2012-10-21
Andreas Haas
##
/
##
MASTER SLIDE
RACES Workshop, October 2012
How FIFO is Your Concurrent FIFO Queue?
Andreas Haas, Christoph M. Kirsch, Michael Lippautz, Hannes Payer
University of Salzburg
0
500
1000
1500
2000
2500
3000
3500
4000
4500
5000
2
10
20
30
40
50
60
70
80
operations/ms (more is better)
number of threads
2RA Scal (p=80)
LB
MS
FC
US k-FIFO (k=80)
RR Scal (p=80)
linearizable with respect to strict FIFO queue semantics
strict FIFO queue implementations
linearizable with respect to relaxed FIFO queue semantics
relaxed FIFO queue implementations
bounded out-of-order treatment of queue elementspossible
We say relaxed FIFO queue implementations can be even more FIFO than strict FIFO queue implementations.
Some people say relaxed FIFO queues are not enough FIFO.
No applications for relaxed FIFO queues.
linearization point
time
a
enq
b
enq
a
deq
b
deq
time
a
enq
b
enq
a
deq
b
deq
linearizable
not linearizable
out-of-order executionof overlapping operations
out-of-order treatmentof queue elements
Record concurrent histories of various FIFOqueue implementations.
Analyze these concurrent histories using only the invocation times of operations.
2.)
1.)
Ideally operations would take zero time
Independent of the execution time of operations
time
a
enq
b
enq
a
deq
b
deq
element
overtakes element
a
b
b
enq
a
deq
b
deq
element-fairness = number of overtakings in the zero-time linearization
Definition
zero-time linearization
for 10.000 iterations
calculate Pi
dequeue element
{
}
enqueue unique element
calculate Pi
all threads do in parallel
No dequeues in the first 200 iterations to avoid empty checks.
No enqueues in the last 200 iterations to empty the queue.
0.1
1
10
100
1000
0
1000
2000
4000
8000
16000
32000
64000
element-fairness per element
(logscale, less is better)
computational load (logscale)
80 threads
LB
MS
FC
US k-FIFO (k=80)
RR Scal (p=80)
2RA Scal (p=80)
time
a
enq
b
enq
a
deq
b
deq
operation enq
a
b
overtakes operation enq
operation-fairness = number of overtakings in a concurrent history
Definition
Observation: Linearization points induce a strict order onthe queue operations
Measure the out-of order execution of single operations
age (op) = number of operations op overtakes
lateness (op) = number of operations which overtake op
Definition
Definition
a
enq
b
enq
age(enq
a
) = 0
age(enq
b
) = 1
lateness(enq
a
) = 1
lateness(enq
b
) = 0
for 10.000 iterations
enqueue unique element
{
}
calculate Pi
all threads do in parallel
Only for strict FIFO queue implementations at the moment.
Measuring relaxed implementations is future work.
dequeue all elements sequentially
one thread does
1
10
100
0
1000
2000
4000
8000
16000
32000
64000
maximum operation-age
(logscale, less is better)
computational load (logscale)
80 threads
LB
MS
FC
10
100
1000
10000
100000
0
1000
2000
4000
8000
16000
32000
64000
maximum operation-lateness
(logscale, less is better)
computational load (logscale)
80 threads
LB
MS
FC
0
20
40
60
80
100
0
1000
2000
4000
8000
16000
32000
64000
% of enqueue operations with operation-age > 0
(less is better)
computational load (logscale)
80 threads
LB
MS
FC
0
20
40
60
80
100
0
1000
2000
4000
8000
16000
32000
64000
% of enqueue operations with operation-lateness > 0
(less is better)
computational load (logscale)
80 threads
LB
MS
FC
Future work
Measure operation-fairness of relaxed FIFO queue implementations.
Use element-fairness to analyze implementations of otherdata structures, e.g. stacks.
We introduced metrics to compare the behavior of variousFIFO queue implementations.
Relaxed implementation can appear more FIFO thanstrict implementations.
Thank You
For more information about the queue implementations see http://scal.cs.uni-salzburg.at/