Skip to Main content Skip to Navigation
Conference papers

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
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.
Document type :
Conference papers
Complete list of metadatas
Contributor : Philippe Clauss <>
Submitted on : Wednesday, October 1, 2014 - 6:53:35 PM
Last modification on : Saturday, October 27, 2018 - 1:26:50 AM

Links full text



Aravind Sukumaran-Rajam, Juan Manuel Martinez, Willy Wolff, Alexandra Jimborean, Philippe Clauss. Speculative Program Parallelization with Scalable and Decentralized Runtime Verification. Runtime Verification, Sep 2014, Toronto, Canada. pp.124-139, ⟨10.1007/978-3-319-11164-3_11⟩. ⟨hal-01070610⟩



Record views