RT info:eu-repo/semantics/article
T1 On the choice of the best chunk size for the speculative execution of loops
A1 Estebanez, Alvaro
A1 Llanos, Diego R.
A1 Orden, David
A1 Palop, Belen
K1 Informática
K1 1203 Ciencia de Los Ordenadores
K1 3304 Tecnología de Los Ordenadores
AB Loops are a rich source of parallelism. Unfortunately, many loops cannot be safely parallelized at compile time because the compiler is not able to guarantee that there will be no dependence violations. Thread-Level Speculation (TLS) techniques, either hardware or software-based, allow the parallel execution of non-analyzable loops, issuing the execution of blocks of consecutive iterations (called chunks) while a hardware or software monitor ensures that no dependence violations arise. If such a dependence violation occurs, the chunk that was fed with incorrect values is discarded and re-started, in order to consume the correct information. In the speculative execution of non-analyzable loops, it is very important to correctly choose the chunk size, because this choice dramatically affects the performance of the parallel execution. Bigger chunks imply less scheduling overheads, but smaller chunks allow fewer calculations to be discarded in the event of a dependence violation. To find a good chunk size is not a simple task, because loops may present dependencies that cannot be detected at compile time. In this paper, we present a comprehensive evaluation of different scheduling methods to estimate the optimal chunk size in the speculative execution of non-analyzable loops. This evaluation ranges from the simple, classical methods originally devised to achieve load balancing in loops with no dependencies, to methods that make some assumptions on the distribution pattern of dependencies, such as Meseta and Just-in-Time scheduling. We also propose and evaluate a general, more complex method called Moody Scheduling, that does not require a-priori assumptions to achieve the highest performance.
PB Plos ONE
SN 1932-6203
YR 2022
FD 2022
LK https://uvadoc.uva.es/handle/10324/70095
UL https://uvadoc.uva.es/handle/10324/70095
LA eng
NO PLOS One, may 2022, ISSN 1932-6203.
NO Producción Científica
DS UVaDOC
RD 24-nov-2024