High-Performance Computing and Quantum Mechanics : Analysis of Time and Memory Efficient Algorithms.
Calcul Haute-Performance et Mécanique Quantique : analyse des ordonnancements en temps et en mémoire
Résumé
This work shows the importance of scheduling for the programming of high performance numerical applications of quantum physics and chemistry. We focus on two methods for the Schrödinger equation : the Quantum Box (QB) and the order two Moeller-Plesset (MP2) perturbation algorithm. Both require very large amounts of computing time and memory. The traditional programming (message passing and/or multithreading) of parallel architectures (distributed or SMP) is illustrated through the performances obtained with the Linpack benchmark on the I-Cluster machine of INRIA. The lack of portability of the high-performance code obtained shows the need for an environment for parallel programming that allows the disconnecting of algorithm coding from its scheduling on the target machine. We then introduce Athapascan, that relies on the analysis of the data flow to dynamically compute some schedules of proven efficiency. For the execution time on some machine models, both theory and experiments show that Athapascan provides some schedules that guarantee good performance for algorithms adapted to QB, of iterative nature (Lanczos algorithm). Another aim is to bound the memory required by parallel executions in numerical computing ; this is especially true for MP2. We propose to annotate the Data Flow Graph (DFG) to take the memory into account and allow scheduling that is time and memory efficient. For MP2, whose DFG is statically known, a memory and time efficient scheduling is given.
Ce travail présente l'apport de l'ordonnancement pour la programmation parallèle performante d'applications numériques en mécanique et chimie quantique. Nous prenons deux exemples types de résolution de l'équation de Schrödinger --- Boîte Quantique (BQ) et Méthode des Perturbations d'ordre 2 (MP2) --- qui nécessitent de grosses ressources en calcul et mémoire. La programmation traditionnelle (échange de messages et/ou multithreading) des machines parallèles (distribuées ou SMP) est illustrée par les performances obtenues avec le benchmark Linpack sur la grappe I-cluster (INRIA). Le manque de portabilité du code hautement performant obtenu montre l'importance d'un environnement de programmation parallèle permettant de découpler le codage de l'algorithme de son ordonnancement sur la machine cible. Nous introduisons alors Athapascan, qui repose sur l'analyse du flot de données, pour calculer dynamiquement des ordonnancements prouvés efficaces. Un premier critère d'efficacité est le temps de calcul. Sur certains modèles de machines, la théorie et l'expérience montrent que Athapascan permet des ordonnancements qui garantissent des exécutions efficaces pour certains algorithmes adaptés à BQ, de type itératif (méthode de Lanczos). Un deuxième critère fondamental est l'espace mémoire requis pour les exécutions parallèles en calcul numérique ; c'est particulièrement critique pour MP2. Nous proposons d'annoter le Graphe de Flot de Données (GFD) manipulé par Athapascan pour prendre en compte la mémoire et permettre des ordonnancements dynamiques efficaces en mémoire. Pour MP2, dont le GFD est connu statiquement, un ordonnancement efficace en temps et en mémoire est donné.