Academic literature on the topic 'Parallélisme (informatique) – Évaluation'

Nous analysons dans ce travail de these le processus d'implantation sur des machines mimd a passage de messages d'une classe importante d'algorithmes en traitement du signal: les algorithmes adaptatifs. Ce processus est long et couteux, raison pour laquelle on essaie de predire la performance des implantations avant de les programmer. Nous introduisons un modele du comportement temporel des implantations utilisant un faible nombre de parametres pour representer l'algorithme et l'architecture cible. Ensuite, nous definissons la machine ideale m#0 nous permettant d'atteindre une periode d'iteration minimale. Nous demontrons que cette periode d'iteration peut etre atteinte par une implantation reelle m#2 ayant un faible nombre de processeurs et prenant en compte les durees des communications. Nous avons developpe des algorithmes heuristiques permettant de trouver m#2 et de prendre en compte des restrictions materielles pour trouver des implantations performantes de plusieurs algorithmes adaptatifs classiques (lms, rls, ftf, felms, rlsl). Finalement, on presente un ensemble d'outils developpes pour aider au processus d'implantation sur des machines paralleles, nous permettent de predire les bornes de performance des implantations, de suggerer des configurations materielles et logicielles, et de simuler le fonctionnement temporel des implantations pour evaluer leur performance

L'accroissement des performances nécessaires au développement des applications en intelligence artificielle qui utilisent notamment la programmation logique, nécessite de recourir à l'exploitation du parallélisme. La programmation logique utilise deux formes de parallélisme: d'une part, le parallélisme explicite exploité par les langages gardes, tels CP, GHC et Prolog, d'autre part le parallélisme implicite exploitant les possibilités intrinsèques présentes dans un langage tel Prolog. L'exploitation du parallélisme implicite conduit généralement à s'éloigner de la sémantique opérationnelle classique, à générer des solutions dans un ordre non usuel rendant difficile l'introduction des prédicats à effet de bord. Le schéma d'évaluation parallèle de Prolog proposé dans le cadre du projet LOG-ARCH respecte la sémantique opérationnelle traditionnelle sans nécessiter d'annotations de la part d'un programmeur. Il exploite un parallélisme OU qui se développe par le bas de l'arbre ET/OU, et un parallélisme ET sous forme de pipeline. Un mécanisme de verrouillage est utilisé pour contrôler la production et la consommation des solutions, facilitant ainsi la prise en compte des prédicats à effet de bord. L'évaluation du modèle parallèle a été réalisée d'une part à l'aide d'un simulateur, d'autre part à partir de l'exécution véritable de programmes dont l'évaluation parallèle est reconstituée. Cette évaluation a permis de vérifier la validité du modèle et de mesurer le taux de parallélisme obtenu, dont l'ordre de grandeur est similaire à celui développé lors d'une exécution OU parallèle

Cette these sur le lancer de rayon parallele et l'analyse des performances se decompose en trois parties: 1) nous presentons une formalisation du lancer de rayon a l'aide de quatre graphes: le graphe des objets reels (objets de la scene et boites englobantes), graphe des objets virtuels (rayons), graphe des processus (description algorithmique du programme) et le graphe des machines. Ce formalisme permet de decrire les differentes optimisations a travers la structuration des graphes. Une nouvelle taxinomie des methodes d'optimisation tant sequentielles que paralleles est deduite. 2) une optimisation parallele du lancer de rayon basee sur l'exploitation d'informations topologiques deduites des calculs est presentee. Cette methode utilise un ensemble de regles logiques agissant au niveau des processus, ainsi que des messages echanges entre ceux-ci. Ces regles optimisent principalement les calculs sur les rayons primaires mais permettent egalement d'optimiser ceux concernant les rayons secondaires et d'ombre grace a l'ajustement des boites englobantes. Elles sont accompagnees d'une seconde serie de regles simples redefinissant la notion de coherence ainsi que d'une troisieme applicable a l'animation. 3) la derniere partie est consacree a l'analyse des performances selon deux approches. Dans un premier temps, le lancer de rayon est analyse pour en extraire un certain nombre de parametres caracterisant les performances calculatoires. Un protocole de tests est defini: ces tests sont independants de la machine et reproductibles. Dans un second temps, une version simplifiee de notre lancer de rayon est decrite mathematiquement par des moyens statistiques. Il est alors par exemple possible de donner une formule mathematique du gain de cette methode et de rechercher grace au calcul des variations le meilleur decoupage ecran maximisant ce gain. Cette approche encore limitee aux rayons primaires semble ouvrir de nouvelles pistes de recherche

Il est proposé une extension du jeu des combinateurs de turner et de l'algorithme d'abstractions correspondant, dont l'intérêt pratique est la diminution du taux d'extension du code combinatoire par rapport au nombre d'atomes du code source. L'auteur définit alors une machine abstraite, permettant de réduire un code combinatoire selon diverses stratégies parallèles, exploitant diverses sources de parallélisme. Un simulateur de ce réducteur parallèle a été réalisé, ainsi qu'un jeu de tests comportant principalement des fonctions de traitement symbolique. L'auteur a alors effectué un important travail d'expérimentations. Les mesures obtenus montrent que des techniques de compilation permettent d'engendrer, à partir d'un langage fonctionnel, un degré de parallélisme exploitable par une machine specialisée: une stratégie d'évaluation est alors proposée. Mais ces mesures soulignent aussi l'importance de la responsabilité du programmeur pour la mise en œuvre de cette algorithmique. En effet, le degré de parallélisme obtenu semble relativement difficile à prédire avant l'exécution.

La complexite des problemes poses par la conception des systemes temps reel destines a etre implantes sur des machines cibles multi-processeurs necessite l'elaboration d'une methodologie de conception pour ces systemes. Le travail presente dans ce memoire se situe dans ce cadre et a travers les propositions qui y sont faites, apporte une nouvelle dimension dans la conception des systemes temps reel. La premiere contribution de ce memoire est de proposer une methodologie s'appuyant sur cinq vues complementaires: environnement, fonction, performance, comportement et physique. Ces cinq vues correspondent a cinq nouveaux modeles qui ameliorent le traitement des problemes concernes par la specification et la conception des systemes temps reel. Le cycle de vie est decompose en six etapes: analyse et definition des besoins, analyse environnementale, raffinage fonctionnel du systeme, analyse comportementale, evaluation des performances et implantation. La deuxieme contribution de ce memoire consiste a resoudre les problemes particuliers rencontres frequemment dans les applications temps reel developpees sur les multiprocesseurs: satisfaction des contraintes temporelles, transformation de diagramme fonctionnel et de diagramme comportemental en programme parallele, validation des proprietes de surete, vivacite et terminaison des programmes paralleles, allocation et ordonnancement des processus sur les processeurs et equilibrage de charge de travail sur les processeurs. Concernant l'equilibrage de charge, nous presentons une etude de cas portant sur la modelisation des systemes temps reel repartis par les reseaux de files d'attente avec des arrivees negatives et positives. La derniere contribution permet de valider la methodologie proposee a travers le developpement d'un simulateur pour la generation de trames de telemesure aux normes ccsds sur des reseaux de transputers. Ce simulateur peut produire des trames conformes aux normes ccsds et identiques a celles que produirait un generateur bord de trames de telemesure

Le développement de calculateurs parallèles à très grand nombre de processeurs se heurte au problème physique des liaisons de transmission entre les processeurs. Dans cette thèse, on étudie les possibilités offertes par l'optique pour résoudre ce problème. L'étude des systèmes optiques montre les capacités de cette technologie à réaliser des réseaux de type crossbar où n'importe quelle paire de processeurs peut être connectée. Les caractéristiques intrinsèques des réseaux optiques supplantent celles des réseaux électroniques, aussi bien en nombre de processeurs connectés qu'en débit d'information. Une maquette de démonstration baptisée milord illustre un reseau de communication optique en espace libre servant à faire communiquer 16 microprocesseurs de type transputer. Les caractéristiques d'un tel système sont analysées, plus particulièrement le temps de programmation du réseau. La relative lenteur de commutation de voies optiques nous conduit à proposer des stratégies qui utilisent le concept de reconfiguration. Les programmes exploités dans ce contexte sont découpés en phases séquentielles séparées par des points de reconfiguration de l'interconnexion des processeurs. Une analyse des différents composants optiques existants ou probables dans un avenir proche nous conduit à définir les principales caractéristiques de futurs systèmes de communication.

L'ensemble des travaux resumes dans cette these et par le sigle coala (calculateur oriente acteurs pour la logique et ses applications) ont pour objet la mise en uvre et le support efficace du parallelisme inherent au langage prolog, sans l'intervention du programmeur. Le modele d'interpretation repartie utilise le graphe de connexion et/ou de r. Kowalski comme representation interne des programmes, et correlativement, utilise sa procedure de preuve comme methode de resolution parallele. Dans ce graphe, deux litteraux pouvant s'appareiller de part et d'autre du symbole implication dans deux clauses differentes sont relies par un arc. A chaque arc du graphe correspond un resolvant possible. Deux niveaux de parallelisme sont exploites: le parallelisme associe a la construction des differents arcs pour chaque resolvant. Ces deux niveaux sont cependant intimement meles et correspondent respectivement aux parallelismes- ou et et. A partir d'une premiere version du modele d'execution, plusieurs extensions ont ete proposees et realisees. Elles concernent le parallelisme-et independant, le parallelisme de recherche et l'ajout des predicats evaluables et a effets de bord. Afin de garantir une certaine efficacite du modele d'execution, une premiere implantation de ce modele d'execution a ete etudiee sur une maquette multiprocesseur a base de transputers, baptisee hypertore. Elle a permis de specifier la machine abstraite ciam (coala inference abstract machine), liee a la compilation du modele d'execution. Dans cette approche, il s'agit de traduire le comportement de chaque arc du graphe en une sequence d'instructions, dans le meme esprit que la compilation sequentielle du langage prolog

La programmation des jeux de reflexion fut consideree comme the drosophilia melanogaster of machine intelligence. Ce domaine devait permettre l'elaboration de techniques et d'algorithmes reutilisables dans d'autres domaines de l'intelligence artificielle. Selon c. Shannon, il s'agit d'un sujet sensible ou l'avancee est facilement communicable au public. Nous abordons cette question dans le cadre de programmes de jeux devant repondre a un probleme dans des conditions de tournois. Nous comparons les differentes recherches minimax basees sur des elagages alpha-beta avec l'algorithme negac* que nous avons defini et donnons les principaux resultats que nous avons etablis sur sa complexite. Nous definissons, dans le paradigme negamax, le nouvel algorithme de recherche de nombre de preuves et nous le comparons avec notre programme d'echecs ecume, dans le cadre des recherches de mats. Nous exposons un ensemble d'heuristiques qui permettent de rendre les recherches negamax plus rapides et plus fiables en explicitant les options que nous avons prises dans nos programmes d'echecs. Nous presentons nos resultats sur la parallelisation de la recherche minimax pour une machine distribuee: la connection machine 5. Ils nous ont permis de definir une nouvelle methode que nous avons comparee aux meilleures methodes connues jusqu'alors, sur des arbres de jeux simules et reels. Nous continuons par la presentation de notre methode de construction de fonctions d'evaluation en expliquant comment nous avons pu introduire la notion de plan strategique. Nous montrons aussi comment construire automatiquement une fonction d'evaluation par apprentissage dans la finale roi et dame contre roi et dame. Enfin, nous decrivons l'ensemble des caracteristiques de nos programmes d'echecs, dont cumulus 2. 0 qui a remporte le titre de vice-champion du monde d'echecs logiciels toutes categories

Une architecture parallèle pour le traitement d'images, articulée autour d'un bus rapide, est étudiée en vue d'effectuer des rectifications géométriques d'images satellites de grande dimension. Une parallélisation de l'algorithme est proposée en tenant compte d'une optimisation possible du découpage de l'image