OPUS - Passau

Bibliographische Daten und PDF-Volltexte aus der Universität Passau
... die Wissenschaft der Hochschule sichtbar machen!

Home

Suchen

Melden

Veröffentlichen

Hilfe

Kontakt

OPUS-Frontdoor

Größlinger, Armin

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

Die Herausforderungen nichtlinearer Parameter und Variablen in automatischer Schleifenparallelisierung

Open Access: Freier Zugang zum Volltext!

pdf-Format:

Dokument 1.pdf (2.107 KB)

SWD-Schlagwörter:		Automatische Parallelisierung , Codegenerierung , Optimierender Compiler
Freie Schlagwörter (Deutsch):		Schleifentransformation , Codegenerierung für nicht-polyedrische Iterationsräume , Polyedermodell
Freie Schlagwörter (Englisch):		automatic parallelization , loop transformations , code generation for non-polyhedral domains , polyhedron model , optimizing compilers
CCS - Klassifikation:		I.2.2
Beteiligte Einrichtung:		Sonstiger Autor der Fakultät für Informatik und Mathematik
Fakultät:		Fakultät für Informatik und Mathematik
DDC-Sachgruppe:		Informatik
Dokumentart:		Dissertation
Hauptberichter:		Lengauer, Christian (Prof. Dr.)
Sprache:		Englisch
Tag der mündlichen Prüfung:		02.12.2009
Erstellungsjahr:		2009
Publikationsdatum:		18.12.2009
Kurzfassung auf Englisch:		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 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.
Lizenz:		Veröffentlichungsvertrag für Publikationen ohne Print on Demand

Lizenz

URN: http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-17893
URL dieser Seite: http://www.opus-bayern.de/uni-passau/volltexte/2009/1789/