  Beowulf HOWTO
  Jacek Radajewski and Douglas Eadline (traduction : Emmanuel
  PIERRE, epierre@e-nef.com )
  v1.1.1, 22 Novembre 1998

  Ce document est une introduction  l'architecture Beowulf Supercompu
  teur. Il fournit les informations de base sur la programmation par
  allle, et inclut des liens vers des documents plus spcifiques et des
  pages web.
  ______________________________________________________________________

  Table des matires






















































  1. Prambule

     1.1 Mise en garde
     1.2 Copyright
     1.3 Au sujet de ce HOWTO
     1.4 Au sujet des auteurs
     1.5 Remerciements

  2. Introduction

     2.1 A qui s'adresse ce HOWTO ?
     2.2 Qu'est-ce que Beowulf ?
     2.3 Classification

  3. Aperu de l'Architecture

     3.1 A quoi cela ressemble-t-il ?
     3.2 Comment utiliser les autres noeuds ?
     3.3 En quoi un Beowulf diffre-t-il d'un COW ?

  4. Conception du Systme

     4.1 Brefs rappels sur la programmation parallle
     4.2 Les mthodes de programmation parallle
        4.2.1 Pourquoi plus d'un CPU ?
        4.2.2 La "caisse" en programmation parallle
           4.2.2.1 Systmes d'exploitation Mono-Tche:
           4.2.2.2 Systmes d'exploitation Multi-Tches:
           4.2.2.3 Systmes d'exploitation Multi-Tches avec plusieurs CPU:
           4.2.2.4 Sous-tches (Threads) sur les autres CPU d'un Systme d'exploitation Multi-Tches:
           4.2.2.5 Envoyer des messages sur des Systmes d'exploitation Multi-Tches avec plusieurs CPU:
     4.3 Architectures pour le calcul parallle
        4.3.1 Architectures Matrielles
        4.3.2 Architectures Logicielles et API
           4.3.2.1 Messages
           4.3.2.2 Threads
        4.3.3 Architecture des Applications
     4.4 Convenance
     4.5 Ecrire et porter des logiciels parallles
        4.5.1 Dterminer les parties concurrentes de votre programme
        4.5.2 Estimer le paralllisme efficacement
        4.5.3 Dcrire les parties concurrentes de votre programme
           4.5.3.1 Les mthodes explicites
           4.5.3.2 Mthodes Implicites

  5. Ressources Beowulf

     5.1 Points de dpart
     5.2 Documentation
     5.3 Publications
     5.4 Logiciels
     5.5 Machines Beowulf
     5.6 D'autres Sites Intressants
     5.7 Histoire

  6. Code Source

     6.1 sum.c
     6.2 sigmasqrt.c
     6.3 prun.sh


  ______________________________________________________________________



  11..  PPrraammbbuullee

  11..11..  MMiissee eenn ggaarrddee

  Nous n'accepterons aucune responsabilit pour toute information
  incorrecte prsente dans ce document, ni pour aucun des dommages qui
  pourraient en rsulter.



  11..22..  CCooppyyrriigghhtt

  Copyright  1997 - 1998 Jacek Radajewski et Douglas Eadline.  Le droit
  de distribuer et de modifier ce document est autoris sous la licence
  GNU General Public License.


  11..33..  AAuu ssuujjeett ddee ccee HHOOWWTTOO


  Jacek Radajewski a commenc  travailler sur ce document en novembre
  1997 et a t ensuite rejoint par Douglas Eadline. En quelques mois,
  le HOWTO Beowulf est devenu un document consistant, et en aot 1998,
  il a t dcoup en trois: Beowulf HOWTO, Beowulf Architecture Design
  HOWTO, the Beowulf Installation and Administration HOWTO. La Version
  1.0.0 de ce document a t soumise au Linux Documentation Project le
  11 novembre 1998. Nous esprons que ce ne soit que le dbut de ce qui
  deviendra une documentation complte du Projet de Documentation
  Beowulf (Beowulf Documentation Project).


  11..44..  AAuu ssuujjeett ddeess aauutteeuurrss


    Jacek Radajewski est Administrateur Rseau, et prpare un degr
     honorifique en Informatique  l'Universit du Southern Queensland,
     Australie. Le premier contact de Jacek avec Linux eut lieu en 1995
     et il en tomba amoureux du premier coup. Jacek construisit son
     premier cluster Beowulf en Mai 1997 et a jou avec cette
     technologie depuis, toujours  la recherche de la meilleure manire
     de tout organiser.  Vous pouvez joindre Jacek par courriel 
     jacek@usq.edu.au

    Douglas Eadline, Ph.D. est le President et le Principal
     Scientifique (Principal Scientist)  Paralogic, Inc., Bethlehem,
     PA, USA.  Form en tant que Chimiste Physique/Analytique, il s'est
     investi dans les ordinateurs depuis 1978, anne o il a construit
     sa premire machine pour l'utiliser avec l'instrumentation
     chimique. A ujourd'hui, le Dr. Eadline s'intresse  Linux, aux
     clusters Beowulf, et aux algorithmes parallles.  Le Dr. Eadline
     peut tre joint par courriel  deadline@plogic.com


  11..55..  RReemmeerrcciieemmeennttss

  L'criture du HOWTO Beowulf a t longue, et il est finalement complet
  grce  de nombreuses personnes. Nous voudrions remercier celles qui
  suivent pour leur aide et leurs contributions  ce HOWTO:

    Becky pour son amour, son soutien, et sa comprhension.

    Tom Sterling, Don Becker, et les autres personnes de la NASA qui
     furent  l'origine du projet Beowulf.

    Thanh Tran-Cong et la Faculty of Engineering and Surveying pour
     avoir donn la machine Beowulf _t_o_p_c_a_t pour les tests de Beowulf.
    Mon suprieur Christopher Vance pour de nombreuses bonnes ides.

    Mon ami Russell Waldron pour de grandes ides de programmation, son
     intrt gnral pour le projet, et son soutien.

    Mon ami David Smith pour la relecture de ce document.

    Et de nombreuses autres personnes sur la liste de diffusion Beowulf
     qui nous ont fournis beaucoup de retour et d'ides.

    Toutes les personnes qui sont responsables du systme
     d'exploitation Linux et de tous les autres outils gratuits utiliss
     sur _t_o_p_c_a_t et les diverses machines Beowulf.



  22..  IInnttrroodduuccttiioonn

  Au fur et  mesure que les niveaux de performance et de commodit des
  ordinateurs et des rseaux augmentent, il devient de plus en plus
  facile de construire des systmes informatiques parallles  partir de
  composants facilement disponibles, plutt que de construire des
  processeurs sur de trs coteux Superordinateurs.  En fait, le rapport
  prix/performances d'une machine de type Beowulf est de trois  dix
  fois meilleur que celui des superordinateurs traditionnels.
  L'architecture Beowulf s'chelonne bien, elle est facile  construire
  et vous ne payez que pour le matriel, puisque la pluspart des
  logiciels sont gratuits.


  22..11..  AA qquuii ss''aaddrreessssee ccee HHOOWWTTOO ??

  Ce HOWTO s'adresse aux personnes qui ont dj eu au moins des contacts
  avec le systme d'exploitation Linux. La connaissance de la
  technologie Beowulf ou d'un systme d'exploitation plus complexe et de
  concepts rseaux n'est pas essentielle, mais des aperus de la
  programmation parallle sont bienvenus (aprs tout, vous devez avoir
  de bonnes raisons de lire ce document). Ce HOWTO ne rpondra pas 
  toutes les questions que vous pourriez vous poser au sujet de Beowulf,
  mais, esprons-le, vous donnera des ides et vous guidera dans la
  bonne direction. Le but de ce HOWTO est de fournir des informations de
  base, des liens et des rfrences vers des documents plus approfondis.


  22..22..  QQuu''eesstt--ccee qquuee BBeeoowwuullff ??

  _F_a_m_e_d _w_a_s _t_h_i_s _B_e_o_w_u_l_f_: _f_a_r _f_l_e_w _t_h_e _b_o_a_s_t _o_f _h_i_m_, _s_o_n _o_f _S_c_y_l_d_, _i_n
  _t_h_e _S_c_a_n_d_i_a_n _l_a_n_d_s_.  _S_o _b_e_c_o_m_e_s _i_t _a _y_o_u_t_h _t_o _q_u_i_t _h_i_m _w_e_l_l _w_i_t_h _h_i_s
  _f_a_t_h_e_r_'_s _f_r_i_e_n_d_s_, _b_y _f_e_e _a_n_d _g_i_f_t_, _t_h_a_t _t_o _a_i_d _h_i_m_, _a_g_e_d_, _i_n _a_f_t_e_r
  _d_a_y_s_, _c_o_m_e _w_a_r_r_i_o_r_s _w_i_l_l_i_n_g_, _s_h_o_u_l_d _w_a_r _d_r_a_w _n_i_g_h_, _l_i_e_g_e_m_e_n _l_o_y_a_l_: _b_y
  _l_a_u_d_e_d _d_e_e_d_s _s_h_a_l_l _a_n _e_a_r_l _h_a_v_e _h_o_n_o_r _i_n _e_v_e_r_y _c_l_a_n_.  Beowulf est le
  pome pique le plus ancien en Anglais qui ait t conserv.  C'est
  l'histoire d'un hros d'une grande force et d'un grand courage qui a
  dfait un monstre appel Grendel. Voir l'``Historique'' pour en savoir
  plus sur le hros Beowulf.


  Il y a peut-tre de nombreuses dfinitions de Beowulf, autant que de
  personnes qui construisent ou utilisent des Superordinateurs Beowulf.
  Certains disent qu'ils peuvent appeler leur systme Beowulf seulement
  s'il est construit de la mme faon que la machine d'origine de la
  NASA. D'autres vont  l'extrme inverse et appellent ainsi n'importe
  quel systme de stations qui excutent du code parallle. Ma
  dfinition d'un Beowulf se situe entre ces deux avis, et est fonde
  sur de nombreuses contributions dans la liste de diffusion Beowulf.

  Beowulf est une architecture multi-ordinateurs qui peut tre utilise
  pour la programmation parallle. Ce systme comporte habituellement un
  noeud serveur, et un ou plusieurs noeuds clients connects entre eux 
  travers Ethernet ou tout autre rseau. C'est un systme construit en
  utilisant des composants matriels existants, comme tout PC capable de
  faire tourner Linux, des adaptateurs Ethernet standards, et des
  switches. Il ne contient aucun composant matriel propre et est
  aisment reproductible. Beowulf utilise aussi des lments comme le
  systme d'exploitation Linux, Parallel VirtualMachine (PVM) et Message
  Passing Interface (MPI). Le noeud serveur contrle l'ensemble du
  cluster et sert de serveur de fichiers pour les noeuds clients.  Il
  est aussi la console du cluster et la passerelle (gateway) vers le
  monde extrieur. De grandes machines Beowulf peuvent avoir plus d'un
  noeud serveur, et ventuellement aussi d'autres noeuds ddis  des
  tches particulires, par exemple comme consoles ou stations de
  surveillance.  Dans de nombreux cas, les noeuds clients d'un systme
  Beowulf sont idiots (dumb): plus ils sont idiots, mieux ils sont. Les
  noeuds sont configurs et contrls par le noeud serveur, et ne font
  que ce qu'on leur demande de faire. Dans une configuration client sans
  disque (diskless), les noeuds clients ne connaissent mme pas leur
  adresse IP ou leur nom jusqu' ce que le serveur leur dise qui ils
  sont. Une des principales diffrences entre Beowulf et un Cluster de
  Stations de travail (COW) est le fait que Beowulf se comporte plus
  comme une simple machine plutt que comme plusieurs stations de
  travail. Dans de nombreux cas, les noeuds clients n'ont pas de
  claviers ni de moniteurs, et on n'y accde que par une connection
  distante ou par un terminal srie. Les noeux Beowulf peuvent tre
  envisags comme un CPU + des ensembles de mmoires qui peuvent tre
  branchs dans le cluster, exactement comme un CPU ou un module mmoire
  peut tre branch dans une carte mre.


  Beowulf n'est pas un ensemble de matriels spcialiss, une nouvelle
  topologie rseau ou le dernier hack du kernel. Beowulf est une
  technologie de clustering d'ordinateurs Linux pour former un
  superordinateur parallle, virtuel. Mme s'il y a de nombreux
  paquetages comme des patches du noyau, PVM, les librairies MPI, et des
  outils de configuration qui rendent l'architecture Beowulf plus
  rapide, plus facile  configurer, et plus facilement utilisable, on
  peut construire une machine de classe Beowulf en utilisant une
  distribution Standard de Linux sans ajouter d'autres logiciels.  Si
  vous avez deux Linux en rseau qui partagent au moins le mme systme
  de fichier racine via NFS, et qui se font confiance pour excuter des
  sessions distantes (rsh), alors on peut dire que vous avez un simple
  Beowulf de deux noeuds.



  22..33..  CCllaassssiiffiiccaattiioonn

  Les systmes Beowulf ont t construits  partir de nombreux
  constituants.  Pour des considrations de performances, des composants
  moins communs (i.e.  produits par un seul fabricant) ont t utiliss.
  Afin de recenser les diffrents types de systmes et de rendre les
  discussions au sujet des machines un peu plus faciles, nous proposons
  la mthode simple de classification suivante:

  CLASSE I BEOWULF:

  Cette classe concerne des machines faites d'lments globalement
  disponibles.  Nous devrons utiliser les tests de certification
  "Computer Shopper" pour dfinir les composants d'assemblage.
  ("Computer Shopper" est un mensuel sur les PC et leurs composants.)
  [NdT: US seulement ; pour un quivalent, on peut voquer par exemple
  "PC Direct".] Le test est le suivant:

  Un Beowulf CLASSE I est une machine qui peut tre assemble  partir
  de pices trouves dans au moins quatre journaux de publicit de
  grande diffusion.


  Les avantages des systmes de CLASS I sont:

    le matriel est disponible de noubreuses sources (faible cot,
     maintenance facile)

    ne dpendant pas d'un seul vendeur de matriel

    support des drivers par les commodits Linux

    bas habituellement sur des standards (SCSI, Ethernet, etc.)

  Les dsavantages d'un systme de CLASSE I sont:

    de meilleures performances peuvent ncessiter du matriel de CLASSE
     II

  CLASSE II BEOWULF

  Un Beowulf CLASSE II Beowulf est simplement une machine qui ne passe
  pas le test de certification "Computer Shopper". Ce n'est pas une
  mauvaise chose.  D'autre part, il s'agit plutt d'une classification
  de la machine.

  Les avantages d'un systme de CLASSE II sont:

    les performances peuvent tre assez bonnes !

  Les dsavantages des systmes de CLASSE II sont:

    le support des drivers peut varier

    reposent sur un seul vendeur de matriel

    peuvent tre plus chers que les systmes de CLASSE I.

  Une CLASSE n'est pas ncessairement meilleure qu'une autre. Cela
  dpend surtout de vos besoins et de votre budget. Cette classification
  des systmes sert seulement  rendre les discussions sur les systmes
  Beowulf un peu plus succintes. La "Conception du Systme" peut aider 
  dterminer quelle sorte de systme est le plus appropri  vos
  besoins.





  33..  AAppeerruu ddee ll''AArrcchhiitteeccttuurree



  33..11..  AA qquuooii cceellaa rreesssseemmbbllee--tt--iill ??

  Je pense que la meilleure faon de dcrire l'architecture d'un
  superordinateur Beowulf est d'utiliser un exemple qui est trs proche
  du vrai Beowulf, mais aussi familier  beaucoup d'administrateurs
  systmes.  L'exemple le plus proche d'une machine Beowulf est un Unix
  de laboratoire avec un serveur et un certain nombre de clients. Pour
  tre plus spcifique, j'utiliserai le DEC Alpha au laboratoire
  d'informatique de la Facult des Sciences de l'USQ comme exemple. Le
  serveur est appel _b_e_l_d_i_n et les machines clientes sont _s_c_i_l_a_b_0_1,
  _s_c_i_l_a_b_0_2, _s_c_i_l_a_b_0_3, jusqu' _s_c_i_l_a_b_2_0. Tous les clients ont une copie
  locale du systme d'exploitation Digital Unix 4.0 install, mais ont
  l'espace disque utilisateur (/home) et /usr/local du serveur via NFS
  (Network File System). Chaque client a une entre pour le serveur et
  tous les autres clients dans son fichier /etc/hosts.equiv: ainsi tous
  les clients peuvent excuter une cession distante (rsh) vers tout
  autre. La machine serveur est un serveur NIS pour tout le laboratoire,
  ainsi les informations des comptes sont les mmes sur toutes les
  machines. Une personne peut s'asseoir  la console de _s_c_i_l_a_b_0_2, se
  logue, et a le mme environnement que s'il tait logu sur le serveur,
  ou _s_c_i_l_a_b_1_5. La raison pour laquelle les clients ont la mme
  prsentation est que le systme d'exploitation est install et
  configur de la mme faon sur toutes les machines, les espaces /home
  et /usr/local sont physiquement sur le mme serveur et les clients y
  accdent via NFS. Pour plus d'informations sur NIS et NFS, reportez-
  vous  NIS et NFS.



  33..22..  CCoommmmeenntt uuttiilliisseerr lleess aauuttrreess nnooeeuuddss ??


  Maintenant que nous avons une vision correcte de l'architecture du
  systme, regardons comment nous pouvons utiliser les cycles CPU des
  machines dans le laboratoire. Toute personne peut se loguer sur
  n'importe laquelle des machines, et lancer un programme dans son
  rpertoire de base, mais peut aussi clater la mme tche sur
  diffrentes machines simplement en excutant un shell distant. Par
  exemple, si nous voulons calculer la somme des racines carres de tous
  les entiers inclus strictement entre 1 et 10, nous crivons un simple
  programme appel sigmasqrt (voir ``code source'') qui fait cela
  exactement. Pour calculer la somme des racines carres des nombres de
  1  10, nous excutons :

  [jacek@beldin sigmasqrt]$ time ./sigmasqrt 1 10
  22.468278

  real    0m0.029s
  user    0m0.001s
  sys     0m0.024s


  La commande time nous permet de vrifier le temps mis en excutant
  cette tche. Comme nous pouvons le voir, cet exemple a pris seulement
  une petite fraction de seconde (0.029 sec) pour s'excuter, mais que
  se passe-t-il si je veux ajouter la racine carre des entiers de 1  1
  000 000 000 ?  Essayons ceci, et calculons le temps coul:


  [jacek@beldin sigmasqrt]$ time ./sigmasqrt 1 1000000000
  21081851083600.559000

  real    16m45.937s
  user    16m43.527s
  sys     0m0.108s




  Cette fois, le temps d'excution de ce programme est considrablement
  suprieur.  La question vidente qui se pose est: est-il possible de
  diminuer le temps d'excution de cette tche et comment ? La rponse
  vidente est de dcouper la tche en un ensemble de sous-tches et
  d'excuter ces sous-tches en parallle sur tous les ordinateurs. Nous
  pouvons sparer la grande tche d'addition en 20 parties en calculant
  un intervalle de racines carres et en les additionnant sur un seul
  noeud.  Quand tous les noeuds ont fini les calculs et retournent leurs
  rsultats, les 20 nombres peuvent tre additionns ensemble et fournir
  la solution finale. Avant de lancer ce processus, nous allons crer un
  "named pipe" qui sera utilis par tous les processus pour crire leurs
  rsultats:


  [jacek@beldin sigmasqrt]$ mkfifo output
  [jacek@beldin sigmasqrt]$ ./prun.sh & time cat output | ./sum
  [1] 5085
  21081851083600.941000
  [1]+  Done                    ./prun.sh

  real    0m58.539s
  user    0m0.061s
  sys     0m0.206s



  Cette fois, cela prend 58.5 secondes. C'est le temps qui a t
  ncessaire entre le dmarrage du processus et le moment o les noeuds
  ont fini leurs calculs et crit leurs rsultats dans la pipe. Ce temps
  n'inclut pas l'addition finale des 20 nombres, mais il reprsente une
  petite fraction de seconde et peut tre ignor. Nous pouvons voir
  qu'il y a un avantage significatif  excuter une tche en parallle.
  En fait la tche en parallle s'est excute 17 fois plus vite, ce qui
  est trs raisonnable pour un facteur 20 d'augmentation du nombre de
  CPU. Le but de l'exemple prcdent est d'illustrer la mthode la plus
  simple de parallliser du code concurrent. En pratique, des exemples
  aussi simples sont rares et diffrentes techniques (les API de PVM et
  PMI) sont utilises pour obtenir le paralllisme.



  33..33..  EEnn qquuooii uunn BBeeoowwuullff ddiiffffrree--tt--iill dd''uunn CCOOWW ??

  Le laboraroire d'informatique dcrit plus haut est un exemple parfait
  d'un cluster de stations (COW). Qu'est-ce qui rend donc Beowulf si
  spcial et en quoi diffre-t-il d'un COW ? En ralit il n'y a pas
  beaucoup de diffrence, mais un Beowulf a quelques caractristiques
  uniques. La premire est que dans la plupart des cas, les noeuds
  clients dans un cluster Beowulf n'ont pas de clavier, de souris, de
  carte graphique ni de moniteur. Tous les accs aux noeuds clients sont
  faits par une connection distante du noeud serveur, un noeud ddi 
  une console, ou une console srie. Cela parce qu'il n'y a aucun besoin
  pour un noeud client d'accder  des machines en dehors du cluster, ni
  pour des machines en dehors du cluster d'accder  des noeuds clients
  directement; c'est une pratique habituelle que les noeuds clients
  utilisent des adresses IP prives comme les plages d'adresses
  10.0.0.0/8 ou 192.168.0.0/16 (RFC 1918
  http://www.alternic.net/rfcs/1900/rfc1918.txt.html). D'habitude la
  seule machine qui est aussi connecte au monde externe en utilisant
  une seconde carte rseau est le noeud serveur. La faon la plus
  habituelle d'accder au systme est soit d'utiliser la console du
  serveur directement, soit de faire un telnet ou un login distant
  (rlogin) sur le noeud serveur d'une station personnelle. Une fois sur
  celui-ci, les utilisateurs peuvent diter et compiler leur code, et
  aussi distribuer les tches sur tous les noeuds du cluster. Dans la
  plupart des cas, les COW sont utilises pour des calculs parallles la
  nuit et les week-ends, quand les stations ne sont pas utilises
  pendant les journes de travail, utilisant ainsi les priodes de
  cycles libres des CPU. D'autre part, le Beowulf est une machine ddie
  au calcul parallle, et optimise pour cette tche. Il donne aussi un
  meilleur rapport prix/performance puisqu'il est constitu de
  composants grand public et qu'il tourne principalement  partir de
  logiciels libres. Beowulf donne aussi davantage l'image d'une seule
  machine, ce qui permet aux utilisateurs de voir le cluster Beowulf
  comme une seule station de calcul.



  44..  CCoonncceeppttiioonn dduu SSyyssttmmee

  Avant d'acheter du matriel, il serait de bon aloi de considrer le
  design de votre systme. Il y a deux approches matrielles qui sont
  impliques dans le design d'un systme Beowulf: le type de noeuds ou
  d'ordinateurs que vous allez utiliser, et la mthode que vous allez
  utiliser pour vous connecter aux noeuds d'ordinateurs. Il n'y a qu'une
  seule approche logicielle qui puisse affecter votre choix matriel: la
  librairie de communication ou API. Une discussion plus dtaille sur
  le matriel et les logiciels de communication est fournie plus loin
  dans ce document.

  Alors que le nombre de choix n'est pas grand, il y a des
  considrations de conception qui doivent tre prises pour la
  construction d'un cluster Beowulf. La science (ou art) de la
  "programmation parallle" tant l'objet de nombreuses interprtations,
  une introduction est fournie plus bas. Si vous ne voulez pas lire les
  connaissances de base, vous pouvez survoler cette section, mais nous
  vous conseillons de lire la section ``Convenance'' avant tout choix
  dfninitif de matriel.


  44..11..  BBrreeffss rraappppeellss ssuurr llaa pprrooggrraammmmaattiioonn ppaarraallllllee

  Cette section fournit des informations gnrales sur les concepts de
  la programmation parallle. Ceci n'est PAS exhaustif, ce n'est pas une
  description complte de la programmation parallle ou de sa
  technologie. C'est une brve description des enjeux qui peuvent
  influer fortement sur le concepteur d'un Beowulf, ou sur son
  utilisateur.


  Lorsque vous dciderez de construire votre Beowulf, de nombreux points
  dcrits plus bas deviendront importants dans votre processus de choix.
  A cause de la nature de ses "composants", un Superordinateur Beowulf
  ncessite de prendre de nombreux facteurs en compte, car maintenant
  ils dpendent de nous. En gnral, il n'est pas du tout difficile de
  comprendre les objectifs impliqus dans la programmation parallle.
  D'ailleurs, une fois que ces objectifs sont compris, vos attentes
  seront plus ralistes, et le succs plus probable. Contrairement au
  "monde squentiel", o la vitesse du processeur est considre comme
  le seul facteur important, la vitesse des processeurs dans le "monde
  parallle" n'est que l'un des paramtres qui dtermineront les
  performances et l'efficacit du systme dans son ensemble.



  44..22..  LLeess mmtthhooddeess ddee pprrooggrraammmmaattiioonn ppaarraallllllee

  La programmation parallle peut prendre plusieurs formes. Du point de
  vue de l'utilisateur, il est important de tenir compte des avantages
  et inconvnients de chaque mthodologie. La section suivante tente de
  fournir quelques aperus sur les mthodes de programmation parallle
  et indique o la machine Beowulf fait dfaut dans ce continuum.


  44..22..11..  PPoouurrqquuooii pplluuss dd''uunn CCPPUU ??

  Rpondre  cette question est important. Utiliser 8 CPU pour lancer un
  traitement de texte sonne comme "trop inutile" -- et ce l'est. Et
  qu'en est-il pour un serveur web, une base de donnes, un programme de
  ray-tracing, ou un planificateur de projets ? Peut-tre plus de CPU
  peuvent-ils amliorer les performances. Mais qu'en est-il de
  simulations plus complexes, de la dynamique des fluides, ou d'une
  application de Fouille de Donnes (Data Mining) ? Des CPU
  supplmentaires sont absolument ncessaires dans ces situations.
  D'ailleurs, de multiples CPU sont utiliss pour rsoudre de plus en
  plus de problmes.

  La question suivante est habituellement: "Pourquoi ai-je besoin de
  deux ou quatre CPU ? Je n'ai qu' attendre le mga super rapide
  processeur 986." Il y a de nombreuses raisons:

  1. Avec l'utilisation de systmes d'exploitations multi-tches, il est
     possible de faire plusieurs choses en mme temps. Cela est un
     "paralllisme" naturel qui est exploit par plus d'un CPU de bas
     prix.

  2. La vitesse des processeurs double tous les 18 mois mais qu'en est-
     il de la vitesse de la mmoire ? Malheureusement, celle-ci
     n'augmente pas aussi vite que celle des processeurs. Gardez 
     l'esprit que beaucoup d'applications ont besoin de mmoire autre
     que celle du cache processeur et de l'accs disque. Faire les
     choses en parallle est une faon de contourner ces limitations.

  3. Les prdictions indiquent que la vitesse des processeurs ne
     continuera pas  doubler tous les 18 mois aprs l'an 2005. Il y a
     divers obstacles  surmonter pour maintenir ce rythme.

  4. Suivant l'application, la programmation parallle peut acclrer
     les choses de 2  500 fois (et mme plus dans certains cas). De
     telles performances ne sont pas disponibles sur un seul processeur.
     Mme les Superordinateurs qui utilisaient  un moment un seul
     processeur spcialis trs rapide sont maintenant constitus de
     nombreux CPU plus banals.

  Si vous avez besoin de vitesse --  cause d'un problme li au calcul
  et/ou aux entres/sorties --, il vaut la peine de considrer
  l'approche parallle.  Comme le calcul parallle est implment selon
  de nombreuses voies, rsoudre votre problme en parallle ncessitera
  de prendre quelques dcisions importantes. Ces dcisions peuvent
  affecter dramatiquement la protabilit, la performance, et le cot de
  votre application.

  Avant d'tre par trop technique, regardons un vrai "problme de calcul
  parallle" en utilisant un exemple qui nous est familier: faire la
  queue  une caisse.


  44..22..22..  LLaa ""ccaaiissssee"" eenn pprrooggrraammmmaattiioonn ppaarraallllllee

  Considrons un grand magasin avec 8 caisses regroupes devant le
  magasin. Imaginons que chaque caisse est un CPU et chaque client un
  programme informatique. La taille du programme (quantit de calcul)
  est la taille de la commande de chaque client. Les analogies suivantes
  peuvent tre utilises pour illustrer les concepts de la programmation
  parallle:


  44..22..22..11..  SSyyssttmmeess dd''eexxppllooiittaattiioonn MMoonnoo--TTcchhee::

  Une caisse ouverte (et en service) qui ne peut traiter qu'un client 
  la fois.

  Exemple en Informatique : MS DOS



  44..22..22..22..  SSyyssttmmeess dd''eexxppllooiittaattiioonn MMuullttii--TTcchheess::

  Une caisse ouverte, mais maintenant nous pouvons traiter une partie de
  chaque commande  un instant donn, aller  la personne suivante et
  traiter une partie de sa commande. Tout le monde "semble" avancer dans
  la queue en mme temps, mais s'il n'y a personne dans la queue, vous
  serez servi plus vite.

  Exemple en Informatique : UNIX, NT avec un seul CPU


  44..22..22..33..  SSyyssttmmeess dd''eexxppllooiittaattiioonn MMuullttii--TTcchheess aavveecc pplluussiieeuurrss CCPPUU::

  Maintenant on ouvre plusieurs caisses dans le magasin. Chaque commande
  peut tre traite par une caisse diffrente et la queue peut avancer
  plus vite.  Ceci est appel SMP - Gestion Multiple Symtrique
  (Symmetric Multi-processing).  Mme s'il y a plus de caisses ouvertes,
  vous n'avancerez pas plus vite dans la queue que s'il n'y avait qu'une
  seule caisse.

  Exemple en Informatique : UNIX, NT avec plusieurs CPU



  44..22..22..44..  SSoouuss--ttcchheess ((TThhrreeaaddss)) ssuurr lleess aauuttrreess CCPPUU dd''uunn SSyyssttmmee
  dd''eexxppllooiittaattiioonn MMuullttii--TTcchheess::

  Si vous "sparez" les objets de votre commande, vous pouvez tre
  capable d'avancer plus vite en utilisant plusieurs caisses en mme
  temps. D'abord, nous postulons que vous achetez une grande quantit
  d'objets, parce que le temps que vous investirez pour "sparer" votre
  commande doit tre regagn en utilisant plusieurs caisses. En thorie,
  vous devriez tre capables de vous dplacer dans la queue "n" fois
  plus vite qu'avant, o "n" est le nombre de caisses. Quand les
  caissiers ont besoin de faire des sous-totaux, ils peuvent changer
  rapidement les informations visuellement et en discutant avec toutes
  les autres caisses "locales". Ils peuvent aussi aller chercher
  directement dans les registres des autres caisses pour trouver les
  informations dont ils ont besoin pour travailler plus vite. La limite
  tant le nombre de caisses qu'un magasin peut effectivement installer.

  La loi de Amdals montre que l'acclration de l'application est lie 
  la portion squentielle la plus lente excute par le programme (NdT:
  i.e. majore par la tche la plus lente).

  Exemple en Informatique : UNIX ou NT avec plusieurs CPU sur la mme
  carte-mre avec des programmes multi-threads.



  44..22..22..55..  pplluussiieeuurrss CCPPUU:: EEnnvvooyyeerr ddeess mmeessssaaggeess ssuurr ddeess SSyyssttmmeess
  dd''eexxppllooiittaattiioonn MMuullttii--TTcchheess aavveecc

  De faon  amliorer la performance, la Direction ajoute 8 caisses 
  l'arrire du magasin. Puisque les nouvelles caisses sont loin du
  devant du magasin, les caissiers doivent tlphoner pour envoyer leurs
  sous-totaux vers celui-ci. La distance ajoute un dlai supplmentaire
  (en temps) dans la communication entre caissiers, mais si la
  communication est minimise, cela ne pose pas de problme. Si vous
  avez vraiment une grosse commande, une qui ncessite toutes les
  caisses, alors comme avant votre vitesse peut tre amliore en
  utilisant toutes les caisses en mme temps, le temps sopplmentaire
  devant tre pris en compte. Dans certains cas, le magasin peut n'avoir
  que des caisses (ou des lots de caisses) localiss dans tout le
  magasin : chaque caisse (ou lot) doit communiquer par tlphone.
  Puisque tous les caissiers peuvent discutter par tlphone, leur
  emplacement importe peu.

  Exemple en Informatique : Une ou plusieurs copies d'UNIX ou NT avec
  plusieurs CPU sur la mme, ou diffrentes cartes-mres communiquant
  par messages.

  Les scnarios prcdents, mme s'ils ne sont pas exacts, sont une
  bonne reprsentation des contraintes qui agissent sur les systmes
  parallles.  Contrairement aux machines avec un seul CPU (ou caisse),
  la communication est importante.


  44..33..  AArrcchhiitteeccttuurreess ppoouurr llee ccaallccuull ppaarraallllllee

  Les mthodes et architectures habituelles de la programmation
  parallle sont reprsentes ci-dessous. Mme si cette description
  n'est en aucun cas exhaustive, elle est suffisante pour comprendre les
  impratifs de base dans la conception d'un Beowulf.


  44..33..11..  AArrcchhiitteeccttuurreess MMaattrriieelllleess


  Il y a typiquement deux faons d'assembler un ordinateur parallle:


  1. La mmoire locale des machines qui communiquent par messages
     (Clusters Beowulf)

  2. Les machines  mmoire partage qui communiquent  travers la
     mmoire (machines SMP)

  Un Beowulf typique est une collection de machines mono-processeurs
  connectes utilisant un rseau Ethernet rapide, et qui est ainsi une
  machine  mmoire locale. Une machine  4 voies SMP est une machine 
  mmoire partage et peut tre utilise pour du calcul parallle -- les
  applications parallles communiquant via la mmoire partage. Comme
  pour l'analogie du grand magasin, les machines  mmoire locale (donc
   caisse individuelle) peuvent tre scalairises jusqu' un grand
  nombre de CPU ; en revanche, le nombre de CPU que les machines 
  mmoire partage peuvent avoir (le nombre de caisses que vous pouvez
  placer en un seul endroit) peut se trouver limit  cause de
  l'utilisation (et/ou de la vitesse) de la mmoire.

  Il est toutefois possible de connecter des machines  mmoire partage
  pour crer une machine  mmoire partage "hybride". Ces machines
  hybrides "ressemblent"  une grosse machine SMP pour l'utilisateur et
  sont souvent appeles des machines NUMA (accs mmoire non uniforme)
  parce que la mmoire globale vue par le programmeur et partage par
  tous les CPU peut avoir diffrents temps d'accs. A un certain niveau
  d'ailleurs, une machine NUMA doit "passer des messages" entre les
  groupes de mmoires partages.

  Il est aussi possible de connecter des machines SMP en tant que noeuds
  de mmoire locale. Typiquement, les cartes-mres de CLASSE I ont soit
  2 ou 4 CPU et sont souvent utilises comme moyens pour rduire le cot
  global du systme.  L'arrangeur (scheduler) interne de Linux dtermine
  combien de ces CPU sont partags. L'utilisateur ne peut ( ce jour)
  affecter une tche  un processeur SMP spcifique. Cet utilisateur
  peut quand mme dmarrer deux processus indpendants ou un programme
  multi-threads et s'attendre  voir une amlioration de performance par
  rapport  un systme  simple CPU.




  44..33..22..  AArrcchhiitteeccttuurreess LLooggiicciieelllleess eett AAPPII

  Il y a basiquement deux faons d'"exprimer" la concurrence dans un
  programme:

  1. En envoyant des Messages entre les processeurs

  2. En utilisant les threads du systme d'exploitation (natives)

  D'autres mthodes existent, mais celles-l sont le plus gnralement
  employes. Il est important de se souvenir que l'expression de
  concurrence n'est pas ncessairement contrle par la couche
  matrielle. Les Messages et les Threads peuvent tre implments sur
  des SMPn NUMA-SMP, et clusters -- mme si, comme expliqu ci-dessous,
  l'efficacit et la portabilit sont des facteurs importants.



  44..33..22..11..  MMeessssaaggeess

  Historiquement, la technologie de passage de messages refltait les
  dbuts des ordinateurs parallles  mmoire locale. Les messages
  ncessitent la copie des donnes tandis que les Threads utilisent des
  donnes  la place. Le temps de latence et la vitesse  laquelle les
  messages peuvent tre copis sont les facteurs limitants des modles
  de passage de messages. Un message est assez simple: des donnes et un
  processeur de destination. Des API de passage de messages rpandues
  sont entre autres PVM ou MPI. Le passage de Messages peut tre
  implment avec efficacit en utilisant ensemble des Threads et des
  Messages entre SMP et machines en cluster.  L'avantage d'utiliser les
  messages sur une machine SMP, par rapport aux Threads, est que si vous
  dcidez d'utiliser des clusters dans le futur, il est facile d'ajouter
  des machines ou de scalairiser vos applications.


  44..33..22..22..  TThhrreeaaddss

  Les Threads ont t dvelopps sur les systmes d'exploitation parce
  que la mmoire partage des SMP (moutiprocessorage symmtrique)
  permettait une communication trs rapide et une synchronisation de la
  mmoire partage entre les parties d'un programme. Les Threads
  marchent bien sur les systmes SMP parce que la communication a lieu 
  travers la mmoire partage. Pour cette raison, l'utilisateur doit
  isoler les donnes locales des donnes globales, sinon les programmes
  ne fonctionneront pas correctement.  Cela est en contraste avec les
  messages: une grande quantit de copie peut tre limine avec les
  threads car les donnes sont partages entre les processus (threads).
  Linux implmente les Threads POSIX. Le problme avec les Threads vient
  du fait qu'il est difficile de les tendre au-del d'une machine SMP,
  et, comme les donnes sont partages entre les CPU, la gestion de la
  cohrence du cache peut contribuer  le charger. Etendre les Threads
  au-del des limites des performances des SMP ncessite la technologie
  NUMA qui est chre et n'est pas nativement supporte par Linux.
  Implmenter des Threads par dessus les messages a t fait
  ((http://syntron.com/ptools/ptools_pg.htm)), mais les Threads sont
  souvent inefficients une fois implments en utilisant des messages.

  On peut rsumer ainsi les performances:








            performance        performance
            machine SMP     cluster de machines  scalabilit
            -----------     -------------------  -----------
  messages     bonne             meilleure        meilleure

  threads    meilleure           mauvaise*        mauvaise*

  * ncessite une technologie NUMA coteuse.




  44..33..33..  AArrcchhiitteeccttuurree ddeess AApppplliiccaattiioonnss

  Pour excuter une application en parallle sur des CPU multiples,
  celle-ci doit tre explicitement dcoupe en parties concurrentes. Une
  application standard mono-CPU ne s'excutera pas plus rapidement mme
  si elle est excute sur une machine multi-processeurs. Certains
  outils et compilateurs peuvent dcouper les programmesn mais la
  paralllisation n'est pas une opration "plug and play".  Suivant
  l'application, la paralllisation peut tre facile, extrmement
  difficile, voire impossible suivant les contraintes de l'algorithme.

  Avant de parler des besoins applicatifs, il nous faut introduire le
  concept de Convenance (Suitability).


  44..44..  CCoonnvveennaannccee

  Beaucoup de questions au sujet du calcul parallle ont la mme
  rponse:

  "Cela dpend entirement de l'application."

  Avant de passer directement aux opportunits, il y a une distinction
  trs importante qui doit tre faite: la diffrence entre CONCURRENT et
  PARALLELE.  Pour clarifier cette discussion, nous allons dfinir ces
  deux termes ainsi:

  les parties CONCURRENTES d'un programme sont celles qui peuvent tre
  calcules indpendamment.

  Les parties PARALLELES d'un programme sont celles qui sont excutes
  sur des lments de calculs au mme moment.

  La distinction est trs importante, parce que la CONCURRENCE est une
  proprit d'un programme et l'efficacit en PARALLELISME est une
  proprit de la machine.  Idalement, l'excution en parallle doit
  produire des performances plus grandes. Le facteur limitant les
  performances en parallle est la vitesse de communication et le temps
  de latence entre les noeuds de calcul. (Le temps de latence existe
  aussi dans les applications TMP threades  cause de la cohrence du
  cache). De nombreux tests de performances communs sont hautement
  parallles, et ainsi la communication et le temps de latence ne sont
  pas les points importants. Ce type de problme peut tre appel
  "videmment parallle".  D'autres applications ne sont pas si simples
  et excuter des parties CONCURRENTES du programme en PARALLELE peut
  faire en sorte que le programme fonctionne plus lentement, et ainsi
  dcaler toute performance de gain dans d'autres parties CONCURRENTES
  du programme. En termes plus simples, le cot en temps de
  communication doit en ptir au profit de celui gagn en temps de
  calcul, sinon l'excution PARALLELE des parties CONCURRENTES est
  inefficace.

  La tche du programmeur est de dterminer quelles parties CONCURRENTES
  le programmeur DOIT excuter en PARALLELE et pour quelles parties il
  NE DOIT PAS le faire. Sa rponse dterminera l'EFFICACITE de
  l'application. Le graphe suivant rsume la situation pour le
  programmeur:





           | *
           | *
           | *
   % des   | *
   appli-  |  *
   cations |  *
           |  *
           |  *
           |    *
           |     *
           |      *
           |        ****
           |            ****
           |                ********************
           +-----------------------------------
            temps de communication/temps de calcul



  Dans un ordinateur parallle parfait, le rapport communication/calcul
  devrait tre gal et tout ce qui est CONCURRENT pourrait tre
  implment en PARALLELE.  Malheureusement, les vrais ordinateurs
  parallles, incluant les machines  mmoire partage, sont sujets aux
  effets dcrits dans ce graphe. En concevant un Beowulf, l'utilisateur
  devrait garder celui-ci en tte parce que la performance dpend du
  rapport entre le temps de communication et le temps de calcul pour un
  ORDINATEUR PARALLELE SPECIFIQUE. Les applications peuvent tre
  portables entre les ordinateurs parallles, mais il n'y a aucune
  garantie qu'elles seront efficaces sur une plateforme diffrente.

  EN GENERAL, IL N'EXISTE PAS DE PROGRAMME PORTABLE EFFICACE EN
  PARALLELE

  Il y a encore une autre consquence au graphe prcdent. Puisque
  l'efficacit dpend du rapport communication/calcul, changer juste un
  composant du rapport ne signifie pas ncessairement qu'une application
  s'excutera plus rapidement. Un changement de vitesse processeur, en
  gardant la mme vitesse de communication, peut avoir des effets
  inattendus sur votre programme. Par exemple, doubler ou tripler la
  vitesse du processeur, en gardant la mme vitesse de communication,
  peut maintenant rendre des parties de votre programme qui sont
  efficaces en PARALLELE, plus efficaces si elles taient excutes
  SEQUENTIELLEMENT. Cela dit, il se peut qu'il soit plus rapide
  maintenant d'excuter les parties qui taient avant PARALLELES en tant
  que SEQUENTIELLES. D'autant plus qu'excuter des parties inefficaces
  en PARALLELE empchera votre application d'atteindre sa vitesse
  maximale. Ainsi, en ajoutant un processeur plus rapide, vous avez
  peut-tre ralenti votre application (vous enpchez votre nouveau CPU
  de fonctionner  sa vitesse maximale pour cette application).

  UPGRADER VERS UN CPU PLUS RAPIDE PEUT REELLEMENT RALENTIR VOTRE
  APPLICATION

  Donc, en conclusion, pour savoir si oui ou non vous pouvez utiliser un
  environnement matriel parallle, vous devez avoir un bon aperu des
  capacits d'une machine particulire pour votre application. Vous
  devez tenir compte de beaucoup de facteurs: vitesse de la CPU,
  compilateur, API de passage de messages, rseau... Notez que se
  contenter d'optimiser une application ne donne pas toutes les
  informations. Vous pouvez isoler une lourde partie de calcul de votre
  programme, mais ne pas connatre son cot au niveau de la
  communication. Il se peut que pour un certain systme, le cot de
  communication ne rende pas efficace de parallliser ce code.


  Une note finale sur une erreur commune: on dit souvent qu'"un
  programme est PARALLELISE", mais en ralit seules les parties
  CONCURRENTES ont t identifies. Pour toutes les raisons prcdentes,
  le programme n'est pas PARALLELISE. Une PARALLELISATION efficace est
  une proprit de la machine.



  44..55..  EEccrriirree eett ppoorrtteerr ddeess llooggiicciieellss ppaarraalllllleess

  A partir du mmoment o vous avez dcid de concevoir et de construire
  un Beowulf, considrer un instant votre application en accord avec les
  observations prcdentes est une bonne ide.

  En gnral, vous pouvez faire deux choses:

  1. Y aller et construire un Beowulf CLASSE I et aprs y ajuster votre
     application. Ou excuter des applications parallles que vous savez
     fonctionner sur votre Beowulf (mais attention  la portabilit et 
     l'efficacit en accord avec les informations cites ci-dessus).

  2. Examiner les applications dont vous avez besoin sur votre Beowulf,
     et faire une estimation quant au type de matriel et de logiciels
     qu'il vous faut.

  Dans chaque cas, vous devrez considrer les besoins en efficacit.  En
  gnral, il y a trois choses  faire:

  1. Dterminer les parties concurrentes de votre programme

  2. Estimer le paralllisme efficacement

  3. Dcrire les parties concurrentes de votre programme

  Examinons-les successivement:


  44..55..11..  DDtteerrmmiinneerr lleess ppaarrttiieess ccoonnccuurrrreenntteess ddee vvoottrree pprrooggrraammmmee

  Cette tape est couvent considre comme "parallliser votre
  programme".  Les dcisions de paralllisation seront faites  l'tape
  2. Dans cette tape, vous avez besoin de dterminer les liens et les
  besoins dans les donnes.

  D'un point de vue pratique, les applications peuvent prsenter deux
  types de concurrence: calcul (travaux numriques) et E/S (Bases de
  Donnes). Mme si dans de nombreux cas, la concurrence entre calculs
  et E/S est orthogonale, des applications ont besoin des deux. Des
  outils existants peuvent faire l'analyse de la concurrence sur des
  applications existantes. La plupart de ces outils sont conus pour le
  FORTRAN. Il y a deux raisons pour lesquelles le FORTRAN est utilis:
  historiquement, la majorit des applications gourmandes en calculs
  numriques taient crites en FORTRAN et c'tait donc plus facile 
  analyser. Si aucun de ces outils n'est disponible, alors cette tape
  peut tre quelque peu difficile pour des applications existantes.




  44..55..22..  EEssttiimmeerr llee ppaarraalllllliissmmee eeffffiiccaacceemmeenntt

  Sans l'aide d'outils, cette tape peut ncessiter un cycle de tests et
  erreurs, ou seulement de bons vieux rflexes bien duqus. Si vous
  avez une application spcifique en tte, essayez de dterminer la
  limite du CPU (lie au calcul) ou les limites des disques (lies aux
  E/S). Les spcifits de votre Beowulf peuvent beaucoup dpendre de vos
  besoins. Par exemple, un problme li au calcul peut ne ncessiter
  qu'un petit nombre de CPU trs rapides et un rseau trs rapide 
  faible temps de latence, tandis qu'un problme li aux E/S peut mieux
  travailler avec des CPU plus lents et un Ethernet rapide.

  Cette recommandation arrive souvent comme une surprise pour beaucoup,
  la croyance habituelle tant que plus le processeur est rapide, mieux
  c'est.  Mais cela n'est vrai que si vous avez un budget illimit: les
  vrais systmes peuvent avoir des contraintes de cots qui doivent tre
  optimises.  Pour les problmes lis aux E/S, il existe une loi peu
  connue (appele la loi de Eadline-Dedkov) qui est assez utile:

  Soient deux machines parallles avec le mme index de performance CPU
  cumule, celle qui a les processeurs les plus lents (et probablement
  un rseau de communication interprocesseur plus lent) aura les
  meilleures performances pour des applications domines par les E/S.

  Mme si les preuves de cette rgle vont au-del de ce document, vous
  pouvez trouver intressant de lire l'article _P_e_r_f_o_r_m_a_n_c_e
  _C_o_n_s_i_d_e_r_a_t_i_o_n_s _f_o_r _I_/_O_-_D_o_m_i_n_a_n_t _A_p_p_l_i_c_a_t_i_o_n_s _o_n _P_a_r_a_l_l_e_l _C_o_m_p_u_t_e_r_s
  (format Postscript 109K) (ftp://www.plogic.com/pub/papers/exs-pap6.ps)

  Une fois que vous aurez dtermin quel type de concurrence vous avez
  dans votre application, vous devrez estimer  quel point elle sera
  efficace en parallle. Voir la Section ``Logiciels'' pour une
  description des outils Logiciels.

  En l'absence d'outils, il vous faudra peut-tre improviser votre
  chemin lors de cette tape. Si une boucle lie aux calculs est mesure
  en minutes et que les donnes peuvent tre transfres en secondes,
  alors c'est un bon candidat pour la paralllisation. Mais souvenez-
  vous que si vous prenez une boucle de 16 minutes et la coupez en 32
  morceaux, et que vos transferts de donnes ont besoin de quelques
  secondes par partie, alors cela devient plus rduit en termes de
  performances. Vous atteindrez un point de retours en diminution.


  44..55..33..  DDccrriirree lleess ppaarrttiieess ccoonnccuurrrreenntteess ddee vvoottrree pprrooggrraammmmee

  Il y a plusieurs faons de dcrire les parties concurrentes de votre
  programme:

  1. L'excution parallle explicite

  2. L'excution parallle implicite

  La diffrence principale entre les deux est que le paralllisme
  explicite est dtermin parl'utilisateur, alors que le paralllisme
  implicite est dtermin par le compilateur.


  44..55..33..11..  LLeess mmtthhooddeess eexxpplliicciitteess

  Il y a principalement des mthodes o l'utilisateur peut modifier le
  code source spcifique pour une machine parallle. L'utilisateur doit
  soit ajouter des messages en utilisant PVM ou MPI, soit ajouter des
  threads POSIX. (Souvenez vous que les threads ne peuvent se dplacer
  entre les cartes-mres SMP).

  Les mthodes explicites tendent  tre les plus difficiles 
  implmenter et  dboguer. Les utilisateurs ajoutent typiquement des
  appels de fonctions dans le code source FORTRAN 77 standard ou C/C++.
  La librairie MPI a ajout des fonctions pour rendre certaines mthodes
  parallles plus faciles  implmenter (i.e. les fonctions
  scatter/gather). De plus, il est aussi possible d'ajouter des
  librairies standard qui ont t crites pour des ordinateurs
  parallles.  Souvenez-vous quand mme du compromis
  efficacit/portabilit.


  Pour des raisons historiques, beaucoup d'applications gourmandes en
  calculs sont crites en FORTRAN. Pour cette raison, FORTRAN dispose du
  plus grand nombres de supports pour le calcul parallle (outils,
  librairies ...). De nombreux programmeurs utilisent maintenant C ou
  rcrivent leurs applications FORTRAN existantes en C, avec l'ide que
  C permettra une excution plus rapide.  Mme si cela est vrai puisque
  C est la chose la plus proche du code machine universel, il a quelques
  inconvnients majeurs. L'utilisation de pointeurs en C rend la
  dtermination des dpendances entre donnes et l'analyse automatique
  des pointeurs extrmement difficiles. Si vous avez des applications
  existantes en FORTRAN et que vous voudrez les parallliser dans le
  futur - NE LES CONVERTISSEZ PAS EN C !


  44..55..33..22..  MMtthhooddeess IImmpplliicciitteess

  Les mthodes implicites sont celles dans lesquelles l'utilisateur
  abandonne quelques dcisions de paralllisation (ou toutes) au
  compilateur. Par exemple le FORTRAN 90, High Performance FORTRAN
  (HPF), Bulk Synchronous Parallel (BSP), et toute une srie de mthodes
  qui sont en cours de dveloppement.

  Les mthodes implicites ncessitent de la part de l'utilisateur des
  informations concernant la nature concurrente de leur application,
  mais le compilateur prendra quand mme beaucoup de dcicions sur la
  manire d'excuter cette concurrence en parallle. Ces mthodes
  procurent un niveau de portabilit et d'efficacit, mais il n'y a pas
  de "meilleure faon" de dcrire un problme concurrent pour un
  ordinateur parallle.


  55..  RReessssoouurrcceess BBeeoowwuullff



  55..11..  PPooiinnttss ddee ddppaarrtt



    Liste de diffusion US Beowulf. Pour s'inscrire, envoyer un courriel
      beowulf-request@cesdis.gsfc.nasa.gov avec le mot _s_u_b_s_c_r_i_b_e dans
     le corps du message.

    Homepage Beowulf http://www.beowulf.org

    Extreme Linux http://www.extremelinux.org

    Extreme Linux Software pour Red Hat http://www.redhat.com/extreme



  55..22..  DDooccuummeennttaattiioonn



    La dernire version du Beowulf HOWTO en
     Anglaishttp://www.sci.usq.edu.au/staff/jacek/beowulf.

    La dernire version du Beowulf HOWTO en Franaishttp://www.e-
     nef.com/linux/beowulf.

    Construire un systme Beowulf
     http://www.cacr.caltech.edu/beowulf/tutorial/building.html

    Les liens de Jacek sur Beowulf
     http://www.sci.usq.edu.au/staff/jacek/beowulf.

    Beowulf Installation and Administration HOWTO (DRAFT)
     http://www.sci.usq.edu.au/staff/jacek/beowulf.

    Linux Parallel Processing HOWTO
     http://yara.ecn.purdue.edu/~pplinux/PPHOWTO/pphowto.html



  55..33..  PPuubblliiccaattiioonnss



    Chance Reschke, Thomas Sterling, Daniel Ridge, Daniel Savarese,
     Donald Becker, and Phillip Merkey _A _D_e_s_i_g_n _S_t_u_d_y _o_f _A_l_t_e_r_n_a_t_i_v_e
     _N_e_t_w_o_r_k _T_o_p_o_l_o_g_i_e_s _f_o_r _t_h_e _B_e_o_w_u_l_f _P_a_r_a_l_l_e_l _W_o_r_k_s_t_a_t_i_o_n.
     Proceedings Fifth IEEE International Symposium on High Performance
     Distributed Computing, 1996.
     http://www.beowulf.org/papers/HPDC96/hpdc96.html


    Daniel Ridge, Donald Becker, Phillip Merkey, Thomas Sterling
     Becker, and Phillip Merkey. _H_a_r_n_e_s_s_i_n_g _t_h_e _P_o_w_e_r _o_f _P_a_r_a_l_l_e_l_i_s_m _i_n
     _a _P_i_l_e_-_o_f_-_P_C_s. Proceedings, IEEE Aerospace, 1997.
     http://www.beowulf.org/papers/AA97/aa97.ps


    Thomas Sterling, Donald J. Becker, Daniel Savarese, Michael R.
     Berry, and Chance Res. _A_c_h_i_e_v_i_n_g _a _B_a_l_a_n_c_e_d _L_o_w_-_C_o_s_t _A_r_c_h_i_t_e_c_t_u_r_e
     _f_o_r _M_a_s_s _S_t_o_r_a_g_e _M_a_n_a_g_e_m_e_n_t _t_h_r_o_u_g_h _M_u_l_t_i_p_l_e _F_a_s_t _E_t_h_e_r_n_e_t _C_h_a_n_n_e_l_s
     _o_n _t_h_e _B_e_o_w_u_l_f _P_a_r_a_l_l_e_l _W_o_r_k_s_t_a_t_i_o_n.  Proceedings, International
     Parallel Processing Symposium, 1996.
     http://www.beowulf.org/papers/IPPS96/ipps96.html


    Donald J. Becker, Thomas Sterling, Daniel Savarese, Bruce Fryxell,
     Kevin Olson. _C_o_m_m_u_n_i_c_a_t_i_o_n _O_v_e_r_h_e_a_d _f_o_r _S_p_a_c_e _S_c_i_e_n_c_e _A_p_p_l_i_c_a_t_i_o_n_s
     _o_n _t_h_e _B_e_o_w_u_l_f _P_a_r_a_l_l_e_l _W_o_r_k_s_t_a_t_i_o_n.  Proceedings,High Performance
     and Distributed Computing, 1995.
     http://www.beowulf.org/papers/HPDC95/hpdc95.html



    Donald J. Becker, Thomas Sterling, Daniel Savarese, John E.
     Dorband, Udaya A. Ranawak, Charles V. Packer. _B_E_O_W_U_L_F_: _A _P_A_R_A_L_L_E_L
     _W_O_R_K_S_T_A_T_I_O_N _F_O_R _S_C_I_E_N_T_I_F_I_C _C_O_M_P_U_T_A_T_I_O_N. Proceedings, International
     Conference on Parallel Processing, 95.
     http://www.beowulf.org/papers/ICPP95/icpp95.html

    Publications sur le site de Beowulf
     http://www.beowulf.org/papers/papers.html




  55..44..  LLooggiicciieellss


    PVM - Parallel Virtual Machine/Machine Parallle Virtuelle
     http://www.epm.ornl.gov/pvm/pvm_home.html



    LAM/MPI - Local Area Multicomputer / Message Passing Interface
     Multi-Ordinateurs locaux  / Interface de Transmission de Messages
     http://www.mpi.nd.edu/lam

    BERT77 - outil de conversion FORTRAN
     http://www.plogic.com/bert.html

    logiciels Beowulf de la page du Projet Beowulf
     http://beowulf.gsfc.nasa.gov/software/software.html

    Jacek's Beowulf-outils ftp://ftp.sci.usq.edu.au/pub/jacek/beowulf-
     utils

    bWatch - logiciel de surveillance de
     clusterhttp://www.sci.usq.edu.au/staff/jacek/bWatch




  55..55..  MMaacchhiinneess BBeeoowwuullff


    Avalon consiste en 140 processeurs Alpha, 36 Go de RAM, et est
     probablement la machine Beowulf la plus rapide, allant  47.7
     Gflops et classe 114me sur la liste du Top 500.
     http://swift.lanl.gov/avalon/

    Megalon-A Massively PArallel CompuTer Resource (MPACTR) consiste en
     14 quadri CPU Pentium Pro 200 noeuds, et 14 Go de RAM.
     http://megalon.ca.sandia.gov/description.html

    theHIVE - Highly-parallel Integrated Virtual Environment est un
     autre Superordinateur Beowulf rapide. theHIVE est de 64 noeuds, une
     machine de 128 CPU avec un total de 4 Go de RAM.
     http://newton.gsfc.nasa.gov/thehive/

    Topcat est une machine beaucoup plus petite, constitue de 16 CPU
     et 1.2 Go de RAM. http://www.sci.usq.edu.au/staff/jacek/topcat

    MAGI cluster -- c'est un trs bon site avec de nombreux liens de
     qualit. http://noel.feld.cvut.cz/magi/




  55..66..  DD''aauuttrreess SSiitteess IInnttrreessssaannttss



    Linux SMPhttp://www.linux.org.uk/SMP/title.html

    Paralogic - Achetez un Beowulf http://www.plogic.com


  55..77..  HHiissttooiirree



    Lgendes - Beowulf  http://legends.dm.net/beowulf/index.html

    Les Aventures de Beowulf
     http://www.lnstar.com/literature/beowulf/beowulf.html


  66..  CCooddee SSoouurrccee


  66..11..  ssuumm..cc


  /* Jacek Radajewski jacek@usq.edu.au */
  /* 21/08/1998 */

  #include <stdio.h>
  #include <math.h>

  int main (void) {

    double result = 0.0;
    double number = 0.0;
    char string[80];


    while (scanf("%s", string) != EOF) {

      number = atof(string);
      result = result + number;
    }

    printf("%lf\n", result);

    return 0;

  }




  66..22..  ssiiggmmaassqqrrtt..cc

























  /* Jacek Radajewski jacek@usq.edu.au */
  /* 21/08/1998 */

  #include <stdio.h>
  #include <math.h>

  int main (int argc, char** argv) {

    long number1, number2, counter;
    double result;

    if (argc < 3) {
      printf ("usage : %s number1 number2\n",argv[0]);
      exit(1);
    } else {
      number1 = atol (argv[1]);
      number2 = atol (argv[2]);
      result = 0.0;
    }

    for (counter = number1; counter <= number2; counter++) {
      result = result + sqrt((double)counter);
    }

    printf("%lf\n", result);

    return 0;

  }





  66..33..  pprruunn..sshh































  #!/bin/bash
  # Jacek Radajewski jacek@usq.edu.au
  # 21/08/1998

  export SIGMASQRT=/home/staff/jacek/beowulf/HOWTO/example1/sigmasqrt

  # $OUTPUT doit tre un canal nomm (named pipe)
  # mkfifo output

  export OUTPUT=/home/staff/jacek/beowulf/HOWTO/example1/output

  rsh scilab01 $SIGMASQRT         1  50000000 > $OUTPUT < /dev/null&
  rsh scilab02 $SIGMASQRT  50000001 100000000 > $OUTPUT < /dev/null&
  rsh scilab03 $SIGMASQRT 100000001 150000000 > $OUTPUT < /dev/null&
  rsh scilab04 $SIGMASQRT 150000001 200000000 > $OUTPUT < /dev/null&
  rsh scilab05 $SIGMASQRT 200000001 250000000 > $OUTPUT < /dev/null&
  rsh scilab06 $SIGMASQRT 250000001 300000000 > $OUTPUT < /dev/null&
  rsh scilab07 $SIGMASQRT 300000001 350000000 > $OUTPUT < /dev/null&
  rsh scilab08 $SIGMASQRT 350000001 400000000 > $OUTPUT < /dev/null&
  rsh scilab09 $SIGMASQRT 400000001 450000000 > $OUTPUT < /dev/null&
  rsh scilab10 $SIGMASQRT 450000001 500000000 > $OUTPUT < /dev/null&
  rsh scilab11 $SIGMASQRT 500000001 550000000 > $OUTPUT < /dev/null&
  rsh scilab12 $SIGMASQRT 550000001 600000000 > $OUTPUT < /dev/null&
  rsh scilab13 $SIGMASQRT 600000001 650000000 > $OUTPUT < /dev/null&
  rsh scilab14 $SIGMASQRT 650000001 700000000 > $OUTPUT < /dev/null&
  rsh scilab15 $SIGMASQRT 700000001 750000000 > $OUTPUT < /dev/null&
  rsh scilab16 $SIGMASQRT 750000001 800000000 > $OUTPUT < /dev/null&
  rsh scilab17 $SIGMASQRT 800000001 850000000 > $OUTPUT < /dev/null&
  rsh scilab18 $SIGMASQRT 850000001 900000000 > $OUTPUT < /dev/null&
  rsh scilab19 $SIGMASQRT 900000001 950000000 > $OUTPUT < /dev/null&
  rsh scilab20 $SIGMASQRT 950000001 1000000000 > $OUTPUT < /dev/null&



































