The goal of the QPACE project is to build a novel cost-efficient massive parallel supercomputer optimized for LQCD (Lattice Quantum Chromodynamics) applications. Unlike previous projects which use custom ASICs, this is accomplished by using the general purpose multi-core CPU PowerXCell 8i processor tightly coupled with a custom network processor implemented on a modern FPGA. The heterogeneous architecture of the PowerXCell 8i processor and its core-independent OS-bypassing access to the custom network hardware and application-oriented 3D torus topology pose interesting challenges for the implementation of the applications. This work will describe and evaluate the implementation possibilities of message passing APIs: the more general MPI, and the more QCD-oriented QMP, and their performance in PPE centric or SPE centric scenarios. These results will then be employed to optimize HPL for the QPACE architecture. Finally, the developed approaches and concepts will be briefly discussed regarding their applicability to heterogeneous node/network architectures as is the case in the "High-speed Network Interface with Collective Operation Support for Cell BE (NICOLL)" project.

Un préconditionneur à deux niveaux, reposant sur la technique d’accélération d’Aitken d’une suite de q vecteurs solutions de l’interface d’un pro- cessus itératif de Schwarz Additif Restreint, est conçu. Cette nouvelle technique, dénomée ARAS(q), utilise une approximation grossière de la solution sur l’interface. Différentes méthodes sont proposées, aboutissant au développement d’une tech- nique d’approximation par Décomposition en Valeures Singulières de la suite de vecteurs. Des implémentations parallèles des méthodes d’Aitken-Schwarz sont pro- posées et l’étude conduit à l’implémentation d’un code totalement algébrique, sur un ou deux niveaux de parallélisation MPI, écrit dans l’environnement de la biblio- thèque PETSc. Cette implémentation pleinement parallèle et algébrique procure un outil flexible pour la résolution de systèmes linéaires tels que ceux issus de la dif- férentiation automatique des solutions de Navier-Stokes dépendant des paramètres de la simulation / A two level preconditioner, based on the Aitken acceleration technique of a sequence of q interface’s solution vectors of the Restricted Additive Schwarz iterative process, is designed. This new technique, called ARAS(q), uses a coarse approximation of the solution on the interface. Different methods are discussed, leading to the development of an approximation technique by Singular Value De- composition of the sequence of vectors. Parallel implementations of Aitken-Schwarz methods are proposed, and the study leads to a fully algebraic one-level and two- level MPI implementation of ARAS(q) written into the PETSc library framework. This fully parallel and algebraic code gives an adaptive tool to solve linear systems such as those arising from automatic differentiation of compressible Navier-Stokes solution with respect to the simulation’s parameters

<p>Methods for performing large-scale parallel Molecular Dynamics(MD) simulations are investigated. A perspective on the field of parallel MD simulations is given. Hardware and software aspects are characterized and the interplay between the two is briefly discussed. </p><p>A method for performing <i>ab initio </i>MD is described; the method essentially recomputes the interaction potential at each time-step. It has been tested on a system of liquid water by comparing results with other simulation methods and experimental results. Different strategies for parallelization are explored.</p><p>Furthermore, data-parallel methods for short-range and long-range interactions on massively parallel platforms are described and compared. </p><p>Next, a method for treating electrostatic interactions in MD simulations is developed. It combines the traditional Ewald summation technique with the nonuniform Fast Fourier transform---ENUF for short. The method scales as <i>N log N</i>, where <i>N </i>is the number of charges in the system. ENUF has a behavior very similar to Ewald summation and can be easily and efficiently implemented in existing simulation programs.</p><p>Finally, an outlook is given and some directions for further developments are suggested.</p>

Ce travail porte sur l'étude des méthodes de décomposition de domaine et leur application pour résoudre des problèmes de contrôle optimal régis par des équations aux dérivées partielles. Le principe de ces méthodes consiste à ramener des problèmes de grande taille sur des géométries complexes en une suite de sous-problèmes de taille plus petite sur des géométries plus simples. En considérant une décomposition sans recouvrement, l'intérêt de ces méthodes pour les problèmes de contrôle optimal réside au niveau de l'intégration de l'équation d'état, puisqu'il est possible de partitionner le problème en une suite de problèmes plus petits, quitte à contraindre les interfaces entre les sous-domaines à obéir à des conditions de raccordement afin de déduire la solution globale à partir des solutions locales. Dans une première partie, nous étudions le cas elliptique. Nous considérons simultanément la minimisation de la fonction coût et des raccordements sur les frontières entre les sous-domaines. Cette combinaison de problèmes de minimisation et de méthodes de décomposition de domaine est traitée par des techniques de Lagrangien augmenté. Nous montrons que, sur le domaine décomposé, le problème initial se réduit à la recherche d'un point-selle. Une étude des méthodes de Lagrangien nous a permis de choisir une variante d'algorithmes existants dans la littérature et de les combiner avec un algorithme de décomposition de domaine. Dans la seconde partie, nous développons l'extension de cette approche aux problèmes de contrôle optimal régis par des systèmes paraboliques en considérant uniquement une décomposition en espace du domaine de calcul. Dans une dernière partie, nous considérons une décomposition de domaine avec recouvrement à chaque pas de la minimisation. D'une part, nous construisons un algorithme parallèle en utilisant la méthode de Schwarz multiplicative en tant que solveur. Ceci permet de déduire naturellement l'état adjoint par transposition des systèmes directs locaux. L'algorithme global défini par la méthode de minimisation de type quasi-Newton et ce solveur de Schwarz constitue une méthode robuste de résolution du problème de contrôle optimal, mais coûteuse. D'autre part, et plus particulièrement, pour des problèmes de grande taille, l'algorithme de type quasi-Newton, combiné avec le solveur de Krylov BiCGSTAB préconditionné par une méthode de Schwarz additive, est plus compétitif dans la mesure oû l'on obtient de bonnes performances parallèles. De nombreux résultats sont présentés pour préciser le comportement des algorithmes d'optimisation quand ils sont utilisés avec des méthodes de Schwarz.

Methods for performing large-scale parallel Molecular Dynamics(MD) simulations are investigated. A perspective on the field of parallel MD simulations is given. Hardware and software aspects are characterized and the interplay between the two is briefly discussed. A method for performing ab initio MD is described; the method essentially recomputes the interaction potential at each time-step. It has been tested on a system of liquid water by comparing results with other simulation methods and experimental results. Different strategies for parallelization are explored. Furthermore, data-parallel methods for short-range and long-range interactions on massively parallel platforms are described and compared. Next, a method for treating electrostatic interactions in MD simulations is developed. It combines the traditional Ewald summation technique with the nonuniform Fast Fourier transform---ENUF for short. The method scales as N log N, where N is the number of charges in the system. ENUF has a behavior very similar to Ewald summation and can be easily and efficiently implemented in existing simulation programs. Finally, an outlook is given and some directions for further developments are suggested.

L'objectif global de ce travail est d'étudier une modélisation multi-échelle et de développer une méthode adaptée pour la simulation numérique du processus d'érosion à l'échelle du bassin versant. Après avoir passé en revue les différents modèles existants, nous dérivons une solution analytique non triviale pour le système couplé modélisant le transport de sédiments par charriage. Ensuite, nous étudions l'hyperbolicité de ce système avec diverses lois de sédimentation proposées dans la littérature. Concernant le schéma numérique, nous présentons le domaine de validité de la méthode de splitting, pour les équations modélisant l'écoulement et celle décrivant l'évolution du fond. Pour la modélisation du transport en suspension à l'échelle de la parcelle, nous présentons un système d'équations couplant les mécanismes d'infiltration, de ruissellement et le transport de plusieurs classes de sédiments. L'implémentation et des tests de validation d'un schéma d'ordre élevé et de volumes finis bien équilibré sont également présentés. Ensuite, nous discutons sur l'application et la calibration du modèle avec des données expérimentales sur dix parcelles 1m2 au Niger. Dans le but d'aboutir la simulation à l'échelle du bassin versant, nous développons une modélisation multi échelle dans laquelle nous intégrons le taux d'inondation dans les équations d'évolution afin de prendre en compte l'effet à petite échelle de la microtopographie. Au niveau numérique, nous étudions deux schémas bien équilibrés : le schéma de Roe basé sur un chemin conservatif, et le schéma avec reconstruction hydrostatique généralisée. Enfin, nous présentons une première application du modèle avec les données expérimentales du bassin versant de Ganspoel qui nécessite la parallélisation du code.

Streptococcus pneumoniae (S. pneumoniae) és un colonitzador habitual del tracte respiratori superior dels humans. Es tracta d’un patogen comú de l’espècie humana que presenta una elevada taxa de morbiditat i mortalitat arreu del món. El bacteri pot causar otitis mitjana, sinusitis o infeccions de tracte respiratori superior, (per contigüitat) però també pot causar malaltia invasiva, quan habita en un territori habitualment estèril, produint pneumònia, bacterièmia, septicèmies i meningitis, entre d’altres. La malaltia pneumocòccica és un important problema de salut pública i és la principal causa individual de mortalitat infantil en el món. Segons dades de la Organització Mundial de la Salut (OMS), s’estima que a l’any 2000 es van produir 14.5 milions d’episodis greus de malaltia pneumocòccica, que va resultar en 826 000 morts en nens menors de dos anys. Un 61% d’aquestes morts es van produir a l’Àfrica subsahariana i al sud-est asiàtic. Tanmateix, en aquests països i, en especial a les zones rurals, les capacitats de diagnòstic són limitades o inexistents i la identificació de l’agent etiològic es basa en signes i símptomes clínics. És molt important aïllar l’agent etiològic causant de malaltia per tal de poder avaluar el millor tractament possible. No obstant, les tècniques actuals per al diagnòstic de la malaltia presenten una limitada sensibilitat i especificitat. El cultiu microbiològic, com a mètode de diagnòstic clàssic, té una baixa sensibilitat per a detectar el pneumococ. L’objectiu d’aquesta tesi és avaluar el potencial de les tècniques moleculars per al diagnòstic i caracterització de la malaltia pneumocòccica i discernir si l’ús de tècniques moleculars com la reacció en cadena de la polimerasa (PCR) poden suposar un avantatge tant per la rapidesa del mètode com per la detecció del patogen present en una mostra a baixa concentració. L’aplicació d’aquest tipus de tècniques en mostres biològiques impregnades en paper de filtre (dried-spot) i conservades a temperatura ambient poden ser un excel•lent sistema per a la detecció i serotipat de S. pneumoniae en països en vies de desenvolupament on la falta de recursos econòmics esdevé una de les principals limitacions. La capacitat del pneumococ de causar malaltia depèn de la presència d’una càpsula polisacàrida que impedeix la fagocitosi. Tot i que la presència de la càpsula és un requisit perquè produeixi malaltia, no és suficient per conferir virulència, sinó que són necessaris una varietat de factors determinants addicionals, com ara les adhesines, les proteases, les toxines, els sistemes de transport i enzims que modifiquen el medi extracel•lular. Recentment, s’ha descobert un determinant de virulència del pneumococ que és la proteïna rica en repeticions de serina, PsrP (Pneumococcal-serine rich protein). Es tracta d’una adhesina que intervé en l’adhesió del pneumococ a les cèl•lules pulmonars. PsrP és un important factor de virulència capaç de causar malaltia i un potencial candidat a una nova vacuna proteica. / Streptococcus pneumoniae (S. pneumoniae) is a common colonizer of the upper respiratory tract of humans. This is a major human pathogen and leading cause of morbidity and mortality worldwide. The bacteria can cause otitis media, sinusitis or upper respiratory tract infections (contiguity) but can also cause invasive disease, when living in an area usually sterile, causing pneumonia, bacteraemia, sepsis and meningitis, among others. According to the World Health Organization, in 2000, pneumococcal disease was estimated to have caused about 14.5 million severe episodes. There were approximately 826 000 deaths from pneumococcal disease in children under five years and 61% of these deaths occurred in sub-Saharan Africa and Southeast Asia. However, in these countries, especially in rural areas, diagnostic capabilities are limited or nonexistent and agent identification is based on clinical signs and symptoms. It is very important to isolate the etiologic agent of disease in order to assess the best treatment possible. However, present techniques for the diagnosis of the disease have a limited sensitivity and specificity. Microbiological culture, considered the “gold-standard” in microbiological diagnosis has low sensitivity to detect pneumococcus. The aim of this Thesis is to evaluate the potential of molecular techniques for diagnosis and characterization of pneumococcal disease and to discern whether the use of molecular techniques such as PCR, can be an advantage both for the speed of method as for the detection of the pathogen present in a sample in low concentration. The application of these techniques in biological samples impregnated filter paper (dried-spot) and kept at room temperature can be an excellent system for the detection and serotyping of S. pneumoniae in developing countries where lack of financial resources is a major constraint. The ability of the pneumococcus to cause disease depends on the presence of a polysaccharide capsule that prevents phagocytosis. Although the presence of the capsule is a requirement to produce disease, is not sufficient to confer virulence, but need a large number of additional factors such as adhesins, proteases, toxins, transportation systems and enzymes that modify the extracellular medium. One recently identified pneumococcal virulence determinant is the pneumococcal serine-rich repeat protein (PsrP). This is an adhesin involved in adherence of pneumococci to lung cells. PsrP is an important virulence factor capable of causing disease and a potential new vaccine candidate protein.

Collective Communication Operations are widely used in MPI applications and play an important role in their performance. Hence, various projects have focused on optimization of collective communications for various kinds of parallel computing environments including LAN settings, heterogeneous networks and most recently Grid systems. The distinguishing factor of Grids from all the other environments is heterogeneity of hosts and network, and dynamically changing resource characteristics including load and availability. The first part of the thesis develops a solution for MPI broadcast (one-to-many) on Grids. Some current strategies take into consideration static information about network topology for determining an efficient broadcast tree for Grids. Some other strategies take into account only transient network characteristics. We combined both these strategies and cluster the network dynamically on the basis of link bandwidths. Given a set of network parameters we use Simulated Annealing (SA) to obtain the best schedule. Also, we can time tune individual. SAs, to adapt the solution finding process, on the basis of estimated available times before next broadcast invocations in the application. We also developed software architecture for updation of schedules. We compared our algorithm with the earlier approaches under loaded network conditions, and obtained average performance improvement of 20%. The second part of the thesis extends the work for MPI all gather (many-to-many) operation. Current popular techniques consider strict hierarchical schemes for this operation, wherein from each cluster a representative (or coordinator) node is chosen, and inter cluster communication is done through these representative nodes. This is non optimal as inter cluster communication is usually on high capacity links that can sustain more than one transfer with the same through- put. We developed a cluster based and incremental heuristic algorithm for allgather on Grids. We compared the time taken by allgather schedules determined by this algorithm with current popular implementations. We also compared our algorithm with a strategy where allgather is constructed from a set of broadcast trees. We obtained average performance improvement of 67% over existing strategies.

L'étude de la qualité numérique est cruciale pour les codes industriels tels que ceux développés à EDF R&D. C'est d'autant plus important dans le contexte actuel où les simulations numériques sont faites sur des architectures pouvant exécuter des milliards d'opérations flottantes par seconde. Des études ont montré que la bibliothèque CADNA est un outil adapté à la validation numérique des codes industriels. Toutefois, CADNA ne peut être utilisée simplement sur des grands codes industriels, ces derniers faisant appel à des bibliothèques externes (MPI, BLACS, BLAS, LAPACK). Il est donc nécessaire de développer des extensions compatibles avec l'outil CADNA. L'implémentation de ces diverses extensions pose un problème de performance, la complexité algorithmique et la taille des logiciels de calcul numérique impliquant d'importants temps d'exécution. A titre d'exemple, l'implémentation directe de CADNA dans la routine de produit matriciel DGEMM des BLAS, introduit un surcoût supérieur à 1000 pour une matrice carrée de taille 1024. Les raisons de ce surcoût sont expliquées dans ce mémoire. Nous présentons également, à travers notre routine DgemmCADNA, la méthodologie pour réduire ce surcoût. Cette routine a permis de réduire ce surcoût d'un facteur 1100 à un facteur 35 par rapport à la version GotoBLAS. Une deuxième partie de notre travail a été consacrée à l'étude de la qualité numérique du code Telemac-2D. Pour valider entièrement le code, nous avons implémenté une extension de CADNA pour le standard MPI. Le débogage numérique à l'aide de CADNA a montré que plus de 30% des instabilités détectées apparaissent dans les produits scalaires. L'utilisation des algorithmes de produit scalaire compensé permet d'améliorer la précision des résultats sans dégrader les performances du code.

In this paper we describe a parallel algorithm for calculating nonequispaced fast Fourier transforms on massively parallel distributed memory architectures. These algorithms are implemented in an open source software library called PNFFT. Furthermore, we derive a parallel fast algorithm for the computation of the Coulomb potentials and forces in a charged particle system, which is based on the parallel nonequispaced fast Fourier transform. To prove the high scalability of our algorithms we provide performance results on a BlueGene/P system using up to 65536 cores.