Coarse-grained loop parallelization: Iteration Space Slicing vs affine transformations

被引：29

作者：

Beletska, Anna ^{[2
]}

Bielecki, Wlodzimierz ^{[1
]}

Cohen, Albert ^{[2
]}

Palkowski, Marek ^{[1
]}

Siedlecki, Krzysztof ^{[1
]}

机构：

[1] W Pomeranian Tech Univ, Dept Comp Sci, PL-71210 Szcecin, Poland

[2] INRIA Saclay, F-91893 Orsay, France

来源：

PARALLEL COMPUTING | 2011年 / 37卷 / 08期

关键词：

Coarse-grained parallelism; Iteration Space Slicing; Affine transformations; TRANSITIVE CLOSURE; GENERATION;

D O I：

10.1016/j.parco.2010.12.005

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Automatic coarse-grained parallelization of program loops is of great importance for parallel computing systems. This paper presents the theory of Iteration Space Slicing aimed at extracting synchronization-free parallelism available in arbitrarily nested program loops. We demonstrate that Iteration Space Slicing algorithms permits for extracting more coarse-grained parallelism than that extracted by means of the Affine Transformation Framework provided that we are able to calculate the transitive closure of the union of relations describing all dependences in the affine loop. Experimental results show that by means of Iteration Space Slicing algorithms, we are able to extract coarse-grained parallelism for many loops of NAS and UTDSP benchmarks. Problems to be resolved in order to enhance the theory of Iteration Space Slicing are discussed. (C) 2011 Elsevier B.V. All rights reserved.

引用

页码：479 / 497

页数：19

共 31 条

[1]

ANCOURT C, 1991, SIGPLAN NOTICES, V26, P39, DOI 10.1145/109626.109631

[2]

[Anonymous], UTDSP BENCHMARKS SUI

[3]

[Anonymous], INTEGER SET LIB ISL

[4] Code generation in the polyhedral model is easier than you think [J].

Bastoul, C .

13TH INTERNATIONAL CONFERENCE ON PARALLEL ARCHITECTURE AND COMPILATION TECHNIQUES, PROCEEDINGS, 2004, :7-16

[5]

Bastoul C., 2003, International Workshop on Languages and Compilers for Parallel Computing, P209

[6]

Bau David., 1994, P 7 ANN WORKSHOP LAN, P46

[7]

Beletska A., 2009, 22 INT WORKSH LANG C

[8]

Beletska A, 2008, LECT NOTES COMPUT SC, V5073, P871

[9]

Beletska A, 2009, LECT NOTES COMPUT SC, V5573, P98, DOI 10.1007/978-3-642-02026-1_9

[10] Using message passing for developing coarse-grained applications in OpenMP [J].

Bielecki, Wlodzimierz ;

Marek, Palkowski .

ICSOFT 2008: PROCEEDINGS OF THE THIRD INTERNATIONAL CONFERENCE ON SOFTWARE AND DATA TECHNOLOGIES, VOL PL/DPS/KE, 2008, :145-152

← 1 2 3 4 →