München, Techn. Universiẗat, Diss., 2000.

Techn. Universiẗat, Diss., 2005--München.

L'objectif de cette these est l'etude d'un environnement d'execution pour machines paralleles sans memoire commune. Elle comprend la definition d'un modele de programme parallele, base sur l'echange de message offrant une forme restreinte de memoire partagee. La communication est indirecte, via des portes; les processus utilisent les barrieres pour la synchronisation. Les entites du systeme, processus, portes et barrieres, sont creees dynamiquement, et placees sur un processeur quelconque du reseau de processeurs de facon explicite. Nous proposons une implantation de ce modele comme la mise en oeuvre systematique d'une architecture client/ serveur. Cette implantation a ete effectuee sur une machine Supernode. La base est un Micro Noyau Parallele, ou le composant principal est un mecanisme d'appel de procedure a distance minimal.

Cette these traite de la migration de processus dans les systemes massivement paralleles. L'interet d'une telle fonctionnalite est de permettre a un systeme d'exploitation une gestion efficace des ressources. Les criteres de conception sont la transparence de la migration, la reduction des couts induits, et l'adequation entre les algorithmes de migration et l'extensibilite des architectures cibles. La migration d'un processus vers un nouveau processeur necessite la suspension du processus, le transfert de son contexte d'execution et la reprise de l'execution sur le nouveau processeur. De plus, les protocoles de communication et d'acces doivent etre reconsideres afin de tenir compte de la migration de processus. Pour ces differentes actions et selon les criteres de conception retenus, de nouveaux algorithmes ont ete proposes. La mise en oeuvre de ces algorithmes dans le noyau de systeme Parallele ParX nous a permis de montrer que la realisation d'un mecanisme de migration de processus dans un systeme massivement parallele peut s'effectuer sans penaliser les performances du systeme de facon significative. Enfin, nous avons propose un algorithme de repartition de charge qui utilise la migration de processus. Compare a un algorithme uniquement fonde sur le placement des processus, les experimentations effectuees montrent que notre algorithme ameliore les temps de reponse du systeme grace a la migration de processus. Cette amelioration est obtenue lorsque les temps d'execution et d'inter-creation des processus sont variables et le cout de migration negligeable par rapport a la duree d'execution des processus.

Zugl.: Dresden, Techn. Univ., Diss. 2007

Techn. University, Diss., 2002--München.

Connected-Component-Labeling (CCL) für 2D-Bilddaten ist ein bekanntes Problem im Bereich der Bildverarbeitung. Ziel ist es, zusammenhängende Pixelgruppen mit gleichen Eigenschaften zu erkennen und mit einem eindeutigen Label zu versehen. Zur Lösung von CCL-Problemen für 2D-Bilddaten werden sowohl sequentielle als auch parallele Algorithmen untersucht. Unter den bekannten Algorithmen gibt es solche, die asymptotisch optimale Eigenschaften besitzen. Speziell für den Bereich der Bildverarbeitung interessant sind außerdem auf Konturierung basierende Algorithmen. Die zusätzlich extrahierten Konturen können z.B. für die Buchstabenerkennung genutzt werden. Seit der jüngeren Vergangenheit werden Grafikprozessoren (GPUs) mit großem Erfolg für allgemeines Computing eingesetzt. So existieren auch mehrere Implementationen von Connected-Component-Labeling-Algorithmen für GPUs, welche im Vergleich mit Varianten für CPUs oft deutlich schneller sind. Diese GPU-basierten Ansätze verarbeiten typischerweise das Pixelgitter direkt. Im Rahmen der vorliegenden Arbeit werden mehrere neue parallele CCL-Algorithmen vorgeschlagen, welche auf Konturen basieren und sowohl für GPUs als auch für Multicore-CPUs geeignet sind. Diese werden experimentell mit Implementationen aus der Literatur unter Verwendung aktueller GPUs und CPUs verglichen. Dabei erreichen in vielen Fällen die vorgeschlagenen Techniken ein besseres Laufzeitverhalten. Das ist auf GPUs insbesondere dann besonders deutlich, wenn sich die evaluierten Datensätze durch einen geringen Anteil von Konturen im Vergleich zur Fläche der Connected-Components auszeichnen.

Cette these traite d'un ensemble de problemes lies a l'acheminement des messages dans les machines paralleles a memoire distribuee. L'accent est mis sur des solutions extensibles qui necessitent un nombre de ressources independant de la taille de la machine. A travers l'exemple des machines Supernodes (dont les processeurs sont interconnectes par un reseau de Clos 3-etages) nous montrons que l'acheminement des messages par reconfiguration dynamique est difficilement envisageable dans des machines de grande taille. Nous nous interessons ensuite au routage des messages dans des reseaux a topologie quelconque, et proposons une nouvelle methode de generation de fonctions de routage sans interblocage. La nouvelle generation des machines paralleles integre de plus en plus de fonctions dans le materiel, notamment le routage des messages. Pour que cette integration soit la plus efficace possible, des methodes nouvelles de representation compacte de l'information de routage sont necessaires. Santoro et Khatib ont propose une methode, le routage par intervalles, bien adaptee aux reseaux generaux. La deuxieme partie de cette these s'inscrit dans la continuite de ce type de travail et propose de nouvelles methodes de generation de fonctions de routage par intervalles. Deux cas sont consideres : le tore, et les reseaux generaux. Nous insistons plus particulierement sur des solutions sans interblocage, caracteristique rarement prise en compte. De plus dans le cas du tore, les longueurs des chemins sont proches des optima. Enfin, nous proposons une extension de la notion de routage par intervalles, le schema d'etiquetage etendu (SEE), permet de representer un spectre plus large de fonctions de routage.

Le but de cette these est d'etudier les schemas de communications les plus utilises, et plus particulierement la diffusion, pour en proposer des implementations efficaces sur des machines paralleles. Dans une premiere partie nous presentons les principales machines paralleles et les differents modes de communication mis en oeuvre dans ces machines. Cette partie illustre le probleme du choix du reseau d'interconnexion pour assembler les processeurs des ordinateurs massivement paralleles. La deuxieme partie est consacree a l'etude des schemas de communications globales dans les grilles toriques en mode store and forward. Dans un premier temps, on presente une nouvelle famille d'arbres de recouvrement disjoints de profondeur minimale, permettant de realiser la diffusion pipeline en temps optimal. Dans un deuxieme temps, on presente l'utilisation d'autres outils tels que les chemins hamiltoniens pour realiser l'echange total. Sur ce dernier type de communication, une etude en mode wormhole est presentee. L'algorithme est inspire du decoupage recursif de la grille torique. Il permet d'obtenir un nombre d'etapes plus faible qu'avec les algorithmes traditionnels en store and forward. Des resultats experimentaux sur machine MegaNode a 128 Transputers, permettent de valider notre etude theorique en mode store and forward. La troisieme partie est consacree a l'etude du recouvrement des communications par des calculs. L'idee consiste a anticiper les communications, en pipelinant l'envoi de petits messages. Mais la taille des messages a envoyer n'est pas facile a calculer. Nous illustrons ce probleme sur l'exemple du produit matrice-vecteur.

La Memoire Distribuee Partagee a ete concue pour permettre aux utilisateurs d'une machine parallele sans memoire commune de profiter du modele de programmation a donnees partagees. Au plus bas niveau, les mecanismes qui simulent la memoire partagee communiquent par echange de messages. L'utilisateur, en revanche, garde un modele de programmation d'une machine virtuelle a memoire globale accessible directement par tous les processeurs du systeme. Une des approches souvent utilisees pour implanter la Memoire Distribuee Partagee est la memoire virtuelle partagee. En plus d'un espace d'adressage partage, la memoire virtuelle partagee approche offre un mecanisme de gestion de memoire virtuelle a trois niveaux. La memoire virtuelle partagee est une facon transparente et elegante d'implanter la memoire distribuee partagee. Helas, le desir d'offrir une abstraction parfaite d'une memoire unique a conduit a des systemes peu performants. Afin d'approcher des performances acceptables, plusieurs systemes a memoire virtuelle partagee ont relache certaines conditions de coherence de la memoire. Ces modeles offrent la possibilite d'atteindre des performances plus importantes que celles des modeles a coherence forte. Le prix a payer est l'augmentation de la complexite du modele de programmation. Neanmoins, les recherches plus recentes dans le domaine semblent montrer que le choix du modele de coherence de la memoire le plus adapte a une application depend des caracteristiques d'acces aux donnees de l'application. Cette these porte sur la conception d'une machine virtuelle capable d'offrir le support necessaire a la programmation a memoire partagee avec des modeles de coherence multiples. Un module de traitement generique de modeles de coherence et un mecanisme qui permet une interface uniforme de synchronisation ont ete concus dans ce but. La conception de ces mecanismes a ete faite en observant des criteres d'extensibilite de sorte a les adapter aux architectures massivement paralleles. Dans le domaine de la gestion de la memoire virtuelle, nous avons modifie quelques mecanismes classiques, notamment le remplacement et le prechargement des pages, pour les adapter a un environnement multi-modeles. Un prototupe a ete realise pour valider nos mecanismes. L'analyse du comportement d'une meme application dans deux modeles de coherence differents nous a permis de montrer que le choix du modele de coherence a une influence importante sur les performances d'une application.