TY - GEN
T1 - Set-Congruence Dynamic Analysis for Thread-Level Speculation (TLS)
AU - Oancea, Cosmin Eugen
AU - Mycroft, Alan
N1 - @incollection{Oancea:2008:SDA:1485701.1485712,
author = {Oancea, Cosmin E. and Mycroft, Alan},
chapter = {Set-Congruence Dynamic Analysis for Thread-Level Speculation (TLS)},
title = {Languages and Compilers for Parallel Computing},
editor = {Amaral, Jos{\'e} Nelson},
year = {2008},
isbn = {978-3-540-89739-2},
pages = {156--171},
numpages = {16},
url = {http://dx.doi.org/10.1007/978-3-540-89740-8_11},
doi = {10.1007/978-3-540-89740-8_11},
acmid = {1485712},
publisher = {Springer-Verlag},
address = {Berlin, Heidelberg},
}
PY - 2008
Y1 - 2008
N2 - The move to multi-core has increased interest in parallelizing sequential programs. Classical dependency-based techniques, although successful for some classes of programs, often fail due to the one-sided (conservative) approximation of program behavior. Thread-level speculation enables increased parallelism by allowing out-of-order execution: correct dependences are ensured by run-time monitoring and possible rollbacks. Two-sided approximations of program behavior are now acceptable if the rollback ratio is kept small. We describe dynamic analyses, based on representing dependencies as modular congruences, which can be employed on-line or off-line. One, thread partitioning , efficiently enables loop iterations to be allocated to threads (and calculates the maximum effective concurrency); the other, fine-grain memory partitioning , calculates a hash function that reduces space overhead and performance loss due to TLS-metadata-based and cache-based task interference.
AB - The move to multi-core has increased interest in parallelizing sequential programs. Classical dependency-based techniques, although successful for some classes of programs, often fail due to the one-sided (conservative) approximation of program behavior. Thread-level speculation enables increased parallelism by allowing out-of-order execution: correct dependences are ensured by run-time monitoring and possible rollbacks. Two-sided approximations of program behavior are now acceptable if the rollback ratio is kept small. We describe dynamic analyses, based on representing dependencies as modular congruences, which can be employed on-line or off-line. One, thread partitioning , efficiently enables loop iterations to be allocated to threads (and calculates the maximum effective concurrency); the other, fine-grain memory partitioning , calculates a hash function that reduces space overhead and performance loss due to TLS-metadata-based and cache-based task interference.
U2 - 10.1007/978-3-540-89740-8_11
DO - 10.1007/978-3-540-89740-8_11
M3 - Article in proceedings
SN - 978-3-540-89739-2
SP - 156
EP - 171
BT - Languages and Compilers for Parallel Computing (LCPC'08)
PB - Springer Verlag
ER -