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 -