The Challenges of Non-linear Parameters and Variables in Automatic Loop Parallelisation

Die Herausforderungen nichtlinearer Parameter und Variablen in automatischer Schleifenparallelisierung

  • With the rise of manycore processors, parallelism is becoming a mainstream necessity. Unfortunately, parallel programming is inherently more difficult than sequential programming; therefore, techniques for automatic parallelisation will become indispensable. We aim at extending the well-known polyhedron model, which promises this automation, beyond some of its current restrictions. Up to now, loop bounds and array subscripts in the modelled codes must be expressions linear in both the variables and the parameters. We lift this restriction and allow certain polynomial expressions instead of linear ones. With our extensions, we are able to handle more programs in all phases of the parallelisation process (dependence analysis, transformation of the program model, code generation). We extend Banerjee's classical dependence analysis to handle one non-linear parameter p, i.e., we are able to determine precisely the solutions of the system of conflict equalities for input programs with non-linear array accesses like A[p*i] in dependence of tWith the rise of manycore processors, parallelism is becoming a mainstream necessity. Unfortunately, parallel programming is inherently more difficult than sequential programming; therefore, techniques for automatic parallelisation will become indispensable. We aim at extending the well-known polyhedron model, which promises this automation, beyond some of its current restrictions. Up to now, loop bounds and array subscripts in the modelled codes must be expressions linear in both the variables and the parameters. We lift this restriction and allow certain polynomial expressions instead of linear ones. With our extensions, we are able to handle more programs in all phases of the parallelisation process (dependence analysis, transformation of the program model, code generation). We extend Banerjee's classical dependence analysis to handle one non-linear parameter p, i.e., we are able to determine precisely the solutions of the system of conflict equalities for input programs with non-linear array accesses like A[p*i] in dependence of the residue class of p. We make contributions to three transformations desirable in automatic parallelisation. First, we show that using a generalised Simplex algorithm, which we have developed, schedules with non-linear parameters like theta(i)=floor(i/n) can be computed. In addition, such schedules can be expressed easily as a quantifier elimination problem but this approach turns out to be computationally less efficient with the available implementation. As a second transformation, we study parametric tiling which is used to adapt a parallelised program to the number of available processors at run time. Third, we present a localisation technique to exploit scratchpad memories on architectures on which data caching has to be handled by software. We transform a given code such that it keeps values which are reused in successive iterations of a sequential loop in the scratchpad. An access to a value written in an earlier iteration is served from the scratchpad to accelerate the access. In general, this transformation introduces non-linear loop bounds in the transformed model. Finally, we present an algorithm for generating code for arbitrary semi-algebraic iteration sets, i.e., for iteration sets described by polynomial inequalities in the variables and parameters. This is a vast generalisation of existing polyhedral code generation techniques. Although our algorithm is less efficient than polyhedral code generators, this paves the way for a code generator that can handle arbitrary parametric tilings and other transformations which introduce non-linear parameters (like non-linear schedules and the localisation we present) or even non-linear variables.show moreshow less

Download full text files

Export metadata

  • Export Bibtex
  • Export RIS
  • Export XML

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Armin Größlinger
URN:urn:nbn:de:bvb:739-opus-17893
Advisor:Christian Lengauer
Document Type:Doctoral Thesis
Language:English
Year of Completion:2009
Date of Publication (online):2009/12/18
Publishing Institution:Universität Passau
Granting Institution:Universität Passau, Fakultät für Informatik und Mathematik
Date of final exam:2009/12/02
Release Date:2009/12/18
Tag:Codegenerierung für nicht-polyedrische Iterationsräume; Polyedermodell; Schleifentransformation
automatic parallelization; code generation for non-polyhedral domains; loop transformations; optimizing compilers; polyhedron model
GND Keyword:Automatische Parallelisierung; Codegenerierung; Optimierender Compiler
Institutes:Fakultät für Informatik und Mathematik / Sonstiger Autor der Fakultät für Informatik und Mathematik
CCS-Classification:I. Computing Methodologies / I.2 ARTIFICIAL INTELLIGENCE / I.2.2 Automatic Programming (D.1.2, F.3.1, F.4.1)
Dewey Decimal Classification:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik
open_access (DINI-Set):open_access
Licence (German):License LogoStandardbedingung laut Einverständniserklärung

$Rev: 13581 $