Nested loop sequences : towards efficient loop structures in automatic parallelization

Zbigniew Chamski 1
1 API - Parallel VLSI Architectures
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, INRIA Rennes
Abstract : An important problem in automatic parallelization of scientific programs is to generate loops from an algebraic description of the iteration domain. The usual technique is to produce a perfectly nested set of loops, whose bounds consist in maxima and minima of several affine functions. However, perfect loop nests suffer from the run-time overhead of evaluating bound expressions and do not allow to scannon-convex domains efficiently. In this paper we study a candidate loop structure for overcoming these problems. This structure, called nested loop sequence (NLS) is defined as a sequence of DO loops whose bodies are nonempty sequences of DO loops. We propose an algorithm to compute a NLS scanning a given convex polyhedron, which overcomes the run-time overhead problem. The algorithm produces a loop structure in which the bounds of every loop consist each in a single affine functions.
Type de document :
[Research Report] RR-2094, INRIA. 1993
Liste complète des métadonnées
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 15:50:15
Dernière modification le : vendredi 16 novembre 2018 - 01:29:58
Document(s) archivé(s) le : dimanche 4 avril 2010 - 22:00:00



  • HAL Id : inria-00074578, version 1


Zbigniew Chamski. Nested loop sequences : towards efficient loop structures in automatic parallelization. [Research Report] RR-2094, INRIA. 1993. 〈inria-00074578〉



Consultations de la notice


Téléchargements de fichiers