L'objectif de cette thèse est l'étude d'un environnement d'exécution pour machines parallèles sans mémoire commune. Elle comprend la définition d'un modèle de programme parallèle, basé sur l'échange de message offrant une forme restreinte de mémoire partagée. La communication est indirecte, via des portes; les processus utilisent les barrières pour la synchronisation. Les entités du système. processus, portes et barrières, sont créées dynamiquement, et placées sur un processeur quelconque du réseau de processeurs de façon explicite. Nous proposons une implantation de ce modèle comme la mise en oeuvre systématique d'une architecture client/serveur. Cette implantation a été efféctuée sur une machine Supemode. La base est un Micro Noyau Parallèle, où le composant principal est un mécanisme d'appel de procédure à distance minimal. / This thesis describes an execution environment for parallel machines without shared memory. A parallel programming model based on message passing, with a special shared memory. In this model, process communication occurs indirectly, via ports, and the processes use barriers for synchronization. All the entities of the system, such as processes, ports and barriers, are created dynamically and loaded on any processor of the network of processors. The implementation architecture of our model is a systematic realization of the client/server model. An implementation is proposed in a Supernode parallel machine as a parallel micro kernel. The principal parallel micro kernel component is a minimal remote procedure call mechanism.

L'objectif de cette thèse est l'étude d'un environnement d'exécution pour machines parallèles sans mémoire commune. Elle comprend la définition d'un modèle de programme parallèle, basé sur l'échange de message offrant une forme restreinte de mémoire partagée. La communication est indirecte, via des portes; les processus utilisent les barrières pour la synchronisation. Les entités du système. processus, portes et barrières, sont créées dynamiquement, et placées sur un processeur quelconque du réseau de processeurs de façon explicite. Nous proposons une implantation de ce modèle comme la mise en oeuvre systématique d'une architecture client/serveur. Cette implantation a été efféctuée sur une machine Supemode. La base est un Micro Noyau Parallèle, où le composant principal est un mécanisme d'appel de procédure à distance minimal. / This thesis describes an execution environment for parallel machines without shared memory. A parallel programming model based on message passing, with a special shared memory. In this model, process communication occurs indirectly, via ports, and the processes use barriers for synchronization. All the entities of the system, such as processes, ports and barriers, are created dynamically and loaded on any processor of the network of processors. The implementation architecture of our model is a systematic realization of the client/server model. An implementation is proposed in a Supernode parallel machine as a parallel micro kernel. The principal parallel micro kernel component is a minimal remote procedure call mechanism.

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2014-11-25T13:07:50Z No. of bitstreams: 2 Dissertação - Jorge Peixoto de Morais Neto - 2014.pdf: 1582808 bytes, checksum: 3115f942e2c8a9cf83601835af3af1c5 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2014-11-25T14:42:09Z (GMT) No. of bitstreams: 2 Dissertação - Jorge Peixoto de Morais Neto - 2014.pdf: 1582808 bytes, checksum: 3115f942e2c8a9cf83601835af3af1c5 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2014-11-25T14:42:09Z (GMT). No. of bitstreams: 2 Dissertação - Jorge Peixoto de Morais Neto - 2014.pdf: 1582808 bytes, checksum: 3115f942e2c8a9cf83601835af3af1c5 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2014-01-29 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / Let M be a metric space and let P be a subset of M. The well known k-nearest neighbors problem (KNN) consists in finding, given q 2 M, the k elements of P with are closest to q according to the metric of M. We discuss a variation of KNN for a particular class of pseudo-metric spaces, described as follows. Let m 2 N be a natural number and let d be the Euclidean distance in Rm. Given p 2 Rm: p := (p1; : : : ; pm) let C (p) be the set of the m rotations of p’s coordinates: C (p) := f(p1; : : : ; pm); (p2; : : : ; pm; p1); : : : ; (pm; p1; : : : ; pm􀀀1)g we define the special distance de as: de(p;q) := min p02C (p) d(p0;q): de is a pseudo-metric, and (Rm;de) is a pseudo-metric space. The class of pseudo-metric spaces under discussion is f(Rm;de) j m 2 N:g The brute force approach is too costly for instances of practical size. We present a more efficient solution employing parallelism, the FFT (fast Fourier transform) and the fast elimination of unfavorable training vectors.We describe a program—named CyclicKNN —which implements this solution.We report the speedup of this program over serial brute force search, processing reference datasets. / Seja M um espaço métrico e P um subconjunto de M. O conhecido problema k vizinhos mais próximos (k-neareast neighbors, KNN) consiste em encontrar, dado q 2 M, os k elementos de P mais próximos de q conforme a métrica de M. Abordamos uma variação do problema KNN para uma classe particular de espaços pseudo-métricos, descrita a seguir. Seja m 2 N um natural e seja d a distância euclidiana em Rm. Dado um vetor p 2 Rm: p := (p1; : : : ; pm) seja C (p) o conjunto das m rotações das coordenadas de p: C (p) := f(p1; : : : ; pm); (p2; : : : ; pm; p1); : : : ; (pm; p1; : : : ; pm􀀀1)g definimos a distância especial de como: de(p;q) := min p02C (p) d(p0;q): de é uma pseudo-métrica, e (Rm;de) é um espaço pseudo-métrico. A classe de espaços pseudo-métricos abordada é (Rm;de) j m 2 N: A solução por força bruta é cara demais para instâncias de tamanho prático. Nós apresentamos uma solução mais eficiente empregando paralelismo, a FFT (transformada rápida de Fourier) e a eliminação rápida de vetores de treinamento desfavoráveis. Desenvolvemos um programa—chamado CyclicKNN—que implementa essa solução. Reportamos o speedup desse programa em comparação com a força bruta sequencial, processando bases de dados de referência.

Les machines pétascale qui existent aujourd'hui ont un temps moyen entre pannes de plusieurs heures. Il est prévu que dans les futurs systèmes ce temps diminuera. Pour cette raison, les applications qui fonctionneront sur ces systèmes doivent être capables de tolérer des défaillances fréquentes. Aujourd'hui, le moyen le plus commun de le faire est d'utiliser le mécanisme de retour arrière global où l'application fait des sauvegardes périodiques à partir d’un point de reprise. Si un processus s'arrête à cause d'une défaillance, tous les processus reviennent en arrière et se relancent à partir du dernier point de reprise. Cependant, cette solution deviendra infaisable à grande échelle en raison des coûts de l'énergie et de l'utilisation inefficace des ressources. Dans le contexte des applications MPI, les protocoles de journalisation des messages offrent un meilleur confinement des défaillances car ils ne demandent que le redémarrage du processus qui a échoué, ou parfois d’un groupe de processus limité. Par contre, les protocoles existants ont souvent un surcoût important en l’absence de défaillances qui empêchent leur utilisation à grande échelle. Ce surcoût provient de la nécessité de sauvegarder de façon fiable tous les événements non-déterministes afin de pouvoir correctement restaurer l'état du processus en cas de défaillance. Ensuite, comme les journaux de messages sont généralement stockés dans la mémoire volatile, la journalisation risque de nécessiter une large utilisation de la mémoire. Une autre tendance importante dans le domaine des HPC est le passage des applications MPI simples aux nouveaux modèles de programmation hybrides tels que MPI + threads ou MPI + tâches en réponse au nombre croissant de cœurs par noeud. Cela offre l’opportunité de gérer les défaillances au niveau du thread / de la tâche contrairement à l'approche conventionnelle qui traite les défaillances au niveau du processus. Par conséquent, le travail de cette thèse se compose de trois parties. Tout d'abord, nous présentons un protocole de journalisation hiérarchique pour atténuer une défaillance de processus. Le protocole s'appelle Scalable Pattern-Based Checkpointing et il exploite un nouveau modèle déterministe appelé channel-determinism ainsi qu’une nouvelle relation always-happens-before utilisée pour mettre partiellement en ordre les événements de l'application. Le protocole est évolutif, son surcoût pendant l'exécution sans défaillance est limité, il n'exige l'enregistrement d'aucun évènement et, enfin, il a une reprise entièrement distribuée. Deuxièmement, afin de résoudre le problème de la limitation de la mémoire sur les nœuds de calcul, nous proposons d'utiliser des ressources dédiées supplémentaires, appelées logger nodes. Tous les messages qui ne rentrent pas dans la mémoire du nœud de calcul sont envoyés aux logger nodes et sauvegardés dans leur mémoire. À travers de nos expériences nous montrons que cette approche est réalisable et, associée avec un protocole de journalisation hiérarchique comme le SPBC, les logger nodes peuvent être une solution ultime au problème de mémoire limitée sur les nœuds de calcul. Troisièmement, nous présentons un protocole de tolérance aux défaillances pour des applications hybrides qui adoptent le modèle de programmation MPI + tâches. Ce protocole s'utilise pour tolérer des erreurs détectées non corrigées qui se produisent lors de l'exécution d'une tâche. Normalement, une telle erreur provoque une exception du système ce qui provoque un arrêt brutal de l'application. Dans ce cas, l'application doit redémarrer à partir du dernier point de reprise. Nous combinons la sauvegarde des données de la tâche avec une journalisation des messages afin d’aider à la reprise de la tâche qui a subi une défaillance. Ainsi, nous évitons le redémarrage au niveau du processus, plus coûteux. Nous démontrons les avantages de ce protocole avec l'exemple des applications hybrides MPI + OmpSs. / Existing petascale machines have a Mean Time Between Failures (MTBF) in the order of several hours. It is predicted that in the future systems the MTBF will decrease. Therefore, applications that will run on these systems need to be able to tolerate frequent failures. Currently, the most common way to do this is to use global application checkpoint/restart scheme: if some process fails the whole application rolls back the its last checkpointed state and re-executes from that point. This solution will become infeasible at large scale, due to its energy costs and inefficient resource usage. Therefore fine-grained failure containment is a strongly required feature for the fault tolerance techniques that target large-scale executions. In the context of message passing MPI applications, message logging fault tolerance protocols provide good failure containment as they require restart of only one process or, in some cases, a bounded number of processes. However, existing logging protocols experience a number of issues which prevent their usage at large scale. In particular, they tend to have high failure-free overhead because they usually need to store reliably any nondeterministic events happening during the execution of a process in order to correctly restore its state in recovery. Next, as message logs are usually stored in the volatile memory, logging may incur large memory footprint, especially in communication-intensive applications. This is particularly important because the future exascale systems expect to have less memory available per core. Another important trend in HPC is switching from MPI-only applications to hybrid programming models like MPI+threads and MPI+tasks in response to the increasing number of cores per node. This gives opportunities for employing fault tolerance solutions that handle faults on the level of threads/tasks. Such approach has even better failure containment compared to message logging protocols which handle failures on the level of processes. Thus, the work in these dissertation consists of three parts. First, we present a hierarchical log-based fault tolerance solution, called Scalable Pattern-Based Checkpointing (SPBC) for mitigating process fail-stop failures. The protocol leverages a new deterministic model called channel-determinism and a new always-happens-before relation for partial ordering of events in the application. The protocol is scalable, has low overhead in failure-free execution and does not require logging any events, provides perfect failure containment and has a fully distributed recovery. Second, to address the memory limitation problem on compute nodes, we propose to use additional dedicated resources, or logger nodes. All the logs that do not fit in the memory of compute nodes are sent to the logger nodes and kept in their memory. In a series of experiments we show that not only this approach is feasible, but, combined with a hierarchical logging scheme like the SPBC, logger nodes can be an ultimate solution to the problem of memory limitation for logging protocols. Third, we present a log-based fault tolerance protocol for hybrid applications adopting MPI+tasks programming model. The protocol is used to tolerate detected uncorrected errors (DUEs) that happen during execution of a task. Normally, a DUE caused the system to raise an exception which lead to an application crash. Then, the application has to restart from a checkpoint. In the proposed solution, we combine task checkpointing with message logging in order to support task re-execution. Such task-level failure containment can be beneficial in large-scale executions because it avoids the more expensive process-level restart. We demonstrate the advantages of this protocol on the example of hybrid MPI+OmpSs applications.