Bibliography

PhD thesis

• Georges-André Silber, "Parallélisation automatique par insertion de directives", (in french) Thèse de doctorat de l'École normale supérieure de Lyon, 1999.(Gzipped-postscript),(Postscript), BibTeX reference.

Journals

• Alain Darte, Georges-André Silber and Frédéric Vivien, "Combining retiming and scheduling techniques for loop parallelization and loop tiling", Parallel Processing Letters, 7(4):379-392, 1998. (PPL-7.4), Research report, BibTeX reference.

• Pierre Boulet, Alain Darte, Georges-André Silber and Frédéric Vivien, "Loop parallelization algorithms: from parallelism extraction to code generation", Parallel Computing, 24(3), 1998. (PARCO-24.3), Research report, BibTeX reference.

Conferences

• Georges-André Silber and Alain Darte, "The Nestor library: a tool for implementing Fortran source to source transformations", High Performance Computing and Networking (HPCN), 1999. (HPCN1999), BibTeX reference.

• Georges-André Silber, Vivien, "Nestor : un système de parallélisation automatique", RenPar' 10 : dixièmes rencontres francophones du parallélisme, juin 1998. (Renpar10), BibTeX reference.

Research reports

• Alain Darte, Georges-André Silber and Frédéric Vivien, "Combining retiming and scheduling techniques for loop parallelization and loop tiling", Research report 1996-34.

• Pierre Boulet, Alain Darte, Georges-André Silber and Frédéric Vivien, "Loop parallelization algorithms: from parallelism extraction to code generation", Research report 1997-17.

• Georges-André Silber and Alain Darte, "The Nestor library: a tool for implementing Fortran source to source transformations", Research report 1998-42.

Technical reports

• Georges-André Silber, "A programmer's guide for Nestor. Version 1.", Technical report 1998-04.

Combining retiming and scheduling techniques for loop parallelization and loop tiling.

• By: Alain Darte , Georges-Andre Silber , Frederic Vivien
• Number: RR1996-34
• Date: November 1996
• Abstract:

  Tiling is a technique used for exploiting medium-grain parallelism in nested loops. It relies on a first step that detects sets of permutable nested loops. All algorithms developed so far consider the statements of the loop body as a single block, in other words, they are not able to take advantage of the structure of dependences between different statements. In this report, we overcome this limitation by showing how the structure of the reduced dependence graph can be taken into account for detecting more permutable loops. Our method combines graph retiming techniques and graph scheduling techniques. It can be viewed as an extension of Wolf and Lam's algorithm to the case of loops with multiple statements. Loop independent dependences play a particular role in our study, and we show how the way we handle them can be useful for fine-grain loop parallelization as well.

• Abstract (in french):

  ``Loop tiling'' est une technique utilisée pour exploiter du parallélisme à grain moyen dans les boucles imbriquées. Elle repose sur une première étape de détection de boucles permutables. Tous les algorithmes développés jusqu'à maintenant considéraient les instructions du corps du nid de boucles comme un bloc indissociable. En d'autres termes, ils ne pouvaient pas tirer profit de la structure des dépendances entre différentes instructions. Dans ce rapport, nous surmontons cette limitation en montrant comment la structure du graphe de dépendance réduit peut être prise en compte pour détecter plus de boucles permutables. Notre méthode combine des techniques de synchronisation et d'ordonnancement de graphes. Elle peut être vue comme une extension de l'algorithme de Wolf et Lam au cas de boucles comportant plusieurs instructions. Les dépendances qui ne sont pas portées par une boucle (loop independent dependences) jouent un rôle particulier dans notre étude et nous montrons comment la façon particulière dont nous les traitons peut être utile également pour la parallélisation à grain fin.

• Keywords:

  Automatic parallelization, nested loops, permutable loops, tiling, medium grain.

• Keywords (in french):

  Parallélisation automatique, nids de boucles, boucles permutables, tiling, grain moyen.

• Availability: Electronic copy only.
• Citation: Published in Parallel Processing Letters, volume 7(4) (BibTeX reference).
• Size: 2+11p
• Format: Compressed PostScript
• Get it
• BibTeX reference.

Loop parallelization algorithms: from parallelism extraction to code generation.

• By: Pierre Boulet , Alain Darte , Georges-Andre Silber , Frederic Vivien
• Number: RR1997-17
• Date: June 1997
• Abstract:

  In this paper, we survey loop parallelization algorithms, analyzing the dependence representations they use, the loop transformations they generate, the code generation schemes they require, and their ability to incorporate various optimizing criteria such as maximal parallelism detection, detection of permutable loops , minimization of synchronizations, easiness of code generation, etc. We complete the discussion by presenting new results related to code generation and loop fusion for a particular class of multi-dimensional schedules, called shifted linear schedules. We demonstrate that algorithms based on such schedules, while generally considered as too complex, can indeed lead to simple codes.

• Abstract (in french):

  Dans ce rapport, nous présentons divers algorithmes de parallélisation, en prenant en compte la représentation des dépendances qu'ils utilisent, les transformations de boucle qu'ils génèrent, les techniques de génération de code dont ils ont besoin, et enfin, leur capacité à incorporer divers critères d'optimisation tels que la détection du parallélisme maximal, la détection de boucles permutables, la minimisation des synchronisations, la simplicité de la génération de code, etc... Nous complétons notre discussion par la présentation de nouveaux résultats liés à la génération de code et à la fusion de boucles pour une classe particulière d'ordonnancements multi-dimensionnels appelés ordonnancements linéaires décalés. Nous montrons que des algorithmes qui se fondent sur de tels ordonnancements, souvent considérés comme trop complexes, peuvent néanmoins générer des codes simples.

• Keywords:

  Automatic Parallelization, Nested Loops, Parallelization Algorithms, Loop Fusion, Synchronizations, Code Generation.

• Keywords (in french):

  Parallélisation automatique, Boucles imbriquées, Algorithmes de parallélisation, Fusion de boucles, Synchronisations, Génération de code.

• Availability: Paper copy available.
• Citation: Published in Journal of Parallel Computing, volume 24(3) (BibTeX reference).
• Size: 2+30p
• Format: Compressed PostScript
• Get it
• BibTeX reference.

The Nestor library: a tool for implementing Fortran source to source transformations.

• By: Georges-Andre Silber , Alain Darte
• Number: RR1998-42
• Date: September 1998
• Abstract:

  We describe Nestor, a library to easily manipulate Fortran programs through a high level internal representation based on C++ classes. Nestor is a research tool that can be used to quickly implement source to source transformations. The input of the library is Fortran 77, Fortran 90, and HPF 2.0. Its current output supports the same languages plus some dialects such as Petit, OpenMP, CrayMP. Compared to SUIF 2.0 that is still announced, Nestor is less ambitious, but is light, ready to use, fully documented and is better suited for Fortran to Fortran transformations.

• Abstract (in french):

  Dans ce rapport, nous décrivons Nestor, une bibliothèque pour manipuler facilement des programme Fortran à l'aide d'une représentation interne de haut niveau qui se fonde sur des classes C++. Nestor est un outil de recherche qui peut être utilisé pour implanter rapidement des transformation source à source. Les langages reconnus par la librairie sont Fortran 77, Fortran 90 et HPF 2.0. Les langages disponibles en sortie sont les précédents plus des dialectes de Fortran comme Petit, OpenMP, CrayMP, etc. Comparé à SUIF 2.0 qui est toujours annoncé, Nestor est moins ambitieux, mais il est léger, prêt à être utilisé et complètement documenté. De plus, Nestor est mieux adapté aux transformations source à source de Fortran.

• Keywords:

  Library, Program Transformations, HPF, Parallelization, Object Oriented.

• Keywords (in french):

  Bibliothèque, Transformation de Programmes, HPF, Parallélisation, Orienté Objet.

• Availability: Electronic copy only.
• Citation: Not published yet.
• Size: 2+19p
• Format: Compressed PostScript
• Get it
• BibTeX reference.
• Landscape slides, Portrait slides.

A programmer's guide for Nestor. Version 1.

• By: Georges-Andre Silber
• Number: TR1998-04
• Date: October 1998
• Abstract:

  This is a programmer's guide for Nestor, a library to easily manipulate Fortran programs through a high level internal representation based on C++ classes. Nestor is a research tool that can be used to quickly implement source to source transformations. The input of the library is Fortran 77, Fortran 90, and HPF 2.0. Its current output supports the same languages plus some dialects such as Petit, OpenMP, CrayMP. Nestor is light, ready to use (Nestor), fully documented and is well suited for Fortran to Fortran transformations.

• Abstract (in french):

  Ce rapport est un guide du programmeur pour Nestor, une bibliothèque pour manipuler facilement des programme Fortran à l'aide d'une représentation interne de haut niveau qui se fonde sur des classes C++. Nestor est un outil de recherche qui peut être utilisé pour implanter rapidement des transformation source à source. Les langages reconnus par la librairie sont Fortran 77, Fortran 90 et HPF 2.0. Les langages disponibles en sortie sont les précédents plus des dialectes de Fortran comme Petit, OpenMP, CrayMP, etc. Nestor est léger, prêt à être utilisé (Nestor) et complètement documenté. De plus, Nestor est bien adapté aux transformations source à source de Fortran.

• Keywords:

  Library, Program Transformations, HPF, Parallelization, Object Oriented.

• Keywords (in french):

  Bibliothèque, Transformation de Programmes, HPF, Parallélisation, Orienté Objet.

• Availability: Electronic copy only.
• Citation: Not published yet.
• Size: 2+117p
• Format: Compressed PostScript
• Get it
• BibTeX reference.