Geodesic
On choosing space-time mappings during automatic parallelization of loop nests with static control flow
Informacionnye tehnologii i vyčislitelnye sistemy, no. 1 (2015), pp. 19-32.

Voir la notice de l'article provenant de la source Math-Net.Ru

Problems of affine scheduling and spatial distribution for programs composed of loop nests with static control flow are considered as multi-objective optimization problems with no uncertainty in context of data locality optimization. Presented method based on polyhedral model appliance computes space-time mapping to expose parallelism while minimizing data reuse latency in time domain and data reuse distance in space domain for each data dependence on the assumption of subjective preferences of the decision maker on optimization quality for each dependence. Subjective preferences are defined by weighting coefficients in linear form of scalarized multi-objective problem. Finding Pareto-optimal solution is reduced to solving of integer linear programming problem. The method allows to specify subjective preferences more precisely (notably for weakly parameterized programs or for programs with artificially de-emphasized parameterization during Just-In-Time compilation) in contradistinction to classic methods relying on lexicographic optimization such as Pluto. Application of the method is illustrated with parallelization of LU-decomposition algorithm. Parallel version of the algorithm obtained with presented method outperforms the result obtained with Pluto compiler.
Keywords: automatic parallelization, locality optimization, polyhedral model, integer linear programming. 
@article{ITVS_2015_1_a2,
     author = {A. S. Lebedev},
     title = {On choosing space-time mappings during automatic parallelization of loop nests with static control flow},
     journal = {Informacionnye tehnologii i vy\v{c}islitelnye sistemy},
     pages = {19--32},
     publisher = {mathdoc},
     number = {1},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ITVS_2015_1_a2/}
}
TY  - JOUR
AU  - A. S. Lebedev
TI  - On choosing space-time mappings during automatic parallelization of loop nests with static control flow
JO  - Informacionnye tehnologii i vyčislitelnye sistemy
PY  - 2015
SP  - 19
EP  - 32
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ITVS_2015_1_a2/
LA  - ru
ID  - ITVS_2015_1_a2
ER  - 
%0 Journal Article
%A A. S. Lebedev
%T On choosing space-time mappings during automatic parallelization of loop nests with static control flow
%J Informacionnye tehnologii i vyčislitelnye sistemy
%D 2015
%P 19-32
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ITVS_2015_1_a2/
%G ru
%F ITVS_2015_1_a2
A. S. Lebedev. On choosing space-time mappings during automatic parallelization of loop nests with static control flow. Informacionnye tehnologii i vyčislitelnye sistemy, no. 1 (2015), pp. 19-32. http://geodesic.mathdoc.fr/item/ITVS_2015_1_a2/