Channels ▼
RSS

test La conception d'algorithmes parallèles 1ère partie


Note du rédacteur : Cet article en plusieurs parties porte sur la conception d'algorithmes parallèles et se base sur le livre Designing and Building Parallel Programs écrit par Ian Foster. Designing and Building Parallel Programs encourage une vision de la programmation parallèle comme discipline d'ingénierie, dans laquelle les programmes sont développés de façon méthodique, et où tant les coûts que les performances sont considérés dans une conception. La 1ère partie se focalise sur la Conception et le Partitionnement méthodiques. Les volets suivants se concentreront sur la Communication, l'Agglomération et le Mappage, avant de finir en examinant les études de cas d'algorithmes parallèles en action. Un remerciement tout particulier à Ian Foster.

La conception d'algorithmes parallèles ne se réduit pas facilement à de simples recettes. Elle requiert plutôt le genre de pensée intégrative qu'on appelle communément la « créativité ». Cependant, elle peut tirer profit d'une approche méthodique qui maximise la gamme d'options considérées, qui fournit des mécanismes pour évaluer les alternatives, et qui réduit les coûts de back-tracking (retour en arrière) après de mauvais choix. Nous décrivons cette approche et illustrons son application à une variété de problèmes. Notre objectif est de suggérer un cadre (ou framework) au sein duquel un concept d'algorithme parallèle peut être exploité. Nous espérons que cela vous aidera à développer de l'intuition afin de savoir ce qui constitue un bon algorithme parallèle.

Après avoir étudié cet article, vous devriez être capable de concevoir des algorithmes parallèles simples de façon méthodique, et de reconnaître les défauts de conception qui compromettent l'efficacité ou la flexibilité. Vous devriez être capable de partitionner les calculs, en utilisant tant des techniques de décomposition fonctionnelle que de domaine, et savoir reconnaître et implémenter des structures de communication à la fois locales et globales, statiques et dynamiques, structurées et non structurées, ainsi que synchrones et asynchrones. Vous devriez aussi être capable d'utiliser l'agglomération comme moyen de réduire les coûts de communication et d'implémentation, et vous devriez être familier avec une variété de stratégies d'équilibrage des charges.

Conception méthodique

La plupart des problèmes de programmation ont plusieurs solutions parallèles. La meilleure solution peut différer de celle suggérée par les algorithmes séquentiels existants. La méthodologie de conception que nous décrivons vise à adopter une approche exploratoire de la conception dans laquelle les problèmes indépendants des machines tels que la simultanéité sont considérés rapidement et où les aspects spécifiques aux machines sont retardés jusqu'à un stade avancé du processus de conception. Cette méthodologie structure le processus de conception en quatre étapes distinctes : le partitionnement, la communication, l'agglomération, et le mappage. (L'acronyme PCAM pourra vous aider à vous souvenir de cette structure.) Dans les deux premières étapes, nous nous focalisons sur la simultanéité et la flexibilité, et nous cherchons à découvrir les algorithmes dotés de ces qualités. Dans les troisième et quatrième étapes, l'attention se porte sur la localité et les autres problèmes de performance. Les quatre étapes sont illustrées dans la Figure 1 et peuvent être résumées comme suit :

  • Le partitionnement. Les calculs devant être réalisés et les données utilisées par ces calculs sont décomposés en petites tâches. Les problèmes pratiques tels que le nombre de processeurs dans l'ordinateur cible sont ignorés, et l'attention se focalise sur la reconnaissance d'opportunités pour une exécution parallèle.
  • La communication. La communication requise pour coordonner l'exécution des tâches est déterminée, et des structures de communication et algorithmes appropriés sont définis.
  • L'agglomération. Les structures de tâches et de communications définies dans les deux premières étapes d'un concept sont évaluées en considérant les exigences de performances et les coûts d'implémentation. Si nécessaire, les tâches sont combinées en de plus larges tâches pour améliorer les performances ou réduire les coûts de développement.
  • Le mappage. Chaque tâche est affectée à un processeur de façon à essayer de satisfaire les objectifs simultanés de maximisation de l'utilisation des processeurs et de minimisation des coûts de communication. Le mappage peut être spécifié de manière statique ou déterminé à l'exécution par des algorithmes d'équilibrage des charges.

Figure 1: PCAM : une méthodologie de conception pour les programmes parallèles. Nous commençons par spécifier le problème, développons une partition, déterminons les exigences de communication, agglomérons les tâches, et finissons par mapper (ou affecter) les tâches aux processeurs.

Le résultat de ce processus de conception peut être un programme qui crée et détruit les tâches de manière dynamique, en utilisant des techniques d'équilibrage des charges pour contrôler le mappage des tâches aux processeurs. Ou bien, le résultat peut être un programme SMPD qui crée exactement une tâche par processeur. Le même processus de découverte des algorithmes s'applique dans les deux cas, bien que si l'objectif est de produire un programme SMPD, les problèmes associés au mappage sont subsumés dans la phase d'agglomération de la conception.

La conception d'algorithmes est présentée ici comme une activité séquentielle. En pratique, cependant, il s'agit d'un processus hautement parallèle, de nombreux problèmes étant considérés simultanément. Aussi, bien que nous cherchions à éviter de revenir en arrière, l'évaluation d'un concept partiel ou complet peut nécessiter des changements par rapport aux décisions de concept réalisées dans les étapes précédentes. Les sections suivantes proposent une étude détaillée des quatre étapes du processus de conception. Nous présentons les principes de bases, utilisons des exemples pour illustrer l'application de ces principes, et incluons des checklists de concept pouvant être utilisées pour évaluer les concepts tandis qu'ils sont développés. Dans les dernières sections de cet article, nous utilisons trois études de cas pour illustrer l'application de ces techniques de conception à des problèmes réalistes.

Le partitionnement

L'étape de partitionnement d'un concept vise à exposer les opportunités d'exécution parallèle. Ainsi, cette étape se focalise sur la définition d'un large nombre de petites tâches afin d'obtenir ce qu'on appelle la décomposition à grains fins d'un problème. Comme le sable fin se déverse plus facilement qu'une pile de briques, une décomposition à grains fins offre la meilleure flexibilité en termes d'algorithmes parallèles potentiels. Dans les étapes ultérieures de la conception, les problèmes d'évaluation des exigences de communication, d'architecture cible, ou d'ingénierie logicielle peuvent nous conduire à renoncer à des opportunités d'exécution parallèle identifiées dans cette étape. Nous revisitons ensuite la partition originale et agglomérons les tâches pour accroître leur taille, ou leur granularité. Cependant, dans cette première étape, nous souhaitons éviter de porter de jugements prématurés sur les stratégies alternatives de partitionnement.

Une bonne partition divise en petits morceaux tant les calculs associés à un problème que les données utilisées pour ces calculs. Lors de la conception d'une partition, les programmeurs se focalisent très communément sur les données associées à un problème, puis déterminent une partition appropriée pour les données, et finissent par déterminer comment associer les calculs aux données. Cette technique de partitionnement est appelée la « décomposition de domaine ». L'approche alternative -- commencer par décomposer les calculs devant être réalisés puis s'occuper des données -- est appelée la décomposition fonctionnelle. Ce sont des techniques complémentaires pouvant être appliquées à différents composants d'un seul problème ou même appliquées au même problème pour obtenir des algorithmes parallèles alternatifs.

Dans cette première étape d'une conception, nous cherchons à éviter la réplication des calculs et données ; en d'autres termes, nous cherchons à définir des tâches qui partitionnent tant les calculs que les données en des ensembles disjoints. A l'instar de la granularité, il s'agit d'un aspect de la conception que nous pourrons réétudier ultérieurement. Il peut être utile de répliquer soit les calculs, soit les données, si cela peut vous permettre de réduire les exigences de communications.

La décomposition de domaine

Dans l'approche de décomposition de domaine du partitionnement des problèmes, nous cherchons d'abord à décomposer les données associées à un problème. Si possible, nous divisons ces données en de plus petits morceaux de tailles à peu près égales. Ensuite, nous partitionnons les calculs devant être réalisés, généralement en associant chaque opération aux données qu'elle utilise. Ce partitionnement réalise un certain nombre de tâches, chacune comprenant des données et un ensemble d'opérations sur ces données. Une opération peut nécessiter les données de plusieurs tâches. Dans ce cas, la communication est requise pour déplacer les données entre les tâches. Cette nécessité est traitée dans la prochaine phase du processus de conception.

Les données décomposées peuvent être l'entrée au programme, la sortie calculée par le programme, ou les valeurs intermédiaires maintenues par le programme. Différentes partitions sont possibles, selon différentes structures de données. De bonnes règles générales consistent à se focaliser d'abord sur la plus large structure de données ou sur la structure de données à laquelle on accède le plus fréquemment. Les différentes phases des calculs peuvent avoir lieu sur différentes structures de données ou demander des décompositions différentes pour les mêmes structures de données. Dans ce cas, nous traitons chaque phase séparément et déterminons ensuite comment les décompositions et les algorithmes parallèles se sont développés ensemble pour chaque phase.

La Figure 2 illustre la décomposition de domaine dans un problème simple mettant en scène une grille tridimensionnelle. (Cette grille pourrait représenter l'état de l'atmosphère dans un modèle climatique, ou un espace tridimensionnel dans un problème de traitement d'images.) Les calculs sont réalisés à plusieurs reprises sur chaque point de la grille. Des décompositions dans les dimensions x, y et/ou z sont possibles. Dans les premières phases d'une conception, nous favorisons la décomposition la plus agressive possible, qui, dans ce cas, définit une tâche par point de la grille. Chaque tâche maintient comme son état les nombreuses valeurs associées à son point de la grille et est responsable des calculs requis pour actualiser cet état.

Figure 2: Décompositions de domaine dans un problème mettant en scène une grille tridimensionnelle. Les décompositions uni-, bi-, et tridimensionnelles sont possibles ; dans chaque cas, les données associées à une seule tâche sont noircies. Une décomposition tridimensionnelle offre une flexibilité optimale et est adoptée au cours des premières étapes d'une conception.

La décomposition fonctionnelle

La décomposition fonctionnelle représente une façon différente et complémentaire de réfléchir aux problèmes. Dans cette approche, on commence par se concentrer sur les calculs devant être réalisés plutôt que sur les données manipulées par les calculs. Si nous parvenons à diviser ces calculs en tâches disjointes, nous passons à l'étude des exigences de données de ces tâches. Ces exigences de données peuvent être disjointes, en quel cas la partition est terminée. Sinon, elles peuvent considérablement se chevaucher, en quel cas une communication importante sera requise pour éviter une réplication des données. Cela démontre souvent qu'il serait plus judicieux d'opter plutôt pour une approche de décomposition de domaine.

Tandis que la décomposition de domaine forme les bases de la plupart des algorithmes parallèles, la décomposition fonctionnelle a beaucoup de valeur en tant que différent moyen de réfléchir aux problèmes. Pour cette seule raison, elle devrait être considérée lorsque vous explorez les divers algorithmes parallèles possibles. Une focalisation sur les calculs devant être réalisés peut parfois révéler la structure d'un problème, et ainsi les opportunités d'optimisation, qu'il n'aurait pas été facile de découvrir avec une étude des données uniquement.

Figure 3: Décomposition fonctionnelle dans un modèle informatisé du climat. Chaque composant du modèle peut être considéré comme une tâche séparée, pour être parallélisé par la décomposition de domaine. Les flèches représentent les échanges de données entre les composants pendant les calculs : le modèle atmosphérique génère les données de vitesse du vent utilisées par le modèle océanique ; le modèle océanique génère les données de température à la surface de la mer utilisées par le modèle atmosphérique, et ainsi de suite.

La décomposition fonctionnelle a aussi un rôle important à jouer en tant que technique de structuration de programme. Une décomposition fonctionnelle qui partitionne non seulement les calculs devant être réalisés mais aussi le code qui réalise ces calculs aura de grandes chances de réduire la complexité du concept dans l'ensemble. C'est souvent le cas dans les modèles informatisés des systèmes complexes, qui peuvent être structurés comme collections des modèles plus simples connectés par interfaces. Par exemple, une simulation du climat terrestre peut inclure des composants représentant l'atmosphère, l'océan, l'hydrologie, la glace, les sources de dioxyde de carbone, et ainsi de suite. Alors que chaque composant pourrait être le plus naturellement parallélisé en utilisant des techniques de décomposition de domaine, l'algorithme parallèle est dans l'ensemble plus simple si le système est d'abord décomposé en utilisant les techniques de décomposition fonctionnelle, même si ce processus ne réalise par un grand nombre de tâches (Figure 3).

Checklist du concept de partitionnement

La phase de partitionnement d'un concept devrait produire une ou plusieurs décomposition(s) possible(s) d'un problème. Avant de procéder à l'évaluation des exigences de communications, nous utilisons la checklist suivante pour garantir que le concept n'a aucun défaut évident. Généralement, une réponse positive devrait être apportée à toutes ces questions.

  • En ordre de grandeur, est-ce que votre partition définit au moins plus de tâches qu'il n'y a de processeurs dans votre ordinateur cible ? Si ce n'est pas le cas, vous disposerez de peu de flexibilité dans les étapes de conception suivantes. Est-ce que votre partition évite les calculs redondants et les nécessités de stockage ? Si ce n'est pas le cas, il se peut que l'algorithme résultant ne soit pas assez flexible pour traiter les problèmes importants.
  • Est-ce que les tâches sont de tailles comparables ? Si ce n'est pas le cas, il sera peut-être difficile d'attribuer à chaque processeur des quantités égales de travail.
  • Est-ce que le nombre de tâches s'adapte à la taille du problème ? Idéalement, une augmentation de la taille du problème devrait accroître le nombre de tâches plutôt que d'augmenter la taille des tâches individuelles. Si ce n'est pas le cas, il se peut que vos algorithmes parallèles ne soient pas capables de résoudre des problèmes plus importants lorsque davantage de processeurs sont disponibles.
  • Avez-vous identifié plusieurs partitions alternatives ? Vous pouvez maximiser la flexibilité dans les étapes de conception suivantes en considérant ces alternatives dès maintenant. Souvenez-vous d'étudier tant la décomposition de domaine que fonctionnelle.

Les réponses à ces questions peuvent suggérer que, en dépit des réflexions approfondies sur cela et sur les étapes de conception suivantes, nous disposons d'une mauvaise conception. Dans cette situation, il est tout simplement risqué de lancer l'implémentation.

A venir

Dans le prochain volet de cet article en plusieurs parties, j'étudierai les flux d'informations spécifiés dans la phase de communication d'une conception.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video