Iteration Space Slicing

 

The TRACO compiler is an implementation of loop parallelization algorithms developed by Prof. Wlodzimierz Bielecki team in the West Pomeranian University of Technology. The code of the iteration space slicing framework (ISSF) is mostly created by Marek Palkowski. The engine of transitive closure is implemented by Tomasz Klimek. The tool realizes iteration space slicing for program loops. TRACO is based on the Omega Calculator library. Loop dependence analysis is calculated by means of the Petit tool. Code generation can be realized by Barvinok/CLOOG or Omega. Details of algorithms can be found in the article below:

article

download

 

The software can be downloaded with the svn repository (recommended). TRACO is currently under development and testing.

SVN is available at the sourceforge.net website
svn checkout http://svn.code.sf.net/p/traco/code/trunk traco-code
http://sourceforge.net/projects/traco/

Free scheduling

 

The another way of extracting parallelism in loops. The statements can be executed parallel in a part of time when all their operands are available. The technique can extract parallel statements also for one slice in iteration space. Details can be found in the article below:

article

source-to-source

 

TRACO supports source-to-source transformation of C code. The output is a parallel code with OpenMP pragmas. Implementation was developed in Python and C/C++.

http://sourceforge.net/projects/traco/

Example


articles

 

Wlodzimierz Bielecki, Marek Palkowski, Tiling arbitrarily nested loops by means of the transitive closure of dependence graphs, AMCS : International Journal of Applied Mathematics and Computer Science, Vol. 26, No. 4, pp. 919-939, 2016.

Marek Palkowski, Impact of Variable Privatization on Extracting Synchronization-Free Slices, Facing the Multicore-Challenge III, Volume 7686 of the series Lecture Notes in Computer Science pp 72-83, LNCS 2013.

Wlodzimierz Bielecki, Marek Palkowski, Tomasz Klimek, Free scheduling for statement instances of parameterized arbitrarily nested affine loops, Parallel Computing, Volume 38 Issue 9, September, 2012, Pages 518-532.

Wlodzimierz Bielecki, Marek Palkowski, Using Free Scheduling for Programming Graphic Cards, Facing the Multicore - Challenge II, Lecture Notes in Computer Science Volume 7174, 2012, pp 72-83

Marek Palkowski, Automatic Privatization for Parallel Execution of Loops, Artificial Intelligence and Soft Computing - 11th International Conference, ICAISC 2012, Zakopane, Poland, April 29-May 3, 2012, Proceedings, Part II. Lecture Notes in Computer Science 7268, 395-403, Springer 2012,

Anna Beletska, Wlodzimierz Bielecki, Albert Cohen, Marek Palkowski, Krzysztof Siedlecki: Coarse-grained loop parallelization: Iteration Space Slicing vs affine transformations. Parallel Computing 37(8): 479-497 (2011)

Wlodzimierz Bielecki, Tomasz Klimek, Marek Palkowski, Anna Beletska: An Iterative Algorithm of Computing the Transitive Closure of a Union of Parameterized Affine Integer Tuple Relations. COCOA (1) 2010: 104-113

Wlodzimierz Bielecki, Marek Palkowski, Coarse-Grained Loop Parallelization for Image Processing and Communication Applications, Image Processing and Communications Challenges 2, Advances in Intelligent and Soft Computing Volume 84, 2010, pp 307-314

Anna Beletska, Wlodzimierz Bielecki, Albert Cohen, Marek Palkowski, Krzysztof Siedlecki: Coarse-Grained Loop Parallelization: Iteration Space Slicing vs Affine Transformations. ISPDC 2009: 73-80

Anna Beletska, Wlodzimierz Bielecki, Albert Cohen, Marek Palkowski: Synchronization-Free Automatic Parallelization: Beyond Affine Iteration-Space Slicing. LCPC 2009: 233-246

Wlodzimierz Bielecki, Marek Palkowski: Extracting Both Affine and Non-linear Synchronization-Free Slices in Program Loops. PPAM (1) 2009: 196-205

Wlodzimierz Bielecki, Anna Beletska, Marek Palkowski, Pierluigi San Pietro: Finding Synchronization-Free Parallelism Represented with Trees of Dependent Operations. ICA3PP 2008: 185-195

Wlodzimierz Bielecki, Marek Palkowski: Using Message Passing for Developing Coarse-Grained Applications in OpenMP. ICSOFT (PL/DPS/KE) 2008: 145-152




Citations

@article{BieleckiAMCS16,
  author    = {Wlodzimierz Bielecki and
               Marek Palkowski},
  title     = {Tiling arbitrarily nested loops by means of the transitive
               closure of dependence graphs},
  journal   = {AMCS : International Journal of Applied Mathematics
               and Computer Science},
  volume    = {26},
  number    = {4},
  year      = {2016},
  pages     = {919-939},
  doi       = {10.1515/amcs-2016-0065},
}


@article{BieleckiPK12,
  author    = {Wlodzimierz Bielecki and
               Marek Palkowski and
               Tomasz Klimek},
  title     = {Free scheduling for statement instances of parameterized
               arbitrarily nested affine loops},
  journal   = {Parallel Computing},
  volume    = {38},
  number    = {9},
  year      = {2012},
  pages     = {518-532},
  ee        = {http://dx.doi.org/10.1016/j.parco.2012.06.001},
}


@article{BeletskaBCPS11,
  author    = {Anna Beletska and
               Wlodzimierz Bielecki and
               Albert Cohen and
               Marek Palkowski and
               Krzysztof Siedlecki},
  title     = {Coarse-grained loop parallelization: Iteration Space Slicing
               vs affine transformations},
  journal   = {Parallel Computing},
  volume    = {37},
  number    = {8},
  year      = {2011},
  pages     = {479-497},
  ee        = {http://dx.doi.org/10.1016/j.parco.2010.12.005},
}

Best Paper Award

 

The paper 'Impact of Variable Privatization on Extracting Synchronization-Free Slices' has got the Best Paper Award (Theory) on the 3rd Facing the Multicore Challenge conference

event