A Study of Transitive Closure based Loop Transformation Techniques of Affine Integer Relations for Coarse Grain Parallelism

Bhos, K (2015) A Study of Transitive Closure based Loop Transformation Techniques of Affine Integer Relations for Coarse Grain Parallelism. Masters thesis, Indian Institute of Technology Hyderabad.

CS13M1011.pdf - Submitted Version

Download (1MB) | Preview


This thesis focuses on computation of transitive closure of affine integer tuple relations and its effect on improvement on run time of the resultant parallelized programs. Scalability issues of the computation are also discussed. Different strategies are used by automatic parallelization compilers to find statements that can be executed in parallel. Most of the current approaches like Pluto [1] and Polly [2] use linear/integer- linear programming based techniques as a means to do the same. An emerging alternative is to use the transitive closure to do the same. The transitive closure based methods are different in strategy and complexity with compared with methods that use the linear programming based approaches. Traco [3] is a source to source transformation tool which tries to find slices of program that can be executed in parallel using Transitive Closure. Polly [2] is a branch of LLVM which uses scanning of AST to obtain independent dimension of iteration vector. Both Traco and Polly use OpenMP [4] pragmas to show detected parallelism. We do a comparative study of Traco and Polly to extract coarse grained parallelization. We suggest important modifications to Polly’s algorithm of dependence extraction. We show limitations of the Traco compiler on various fronts: limitations in extracting parallelism, scalability because of dependence on transitive closure etc.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Item Type: Thesis (Masters)
Uncontrolled Keywords: Transitive closure, affine integer relations, course grain parallelism, TD283
Subjects: Computer science > Big Data Analytics
Divisions: Department of Computer Science & Engineering
Depositing User: Library Staff
Date Deposited: 01 Jul 2015 06:49
Last Modified: 13 May 2019 09:38
URI: http://raiith.iith.ac.in/id/eprint/1630
Publisher URL:
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 1630 Statistics for this ePrint Item