Dynamic and Speculative Polyhedral ParallelizationUsing Compiler-Generated Skeletons

Jimborean, Alexandra; Clauss, Philippe; Dollinger, Jean-François; Loechner, Vincent; Martinez Caamaño, Juan Manuel

Publication:
Dynamic and Speculative Polyhedral ParallelizationUsing Compiler-Generated Skeletons

dc.contributor.author	Jimborean, Alexandra
dc.contributor.author	Clauss, Philippe
dc.contributor.author	Dollinger, Jean-François
dc.contributor.author	Loechner, Vincent
dc.contributor.author	Martinez Caamaño, Juan Manuel
dc.contributor.department	Ingeniería y Tecnología de Computadores
dc.date.accessioned	2024-02-01T08:33:05Z
dc.date.available	2024-02-01T08:33:05Z
dc.date.issued	2013-08-09
dc.description.abstract	We propose a framework based on an original generation and use of algo-rithmic skeletons, and dedicated to speculative parallelization of scientific nested loopkernels, able to apply at run-time polyhedral transformations to the target code in orderto exhibit parallelism and data locality. Parallel code generation is achieved almostat no cost by using binary algorithmic skeletons that are generated at compile-time,and that embed the original code and operations devoted to instantiate a polyhedralparallelizing transformation and to verify the speculations on dependences. The skele-tons are patched at run-time to generate the executable code. The run-time processincludes a transformation selection guided by online profiling phases on short samples,using an instrumented version of the code. During this phase, the accessed memoryaddresses are used to compute on-the-fly dependence distance vectors, and are alsointerpolated to build a predictor of the forthcoming accesses. Interpolating functionsand distance vectors are then employed for dependence analysis to select a paral-lelizing transformation that, if the prediction is correct, does not induce any rollbackduring execution. In order to ensure that the rollback time overhead stays low, the code is executed in successive slices of the outermost original loop of the nest. Eachslice can be either a parallel version which instantiates a skeleton, a sequential originalversion, or an instrumented version. Moreover, such slicing of the execution providesthe opportunity of transforming differently the code to adapt to the observed executionphases, by patching differently one of the pre-built skeletons. The framework has beenimplemented with extensions of the LLVM compiler and an x86-64 runtime system.Significant speed-ups are shown on a set of benchmarks that could not have beenhandled efficiently by a compiler.	es
dc.embargo.terms	1-ene-2999
dc.format	application/pdf	es
dc.format.extent	14	es
dc.identifier.citation	International Journal Parallel Programming (2014) 42:529–545
dc.identifier.doi	10.1007/s10766-013-0259-4
dc.identifier.issn	0885-7458
dc.identifier.uri	http://hdl.handle.net/10201/138367
dc.language	eng	es
dc.publisher	Springer	es
dc.relation	Sin financiación externa a la Universidad	es
dc.rights.accessRights	info:eu-repo/semantics/restrictedAccess
dc.subject	Algorithmic skeletons	es
dc.subject	Polytope model	es
dc.subject	Automatic parallelization	es
dc.subject	Dynamic parallelization	es
dc.subject	Loop nests·Compilation	es
dc.subject	Speculative parallelization	es
dc.title	Dynamic and Speculative Polyhedral ParallelizationUsing Compiler-Generated Skeletons	es
dc.type	info:eu-repo/semantics/article	es
dspace.entity.type	Publication	es