Haenni's PhD thesis

Architecture EPIC et jeux d'instructions
multimédias pour applications
cryptographiques

Thèse de doctorat

[English]

Auteur : Jacques-Olivier Haenni
Directeur de thèse : Prof. Eduardo Sanchez

Résumé

L'amélioration des performances d'un système, quel qu'il soit, par l'exploitation du parallélisme est une technique appliquée depuis longtemps. Au niveau de l'architecture des processeurs, différents types de parallélisme peuvent être distingués, à savoir le parallélisme de tâches (systèmes multiprocesseurs ou processeurs multitâches), le parallélisme d'instructions (processeurs superscalaires, VLIW ou EPIC) et le parallélisme de données (processeurs vectoriels, instructions multimédias).

A côté du parallélisme d'instructions, présent dans tous les processeurs modernes à hautes performances, la largeur des mots traités a constamment évolué, passant de 4 bits pour le 4004 d'Intel en 1971 à 64 bits actuellement. Cependant, de nombreuses applications sous-exploitent cette capacité de calcul car elles manipulent des valeurs tenant sur 8, 16 ou 32 bits.

Ainsi, afin de mieux répondre aux besoins de certaines applications, les constructeurs de processeurs ont implémenté des instructions dites multimédias, capables de traiter un registre du processeur comme un vecteur de composantes 8, 16, voire 32 bits.

L'utilisation de ces instructions multimédias est toutefois laborieuse, car les compilateurs actuels ne sont pas capables de les exploiter, et le développeur désireux d'en tirer profit se voit contraint d'avoir recours à des bibliothèques de routines prédéfinies ou alors d'écrire du code utilisant explicitement les instructions multimédias, que ce soit par du code assembleur ou par l'appel de pseudo-fonctions (intrinsics).

HP et Intel ont sorti, en 2001, le premier processeur de leur nouvelle architecture 64 bits IPF (initialement nommée IA-64) appelé Itanium. Cette architecture définit des instructions multimédias qui, contrairement aux jeux d'instructions multimédias précédents, sont complètement intégrées au jeu d'instructions de base et ne portent pas de nom particulier.

Notre étude des spécifications d'Itanium a montré que la latence entre une instruction multimédia et une instruction arithmétique ou logique est de 4 ou 12 cycles d'horloge en fonction de la distance, en terme de cycles d'horloge, séparant les instructions. Une telle latence peut faire chuter les performances d'un programme et même un bon ordonnancement des instructions ne peut pas forcément éviter ce problème. La solution proposée est l'éloignement des instructions concernées par l'ajout, à défaut de mieux, d'instructions nops ; nous appelons cette transformation la noptimisation. Nos expériences, tout d'abord sur des prototypes d'Itanium puis sur des circuits commerciaux, ont mis en évidence des gains en performance entre 20% et 60% pour les algorithmes de cryptographie IDEA et RC6 grâce à la noptimisation. Cette dernière a été implémentée dans le compilateur Pro64 de SGI qui constitue actuellement le compilateur du domaine public le plus performant pour Itanium. Cette modification a été soumise à SGI qui l'a intégrée dans la version officielle de Pro64.

Les avantages que peuvent apporter les instructions multimédias aux applications graphiques par exemple sont bien connus, alors que les applications cryptographiques peuvent aussi en bénéficier. Nous avons réalisé des implémentations optimisées des algorithmes IDEA et RC6 en utilisant les instructions multimédias d'IPF et d'Altivec (Motorola PowerPC G4). Ces programmes ont été exécutés sur des machines commerciales après avoir été simulés, dans le cas d'IPF, sur le simulateur fonctionnel ski auquel nous avons eu accès grâce au soutien de HP. Ces travaux ont révélé que l'utilisation des instructions multimédias permet des gains très importants et les débits de cryptage mesurés dépassent ceux des implémentations existantes. Ces travaux montrent également les avantages du jeu d'instructions multimédias Altivec par rapport aux instructions multimédias d'IPF, ainsi que le besoin pour des compilateurs supportant les instructions multimédias.

Actuellement, plusieurs projets de recherche travaillent sur des compilateurs capables d'exploiter les instructions multimédias. Cependant, leur bilan est plutôt mitigé et les faibles résultats obtenus montrent clairement la difficulté du problème.

La voie que ces recherches ont initialement suivie consistait à reprendre les résultats des travaux concernant la compilation pour les machines vectorielles en essayant de paralléliser les boucles d'un programme. Une autre approche, qui possède de nombreux avantages, consiste plutôt à dérouler les boucles, puis à y chercher des instructions qui peuvent être remplacées par une instruction multimédia. Nous justifions cette approche par une simplification de l'analyse des dépendances et par le fait que les machines vectorielles possèdent de nombreuses différences par rapport aux instructions multimédia, parmi lesquelles la taille et l'organisation en mémoire des vecteurs manipulés.

Enfin, nous décrivons les problèmes majeurs posés par la recherche automatique de parallélisme de données et y apportons des solutions ou des pistes à suivre lors de travaux futurs.

Note


Last update: March 21st, 2002
Jacques-Olivier Haenni
E-mail: haenni@mail.com