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.