DEA - Module ALPA, Étude d'approfondissement : Le Pavage

ALPA comprend une étude indépendante détaillée d'un sujet de recherche contemporain. Vous démarrez de quelques références, puis selon vos motivations irez en chercher d'autres pour vous faire une idée assez claire du domaine de recherche considéré. Une partie de l'examen final sera basé sur cette étude. Vous êtes fortement encouragés à travailler ensemble afin d'échanger vos points de vue avec les autres étudiants et éventuellement avec les enseignants. Il est aussi crucial que vous commenciez cette étude tôt car c'est un travail de longue haleine qui ne pourra être fait au dernier moment.

Le pavage (partitionnement ou "tiling" en anglais) est un partitionnement régulier d'un espace d'index représentant soit des calculs (par exemple, l'espace d'itération d'une boucle imbriquée), soit des données (par exemple, un tableau distribué à travers les processeurs d'une machine parallèle). Originellement présenté dans le papier de F. Irigoin et R. Triolet [6] pour augmenter la granularité des calculs parallèles, le pavage peut être utilisé pour plusieurs choses: exploiter la localité des données dans les machines à hiérarchie de mémoire, optimiser les communications par agrégation de messages, recouvrir les calculs et les communications, réduire la latence, etc. Deux autres papiers décrivant la transformation ont étés proposés par Schreiber et Dongarra [9] et Ramanujam et Sadayappan [8]. Xue [11] propose une bonne synthèse de ces résultats précurseurs et de quelques extensions.

Il y eu des travaux sur le choix des paramètres du pavage (notamment la taille et la forme des tuiles) pour optimiser divers critères plus ou moins réalistes suivant le contexte dans lequel le pavage est réalisé, notamment par Andonov et Rajopadhye [2], Hodzic et Shang [4], Ohta et al [7] (qui est beaucoup cité en dépit d'une erreur dans leur théorème principal), ainsi que Hogstedt et al [5]. Lam et Wolfe [10] et Agarwal et al [1] ont étudié le problème de choix de pavage qui optimise la performance sur des machines à hiérarchie mémoire (caches). En 1998 le workshop Tiling for Optimal Resource Utilization s'est tenu en Allemagne la page correspondante contient des liens vers d'autre références. 

Le travail de l'approfondissement consistera d'abord en la lecture et la maîtrise complète du papier de Xue [11]. Ensuite, vous devrez autant que possible essayer d'étudier un aspect particulier des recherches sur le pavage à travers les articles cités ci-dessus (ou d'autres si nécessaire, bien sur). Des pistes possibles sont indiquées plus tard. Cette étude sert de contrôle continu, vous rendrez un résumé succinct de vos lectures (2-3 pages maximum, nous précisons que ce rapport ne doit pas être écrit à la main mais produit par un des outils de bureautique mis à votre disposition). Il sera à rendre la dernière semaine de cours (vendredi 10 décembre, 17h00, dernier délai). De plus, lors de l'examen final, une question portera sur le sujet.

Quelques "règles de jeu"

Quelques pistes potentielles

Après avoir lu le papier de Xue [11], vous pouvez aller dans plusieurs différentes directions. Voici quelques possibilités.
  1. Une étude historique : étudier les papiers qui le précèdent (eg. [6] [8] et [9], mais il se peut que tous les travaux précédents ne sont pas cités) et suivre les développements : comment les auteurs ont progressés, quelles étaient les difficultés, est-ce que certains résultats étaient obtenus, indépendamment, ou progressivement, etc.
  2. Une étude sur la sélection des paramètres de pavage. Plusieurs auteurs ont travaillé sur se sujet, souvent avec des différents (i) hypothèses sur la nature des programmes traités, des machines, etc., (ii) mesures de qualité (fonctions de coût) et (iii) techniques d'optimisation. Vous pouvez étudier de près l'un de ces approches et faire la synthèse sur ces avantages et désavantages. Une liste non-exhaustive des possibilités est
    1. [8] et [4]
    2. [5] et [3]
    3. [2] et [7]
  3. Au départ, les travaux sur le pavage étaient faites dans le contexte des machines parallèles (et de la parallélisation des boucles). Un paramètre qui devient de plus en plus important est la latence de mémoire. Alors, une autre piste est de étudier comment les méthodes ont été étendus pour modéliser les mémoires et traiter la localité, comme font [1] et [10].

Bibliographie pour l'étude d'approfondissement:

[1] Agarwal, Kranz et Natarajan  Automatic Partitionning of Parallel Loops and Data Arrays for Distributed Shared Memory Multi-processors dans IEEE trans. Parallel and Distributed Systems, vol 6, no 9, sept 95, pp 943-962.

[2] Andonov et Rajopadhye, Optimal Orthogonal Tiling of 2-D Iterations dans Journal of Parallel and Distributed Computing, septembre 1997 (pages 159-165).

[3] Desprez, Dongarra, Rastello et Robert, Determining the Idle Time of a Tiling à paraître dans Journal of Information Science and Engineering (Special Issue on Compiler Techniques for High-Performance Computing) 1998.

[4] Hodzic et Shang, On Supernode Transformation with Minimized Total Running Time dans IEEE Transactions on Parallel and Distributed Systems, mai 1998 (pages 417-428).

[5] Hogstedt, Carter et Ferrante, Determining the Idle Time of a Tiling dans 1997 ACM Symposium on the Principles of Programming Languages, janvier 1997.

[6] Irigoin et Triolet, Supernode Partitioning dans 15th ACM Symposium on Principles of Programming Languages, janvier 1988, (pages 319-328).

[7] Ohta, Saito, Kainaga et Ono, Optimal Tile Size Adjsutment in Compiling General DOACROSS Loop Nests dans ACM International Conference on Supercomputing juillet 1995 (pages 270-279).

[8] Ramanujam et Sadayappan, Tiling Multidimensional Iteration Spaces for Multicomputers dans Journal of Parallel and Distributed Computing, volume 16, numero 2, 1992 (pages 108-120).

[9] Schreiber et Dongarra, Automatic Blocking of Nested Loops Technical Report No. 90.38 RIACS, NASA Ames Research Center, août 1990.

[10] Wolf et Lam,  A Data Locality Optimizing Algorithm dans ACM Sigplan 91 Conference on Programming Languages Design and Implementation (PLDI 91), juin 1991 pp 30-44.

[11] Xue, On Tiling as a Loop Transformation dans Parallel Processing Letters, volume 7, numero 4, octobre (?) 1997 (pages 490-424).