Analyse et optimisation de codes

Optimisation de codes irréguliers : application à la bio-informatique et à la cryptographie

Dans le panorama des codes irréguliers qui est très vaste, nous nous sommes intéressés à deux problèmes particuliers : l’optimisation des boucles à faible nombre d’itérations, et l’optimisation des structures de branchement complexes (switch). Ces deux types de structure apparaissent fréquemment dans nombre de code « irréguliers » notamment en bio informatique et en cryptographie. Dans les deux cas, les techniques d’optimisation classique sont peu efficaces et nous avons du développer des techniques d’optimisation spécifiques. Nous avons appliqué ces techniques sur deux codes de bio informatique (NR GREP, ABNDM) et à un code de cryptographie (attaque de SHA-0), les gains obtenus étant substantiels (entre 20 et 50%). Sur le code d’attaque de SHA-0 (développé par A. Joux), ces améliorations de performance ont permis de réaliser calculer une collision pour SHA-0, en 80 000 Heures CPU, ce qui est une première mondiale.

Responsable de l'action : William Jalby

Corrélation et minimisation conjointe de temps d’exécution et de taille de code

L’optimisation du temps de calcul d’un côté et de la taille du code de l’autre sont des objectifs largement explorés dans la littérature. Il existe des tentatives qui essayent de combiner l’optimisation du temps de calcul (ordonnancement d’instructions) avec celui de la taille de code. Souvent, ces tentatives parlent de « compromis » : optimiser le temps de calcul augmenterait la taille du code ou inversement. Mais, ces affirmations n’ont pas encore de fondements, et elles ne résultent que de constatations expérimentales ad-hoc. La théorie de l’information ne sait pas à ce jour corréler la taille d’un programme à ses performances, ou, plus précisément, corréler un ordonnancement d’instructions à la taille du code généré. Sans aller jusqu’à essayer de « quantifier » mathématiquement une telle corrélation, la communauté ne sait pas encore comment « qualifier » une telle relation entre l’ordonnancement et la taille du code. Citons cependant les travaux de M. Touati et Mme Eisenbeis qui ont apporté une réponse précise dans le cas d’une boucle simple ordonnancée périodiquement avec la technique du pipeline logiciel. Dans ce cas bien précis (nous n’en connaissons pas d’autre à ce jour), il est possible de quantifier en une seule relation mathématique trois objectifs d’optimisation de codes embarqués : taille de codes, performances, taille de données (registres). En d’autres termes, il a été prouvé qu’il était tout à fait possible d’optimiser le temps d’exécution d’une boucle d’un programme en même temps que sa surface (taille de code + registres) sans avoir à effectuer un compromis performance/espace non nécessaire. Dans certains cas, générer des boucles très compactes avec des performances maximisées ne semble donc pas être des objectifs antagonistes. Ceci nourrit notre optimisme quant à la capacité d’une recherche fondamentale à répondre à des questions plus difficiles, à savoir comment corréler les performances d’un ordonnancement d’instructions en général (cas plus compliqué qu’une simple boucle) à la taille du code engendré.

Responsable de l'action : S. Touati

Ordonnancement d’instructions avec effets de caches

L’objectif de cette action de recherche est de proposer des méthodes d’ordonnancements d'instructions tolérants aux effets des caches de données dans un système embarqué. En d’autres termes, mettre en œuvre des méthodes pour rendre les temps d’exécution des programmes moins sensibles aux effets des caches. Ainsi, le temps d’exécution d’un programme embarqué serait accéléré grâce à la présence d’un ou plusieurs caches, mais les variations des temps des différentes exécutions seraient limitées. Une telle solution logicielle par compilation permettrait la présence des caches dans les systèmes embarqués avec plus de sécurité (dans le cas de traitement temps réels mous). 

Responsable de l'action : S. Touati

Génération de codes optimisés pour les librairies de calcul scientifiques

Un premier axe de recherche a été centré sur l’exécution parallèle des opérations mémoire (load, store) dans le cas de plusieurs processeurs hautes performances (Alpha, Itanium2, Power4). Nous avons montré que malgré le caractère parallèle de ces requêtes mémoires, les processeurs actuels ne les exécutent pas réellement en parallèle, sauf si le flot des adresses mémoires accédées possèdent des propriétés précises de régularité. Nos techniques de microbenchmarking ont permis d’évaluer précisément le phénomène et surtout de dériver une technique efficace d’ordonnancement des requêtes mémoires (vectorisation), au prix d’une consommation accrue du nombre de registres.
Nous avons étendu ces résultats de manière plus systématique à l’optimisation des boucles vectorielles : les techniques de microbenchmarking systématique permettent de générer les « bonnes » règles d’optimisation, ensuite une base de noyaux élémentaires est optimisée en utilisant ces règles et des techniques de génération multiversion pour assurer la robustesse des performances, enfin, les boucles vectorielles générales sont décomposées en noyaux élémentaires et le code correspondant est produit. Nous avons appliqué cette technique à des bibliothèques scientifiques (BLAS), pour lesquelles nous avons obtenu des codes nettement plus efficaces que ceux générés par les compilateurs natifs et très  compétitifs par rapport aux librairies constructeurs optimisées manuellement.

L’ensemble de la chaîne d’optimisation a fait l’objet d’un dépôt de brevet (janvier 2004) conjoint entre le PRiSM, CEA DAM et CAPS-Entreprise qui exploite industriellement les résultats de ce brevet.

Responsable de l'action: William Jalby

Reconnaissance d'algorithmes

La reconnaissance d'algorithmes consiste en la recherche, dans un programme séquentiel, de portions de code implémentant des algorithmes classiques, généralement issus de l'algèbre linéaire. L'intérêt de cette recherche vient de la complexité croissante des processeurs modernes, qui rend très difficile l'optimisation automatique. La compilation adaptative ne permet en effet pour l'instant qu'une optimisation efficace de codes de bibliothèques. En revanche l'utilisation des bibliothèques optimisées, produites par compilation adaptative [Atlas, FFTW] ou bien fournies par des constructeurs [bibliothèques Intel]  est encore du ressort du programmeur. Nous proposons d'utiliser la reconnaissance d'algorithmes pour transférer cette tâche au compilateur. L'objectif est, outre d'optimiser le code, de gagner en portabilité, et de gagner en temps de développement, d'autant plus que les bibliothèques sont importantes. 
La principale difficulté est d'allier des algorithmes de complexité élevée avec des applications de taille réelle. Le cœur de la méthode est un semi-algorithme qui montre si un programme est une instance d'un template, avec les instanciations possibles. Cette méthode est une extension des travaux faits en collaboration avec X.Redon et P.Feautrier. Afin de choisir les portions de code intéressantes dans un programme, nous avons proposé une méthode rapide de localisation des codes susceptibles de correspondre à des codes de bibliothèques. La localisation s'appuie sur une analyse SSA du programme (peu coûteuse), et la méthode d'équivalence sur une représentation sous forme de système d'équations récurrentes affines. Les deux méthodes ont été implémentées et testées en prenant le compilateur LLVM (université d'Urbana Champaign) comme front-end. 
La méthode de localisation trouve de nombreuses portions de codes,  la plupart ne correspondant pas à des appels de bibliothèques et qui sont écartés par la méthode trouvant les instanciations. En revanche, aucun code qui pourrait être remplacé par un appel à une bibliothèque n'est oublié. La puissance de l'approche dépend principalement de son aptitude à reconnaître les variations entre deux codes équivalents. Des codes équivalents sémantiquement peuvent différer par leurs variables (scalaires, tableaux, nombre de temporaires), les espaces d'itérations (fusion, fission, skewing, unroll ou autre manipulations affines). Ces variations sont supportées par notre approche, ainsi que quelques variations d'ordre sémantique (distributivité, ou associativité, ou multiplication par 0, 1). 
 Le gain de performance obtenu par l'application de cette méthode de reconnaissance d'algorithme reste encore à mesurer, et dépendra évidemment et du code, et du gain de performance de la bibliothèque considérée. Dans le cadre de l'ACI ALGO, les codes de calcul du satellite Gaia sont optimisés par cette approche, avec d'une part les bibliothèques Altivec pour Powerpc, d'autre part d'autres bibliothèques de calcul de traitement du signal.

 

Responsable de l'action: Denis Barthou

Génération dynamique de code pour applications multimédia

La génération de code est statique quand le code binaire d'une application est généré au moment de la compilation. Elle peut être dynamique quand le code binaire est généré lors du chargement de l'application en mémoire, comme dans les JIT (Just In Time Compiler) par exemple.
Nous avons conçu un système de génération de code au moment de l'exécution d'une procédure (les compilettes). Cela permet de prendre en compte les valeurs des paramètres de la procédure et de les utiliser pour faire de l'évaluation partielle et générer un code très efficace. Cela permet aussi d'utiliser des instructions machines que les compilateurs n'arrivent pas a utiliser.
Les mécanismes mis en oeuvre sont très rapides et permettent une utilisation de cette technique dans des codes nécessitant de hautes performances. 
Nous avons expérimenté cette technique sur des applications multimédia et obtenu des accélérations de l'ordre de 40%.

Responsable de l'action : H-P. Charles

Optimisation du calcul d’adresse dans les codes DSP

Nous avons initié un sujet de recherche conjoint entre les participants ci-dessus. Le problème est de générer des codes de traitement de signal (DSP) ayant un nombre minimal de calcul d’adresse. Dans les processeurs DSP, le calcul d’adresse s’effectue exclusivement par initialisation et incrémentation (le mode d’adressage est très limité). Par conséquent, le placement des variables en mémoire influe directement sur le nombre d’instructions entières. Ce problème a été largement traité dans la littérature dans le cas d’un registre unique. Nous souhaitons généraliser ces études vers un nombre arbitraire de registres. Le problème fondamental n’est pas le même. Bien que nous ayions prouvé que notre problème est NP-complet, nous sommes en train de tester expérimentalement des heuristiques.

Responsable de l'action : S. Touati

Microbenchmarking des processeurs à hautes performances

Nos travaux de recherche sont essentiellement concentrés sur l’évaluation et l’analyse expérimentale des performances pour des applications de type calcul scientifique.   
De manière systématique, notre approche des problèmes comporte trois phases: tout d'abord, nous analysons qualitativement et quantitativement les interactions matériel/logiciel puis à partir de cette analyse nous développons de nouveaux mécanismes matériels ou logiciels et enfin nous étudions l'intérêt des mécanismes  proposés. L'ensemble de ces trois phases requiert un effort expérimental élevé: utilisation intensive de simulateurs, analyse de données, mesures sur des systèmes réels.
La latence d'accès à la mémoire (typiquement entre 100 et 200 cycles CPU) est un problème majeur de tous les processeurs modernes: il s'agit essentiellement d'assurer que durant ces 100 à 200 cycles le processeur ne reste pas inactif en attente de données. Plusieurs mécanismes sont couramment employés pour pallier ce problème: exécution dans le désordre,  mécanisme de préchargement (par exemple, explicite via des instructions spécifiques ou implicite). Malheureusement en pratique, l'efficacité de ces mécanismes est loin d'être garantie: ainsi l'exécution dans le désordre (complètement dynamique) ne permet pas d’assurer que les accès les plus critiques seront traites en priorité. Pour les instructions de préchargement, les difficultés portent essentiellement sur leur génération (choix des tableaux à précharger, position des instructions dans le code) et paramétrage (type de préchargement, distance de préchargement). 
Ceci nous a amené à développer une méthodologie de benchmarking spécifique de bas niveau pour analyser les performances mémoires (uni et multiprocesseurs). L’objectif de ce benchmarking est d’abord de détecter les « bugs » de performance (i.e. pertes de performance inattendues) puis d’en dériver des techniques d’optimisation assurant des niveaux de performance élevés et robustes (insensibles aux variations des différents paramètres tels qu’alignement des données en mémoire). Cette méthodologie a été initialement développée, dans le cadre d’un contrat avec le CEA DAM pour les processeurs Alpha et Power puis ensuite étendu aux processeurs ITANIUM2 et Sparc/HAL.. Cette technique de microbenchmarking nous a permis d’analyser les différentes faiblesses des mécanismes d’accès aux caches et de proposer des techniques efficaces de génération de code.
Les travaux décrits ci dessus sur les systèmes mémoires ont été étendus pour couvrir le cas des enchaînements d’opérations arithmétiques avec un accent particulier sur les mécanismes de branchement.

Responsable de l'action : William Jalby

 Imprimer  E-mail

DMC Firewall is developed by Dean Marshall Consultancy Ltd