Speculative Program Parallelization with Scalable and Decentralized Runtime Verification

Aravind Sukumaran-Rajam 1, 2 Juan Manuel Martinez 1, 2 Willy Wolff 1 Alexandra Jimborean 3 Philippe Clauss 4, 1, 5
1 CAMUS - Compilation pour les Architectures MUlti-coeurS
Inria Nancy - Grand Est, ICube - Laboratoire des sciences de l'ingénieur, de l'informatique et de l'imagerie
2 ICPS
ICube - Laboratoire des sciences de l'ingénieur, de l'informatique et de l'imagerie
Abstract : Thread Level Speculation (TLS) is a dynamic code parallelization technique proposed to keep the software in pace with the advances in hardware, in particular, to automatically parallelize programs to take advantage of the multi-core processors. Being speculative, frameworks of this type unavoidably rely on verification systems that are similar to software transactional memory, and that require voluminous inter-thread communications or centralized registering of the performed memory accesses. The high degree of communication is against the basic principles of high performance parallel computing, does not scale with an increasing number of processor cores, and yields weak performance. Moreover, TLS systems often apply one unique parallelization strategy consisting in slicing a loop into several parallel speculative threads. Such a strategy is also against the basic principles since loops in the original serial code are not necessarily parallel and also, it is well-known that the parallel schedule must promote data locality which is crucial in obtaining good performance. This situation appeals to scalable and decentralized verification systems and new strategies to dynamically generate efficient parallel code resulting from advanced optimizing parallelizing transformations. Such transformations require a more complex verification system that allows intra-thread iterations to be reordered. In this paper, we propose a verification system of this kind, based on a model built at runtime and predicting a linear memory behavior. This strategy is part of the Apollo speculative code parallelizer which is based on an adaptation for dynamic usage of the polyhedral model.
Type de document :
Communication dans un congrès
Borzoo Bonakdarpour; Scott A. Smolka. Runtime Verification, Sep 2014, Toronto, Canada. Springer, 8734, pp.124-139, 2014, 〈http://link.springer.com/chapter/10.1007%2F978-3-319-11164-3_11〉. 〈10.1007/978-3-319-11164-3_11〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01070610
Contributeur : Philippe Clauss <>
Soumis le : mercredi 1 octobre 2014 - 18:53:35
Dernière modification le : jeudi 29 mars 2018 - 09:10:05

Lien texte intégral

Identifiants

Citation

Aravind Sukumaran-Rajam, Juan Manuel Martinez, Willy Wolff, Alexandra Jimborean, Philippe Clauss. Speculative Program Parallelization with Scalable and Decentralized Runtime Verification. Borzoo Bonakdarpour; Scott A. Smolka. Runtime Verification, Sep 2014, Toronto, Canada. Springer, 8734, pp.124-139, 2014, 〈http://link.springer.com/chapter/10.1007%2F978-3-319-11164-3_11〉. 〈10.1007/978-3-319-11164-3_11〉. 〈hal-01070610〉

Partager

Métriques

Consultations de la notice

189