Analysis of Transactional Memory Techniques in Multi-Core Architectures
undefined
Idit Keidar and Dmitri Perelman
Technion
1
S
P
A
A
2
0
0
9
The emergence of multi-core architectures…
Conventional locking…
Transactional Memory is a new synchronization
abstraction…
You may continue by yourself
2
S
P
A
A
2
0
0
9
Aborting transactions is bad:
the work is lost
the resources are wasted
overall throughput decreases
May be even worse:
aborted transactions restart and conflict again
livelock
3
S
P
A
A
2
0
0
9
Some times aborts are necessary
continuing the run would violate correctness
And some times they are not –
spare aborts
the suspicion is unjustified
most of the times based on conflict detection
Our question:
to what degree can we avoid spare aborts?
4
S
P
A
A
2
0
0
9
Previous measures for evaluating spare aborts and
their limitations
Our measures for evaluating spare aborts
Example TM avoiding spare aborts
5
S
P
A
A
2
0
0
9
Opacity
is widely accepted [Guerraoui and Kapalka
08]
Informally: strict serializability, taking into account
all the transactions (including the live and aborted
ones)
6
S
P
A
A
2
0
0
9
Previous measures for evaluating spare aborts and
their limitations
Our measures for evaluating spare aborts
Example TM avoiding spare aborts
7
S
P
A
A
2
0
0
9
Commit-Abort Ratio [Gramoli, Harmanci and Felber]:
|committed| / (|committed aborted|)
Influenced by the decisions of contention manager
We show: every TM is
(L) competitive in terms of its C-
A ratio (L – maximal possible number of live txns)
All TMs are bad in terms of C-A ratio, hard to compare
T
1
o
1
o
2
o
3
T
2
C
A
A
A
A
T
1
o
1
o
2
o
3
T
2
C
A
A
A
A
W
h
i
c
h
t
x
n
t
o
a
b
o
r
t
?
8
S
P
A
A
2
0
0
9
TM is
p-permissive
w.r.t. safety property
p
if it
accepts every history that satisfies
p
[Guerraoui et al
08]
Our focus: opacity-permissiveness
If the given history does not violate opacity, then the TM
should run it without aborts
9
S
P
A
A
2
0
0
9
We show:
there exists no TM providing 0pacity-
permissiveness
Intuition: there is a degree of freedom given to the
read operations
cannot predict what value should be read in order to avoid
spare aborts in future
10
10
S
P
A
A
2
0
0
9
Previous measures for evaluating spare aborts and
their limitations
Our measures for evaluating spare aborts
Example TM avoiding spare aborts
11
11
S
P
A
A
2
0
0
9
Strict Online
Opacity-Permissiveness
: a TM forcefully
aborts a txn only when not aborting any txn violates
opacity.
does not define
which
txns should be aborted
allows returning a value that causes abort in the future
NP-Complete in the number of committed txns
reduction from the view-serializability detection problem
[Papadimitriou 79]
12
12
S
P
A
A
2
0
0
9
The “problem”: the order of committed txns is
undefined
T
1
o
1
o
2
o
3
T
2
C
C
T
4
C
C
Txns serialization:
T
4
T
1
T
2
T
3
T
3
13
13
S
P
A
A
2
0
0
9
Online
opacity-permissiveness
(intuition):
order the committed txns writing to the same objects
this order should be preserved during the run
14
14
S
P
A
A
2
0
0
9
Visible reads have their cost:
cache invalidations in a multi-core environments
Postpone exposing the read if possible
We show:
if a TM satisfies online opacity-
permissiveness the reads must be exposed as they
happen
o
1
o
2
T
1
o
1
o
2
T
1
T
2
A
T
3
T
3
T
4
T
4
15
15
S
P
A
A
2
0
0
9
Previous measures for evaluating spare aborts and
their limitations
Our measures for evaluating spare aborts
Example TM avoiding spare aborts
16
16
S
P
A
A
2
0
0
9
AbortsAvoider algorithm as a possibility proof
Polynomial time operation complexity
Maintains version lists and the precedence graph
17
17
S
P
A
A
2
0
0
9
Directed labeled graph over transactions
different variations in prior works [Napper and Alvisi 05,
Guerraoui and Kapalka 08]
We show:
if a TM maintains PG acyclic and aborts txn only
upon cycle creation, then this TM satisfies online opacity-
permissiveness
o.v
n
o.v
n-1
writer
writer
readers
readers
WaW
RaW
RaW
WaR
18
18
S
P
A
A
2
0
0
9
Reads are simple:
look for the latest version that does not create a cycle in
the PG
Writes are simpler than Reads:
postpone the work till commit (invisible writes)
19
19
S
P
A
A
2
0
0
9
Install the new versions of all written objects
non-blind writes: after the version that has been read
blind writes: plenty of options
The greedy approach does not work
The places to install are sought in iterations
20
20
S
P
A
A
2
0
0
9
Transactions cannot be garbage collected right after
the termination
should be kept in PG as long as it has a potential to
participate in a cycle
We define GC conditions
from some point onward no new incoming edges will be
added to the node
Optimizations to save run-time complexity
21
21
S
P
A
A
2
0
0
9
Avoiding spare aborts is not always possible
Avoiding spare aborts may be costly:
no invisible reads for opacity
complicated conditions for GC
Proof-of-concept algorithm avoiding spare aborts
with polynomial time complexity
“Spare aborts vs. Operations complexity” tradeoff is
yet to be studied
22
22
S
P
A
A
2
0
0
9
23
23
S
P
A
A
2
0
0
9
Emerging multi-core architectures have led to the adoption of Transactional Memory (TM) as a new synchronization method. This study delves into the challenges of TM, examining the consequences of transaction aborts, the need for spare aborts, and evaluating measures to enhance transaction processing efficiency. The concept of opacity in TM is explored, along with discussions on commit-abort ratios and contention management strategies. The analysis aims to improve the effectiveness of TM in complex computing environments.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
IditKeidar and Dmitri Perelman Technion SPAA 2009 1
The emergence of multi-core architectures Conventional locking Transactional Memory is a new synchronization abstraction You may continue by yourself 2 SPAA 2009
Aborting transactions is bad: the work is lost the resources are wasted overall throughput decreases May be even worse: aborted transactions restart and conflict again livelock 3 SPAA 2009
Some times aborts are necessary continuing the run would violate correctness And some times they are not spare aborts the suspicion is unjustified most of the times based on conflict detection Our question: to what degree can we avoid spare aborts? 4 SPAA 2009
Previous measures for evaluating spare aborts and their limitations Our measures for evaluating spare aborts Example TM avoiding spare aborts 5 SPAA 2009
Opacityis widely accepted [Guerraoui and Kapalka 08] Informally: strict serializability, taking into account all the transactions (including the live and aborted ones) 6 SPAA 2009
Previous measures for evaluating spare aborts and their limitations Our measures for evaluating spare aborts Example TM avoiding spare aborts 7 SPAA 2009
Commit-Abort Ratio [Gramoli, Harmanciand Felber]: |committed| / (|committed aborted|) Influenced by the decisions of contention manager We show: every TM is (L) competitive in terms of its C- A ratio (L maximal possible number of live txns) All TMs are bad in terms of C-A ratio, hard to compare Which txn to abort? o1 o1 C A A C o2 o2 T1 T1 A A A o3 o3 T2 T2 A A A 8 SPAA 2009
TM is p-permissive w.r.t. safety property p if it accepts every history that satisfies p [Guerraoui et al 08] Our focus: opacity-permissiveness If the given history does not violate opacity, then the TM should run it without aborts 9 SPAA 2009
We show: there exists no TM providing 0pacity- permissiveness Intuition: there is a degree of freedom given to the read operations cannot predict what value should be read in order to avoid spare aborts in future 10 SPAA 2009
Previous measures for evaluating spare aborts and their limitations Our measures for evaluating spare aborts Example TM avoiding spare aborts 11 SPAA 2009
Strict Online Opacity-Permissiveness: a TM forcefully aborts a txn only when not aborting any txn violates opacity. does not define which txnsshould be aborted allows returning a value that causes abort in the future NP-Complete in the number of committed txns reduction from the view-serializability detection problem [Papadimitriou 79] 12 SPAA 2009
The problem: the order of committed txns is undefined C C C o1 T3 T4 T1 o2 C o3 T2 ? Txns serialization: T4 T1 T2 T3 13 SPAA 2009
Online opacity-permissiveness(intuition): order the committed txnswriting to the same objects this order should be preserved during the run 14 SPAA 2009
Visible reads have their cost: cache invalidations in a multi-core environments Postpone exposing the read if possible We show: if a TM satisfies online opacity- permissiveness the reads must be exposed as they happen must be exposed T3 T3 A o1 o1 T2 o2 o2 T1 T1 T4 T4 15 SPAA 2009
Previous measures for evaluating spare aborts and their limitations Our measures for evaluating spare aborts Example TM avoiding spare aborts 16 SPAA 2009
AbortsAvoideralgorithm as a possibility proof Polynomial time operation complexity Maintains version lists and the precedence graph 17 SPAA 2009
Directed labeled graph over transactions different variations in prior works [Napper and Alvisi 05, Guerraoui and Kapalka08] We show: if a TM maintains PG acyclic and aborts txn only upon cycle creation, then this TM satisfies online opacity- permissiveness WaW writer writer RaW RaW o.vn readers o.vn-1 readers 18 SPAA 2009
Reads are simple: look for the latest version that does not create a cycle in the PG Writes are simpler than Reads: postpone the work till commit (invisible writes) 19 SPAA 2009
Install the new versions of all written objects non-blind writes: after the version that has been read blind writes: plenty of options The greedy approach does not work The places to install are sought in iterations 20 SPAA 2009
Transactions cannot be garbage collected right after the termination should be kept in PG as long as it has a potential to participate in a cycle We define GC conditions from some point onward no new incoming edges will be added to the node Optimizations to save run-time complexity 21 SPAA 2009
Avoiding spare aborts is not always possible Avoiding spare aborts may be costly: no invisible reads for opacity complicated conditions for GC Proof-of-concept algorithm avoiding spare aborts with polynomial time complexity Spare aborts vs. Operations complexity tradeoff is yet to be studied 22 SPAA 2009
23 SPAA 2009
