Speculative Runtime Parallelization of Loop Nests: Towards Greater Scope and Efficiency

Abstract : Runtime loop optimization and speculative execution are becoming more and more prominent to leverage performance in the current multi-core and many-core era. However, a wider and more efficient use of such techniques is mainly hampered by the prohibitive time overhead induced by centralized data race detection, dynamic code behavior modeling and code generation. Most of the existing Thread Level Speculation (TLS) systems rely on slicing the target loops into chunks, and trying to execute the chunks in parallel with the help of a centralized performance-penalizing verification module that takes care of data races. Due to the lack of a data dependence model, these speculative systems are not capable of doing advanced transformations and, more importantly, the chances of rollback are high. The polytope model is a well known mathematical model to analyze and optimize loop nests. The current state-of-art tools limit the application of the polytope model to static control codes. Thus, none of these tools can handle codes with while loops, indirect memory accesses or pointers. Apollo (Automatic POLyhedral Loop Optimizer) is a framework that goes one step beyond, and applies the polytope model dynamically by using TLS. Apollo can predict, at runtime, whether the codes are behaving linearly or not, and applies polyhedral transformations on-the-fly. This paper presents a novel system, which extends the capability of Apollo to handle codes whose memory accesses are not necessarily linear. More generally, this approach expands the applicability of the polytope model at runtime to a wider class of codes.
Type de document :
Communication dans un congrès
20th International Workshop on High-level Parallel Programming Models and Supportive Environments, held in conjunction with 29th IEEE International Parallel & Distributed Processing Symposium, May 2015, Hyderabad, India. 2015
Liste complète des métadonnées

https://hal.inria.fr/hal-01155172
Contributeur : Philippe Clauss <>
Soumis le : mardi 26 mai 2015 - 11:39:18
Dernière modification le : samedi 27 octobre 2018 - 01:27:07

Identifiants

  • HAL Id : hal-01155172, version 1

Citation

Aravind Sukumaran-Rajam, Luis Esteban Campostrini, Martinez Juan Manuel, Philippe Clauss. Speculative Runtime Parallelization of Loop Nests: Towards Greater Scope and Efficiency. 20th International Workshop on High-level Parallel Programming Models and Supportive Environments, held in conjunction with 29th IEEE International Parallel & Distributed Processing Symposium, May 2015, Hyderabad, India. 2015. 〈hal-01155172〉

Partager

Métriques

Consultations de la notice

220