Home

Rapport de Stage de DEA - Département Informatique

Contents

1. metteur de s assurer que le r cepteur sait qu un send est en attente En cas de non r ponse SECP conti nuera signaler le send en attente jusqu avoir un acquittement le pong du poing pong e RECP permet au r cepteur de signaler l metteur que la transaction est achev e et qu il peut signaler la compl tion du send De m me qu avec SECP il s agit d un ping pong et le r cepteur signalera la fin de transaction jusqu avoir un acquittement e BSCP est un sous ensemble de SLR P qui comporte le send et le receive e MICP est un protocole permettant de vider le r seau entre deux n uds suite une faute et de r utiliser les MI La figure 5 illustre les probl mes pouvant survenir dans une transaction les besoins qu ils impliquent pour pouvoir r cup rer sur l erreur et le sous protocole de SCP P qui assure cela La figure 6 illustre une transaction SCP P sans faute Le point important est que chaque tape est gard e par un accus de r ception ce qui permet de d tecter les pertes Le but de cette partie est de fournir un aper u du protocole SCP P pas de l expliquer dans le d tail Pour plus d informations sur SCP P se reporter au rapport de th se d Alexandre Feny AF A Al Al Al J yyy 5 J agag 3 e S jia S Bli S A 5 T T a a lt lt 2 SFCP 2 set E 5 D Bd R P Due i RECP Re u A Re u RFCp T Machine Machine emps source destination Fig
2. t retard ou perdu par un n ud congestionn alors on va r envoyer un message doublon alors qu il a d j t re u par le r cepteur Ceci va augmenter la congestion On a donc tout int r t utiliser un timeout lev On peut aussi songer faire augmenter ce d lai avec le nombre de tentatives de transmissions pour essayer de diminuer la congestion V 6 d Adaptativit Nous avons expliqu plus haut la n cessit d avoir un r seau non adaptatif Mais cela n est vrai que Re u Machine Machine source destination Temps Fig 15 R action du protocole de s curisation un r ordonnancement des paquets Le message arrive toujours destination mais au prix d une retransmission Emmanuel Dreyfus 33 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC dans une certaine mesure En effet un d sordonnancement des paquets sera trait comme une erreur et le syst me de num rotation des paquets va obliger les paquets arriver dans l ordre On peut donc tol rer une faible adaptativit la machine MPC ne fonctionnant que pendant les phases o le r seau se comporte de fa on FIFO La figure 15 donne un exemple de r action un r ordonnancement des paquets Il est vident que moins le r seau se comportera comme une FIFO plus on aura des erreurs et des retransmissions et moins les performances seront bonnes L utilisation de table
3. 1ko on obtient ceci Lecture de l entr e de LPE Prendre le bus PCI 1 cycle Phase d adresse 1 cycle Retournement du bus 1 cycle Lecture de l entr e 4x32 bits 4 cycles L cher le bus 1 cycle Lecture des donn es emmetre Prendre le bus PCI 1 cycle Phase d adresse 1 cycle Retournement du bus 1 cycle Lecture des donn es E n 4 x32 bits E n 4 cycles L cher le bus 1 cycle Total en cycles 12 E n 4 Avec un cycle PCI 30ns on obtient un d bit maximum de 1 message court envoy toutes les 30X 12 E n 4 nanosecondes et donc un accus de r ception renvoy tout les 30x 12 E n 4 nanose condes Supposons un paquet de 12 octets pour les accus s de r ception nous verrons plus loin les raisons qui conduisent a choisir cette taille La bande passante occup e en sens inverse est alors donn e par la for mule suivante 8 dack dack 56 octets taille des acquittements 1024 Tpcr 12 E7 Dutbs Thor 30ns dur e d un cycle PCI Ce d bit pour des petits messages est colossal environ 1 2Gb s Il faut cependant temp rer ce r sul tat il s agit d une majoration Cette formule suppose une situation id ale o le bus PCI est toujours dispo nible et o le logiciel est capable d ajouter des entr es de LPE aussi vite que le mat riel les consomme D apr s les diff rents tests r alis s sur la machine MPC 1 ED on sait bien que cette derni re sup position est erron e Sur la machine MP
4. a permis de d gager des besoins qui n taient pas vidents lors de la conception de PCIDDC e Il manque PCIDDC un m canisme permettant de g rer au niveau mat riel l utilisation de la carte FastHSL par plusieurs processus Ceci passe par l utilisation de plusieures LPE une par processus Des exp riences ont t faites dans ce sens avec RWU d velopp dans le projet NOE JLD e Les messages courts sont trop courts il faudrait pouvoir en faire des plus longs Les messages courts de MPC 1 font 8 octets ce qui est une forte limitation e MPC 1 ne pr voit pas de m canisme pour savoir de quel n ud vient un message On est oblig d utiliser une partie du champ MI cet usage De plus le mat riel de MPC 1 impose l unicit des MI utilis s sur le r seau Ces limitations sont assez contraignante pour le d veloppement de protocoles bas s sur PUT On sou haite donc lever les contraintes impos es par le syst me sur le contenu du champ MI afin que l utilisateur puisse l employer comme il l entend De plus un champ MI plus tendu faciliterait le d veloppement de pro tocoles de haut niveau Emmanuel Dreyfus 19 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC TII S curisation des communications dans la machine MPC 1 Cette partie aborde le probl me de la s curisation des communications sur MPC 1 Apr s un bref rap pel des contraintes inh re
5. define MAX_CHANNELS 4096 Nombre de LPE multiples table des messages en transit typedef struct _transit_table_entry u_short timeout Date d ch ance du retard u_short Ipe_index Index de l entr e de LPE de la premi re page du message u_short misc Num ro de LPE 12 bits compteur de retransmission 4 bits u_short first_seq Num ro de s quence du premier paquet de la premi re page transit_table_entry_t transit_table_entry_t transit_table TRANSIT TABLE SIZE 256 entr es de 64 bits 2ko Index travaillant sur la table des messages en transit u_char first _msg Message le plus ancien pointeur F u_char watched_msg Entr e surveill e par le processus Wd pointeur W u_char next_msg premi re entr e libre dans la table pointeur N table des s quences u_short tx_seq_table MAX_HSL_NODES S quences en transmission u_short rx_seq_table MAX_HSL_NODES S quences en r ception u_short bis_seq_table MAX_HSL_NODES S quences bis en r ception 3 table de 256 entr es de 32 bits 1 5ko File d attente des acquittements 128 entr es de 32bits 0 5ko Total 4ko de donn es stok es dans le FPGA Emmanuel Dreyfus 53 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC VI 6 b Pr sentation des diff rents processus Les processus suivants sont
6. gra der les performances et nous assure la portabilit du m canisme de s curisation d un syst me d exploitation l autre Il est aussi int ressant de signaler que l tude du probl me de s curisation a souvent donn lieu des probl mes annexes n ayant plus de rapport direct avec le probl me de s curisation Ces probl mes sont voqu s en annexe du pr sent rapport Quelques points importants ne sont pas abord s dans le pr sent document Il s agit par exemple de la preuve formelle de la validit du protocole propos pour S PUT c est dire la v rification qu il produise une signalisation correcte o un message est signal sur l metteur et sur le r cepteur si et seulement si il a t int gralement d pos en m moire L tude probabiliste menant l expression du MTBF avec S PUT fait aussi partie des points non abord s Avec l impl mentation de S PUT dans ANI ces deux probl mes restent traiter Emmanuel Dreyfus 66 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC R f rences AF Conception et r alisation d un noyau de communication b ti sur la primitive d criture distante de la machine parall le MPC Alexandre Feny Th se de doctorat soutenir octobre 2000 BSD Design and implementation of the 4 4BSD operating system McKusick Bostic Karels et Quarterman Addison Wesley Reading MA 1996 DDC
7. metteur ne recevra jamais l acquittement du message qui pourtant a t d pos et signal sur le n ud r cepteur Il va donc r p ter les tentatives d envoi et la r ception du message ne sera jamais signal e sur le n ud metteur Emmanuel Dreyfus 28 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC Pour corriger cela il faut introduire un drapeau indiquant que le message est une r mission le dra peau bis Lorsqu il re oit un message mis pour la deuxi me fois le r cepteur sait que si le message est cor rectement re u il doit donner un accus de r ception m me si le message n a pas t d pos en m moire La figure 10 donne un exemple d utilisation du drapeau bis MSg A a bis MSg A seq 2 bis Temps Machine Machine source destination Fig 10 Utilisation du drapeau bis pour g rer une perte d accus de r ception Lorsque le drapeau bis est pr sent le r cepteur accuse r ception du message m me s il n a pas t d pos en m moire V 5 Condition d envoi d un accus de r ception Jusqu au V4 la condition d envoi des accus s de r ception tait le d p t en m moire du dernier paquet d un message Maintenant un accus doit aussi tre g n r lorsqu il n y a pas de d p t et que le dra peau bis est pr sent Examinons plus en d tail la condition laquelle le drapeau bis provoque l envoi
8. nouveau s curiser au niveau SLR ou si l on va travailler au niveau PUT Il y a deux points consid rer D abord la difficult voqu e au II 2 dans le cas de la s curisation PUT on devait g rer la possibilit de voir l metteur craser un tampon d j lib r sur le r cepteur Ceci tait d au fait qu avec PCIDDC nous n avions aucune possibilit d emp cher le d p t d une page sur le r cep teur Avec ANI on a maintenant la possibilit de lever cette limitation et de mettre en place un m canisme de rejet des pages inattendues Cet argument plaidant contre la s curisation au niveau PUT ne tenant plus il reste consid rer la question des performances SLR a un co t important en terme de performances Lorsque l on a port PVM sur MPC MPI on s est bas sur SLR Le r sultat a t suffisamment d cevant en terme de performances pour que lors du portage de MPI sur MPC on ait d cid d utiliser PUT plut t que SLR Ce deuxi me point plaide en faveur d une s curisation au niveau PUT Cela permettra d obtenir des communications s curis es en gardant les meilleures performances possibles pour l impl mentation de MPI Enfin en s curisant PUT on s curise automatiquement SLR qui est b ti au dessus de PUT Par contre en s curisant SLR on ne s curise pas PUT et donc pas MPI puisque MPI repose directement sur PUT Emmanuel Dreyfus 24 17 08 2000 S curisation des primitives de comm
9. ud destinataire inaccessible Tout d abord il y a le cas de la machine inaccessible par exemple parcequ elle est teinte ou parce qu un c ble est d branch Dans ce cas l metteur va r envoyer continuellement ses messages sans jamais r ussir obtenir un accus de r ception puisque le message n arrive jamais destination Ce cas sugg re for tement que le nombre de tentatives d mission soit comptabilis et que l metteur abandonne l mission au bout d un certain nombre de tentatives infructueuses signalant un chec l utilisateur Un probl me peut survenir si on a trop h tivement suppos que le n ud destinataire tait inaccessible On va alor recevoir un accus de r ception pour un message dont l envoi a t abandonn Il faut s assurer que cet accus ne pourra pas provoquer de probl me Dans le cas pr sent on ne peut m me pas v rifier l ab sence d accus bloqu dans le r seau par un ping pong comme expliqu au II 3 si le r seau n est pas adap tatif un ping pong permet de v rifier qu aucun paquet n est bloqu dans le r seau En effet le probl me d tecter est l impossibilit de contacter un n ud Un ping pong chouera donc comme l envoi de n importe quel autre message V 6 c Congestion Les probl mes de congestion imposent de bien choisir les d lais avant retransmission timeout Si le d lai est trop court et que l acquittement d un message
10. 01010 010 Node LPE 0O1 0101 0 010 IDX 9 On envoie un message A avec IDX 0 t 0 m fin messa Fin du message on l ajoute dans la table XR 0 ee Watchdog commence compter Index 011121314715 T 3101001010 R 1100101010 Entr e LPE 0100101010 No k IPE o l o lo o l0 l0 IDX 1 Envoi d un message B avec IDX 1 Le message est fragment en deux paquets IDX l X fin mes sage Fin du message on l ajoute dans la table Index 0O 11213 141 5 IDX 2 On envoie un message C avec IDX 2 T 311101011010 R 1110101010 fin message Entr e LPE 0110 0710 70 Fin du message on l ajoute dans la table Node LPE 010 0101 010 3 t arrive 3 ce qui est l ch ance de l entr e surveill e par YR watchdog pointeur W Le temps est r initialis 0 Index 011121314153 point e par West marqu retransmettre T 0 et T 311 0010 IDX est increment R 111111101010 On ne peut retransmettre le message A tout de suite car un Ent LPetoli1l3l010 0 message D avec IDX 3 est en cours d envoi Node LPE 0 0 0 01 010 t 0 ack IDX Arriv e de l acquitement du message B IDX 1 Le Index 0 51314153 message B est signal comme recu Comme W pointait sur T oli lilolo To le message qui vient d tre recu il passe l entr e suivante R 1111101010 et re initialise t 0 Entr LPE 0 1 3 0 07 0 In message Node PE 0 0 0 01070 Le message D a fini d tre transmis on ajoute l entr e t 0 correspondante dans la table 1 Index 011121314715 I SRE SE Le f
11. 6 une transaction SCP P sans faute Comme il n y a pas d erreur il n y a pas de phase de r cup ra tion des MI donc MICP n est pas utilis On peut constater que chaque communication est gard e par un accus ce qui permet de d tecter et de corriger les fautes Emmanuel Dreyfus 22 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC IV La machine MPC 2 Le but de cette partie est de pr senter le nouveau conttr leur r seau en cours de d veloppement pour la machine MPC 2 ainsi que les perspectives offertes par ce nouveau contr leur du point de vue de la s cu risation des communications IV 1 Un nouveau contr leur r seau ANI Outre les probl mes de fiabilit du lien HSL la machine MPC 1 souffre d une autre limitation impor tante le manque de programmabilit du mat riel En effet pour r gler un probl me sur la machine MPC 1 on dispose de deux possibilit s e Faire un nouveau circuit e Corriger le probl me logiciellement Fabriquer un nouveau circuit est on reux et la perspective de devoir produire un nouveau PCIDDC chaque fois que l on fait un pas dans la phase de mise au point n est pas r aliste D un autre c t la solu tion de corriger tous les d fauts mat riels par le logiciel n est pas id ale non plus Les traitement logiciels additionnels prennent du temps et donc d t riorent les performances et nuisent consid
12. PCIDDC specification http mpc lip6 fr pciddc spec_pciddc ps gz ED Finalisation du portage de PUT et portage de MPI sur la machine MPC Linux Emmanuel Dreyfus rapport de stage ing nieur juin 2000 EMU Emulateur Logiciel MPC 1 Manuel d Installation http mpc lip6 Fr docemu docemu ps gz R3 R Cube Specification http mpc lip6 fr rcube r3 v 1 7 ps gz FW Communication orale de Franck Wajsb rt sur les temps de transfert sur le r seau HSL JLD Conception et r alisation d un contr leur de r seau programmable pour machine parall le de type grappe de PC Jean Lou Desbarbieux th se de doctorat juin 2000 MPC nterface Logicielle MPC I Manuel du Programmeur http mpc lip6 fr docutil docutil ps gz MPI The MPC parallel computer Hardware low level protocol and perofmances Amal Zerrouki Olivier Gl ck Alain Greiner Franck Wajsb rt et Alexandre Feny soumis pour publication Emmanuel Dreyfus 67 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC Annexe des id es en vrac Comme on l a vu au IL 6 il y a un certain nombre de fonctionnalit s qui n existent pas dans MPC 1 et qu on souhaiterait voir dans MPC 2 Celles ci n ayant pas toujours de rapport avec la s curisation des communications elles n ont pas t voqu es en d tail dans le pr sent rapport Dans cette annexe on pro pose quelques pistes pour ces fonctionnalit s D
13. Remerciements Je remercie l ensemble de l quipe de l ASIM pour m avoir accueilli dans leur d partement En particulier je remercie Alain Greiner Franck Wajsb rt Alexandre Feny et Jean Lou Desbarbieux pour l aide qu ils ont pu m apporter dans la mise au point de mes travaux Enfin je remercie Daniel Millot de l Institut National des T l communications pour la relecture du pr sent rapport Emmanuel Dreyfus 4 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC Table des mati res R sum Remerciements Tables des mati res I Introduction et contexte du stage I 2 Le projet MPC I 3 Le sujet du stage I 3 Le contenu de ce document I Architecture g n rale de la machine MPC 1 IL 1 Objectif z ro copie IL2 Aspects mat riels IL3 Exploitation logicielle des cartes FastHSL IL 4 Vocabulaire ILS Fonctionnement global de la primitive PUT IL6 Primitives de communication de plus haut niveau SLR IL7 Limitations de la machine MPC 1 IL7 a MTBF du lien HSL plus faible que pr vu IL 7 b Acc s en configuration sur jeu de composant 440BX IL7 c Fonctionnalit s suppl mentaires HI S curisation des communications dans la machine MPC 1 IL 1 Rappel des contraintes existantes MI 2 S curisation au niveau PUT ou SLR IL 3 Le protocole SCP P IV La machine MPC 2 IV 1 Un nouveau contr leur r seau ANI IV 2 Co conception mat rielle logicielle IV
14. canismes complexes de gestion de la coh rence des caches et de concur rence d acc s la m moire Utiliser un r seau de PC assure donc un co t r duit Mais ce choix pr sente aussi un inconv nient majeur les PC ne sont pas fais pour faire du calcul parall le Si du c t du processeur gr ce la forte demande en puissance de calcul pour les jeux vid o on a des performances tout fait correctes du c t des communications entre processeurs les moyens peu chers r seaux ethernet token ring dont on dispose sur un PC ne sont pas la hauteur C est sur ces constatations que se positionne le projet MPC d une part aujourd hui le processeur d un PC a des performances permettant de concurrencer un n ud de calcul d une grosse machine parall le D autre part l une des plus fortes limitations aujourd hui dans les machines parall les de type grappes de PC c est le manque de performances des moyens de communications Dans le cadre de l activit de design de circuits int gr s du d partement un circuit routeur pour r seau hautes performances nomm R Cube a t d velopp Ce circuit se destine a plusieurs applications telles que les commutateurs gigabit ethernet ou dans le cas qui nous int resse les machines parall les Emmanuel Dreyfus 7 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC Le projet MPC regroupe des ch
15. communication entre le processus d mission et le pro cessus de r ception du contr leur r seau ANI Le probl me principal qui se pr sente ici est le fait qu un n ud ne peut envoyer d accus s de r cep tion pendant qu il est en train d mettre des donn es Il n y a qu un lien de ANT vers R Cube Ceci introduit donc un d lai avant l exp dition des accus s Pour minimiser ce d lai on a d cid de donner aux accus s la priorit la plus haute et d exp dier tous les accus s en attente entre chaque paquet envoy Ceci signifie qu il faut mettre en place une file d attente entre le processus g rant l envoi des acquit tement et le processus d mission des paquets Cette file d attente doit tre dimensionn e de telle fa on que pendant l mission d un paquet de 4ko nous avons propos une taille de paquet de 4ko dans le V 7 elle ne d borde pas Emettre un message de 4ko prend 31 2us Pendant ce temps on peut recevoir un message tous les 240ns comme on l a expliqu plus haut et donc avoir un accus de plus en attente tous les 240ns Ceci impose une longueur de file d attente de 130 places Le FPGA peut fournir des files d attente de 128 ou 256 places La situation d crite ci dessus etant extr me dans la r alit le logiciel n est pas capable d envoyer des messages au rythme de un tous les 240ns on va choisir une longueur de file d attente de 128 places Chaque place doit conten
16. constater que la suite des num ros de s quences a t interrompue et qu un ou plusieurs num ros a t saut Ce m canisme exige un comportement FIFO First In First Out du r seau on doit donc renoncer aux tables de routage adapta tives V2 Accus s de non r ception ou accus s de r ception La s curisation de PUT va obligatoirement passer par des changes de paquets de contr le entre machine source et machine destination qui permettront chaque machine de savoir o en est l autre Par ces paquets de contr le on va accuser r ception ou non r ception des donn es La premi re question que l on peut se poser est le niveau de ces accus s doit on faire des accus s de r ception ou de non r ception des paquets des pages ou des messages L avantage de signaliser des l ments de petite taille tels que les paquets est que l on sait exactement ce qui est perdu On peut donc en cas de perte r acheminer uniquement ce qui est n cessaire ce qui conomise de la bande passante Par contre la gestion de la chose se r v lera n cessairement plus co teuse en terme d occupation m moire puisqu il faudra garder des informations sur de nombreux paquets en transit Travailler au niveau message permet de r duire cette occupation m moire De plus la perte d un paquet tant un v nement peu courant il est sera rare d avoir r envoyer un paquet L conomie en bande passante n est donc pas tr s in
17. d entr e de LPE Emmanuel Dreyfus 68 17 08 2000
18. de communication bas niveau dans une machine parall le de type grappe de PC Etait ce la derni re page du message Lire une entr e de on 2 Recuperer le num ro de s quence du premier paquet Lire une entr e de LPE Sauvegarde du num ro de s quence courant en mission vers le n ud destinataire Incr menter le num ro de sequence en mission vers le n ud destinataire Envoi du paquet lu dans la RAM Incr menter le num ro de sequence en mission vers le n ud destinataire Etait ce le dernier paquet de la page Ajouter une entr e dans la table des messages en transit Fig 25 Partie du processus d mission qui r alise l op ration d envoi d un message Cette parti e est utilis e par les tats Insert et Replay Emmanuel Dreyfus 58 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC gt Invalider l entr e Signaler l echec de l envoi l utilisateur R PCI XRPCI ue 6 R R Sauvegarder le num ro de s quence courrant en emission 4 Trouver l entr e retransmettre dans la table des messages en transit Fixer le champ d cheance la valeur du timeout et incr menter le nombre de tentatives d envoi Nombre de tentatives maximum d emission exc d Reprendre les s quence
19. de la machine MPC 256 n uds ce qui est d j beaucoup les tailles des deux tables diminuent 256 X 16 bits 0 5ko chacune Deux tables de 0 5ko peuvent tenir dans le FPGA Emmanuel Dreyfus 49 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC VI 3 D tection de la r ception compl te des paquets d un messages bis Nous avons expliqu au V S la n cessit d un m canisme de d tection de la r ception de tous les paquets d un message bis qu ils aient t d pos s ou non Comme on est assur du fait qu un seul message bis peut arriver d un n ud metteur un moment donn on va pouvoir surveiller les num ros de s quences des messages bis avec une table de num ros de s quences bis attendus analogue la table des num ros de s quences attendus d crite au VI 2 Cette table va donc occuper 0 5ko suppl mentaires et peut tre g r e mat riellement Pour d tecter que l on doive initialiser le num ro de s quence bis dans la table il faut pouvoir rep rer le premier paquet d un message bis Nous avons donc besoin dans les paquets d un drapeau indiquant si le paquet est le premier d un message Si ce drapeau est pr sent le num ro de s quence bis pour le n ud source est initialis au num ro de s quence du premier paquet du message plus un On va ensuite incr menter le num ro chaque fois qu on re oit un paquet bis avec l
20. de messages diff rents Ceci est assur si les num ros de s quences ne bouclent pas pendant toutes les missions d un m me message Un message peut tre envoy 16 fois chaque envoi etant s par du pr c dent par un temps de retransmission A Ceci nous fait un temps 16 1 8ms avec A 500us pendant lequel des paquets peu vent tre envoy s Ces paquets sont envoy s au rythme maximum de un tous les 240ns ce qui fait en 8ms un nombre maximum de paquet envoy gal 33333 Il faut aussi compter les num ros de s quences utilis s pour le message retransmis Si on limite la taille des messages 64Mo on consomme 16384 num ros de s quence suppl mentaires et donc 65536 num ros de s quences diff rents suffisent On peut alors utiliser des num ros de s quences d une largeur de 16 bits Voyons maintenant les profondeurs des tables de s quences Elles sont d termin es par le nombre de n uds Le r seau HSL comporte au maximum 65536 n uds pour R Cube le num ro du n ud est cod sur 16 bits Ceci nous fait deux tables des s quences de 65536 X 16 bits 256ko C est une valeur beaucoup trop importante pour pouvoir faire tenir la table dans le FPGA celui ci ne dispose que de 25ko on chip et ce m canisme doit donc forcement tre impl ment dans le mat riel Nous devons donc introduire une contrainte sur le seul param tre rest libre le nombre de n uds maximum dans un r seau HSL Moyennant de restreindre la taille
21. infini dans le r seau si un lien est bris par exemple En fonctionnement normal si les paquets sont assez gros on peut compter 2ko de donn es en cours de transit dans le r seau acheminer entre le d part du dernier octet de l metteur et l arriv e du dernier octet sur le r cepteur Ces 2ko de donn es donnent lieu 15us de temps d attente suppl mentaire Nous devons donc prendre une valeur arbitraire en esp rant qu elle sera un bon majorant Prenons un timeout de 500us ce qui fait 1000 fois le temps correspondant au cas id al Emmanuel Dreyfus 40 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC Une tude statistique serait la bienvenue pour tester la validit de cette valeur Pour r aliser cette tude on a besoin de donn es exp rimentales telles que l occupation du bus PCI pendant l utilisation nor male de la machine MPC ou le temps de travers e d un paquet travers le r seau HSL Une autre approche plus pragmatique consisterait essayer diff rentes valeurs jusqu l obtention de r sultats satisfaisants Etant donn que le FPGA est reprogrammable cette derni re solution sera sans doute retenue Calculons le nombre de messages que nous pouvons envoyer pendant le temps A et donc de le nombre de compteurs que nous devons maintenir Pour ce calcul on suppose le cas id al car on veut un majorant du nombre de messages q
22. n cessaire au fonctionnement de S PUT e Emission de messages Tx e r ception de paquets Rx e Surveillance des messages non acquitt s Wd Watchdog e Envoi d acquittements Ack De plus on a besoin des op rateurs suivants e Constructeur de paquets HSL Pb Packet Builder e Extracteur de paquets HSL Pb Packet Extractor e Op rateur de lecture par DMA DMA R e Op rateur d criture par DMA DMA W e Esclave PCI recevant les ordre d envoi de messages PCI La figure 23 pr sente les relations entre ces diff rentes entit s p f Table des messages en transit Table des s quences A Rec ption N Table des s quences bis Rec ption Q 1 _ 7 HSL out HSL in Table des s quences Transmission Transfert de donn es Processus 5 Contr le ou lecture sur une table CL Op rateur Lecture ecriture sur une table D Table File d attente des acquittements Fig 23 relations entre les diff rents processus et op rateurs utilis s par S PUT Dans un effort de synth se les donn es importantes manipul es sont aussi repr sent es Emmanuel Dreyfus 54 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC VL6 c Op rations sur la table des messages en transit Comme on l a dit plus haut 3 processus manipulent cette table pour 4 op rations diff rentes envoi original ou retransmission pour l
23. parall le de type grappe de PC IL3 Exploitation logicielle des cartes FastHSL L exploitation logicielle des cartes FastHSL est assur e par MPC OS pour MPC Operating System EMU MPC OS est impl ment sous forme de modules charger dynamiquement dans les noyaux des sys t mes FreeBSD et Linux e Le module CMEM qui est un gestionnaire de m moire physiquement contigu e Le module HSL charg de l exploitation proprement dite de la carte impl mente un certain nombre de services pour les couches logicielles de plus haut niveau Il impl mente aussi l interface de programma tion PUT qui permet l criture dans un n ud distant en utilisant la carte fastHSL PUT est la primitive de communication de plus bas niveau dans la machine MPC Le module HSL doit dialoguer avec PCIDDC pour envoyer des pages de m moire sur les n uds dis tants Le reste de cette partie aborde les moyens employ s par le module HSL pour communiquer avec PCIDDC La norme PCI impose aux cartes PCI de fournir des registres de configuration Ces registres sont accessibles en lecture et en criture et ils permettent les fonctions d auto d tection et d identification de la carte ainsi que sa configuration lors du d marrage de la machine Habituellement les registres de configuration ne sont utilis s qu au d marrage de la machine pour configurer la carte Lors de ces op rations la m moire d entr e sortie de la carte est remapp e dans l es
24. perdu on doit renvoyer seulement le message dont l accus a t perdu alors que pour un paquet perdu il faut ren voyer autant de messages qu il y a de places dans la table des messages en transit VIlL a Latence Pour mesurer la latence on s int resse l envoi en continu de petits paquets disons des messages courts En temps normal la latence d un tel message est d environ Sus En cas de perte de paquet il faut retransmettre autant de messages qu on peut en envoyer avant de constater que le message perdu n est pas acquitt c est dire autant de messages qu on peut en envoyer pendant la dur e du timeout Ces messages sont retard s du temps d envoi normal 4us plus le d lai de retransmission A 500us plus le temps d ar riv de l accus de r ception Tack lus puisqu en mode retransmission on envoie les messages un par un Ceci fait un total d environ 505us Si on suppose qu on peut envoyer les messages courts au rythme de un tous les Tm 8us le logiciel ne peut en envoyer plus vite avant d avoir un fimeout 500us on peut envoyer Tm 63 messages Nous avons donc 63 messages qui subiront une latence anormalement lev e 505us cause de la faute Le MTBF est de deux minutes Pendant ce temps au mieux on peut envoyer 30 millions de messages au ryth me de un message tous les 8us Ces messages ont une latence normale de Sus Si on calcule la latence moyen ne on obtient
25. perdues avant de rece voir un nouveau paquet On peut dans certaines situations arriver un interbloquage La solution ce pro bl me serait d avoir des paquets vides chang s intervalle de temps r gulier lorsque le lien est inutilis pour donner au r cepteur l opportunit de constater qu un num ro de s quence a t saut e Aussi bien sur l metteur que sur le r cepteur on a des phases de r cup ration sur erreur Ce protocole contrairement au PUT de MPC 1 ne laisse pas les n uds sans tats Ceci implique une certaine complica tion dans l impl mentation du protocole e Troisi me probl me qui lui est insoluble on signalise les non r ceptions l metteur n a donc aucun moyen de savoir quand un message a bien t re u par le r cepteur et donc quand un tampon d mission peut tre lib r A cause du dernier probl me on ne peut pas utiliser d accus s de non r ception Nous allons donc devoir laborer une solution bas e sur des accus s de r ception Si l metteur n a pas re u l accus de r cep tion d un message au bout d un certain d lais il doit r envoyer le message V 3 Perte d un paquet La m thode de signalisation choisie est donc l accus de r ception de chaque message re u Emmanuel Dreyfus 26 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC Du c t du r cepteur on observe les
26. peut tre impl ment que mat riellement En effet c est le contr leur r seau qui d pose les paquets en m moire La machine h te est passive dans cette op ration et n a aucun contr le sur le d p t Seul le contr leur r seau peut d cider de bloquer un paquet ou de le d poser Emmanuel Dreyfus 48 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC Pour obtenir le syst me de num ros de s quences d crits dans le V 1 nous devons mettre en place deux structures de donn es Sur l metteur chaque paquet mis vers un n ud donn doit porter un num ro de s quence croissant Il nous faut donc une table de num ros de s quence courant pour chaque n ud desti nation Sur le r cepteur il nous faut une table donnant pour chaque n ud source le num ro de s quence atten du Ceci nous fait donc deux tables par n ud chaque n ud pouvant jouer le r le d metteur ou celui de r cepteur Ce sont les tables des s quences respectivement en transmission et en r ception Ces tables contin nent autant d entr es qu il y a de n uds sur le r seau HSL Chaque entr e de la table en transmission contient le num ro de s quence courant en mission pour le n ud correspondant et chaque entr e de la table des s quences en r ception contient le num ro de s quence attendu en r ception pour le n ud correspondant L utilisation des num ros de s quences e
27. produirait ainsi pas de charge suppl mentaire due aux accus s de r ceptions Un probl me survient toutefois lorsque le r seau n est pas fortement connexe On peut arriver des trafics tels que celui d crit par la figure 16 Fig 16 exemple de topologie de r seau HSL non fortement connexe On a deux flux de donn es impor tants l un de 3 vers 1 et l autre de 2 vers 4 Le lien entre 5 et 6 est partag pour ces deux flux Avec un tel traffic on n a pas de donn es allant de 4 vers 2 pour placer les accus s de r ception des messages allant de 2 vers 4 On devra donc envoyer des paquets vides ne contenant que des accus s de r cep tion Mais ces paquets vont occuper de la bande passante sur le lien de 6 vers 5 qui est d j charg par les transferts de 3 vers 1 Evaluons la bande passante occup e en sens inverse par les accus s de r ception Elle est directement li s au d bit en message par seconde puisqu un accus est envoy pour chaque message re u Calculons le d bit maximum en message par seconde en fonction de la taille des messages Le goulot d tranglement sur le chemin de donn es tant le bus PCI la vitesse d envoi des messages est limit e par la vitesse de lecture Emmanuel Dreyfus 36 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC des entr es de LPE et des donn es du message Avec un message de n octets n inf rieur
28. rablement la lisibi lit du code source De plus toutes les erreurs mat rielles ne sont pas corrigeables logiciellement On a donc d cid d utiliser un FPGA Field Programmable Gate Array comme contr leur r seau la place de PCIDDC Un FPGA est un circuit dont on peut programmer le comportement Ce nouveau contr leur r seau pour la machine MPC 2 a t nomm ANI Another Network Interface Les b n fices de la programmabilit d ANI sont imm diats Sur la machine MPC 2 il sera possible de corriger mat riellement un probl me mat riel et ceci peu de frais ANT permettra ainsi d valuer diff rentes pistes pour la r solution d un probl me donn de r aliser des tests de performances et de choisir la meilleur m thode De plus passer un nouveau contr leur r seau nous permet d viter les erreurs commises avec PCIDDC Par exemple ANT s interface avec la machine h te par des acc s m moire et non plus par des acc s en configuration comme c tait le cas sur PCIDDC Ceci permet d viter les dysfonctionnements obtenus lorsque l on effectue des acc s en configuration une fr quence trop lev e sur une machine utilisant le jeu de composant Intel 440BX IV 2 Co conception mat rielle logicielle La pr sence dans la machine MPC 2 d un contr leur r seau reprogrammable tel que ANI ouvre de nouvelles perspectives du point de vue de la s curisation des communications Dans la machine MP
29. s en configuration un rythme tr s lev Dans le cas de PCIDDC chaque envoi de page demandant un acc s en configuration on peut tre amen faire des acc s en configuration une fr quence extr mement lev e lorsque l on envoie rapide ment des petites pages par exemple pour envoyer une colonne de matrice Ces acc s en configuration posent probl me lorsque la carte est utilis e avec des cartes m res utili sant le jeu de composants 440BX d Intel Un probl me dans la passerelle PCI de ce jeu de composants pro voque des checs lorsque l on fait des acc s en configuration un rythme trop soutenu Par exemple si on lit un registre d tat par acc s en configuration avec une tr s haute fr quence on finit par lire la valeur OxFFFFFFFE On sait que certains bits de ce registre sont reli s la masse donc on est s r que ce compor tement rel ve du dysfonctionnement Intel reconna t d ailleurs le probl me puisque le document indiquant la sp cification du jeu de com posant 440BX pr cise que les acc s en configuration sont destin s l initialisation et qu il convient de faire attention si l on s en sert pour autre chose Toutes les cartes PCI normales se trouvant sur le march n utili sant les acc s en configuration que pour l initialisation le probl me passe tout fait inaper u sauf avec les cartes FastHSL IL 7 c Fonctionnalit s suppl mentaires L exp rience acquise avec MPC 1
30. 3 S curisation au niveau PUT ou SLR V S curisation au niveau PUT dans MPC 2 V 1 D tection des pertes de paquets V 2 Accus s de non r ceptions ou accus s de r ception V 3 Perte d un paquet V 4 Perte ou retard d un accus de r ception V 5S Condition d envoi d un accus de r ception V 6 Quelques cas pathologiques Emmanuel Dreyfus 5 Ooo N 10 10 11 13 13 14 16 18 18 19 19 20 20 20 21 23 23 23 24 25 25 25 26 28 29 32 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC V 6 a Une mission entre un acquittement perdu et la retransmission correspondante 32 V 6 b N ud destinataire inaccessible 33 V 6 c Congestion 33 V 6 d Adaptativit 33 V 7 Impact sur les performances 34 V T a Latence 34 V 7 b D bit 36 V 8 s curisation au niveau SLR 38 VI Proposition d impl mentation de S PUT 1 0 40 VIL 1 Impl mentation des renvois la table des messages en transit 40 VI L a Table des messages en transit index e par le temps 41 VI 1 b Table des messages en transit avec champ d ch ance 43 VI 2 Impl mentation du rejet des doublons les num ros de s quence 48 VL3 D tection de la r ception compl te des paquets d un messages bis 50 VI 4 Impl mentation du m canisme d envoi des accus s de r ception 51 VI 5 Bilan des contraintes impos es par la s curisation 52 VI 6 S PUT 1 0 en bref 53 VI 6 a Pr sentation des stru
31. C 1 le logiciel est incapable de suivre la vitesse du mat riel pour des petits messages La taille limite est de l ordre du millier d octet La vitesse d mission des petits messages est donc major e par la vitesse d mission des messages de 1ko Le d bit utilis par les accus s de r ception est donc major par 53Mb s d apr s la formule tablie ci dessus Ce chiffre s il est plus raisonnable que les 1 2Gb s initiaux reste lev Il ne faut pas oublier qu il s agit d un majorant Non seulement nous supposons le bus PCI toujours disponible mais en plus il corres pond une utilisation assez artificielle de la machine o on essaye d mettre le plus de donn es possible le plus rapidement possible De tels comportements se rencontrent rarement dans des applications normales de calcul parall le on ne les trouve en r alit que dans les programmes de tests de performances de notre machi Emmanuel Dreyfus 37 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC ne La forte bande passante potentiellement occup e par des accus s de r ception sugg re de faire une l g re am lioration du syst me d accus s il s agirait lorsque cela est possible d accuser r ception de plu sieurs messages la fois Des paquets d accus s de r ceptions multiples devraient donc tre envoy s lorsque le d bit utilis pour accuser r ception des messa
32. C 1 on devait faire avec le comportement de PCIDDC et inventer des m canismes logiciels pour obtenir des com munications s curis es Avec ANI il est maintenant possible de changer le comportement du mat riel pour que le logiciel trouve les services qui lui permettront d assurer des communications sures de fa on simple A chaque probl me de s curit la question de la r solution mat rielle ou logicielle du probl me se pose Faire un traitement en mat riel a un avantage vident la rapidit De plus tout le temps que le CPU ne passe pas contourner des probl mes mat riels il peut le passer calculer On ne peut toutefois pas tout faire Emmanuel Dreyfus 23 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC mat riellement car la m moire et les possibilit s de traitement du FPGA ne sont pas aussi importantes que celles de la machine h te Des traitements trop complexes ou manipulant des donn es trop importantes doi vent donc obligatoirement tre faits logiciellement On est donc en face d un travail de co conception mat rielle logicielle Il faut d cider de ce qui doit tre r alis par le mat riel et ce qui doit tre r alis par le logiciel IV3 S curisation au niveau PUT ou SLR Le titre de cette partie a volontairement un air de d j vu En effet puisqu une nouvelle architecture est disponible on peut se demander si l on va
33. Nous avons un probl me similaire si le r seau est particuli rement charg et que le message et ou son accus de r ception ont pris du retard dans la travers e du r seau Si l accus de r ception arrive apr s un timeout l metteur r met un un message qui a d j t signal comme re ue sur le r cepteur Ce probl me tait difficilement soluble avec PCIDDC Une contrainte de PCIDDC tait que le r cep teur ne pouvait emp cher le d p t d un paquet Cette contrainte est lev e avec ANI nous pouvons savoir quels paquets nous avons re u et bloquer au niveau mat riel le d p t des paquets appartenant un message doublon Nous avons d j le moyen de r aliser ce blocage les paquets du message doublon n auront pas le num ro de s quence attendu et ils ne seront donc pas d pos s La figure 9 illustre ce propos Timeout Machine Machine Temps ne source destination Fig 9 Perte d un accus de r ception Une fois le dernier paquet du message arriv le tampon en r cep tion est lib r et l accus de r ception envoy Si l accus est perdu l metteur va re mettre son message Le tampon en r ception ayant t lib r on ne doit pas re d poser ce message Le syst me de num ros de s quence nous permet cela On a cependant un probl me corriger Le deuxi me envoi du message est rejet mais il doit tout de m me donner lieu un accus de r ception Sans cela le n ud
34. Rapport de Stage de DEA Sp cialit Informatique Universit d Evry val d Essonne S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC Emmanuel Dreyfus Stage effectu au Laboratoire d Informatique de l Universit de Paris 6 LIP6 4 place Jussieu 75252 Paris Cedex 05 sous l encadrement du Pr Alain Greiner Mars 2000 Septembre 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC R sum La machine MPC est une machine parall le de type grappe de PC Elle a t d velopp e avec la conviction que le temps entre deux erreurs mat rielles tait de l ordre de la dizaine d ann es A cause de pro bl mes mat riels impr vus ce temps entre deux fautes est en r alit de l ordre de 2 minutes dans le pire des cas Des m canismes de reprise sur erreur qui paraissaient l origine inutiles sont donc indispensable Dans un premier temps une s curisation logicielle des primitives de communication haut niveau a t mise en uvre Mais cette solution n est pas pleinement satisfaisante car on ne peut utiliser les primitives bas niveau qui permettent les plus hautes performances de fa on sure Une nouvelle version du contr leur r seau de la machine MPC est actuellement en cours d labora tion et ce nouveau circuit sera reprogrammable Le but de mon stage a t d tudier le probl me de l
35. a s cu risation de la primitive bas niveau de la machine MPC en supposant que l on dispose d un contr leur r seau reprogrammable Il s agissait donc d laborer un m canisme de s curisation et de d finir ce qui devait tre impl ment materiellement et ce qui devait tre impl mente logiciellement pour pouvoir fournir une primi tive de communication bas niveau s curis e Abstract The MPC project aim 1s to provide a low cost parallel computer based on networked industry stan dard PCs During the MPC first run developpement it was the assumed that the mean time between failures was about ten years But in practice because of unexpected hardware failures it is lowered down to about a couple of minutes A software based error recovery protocol was developped to address this issue but it only secured the higher MPC communication layer The lower MPC comunication layer which enable the highest performance was left unsecured A new version of the MPC network controler is currently being developped and this new version will be a programmable chip The aim of my training period was to propose a security feature for the lower MPC communication layer using the new network controler This job included deciding what tasks were to be done in hardware and what tasks were to be done in software Emmanuel Dreyfus 3 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC
36. able Mais pour des raisons de simpli cit c est la s curisation au niveau SLR qui a t choisie Emmanuel Dreyfus 20 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC IIL 3 Le protocole SCP P Le d veloppement de la s curisation des communications dans la machine MPC 1 a t effectu par Alexandre Feny au cours de sa th se AF Le protocole s curis rempla ant SLR P s appelle SCP P Il manipule des adresses physiques Un protocole SCP V s appuie sur SCP P pour fournir le m me service avec des adresses virtuelles et il se pr sente en rempla ant de SLR V Avant de d crire le protocole SCP P il faut signaler une des limitations qu il requiert pour fonction ner le r seau ne doit pas tre adaptatif En effet un des probl mes qu il nous faut traiter est le retard d un paquet Le temps qu un paquet peut passer dans le r seau n est pas born En cas de retard d un paquet on ne peut donc pas attendre un certain temps puis se dire que le paquet est forc ment perdu Dans le cas d un r seau non adaptatif pour s assurer qu un paquet n est pas rest bloqu dans le r seau il suffit de faire un ping pong Le comportement FIFO du r seau nous assure que si le ping pong passe alors aucun paquet n est bloqu au milieu du r seau Sur un r seau adaptatif on perd cette garantie le ping pong peut emprunter une route diff r
37. able N R 1 table N T t 4A T ET A gt t N N I D passement du d lais de retransmission Wd faire si table W T gt t et table WIR 0 t 0 ZT ZT table W T table W T 0 FR TR I tant que table WI R 0 et W N W W I attendre At tant que W N attendre At t t l Emmanuel Dreyfus 55 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC Accus de r ception du message IDX Rx si table IDX R 0 et table IDX T 0 table IDX R 0 signalisation de la compl tion de l envoi Rp table IDX T i IDX faire i i 1 tant que i Z N et table i R 0 si i N table i T table i T Rp sinon T T Rp si IDX F F i Retransmission Tx tant que R 0 si table F R Z 0 et table F T 0 tant que table i R Z 0 et table 1 R max_retry envoi du message table F R table F R 1 table F T A tant que table i R Z 0 et table 1 T 0 Attente timeout ou ack attendre At table F T table F T 1 si table i R max_retry table i R 0 signaler l chec R ERE 1 F F 1 Emmanuel Dreyfus 56 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC VI 6 d Comportement du processus d mission Le processus d mission Tx doit g rer deux choses diff rentes l mission originale d un message et la retransmission d
38. aire pour acheminer 4ko sur un bus PCI 33MHz 32bits On va supposer pour des raisons de simplicit que ce transfert sur le bus PCT se fait de fa on id ale c est dire que le bus est disponible quand on en a besoin Un transfert sur le bus se fait en plusieurs op ra tions qui suivent chacune les tapes suivantes Prendre le bus PCI 1 cycle Phase d adresse 1 cycle Retournement du bus 1 cycle Lecture de N mots de 32 bits N cycles Rel cher le bus 1 cycle Total 4 N cycles La dur e du transfert ici N cycles est limit e par la valeur du registre PCI Latency Timer Ce registre indique pendant combien de cycles un p riph rique a le droit de garder le bus Dans la machine MPC pour maximiser les performances on met ce registre sa valeur maximum c est dire 256 cycles On va donc devoir faire 260 cycles pour ramener 256 mots de 32 bits soit 1ko Pour transmettre un paquet de 4ko il nous faut donc 4 op rations comme celle l soit dans le cas id al 1040 cycles Un cycle fait 30ns sur un bus 33MHZ ce transfert prendra donc au pire 31 2us On obtient donc dans ce cas une latence de 35us au lieu de 4us C est une augmentation norme De plus cela n est m me pas une majoration si le bus PCI n est pas disponible d s qu on en a besoin la laten ce peut encore augmenter En fait le bus PCI ne garantit aucune majoration du temps n cessaire pour obte nir le bus donc nous ne pouvons pas majorer la latence Em
39. au num ro du premier envoi du message Envoyer le message Attendre At D crementer le champ cheance Champ cheance nul timeout d pass Champ nombre de tentative non nul entr e valid e accus non re u Non CN Restaurer le num ro de s quence en mission Fig 26 les tats Replay gauche et Insert droite du processus Tx Ces deux tats partagent l op ration d envoi d un message qui est d crite dans la figure 25 Emmanuel Dreyfus 59 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC VI 6 e Comportement du processus de surveillance des messages non acquitt s Le processus Wd est charg de surveiller les messages dont l acquittement est en retard Wd surveille une entr e de la table des messages en transit point e par W Lorsque le d lai de retransmission de cette entr e arrive ch ance l entr e est marqu e retransmettre champ ch ance nul et le processus Tx est notifi de la pr sence de message retransmettre par l incr mentation du compteur R La figure 27 donne le comportement du processus Wd Non Incr menter le compteur de temps et attendre la dur e d un tick L entr e point e par W est devenue invalide Le champ cheance de l entr e point e par W est il superie
40. brement la valeur du timeout sans agrandir la table On va uti liser cette deuxi me version avec les champs d ch ance La figure 21 donne des exemples d utilisation de la table en int grant les r gles donn es au V5 D taillons maintenant le nombre de champs dans chaque entr e de la table Dans une entr e de table des messages en transit nous devons avoir e L ch ance de l entr e On fixe la largeur de ce champ 16 bits Si on compte des ticks de 240ns ce qui corresponds la vitesse maximum auquel le mat riel peut mettre des messages un champ d ch ance de 16 bits permet de g rer des d lais de retransmission d au plus 15ms e Le nombre de tentatives d envoi de l entr e initialement z ro On a choisi de prendre ce champ d une lon gueur de 4 bits Ceci donne 16 tentatives d envoi maximum pour un message Etant donn que la perte d un message est un v nement rare c est une valeur surdimensionn e e Le num ro de s quence du premier paquet de la premi re page du message On verra dans la partie suivante les raisons qui nous poussent fixer la taille de ce champ 16 bits e Le num ro de l entr e de LPE trait e dans PUT 1 la LPE n a pas d autre limite de taille que la m moire disponible La pr sence de ce champ va imposer une taille de LPE maximum dans MPC 2 En prenant ce champ d une taille de 16 bits on limite la taille de la LPE 65536 entr es ce qui para t raiso
41. ce m canisme sera examin e l impl mentation dans la partie VI V 6 Quelques cas pathologiques Dans cette partie sont d taill es quelques transactions posant des probl mes ainsi que les solutions propos es V 6 a Une mission entre un acquittement perdu et la retransmission correspondante Pendant une retransmission de message on doit reprendre les num ros de s quences au num ro du premier paquet du message Ceci a t illustr dans la figure 8 Toutefois la figure 8 n aborde pas le cas d un autre message envoy entre un acquittement perdu et la retransmission du message du l acquittement perdu La figure 14 illustre ceci aussi clairement que possible 7 msg B seg 4 msg B seq 5 MSg A I h eq 1 Bis ml lt MSg A MSsg A seq 3 bi seq 2 bis Re u Re u Machine Machine source destination Fig 14 Probl mes suite la perte d un accus Apr s la retransmission du message pour envoyer le mes sage C il faut reprendre les num ros de s quence o ils en taient avant le retransmission c est dire 6 dans le cas pr sent et non pas 4 Temps Emmanuel Dreyfus 32 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC On voit dans cette figure qu apr s avoir fait la retransmission d un message il faut reprendre les s quences au num ro d avant la retransmission V 6 b N
42. ces Si on arrive jusqu au dernier paquet du message sans jamais avoir saut de num ro de s quence alors tout le message a t envoy avec le drapeau bis La pr sence du drapeau bis indique que l on est en mode de r cup ration sur erreur l metteur n envoie les messages qu un par un et il attend les acquittements avant de continuer Comme on l a expliqu plus haut la conjonction de ce mode Emmanuel Dreyfus 31 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC de r cup ration sur erreur et de la r ception ventuellement sans d p t de tous les paquets du message implique que le message t enti rement d pos en m moire soit au cours des transferts pendant la phase de r cup ration sur erreur soit avant si la retransmission n est due qu un accus perdu comme sur la figu re 10 On peut donc acquitter le message si cette condition est remplie Dernier point claircir Il faut que le r cepteur soit capable de d tecter quel est le premier paquet d un message Sinon 1l peut constater que les paquets d un messages sont arriv s jusqu au dernier sans sauts dans les num ros de s quences et conclure la r ception de la totalit des paquets du message alors que le ou les premiers paquets ont t perdus On devra donc avoir un m canisme permettant de savoir qu un paquet est le premier d un message La mise en place de
43. contr leurs r seaux et des routeurs R Cube Mais pour calculer la latence on s int resse au transit d ue petit message de quelques octets On n a donc pas de donn es en cours de transit dans le r seau prendre en compte Le temps de travers e d un routeur R Cube est valu 150ms L criture d un mot en m moire cen trale en supposant que l on avait d j initi un transfert ce qui est le cas ici prend 30ns sur un bus PCI 33MH7Z 32bits Enfin le temps de travers e d un contr leur r seau est d environ 100ms FW Et supposant que le r seau HSL soit fortement connexe et donc qu il n y a que 2 routeurs R Cube entre deux machines nous obtenons donc un temps suppl mentaire de latence par rapport MPC 1 se d com posant ainsi Propagation du dernier mot Travers e de deux R Cube 2x150ns Travers e des c bles 10ns Travers e de ANI 200ns Ecriture en RAM 30ns Envoi de l accus de r ception Travers e de deux R Cube 2x150ns Travers e des c bles 10ns Total 850ns Emmanuel Dreyfus 34 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC Nous devons donc compter une augmentation de latence de l ordre de la microseconde dans l utili sation de PUT Le PUT de MPC 1 prenait environ 4us nous arrivons donc Suis ce qui repr sente une aug mentation de 25 de la latence C est une augmentation importante mais c e
44. ctures de donn es 53 VI 6 b Pr sentation des diff rents processus 54 VI 6 c Op rations sur la table des messages en transit 55 VIL 6 d Comportement du processus d mission 57 VI 6 e Comportement du processus de surveillance des messages non acquitt s 60 VI 6 f Comportement du processus de r ception 61 VL 6 g Comportement du processus d envoi des acquittements 62 VI 6 h Formats des paquets 63 VII Performances 64 VILa Latence 64 VILb D bit 64 VILc MTBF 65 VIII Conclusions 66 R f rences 67 Annexe des id es en vrac 68 Emmanuel Dreyfus 6 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC I Introduction et contexte du stage II Le projet MPC Cette partie fait une br ve introduction au enjeux du parall lisme et explique les motivations du projet MPC Depuis la fin des ann es 60 les circuits int gr s des syst mes informatiques voluent selon la loi de Moore c est dire en suivant un doublement du nombre de transistors int gr s sur une surface donn e tous les 18 mois pour un prix restant inchang Aux premiers jours ces progr s en miniaturisation des circuits int gr s permettaient d obtenir un doublement de performances sans augmentation du co t sur une chelle de 18 mois Grossi rement plus un circuit est miniaturis moins il dissipe de chaleur et plus on peut lui imposer une haute fr quence de fonctionnement Cependant cette vo
45. curisation des communications de MPC 1 pr sente une note pessimiste il n est pas possible de s curiser les communications au niveau le plus bas savoir au niveau de la primitive PUT Aujourd hui la deuxi me g n ration de la machine MPC MPC 2 est en cours d laboration Le sujet de mon stage a donc t d examiner quels seraient les besoins mat riels et ou logiciels dans la machine MPC 2 pour pouvoir assu rer la s curisation des communications au niveau le plus bas Emmanuel Dreyfus 8 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC L 3 Le contenu de ce document Le pr sent m moire rapporte les travaux accomplis au cours de mon stage de DEA sur le projet MPC Pour cela il commence dans la partie II par introduire la machine MPC de premi re g n ration MPC 1 en tudiant avec un niveau de d tail relativement lev l architecture de la machine et son fonctionnement Cette partie fournit les bases n cessaire la compr hension de la suite du rapport Les lecteurs familiers avec le projet MPC peuvent donc commencer directement leur lecture la partie III La partie III fait le bilan sur les probl mes de s curisation de la machine MPC 1 Apr s avoir situ les contraintes dues l architecture de la machine MPC 1 elle d crit les possibilit s de s curisations ainsi que la solution propos e par Alexandre Feny pour s curiser les couches
46. d envoi R e Le num ro de s quence du premier paquet du message e Le num ro de l entr e de LPE trait e e Le num ro de LPE si on a des LPE multiples Ajoutons cela un certain nombre de quantit s permettant de g rer la table e Le temps courant not t e Le d lai de retransmission timeout A e Le nombre d entr es dans la table n e Le pointeur de premi re entr e libre N e Le pointeur du plus ancien message F e Le pointeur sur le prochain message en timeout W Enfin notons des conditions importantes e La table est vide N F e La table est non pleine N 1 F n e Un l ment est valide il d crit un message en transit si R 0 sinon il est invalide e Un l ment d crit un message en instance de retransmission s il a T 0 et R 0 e Les l ments valides sont entre F inclu et N exclu e Les l ments en instance de retransmission sont entre F inclu et W exclu e Les l ments valides en attente d acquittement sont entre W inclu et N exclu La table est manipul e par trois processus qui ont au total 4 comportements e Le processus d d mission en mode normal ajoute une entr e dans la table lorsqu il a envoy un message Pour cela il initialise l entr e T A et l entr e R 1 premi re tentative e Le processus de surveillance Watchdog observe l entr e point e par W et incr mente t tous les ticks 1tick 240ns Lorsque t devient gal au champ T d
47. d un accus de r ception L envoi de l acquittement la seule condition qu un drapeau bis soit pr sent sur le der nier paquet d un message conduit une mauvaise signalisation En effet comme on peut le voir sur la figu re 11 on acquitterait des messages non re us int gralement MSg A seq 1 bis 2 2 Machine Machine Temps source destination Fig 11 Un cas de double faute Dans ce cas on voit bien qu il ne suffit pas d envoyer un acquittement lors qu on trouve le dernier paquet d un message avec le drapeau bis Emmanuel Dreyfus 29 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC En fait la condition n est m me pas la r ception int grale du message avec le drapeau bis Certaines conditions particuli res font qu on peut tr s bien recevoir en entier un message avec le drapeau bis et ne pas pouvoir envoyer d accus de r ception Une telle situation est d crite par la figure 12 Le probl me de la figure 12 peut tre r gl si l on emp che l metteur d envoyer des messages entre une retransmission et son acquittement Ainsi le message B ne peut tre retransmis avant que le message A soit acquitt et on est ainsi sur qu il sera accept Cette disposition nous donne l change d crit sur la figu e 13 Machine Machine Temps source destination Fig 12 Probl me de double faute On a une double perte du me
48. d e serait de r gler le d lai de r mission 850ns Mais ce serait une grave erreur tout d abord ce chiffre de 850ns est un chiffre id al correspondant une situation o les bus PCI sont toujours disponibles sans d lai o le r cepteur peut envoyer un accus de r cep tion imm diatement et o il n y a aucun retard d de la congestion dans le r seau HSL Nous devons donc utiliser une valeur sup rieure 850ns De plus la perte d un paquet tant un v nement rare avoir un timeout sur dimensionn n a pas un impact norme sur les performances Par contre un fimeout trop petit provoquera de multiples re missions de paquets dus des retards d accus s de r ception Si ces retards sont li s de la congestion sur le r seau HSL on va saturer encore plus le r seau Avoir un timeout court est donc d finitivement une id e rejeter La question reste comment dimensionner le d lai de re mission On a vu qu on pouvait avoir attendre 31us pour que le r cepteur soit en mesure d envoyer un acquittement Si on s int resse aux pro bl mes d obtention du bus PCI on constate qu on peut attendre jusqu 255 transactions de 30ns par p ri ph rique pr sent sur le bus avant d obtenir le bus Ceci nous fait 76 5us au pire si on compte 10 p riph riques sur le bus Ensuite nous avons la travers e du r seau HSL L le probl me est pire encore un paquet pouvant rester bloqu un temps
49. de communication de haut niveau On d crit ensuite dans la partie IV les caract ristiques de la machine MPC nouvelle g n ration MPC 2 c est dire essentiellement les possibilit s offertes par le nouveau contr leur r seau actuellement en cours de d veloppement au LIP6 Les parties V VL et VII correspondent au travail r alis pendant mon stage de DEA La partie V abor de le probl me de la s curisation sur MPC 2 et d gage les besoins satisfaire et les m canismes requis pour obtenir une s curisation sur la machine MPC 2 Au cours de cette partie les diff rentes fautes pouvant sur venir sont examin es et des solutions pour corriger ces erreurs sont propos es La partie VI est une proposition d impl mentation d une primitive de communication bas niveau s curis e S PUT Elle reprends les besoins d gag s dans la partie V et d finit comment les choses pourraient tre impl ment es pour obtenir la s curisation La r partition des t ches entre mat riel et logiciel est trait e au cours de cette partie La partie VI se finit par une r f rence de S PUT qui synth tise les diff rents m ca nismes et comportements qui ont t d crits jusque l Les performances th oriques de S PUT sont finalement tudi es de fa on sommaire dans la partie VIL On y calcule des ordres de grandeur de la latence et du d bit disponibles avec cette nouvelle primitive de communication Il est suppos dans ce rapport qu
50. de l accus de r cep tion Si au bout d un certain temps l accus n arrive pas timeout le message est envoy une deuxi me fois On note que la deuxi me mission doit se faire avec les m mes num ros de s quence que la premi re On constate qu avec cette m thode on sait quand le message a t re u et donc quand on a la certi tude de pouvoir lib rer le tampon d mission Il faut aussi noter que le syst me des num ros de s quences Emmanuel Dreyfus 27 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC impose aux paquets de sortir du r seau dans l ordre o ils y sont entr s On requiert du r seau HSL qu il se comporte en FIFO c est dire qu il ne soit pas adaptatif V 4 Perte ou retard d un accus de r ception Nous avons envisag la perte d un paquet nous devons maintenant envisager la perte d un accus de r ception Lors d une telle perte le r cepteur a d j re u le message et il l a signalis l utilisateur Le tam pon en r ception n est donc pas utilisable Si nous crivons dans ce tampon nous risquons de d truire des donn es crites par l application propri taire du tampon Par ailleurs l metteur ne voyant pas arriver d ac cus de r ception va finir par faire un timeout et renvoyer le message Ce message doublon arrive au desti nataire et ne doit pas tre d pos dans la m moire
51. de routage adaptative para t donc peu avantageuse mais elle reste possible V 7 Impact sur les performances Etudions l impact des propositions pr c dentes sur les performances Plusieurs aspects sont prendre en compte le travail du processeur pour g rer les communications ainsi que la latence et le d bit du r seau tant donn que nous n avons pas encore pr cis ce qui doit tre g r par le logiciel et ce qui doit tre g r par le mat riel il n est pas possible ce stade de l tude de pr ciser la charge de travail incombant au pro cesseur Int ressons nous donc la latence et au d bit V 7 a Latence La latence est augment e par rapport au PUT de MPC 1 Dans MPC 1 le tampon d mission tait lib r d s que le dernier mot de 32 bits quittait PCIDDC Maintenant nous devons compter e le temps d criture dans la m moire distante des donn es en cours de transit dans le r seau e le temps de propagation de ce dernier mot jusqu au contr leur r seau de la machine distante e le temps d crire ce dernier mot dans la m moire distante e le temps que le processus transmetteur du n ud devienne disponible pour mettre un acquittement e le temps de travers e d un accus de r ception jusqu au contr leur r seau de l metteur Au moment de l envoi du dernier mot de 32 bits il reste jusqu une centaine de ko de donn es en cours de transit sur le r seau dans les files d attentes des
52. donn es qu on a mis dans les champs PRSA et PLSA de l entr e de LPE PCIDDC transf re toutes les donn es par DMA donc de fa on totalement asynchrone vis vis du processeur Il est donc n cessaire de pouvoir d tecter la compl tion des diff rentes t ches effectu es par PCIDDC Ceci peut se faire de deux fa ons e par scrutation de la LPE et de la LMI e en demandant PCIDDC de g n rer une interruption lorsque la page correspondant une entr e de LPE a t envoy e ou quand une entr e de LMI correspondant une page arriv e est ajout e Chacune de ces deux m thodes pr sente son avantage par scrutation la latence d un envoi est r dui te car elle ne comprend pas les interruptions Par contre le processeur doit tre sollicit pour scruter p rio diquement la LMI et la LPE Ce temps de scrutation est ainsi perdu pour les calculs La m thode par inter ruption permet d viter de perdre du temps la scrutation mais la latence des changes en est allong e Les deux modes sont disponibles mais pas simultan ment On choisit l une ou l autre en compilant MPC OS avec l option PUT MODEL INTERRUPT DRIVEN pour les interruptions ou PUT MODEL POLLING pour la scrutation La Fig 3 donne une vue d ensemble des diff rentes tapes n cessaires dans la transmission d un bloc de m moire un message constitu d une seule page pour simplifier e Etape 1 criture de l entr e de LPE correspondan
53. e l entr e point e par W il indique que le message d crit par l entr e est renvoyer en mettant le champ T 0 r initialise t 0 et passe l entr e suivante en incr Emmanuel Dreyfus 44 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC mentant W Si W devient gal N il n y a plus de message en transit surveiller et watchdog s endort en attendant l envoi d un nouveau message e Le processus de r ception lorsqu il re oit un accus de r ception supprime l entr e correspondante en mettant son champ R 0 et en reportant l ch ance sur l entr e valide suivante Si c est l entr e point e par F qui a t acquitt e F doit tre incr ment pour pointer sur l entr e valide suivante e Lorsque le processus de surveillance marque une entr e comme tant en instance de retransmission un compteur nomm R est incr ment Lorsque ce compteur est non nul le processus d mission sait qu il doit en priorit renvoyer les messages en timeout avant de pouvoir envoyer de nouveaux messages Il va donc parcourir la table partir de l entr e point e par F et jusqu l entr e point e par W la recherche de mes sages renvoyer chaque message renvoy l ancienne entr e est invalid e et une nouvelle entr e est cr ee l endroit point par N De plus R est decr ment de telle fa on q
54. e le lecteur dispose de connaissances g n rales en informatique et plus particuli rement en architecture et programmation des syst mes parall les Emmanuel Dreyfus 9 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC IT Architecture g n rale de la machine MPC 1 Cette partie est consacr e la description du fonctionnement g n ral de la machine MPC Elle d crit les motivations des choix de fonctionnement le mode z ro copie la fa on dont les donn es sont transf r es ainsi que la fa on dont le logiciel g re tout cela IL 1 Objectif z ro copie Les probl mes de recopie m moire sont parmi ceux qui nuisent le plus aux performances des com munications entre machines dans un r seau de PC La Fig 1 illustre les diff rentes recopies qui se produisent lors d un change quelconque sur un r seau classique Espace m moire utilisateur Espace m moire utilisateur Donn es transferer Espace m moire noyau recopie m moire recopie m moire Espace m moire noyau recopie recopie m moire m moire 5 Carte r seau Carte r seau M moire I O M moire I O Transfert par le r seau R seau Fig 1 Diff rentes recopies m moires mises en jeu lors d un transfert de paquet sur un r seau classique par exemple eth
55. e num ro de s quence gal au num ro bis attendu Si on re oit le dernier paquet du message avec le num ro bis attendu et le drapeau bis alors on envoie un accus de r ception La figure 22 donne un exemple d utilisation de la table seq seq bis Msg A seq bis D but A Entr e en mode comptage 2 des paquets bis 3 3 3 3 3 4 B Sortie du mode comptage des paquets bis Machine Machine source destination Fig 22 Utilisation des num ros de s quence auxiliaire En le r cepteur d tecte un drapeau bis sur un paquet de d but de message En B il d tecte un paquet bis de fin de message avec un num ro de s quence correspondant au num ro auxiliaire attendu ceci provoque l envoi d un acguittement Temps Emmanuel Dreyfus 50 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC VI 4 Impl mentation du m canisme d envoi des accus s de r ception Dernier m canisme mettre en place l envoi des accus s de r ception Ce m canisme pose un pro bl me particulier il requiert une forme de communication entre le processus s occupant de la r ception des paquets et le processus s occupant de l mission des messages non acquitt s ce stade de l tude nous savons que la retransmission des messages non accus s et le syst me de num ros de s quences seront g r s dans le mat riel Il s agit donc de mettre au point la
56. e processus d mission Tx acquittement pour le processus de r ception Rx et d passement du d lai de retransmission timeout pour le processus de surveillance Wd Avant de d tailler les op rations rappelons un certain nombre de notations eT Le champ ch ance d une entr e de la table eR Le nombre de tentatives de renvoi d une entr e de la table et Le temps courant manipul par Wd Il est exprim en ticks de At 240ns A La d lai de retransmission timeout en Le nombre d entr es dans la table e XT La somme des ch ances des entr es de la table eR Le nombre d entr es en instance de renvoi c est a dire ayant le champ R 0 eN Le pointeur de premi re entr e libre F Le pointeur du plus ancien message eW Le pointeur sur le prochain message en timeout Rappelons les conditions importantes nonc es au VI 1 b e La table est vide si N F e La table est non pleine si N 1 F n e Un l ment est valide il d crit un message en transit si R Z 0 sinon il est invalide e Un l ment d crit un message en instance de retransmission si il a T 0 et R 0 e Les l ments valides sont entre F inclus et N exclu e Les l ments en instance de retransmission sont entre F inclu et W exclu e Les l ments valides en attente d acquittement sont entre W inclu et N exclu Et voici le d tail de chaque op ration sur la table Emission originale Tx Si table non pleine envoi du message t
57. ente de celle o un paquet reste bloqu et faire un ping pong ne permet donc pas de savoir si il reste des paquets bloqu s dans le r seau Le protocole SCP P se divise en plusieurs sous protocoles Action refaire RECV si send en attente delai de garde coul N cessite d tection de send en attente Probl me Perte de RECV Cons quence un nouveau SEND en d coulera Probl me N cessite lib rer le tampon d tecter fin d mission de transaction Action refaire un SEND Probl me Perte de SEND N cessite m canisme de r cuperation des MI Probl me x Action ka Probl me sviter Te ttavaii si RECV alt r Paquet corrompu vater e ttavar sui r utilisation de la des donn es alt r es E bo te aux lettres Probl me si SEND alt r s assurer qu il a quitt le r seau Probl 7 N cessite Pa I0 APS d pouvoir vider le r seau i Ga entre deux n uds Fig 5 Construction du protocole SCP Ce diagramme met en relief les probl mes pouvant survenir les solutions mettre en uvre pour les r gler et le sous protocole assurant ces actions e SFCP permet de notifier le r cepteur qu un send est en attente Il s agit d un ping pong qui permet Emmanuel Dreyfus 21 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC l
58. ercheurs du d partement ASIM du Laboratoire d Informatique de l Universit de Paris 6 LIP6 du PRiSM de l Universit de Versailles Saint Quentin UVSQ du LARIA de l Universit de Picardie Jules Verne et des d partements informatiques de l Institut National des T l communications d Evry INT Evry et de l Ecole Nationale Sup rieure de T l communications de Paris ENST Paris Le but du projet est de d velopper une machine parall le co t r duit en utilisant du mat riel stan dard sur le march savoir des compatibles PC auxquels on fournit un r seau hautes performances Les comp tences mises en uvre vont du design de circuits int gr s au d veloppement de composants logiciels pour exploiter les circuits 2 Le sujet du stage Mon stage au LIP6 comportait deux parties clairement distinctes la premi re tait un travail d ing nierie faisant office de stage de fin d tudes pour la derni re ann e du cycle ing nieur INT Elle consistait travailler sur la version Linux des composants logiciels exploitant les cartes r seaux de la machine MPC de premi re g n ration MPC 1 Cette travail a donn lieu un rapport de stage ED et une soutenance PINT Outre un perfectionnement dans les aspects syst mes la partie ing nieur du stage m a permis d exa miner assez profond ment le fonctionnement de la machine MPC 1 ce qui m a t fort utile pour la deuxi me partie du stage Ce
59. ernet On a parfois des recopies suppl mentaires pour l empaquetage Typiquement un processus utilisateur utilise une primitive d envoi un send Cette primitive est impl ment e par un appel syst me ou par un appel de fonction dans une librairie Dans ce dernier cas la librairie effectue quelques traitements et finit par faire un appel syst me On en revient donc toujours un appel syst me c est dire un passage en mode noyau Ce cheminement est in vitable car pour des raisons de s curit et de partage des ressources seul le noyau peut avoir acc s au mat riel Au cours de l appel syst me le processeur va recopier les donn es transmettre depuis l espace m moire du processus utilisateur vers l espace m moire du noyau Une fois en mode noyau c est le pilote de la carte r seau qui travaille Il va g n ralement recopier les donn es transmettre dans une m moire d en tr e sortie situ sur la carte Une fois les donn es copi es dans cette m moire d entr e sortie c est au mat riel de s occuper de leur acheminement sur le r seau Les donn es arrivent alors sur la machine r ceptrice dans la m moire d entr e sortie de la carte r seau Quand un paquet de donn e est re u en entier la carte va lever une interruption pour signaler au pro Emmanuel Dreyfus 10 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC cess
60. es d entre elles ont t corrig es dans PCIDDC second run Parmi les cartes connecteurs Harting certaines sont en PCIDDC first run et d autres en PCIDDC second run Toutes les cartes connecteur Lemo utilisent des circuits PCIDDC second run Pour s y retrouver on parle de r visions de cartes FastHSL Rev PCIDDC first run 7 connecteurs Harting Rev B PCIDDC second run 7 connecteurs Harting Rev C PCIDDC second run 8 connecteurs Lemo Chaque n ud de calcul de la machine MPC est quip d une carte FastHSL Les cartes Fast HSL sont li es entre elles par le r seau de donn es compos de liens HSL Par ailleurs pour les op rations de confi guration la machine MPC requiert un r seau de contr le Celui ci peut tre n importe quel r seau capable de transporter le protocole TCP IP Actuellement c est un r seau ethernet qui est employ La Fig 2 donne un aper u g n ral d une machine MPC 4 n uds Carte PCI Carte PCI FastHSL R seau HSL donn es Carte PCI FastHSL Carte PCI FastHSL Processeur Contr leur ethernet Contr leur ethernet N ud 1 Processeur Contr leur ethernet Processeur Contr leur ethernet R seau ethernet contr le Fig 2 Machine MPC 4 n uds On a choisi ici d utiliser un r seau HSL fortement connexe Emmanuel Dreyfus 12 17 08 2000 S curisation des primitives de communication bas niveau dans une machine
61. es messages courts longs Cette fonctionnalit a t examin e dans le d tail et est m me pr sente dans les diagrammes d taillant le fonctionnement des processus Il s agit d utiliser la LPE et la LMI comme tampon respectivement d mis sion et de r ception Lorsqu une entr e de type message court est lue le champ Length qui indique habi tuellement la longueur de la page transf rer indique la longueur du message court S il est inf rieur 8 il s agit d un message court au sens de MPC 1 sinon on va transf rer les entr es suivantes de la LPE et le d poser dans la LMI On peut ainsi avoir des messages courts de plusieurs dizaines d octets si on le souhai te Des messages courts encapsul s dans les messages Une critique vive qui existait tait le fait que le MI tait trop court Nous avons propos des mesures pour restituer la totalit du MI l utilisateur mais il reste qu il serait agr able de disposer de MI de l ordre de la dizaine d octet Une solution est de permettre la pr sence de messages courts encapsul s l int rieur des messages standards Actuellement une entr e de LPE de message court perdue au milieu des entr es de LPE de message normal est une erreur On pourrait tr s bien admettre qu on d place un message court entre deux pages et que le tout forme un message Dans ce cas on peut tr s bien commencer un message par une entr e de message court et ainsi disposer d oct
62. et l adresse laquelle le bloc doit tre transf r sur le n ud distant PRSA Le champ control permet de d terminer certains comportements optionnels comme par exemple l envoi d un message court Dans ce cas les champs PRSA et PLSA contiennent les donn es transf rer au lieu d indiquer leurs adresses source et destination La liste des messages re us LMD est mise jour par PCIDDC d s que toutes les pages d un messa ge ont t crites dans la m moire Ses entr es sont de type 1Imi entry _t d finies ainsi typedef struct _Ilmi entry u_ short packet number Identifiant du message MI u_ short r3_statut registre R3 u_short reserved Reserved for future use Emmanuel Dreyfus 14 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC u_ short control Options diverses u_ long datal Adresse source u_ long data2 Adresse destination Imi_entry t Le champ packet_number contient le MI du message Le champ r3 statut contient la valeur du registre R3 de PCIDDC qui indique l tat des 8 liens de R Cube Le champ control correspond au champ control de l entr e de LPE associ au message Enfin les champs data1 et data2 correspondent aux adresses sources et destination du bloc trans f r comme les champs PRSA et PLSA de l entr e de LPE Dans le cas des messages courts ces champs contiennent les
63. ets suppl mentaires transf r s de la LPE la LMI pour conce voir des protocoles de haut niveau Des envois de messages entrelac s On a d cid dans le pr sent document que l envoi d un message tait atomique il est impossible d envoyer deux messages la fois en entrela ant les pages ou les paquets Ceci est d au fait que mat riel lement c est beaucoup plus facile g rer Etant donn que la taille des messages n est actuellement pas limi t e on peut se retrouver dans des situations o un processus va accaparer toutes les ressources en envoyant un message trop gros d t riorant ainsi les performances des communications des autres processus L entrelacement des messages est donc tudier Signal d avanc e dans la LPE Avec PCIDDC on signale au contr leur r seau qu on a ajout une entr e de LPE en d pla ant un pointeur par un acc s en configuration PCIDDC va ensuite lire l entr e en m moire par DMA Une id e d optimisation serait de donner directement l entr e de LPE ANT par acc s m moire Soit ANI n a pas d entr es en retard et il peut alors traiter imm diatement l entr e soit il y a des entr es en retard Dans ce dernier cas l acc s m moire provoque simplement une avanc e du pointeur et ANI viendra lire par DMA le descripteur de LPE en temps utile Par cette m thode on peut gagner en latence en vitant un acc s PCI quand ANI n est pas en train de traiter
64. etteur peut se comporter de fa on passive et que c est au r cepteur de s occuper de d tecter les transaction non com pl t es Si l on essayait de s curiser PUT on devrait provoquer l envoi d un accus de r ception chaque fois que le r cepteur re oit un message Dans cette voie l metteur est charg de v rifier la compl tion des tran sactions On le voit ces deux situations ne sont pas identiques Dans le cas de la s curisation de SLR c est au r cepteur de veiller la compl tion des transactions dans le cas de la s curisation de PUT c est l met teur La gestion de la compl tion par l metteur pose un probl me comme le r cepteur ne peut emp cher le d p t d une page si l metteur r envoi une page alors que le tampon a t lib r sur le r cepteur ceci va arriver si un accus se perd et que le r cepteur croit la transaction termin e alors que l metteur croit le contraire on va craser des donn es appartenant une application D autre part si c est le r cepteur qui g re la compl tion des transactions ce probl me dispara t les donn es sont envoy es au r cepteur sa deman de et il ne peut donc pas y avoir crasement des donn es contenues dans un tampon d j lib r Le probl me de la s curisation de PUT sur MPC 1 n est pas insoluble il est probable qu en ajoutant des acquittements d acquittements on parvienne une solution accept
65. eur de la machine destination que des donn es sont arriv es Cette interruption fait passer le processeur de la machine r ceptrice en mode noyau dans le pilote de la carte r seau Les donn es vont alors tre reco pi es de la m moire d entr e sortie de la carte vers un tampon dans l espace m moire du noyau Apr s la r ception des donn es diff rents traitements sont possibles Si les donn es s av rent tre destination d un processus ayant requis des communication asynchrones il faut par exemple lui notifier l ar riv e des donn es par un signal typiquement un S G10 Si le processus destinataire a d j ex cut une pri mitive de r ception un receive il avait t endormi par un sleep en attendant l arriv e des donn es et il faut le r veiller par un wakeup Enfin si le processus destinataire n a rien demand il faut conserver les donn es dans l espace m moire noyau en attendant qu il veuille bien les demander par un appel une pri mitive de r ception de donn es Une fois que le processus destinataire est pr t recevoir les donn es le processeur doit finalement copier l ensemble des donn es pour les ramener de l espace m moire noyau vers l espace m moire utilisa teur Durant cette communication toute simple les processeurs des machines source et destination ont chacun recopi 2 fois les m mes donn es Ceci repr sente un temps consid rable si de grosses quantit s de d
66. ge reste dans la table des mes Emmanuel Dreyfus 41 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC Compteur de temps Index IN entr e de LPE N canal RWU Tentatives Compteur de temps Index Index IN entr e de LPE Tentatives Compteur de temps Index N canal RWU Tentatives N canal RWU Tentatives id Daccus Machine Temps p source Machine destination Fig 18 Table des messages en transit index e par le temps lors d un envoi avec erreur Par souci de clar t on s est limit une table du Temps 5 entr es les dur es des temps d mission et d accus de r ception ne correspondent pas aux valeurs r elles et les messages font tous un paquet Emmanuel Dreyfus 42 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC sages en transit Au bout d un moment le compteur de temps arrive la derni re entr e de la table Il est alors re initialis et le travail continue en reprenant la premi re entr e de la table Arrive alors un moment o le compteur de temps va pointer sur l entr e correspondant au message qui n a pas t acquitt C est le momen
67. ges devient trop important Cette possibilit n est pas appro fondie dans le pr sent document mais elle constitue une piste possible pour optimiser les ressources utilis es par la s curisation des communications Il faut toutefois noter que les suggestions d optimisation sur les accus s de r ception ne sont pas for c ment int ressantes Si le m canisme d acquittement est g r logiciellement alors effectivement l envoi des acquittements dans les en t tes des paquets allant en sens inverse ainsi que l agr gation des acquitte ments seront des id es retenir Par contre si on doit g rer ce m canisme mat riellement ces optimisations deviennent extr mement co teuse Ce qui se fait facilement dans la mat riel ce sont les op rations orthogo nales les collaborations entre t ches mat rielles sont toujours un probl me d licat On n essayera donc pas de les mettre en place si on arrive une solution o les acquittements sont g r s par le mat riel V 8 s curisation au niveau SLR Examinons ce qui se passerait si on tentait de s curiser la machine MPC 2 au niveau SLR La figure 4 d crit un transfert dans les deux cas possibles send avant le receive et receive avant le send D Machine Machine Temps source destination Fig 17 Deux changes SLR bas s sur PUT s curis Maintenant examinons sur la figure 17 ce que donne SLR au dessus du PUT s curis propos dans le pr sent docume
68. ien plus faible que cette valeur attendue de 30 ans En pratique dans le pire cas c est dire avec un r seau charg au maximum on subit des fautes avec un MTBF de deux minutes Emmanuel Dreyfus 18 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC Ceci est principalement d un probl me dans R Cube qui rend le circuit particuli rement sensible la gitte du front d onde des paquets sur les liens HSL Ce probl me est accentu par l usage des connecteurs Lemo qui provoquent des couplages entre le lien montant et le lien descendant sur les c bles bi coaxiaux utilis s pour relier les routeurs R Cube Une erreur se manifeste par la perte d un ou deux paquets sur le lien Comme la machine MPC 1 n a l origine aucun moyen de r cup rer sur cette erreur une faute provoque un arr t de la machine On en arri ve donc une situation o la reprise sur erreur n est plus du tout inutile IL 7 b Acc s en configuration sur jeu de composant 440BX Autre probl me PCIDDC est fait pour tre command par des acc s en configuration Habituellement les cartes PCI sont command es par des acc s en configuration lors du d marrage de la machine pour les initialiser Une fois l initialisation faite sa m moire est mapp e dans la m moire virtuelle de la machine et on la commande par des acc s m moire Les cartes PCI normales n ont donc pas besoin d acc
69. in Retransmission du message A avec IDX 1 R T oliljifofo Message Ee Entr e LPE 0 0 3 410 J0 i Eug Fin du messsage c est une retransmission on travaille sur la Node LPE O0 00000 1 5 SUUN n 3 m me entr e R est gal 2 car c est la deuxi me tentative l a XR 0 J ack IDX Index OI1 213 41 5 L accus du message A IDX 0 arrive Il est accus et F T 3 01 1710 avance jusqu au prochain message renvoyer RO 4Jojijaj29 t arrive 1 ce qui est l echeance de l entr e point e Entr e LPE O 0 31 1710 par W Le message C va donc tre en timeout Node LPE 0101010 01 0 i C est retransmis avec IDX 2 IDX 2 Index 0112131415 T ojolo iTo M R 010711112710 Machine Machine Temps Entr e LPE 0 0 3141170 source destination Node LPE 0101010 01 0 Fig 21 Exemples de manipulation sur la table des messages en transit en int grant les r gles du VS Ainsi on arrive re envoyer les messages avec le m me index Emmanuel Dreyfus 47 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC mais peut exister La seule fa on de l viter est de renoncer la signalisation des chec et tenter d mettre le message ind finiment quitte bloquer la machine en cas de c ble d branch La deuxi me version de la table avec champ d ch ance nous permet tout ce que permet la premi re mais en plus elle permet de manipuler li
70. ion des primitives de communication bas niveau dans une machine parall le de type grappe de PC Dans l exemple de la figure 19 pour ajouter une action par exemple ex cuter dans 32 ticks 1l suf fit d ins rer un l ment dans la cha ne entre le deuxi me et le troisi me avec une ch ance de 2 et de modi fier l ch ance de l l ment suivant pour la faire passer de 5 3 De m me on peut supprimer un l ment moyennant d augmenter le champ d ch ance de l l ment suivant Lorsque l on ajoute ou on supprime des l ments dans la cha ne la somme des champs d ch ance des l ments doit rester constante sauf si l op ration porte sur le dernier l ment ou si il s agit de l ex cution du premier l ment Ce m canisme tel qu il est employ dans 4 4BSD est tr s g n ral On peut l utiliser pour g rer n im porte quelle situation Pour ce qui nous concerne une faible partie de ses fonctionnalit s nous int resse car on est dans un cas particulier le timeout etant fixe les nouveaux l ments sont toujours ajout s la fin de la cha ne jamais au milieu On peut donc se passer de l aspect liste cha n e et se contenter d utiliser une table Ceci a son importance car on d sire si possible g rer ce m canisme mat riellement La table des messages en transit va donc s organiser comme suit chaque entr e contient les champs suivants e Ech ance T e Nombre de tentatives
71. ir 2 champs e Le num ro du n ud destinataire 16 bits e L index du message acquitt 8 bits Ces deux champs ont une largeur totale de 24 bits Le FPGA ne permettant que des largeurs de puis sances de 2 donc une place fera 32 bits avec 8 bits inutilis s La file d attente occupe donc 0 5ko ce qui est raisonnable La file d attente des acquittements est remplie par le processus de r ception des paquets Le proces sus d envoi des acquittement la vide en utilisant l op rateur de construction de paquet nous verrons tout cela plus en d tail dans la partie suivante Lors de l usage de cet op rateur le processus d envoi des acquitte ments entre en conflit avec le processus d mission des messages Comme il a t pr cis pr c demment l arbitrage va toujours du cot du processus d acquittement quand le processus d mission de messages a envoy un paquet 1l ne peut en envoyer un autre tant que le processus d envoi des acquittement n a pas vid la file d attente des accus s de r ception Emmanuel Dreyfus 51 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC VI S Bilan des contraintes impos es par la s curisation Nous avons maintenant une id e tr s claire de ce qui doit tre g r par le logiciel et ce qui doit tre g r par le mat riel Nous n avons laiss aucune t che accomplir par le logiciel C est le FPGA qui pre
72. l faut ajouter 8 bits pour le caract re de fin de paquet End of Packet On arrive 36 bits On souhaite avoir un paquet long d un multiple de 32 bits Si on pla ait un CRC avec la m me disposition que dans les paquets classiques on devrait compter au moins 128 bits au total On pr f re donc se passer de CRC et doubler toutes les donn es pour les prot ger des erreurs Le paquet d acquittement fait donc 12 octets SF xx00 Message normal SF xx01 Message court S P RD sn EH End of Header EP End of Packet IDX Index table des messages en transit Drapeau bis MI Message Identifier D but de message PKL Packet Length RPD Routing Part Destination _ RPS Routing Part Source SEQ Sequence E Champ SF SF System Flags UF User Flags m Type du paquet Fig 30 format des paquets utilis s par S PUT Le format des acquittements est un peu particulier comme on n a pas la place de placer un CRC on envoie tous les champs en double Emmanuel Dreyfus 63 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC VITI Performances Pour finir examinons les performances obtenues avec S PUT 1 0 pour cela on va calculer les d bits et latences moyens obtenus avec le protocole de correction d erreur On va supposer pour cela qu on a pas de doubles fautes On va envisager le pire des cas qui est celui d un paquet perdu pour un accus
73. le mapp e de fa on continue en m moire physique que l on d sire transf rer On peut g rer des pages r seaux correspondantes aux pages de la m moire virtuelle La m moire virtuelle est g r e par pages de 4ko mais cela n est pas une obligation une page r seau a une longueur arbitraire entre 1 et 65536 octets La seule contrainte est la continuit en m moire physique Lors du transfert les pages sont d coup s en un ou plusieurs paquets HSL Emmanuel Dreyfus 13 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC Message Un message est un ensemble de page dont on souhaite se voir notifier le transfert en une seule fois Par exemple si on envoie une colonne de matrice on aura une page par l ment puisqu ils ne sont pas rang s de fa on contigu en m moire mais l ensemble des pages constituera un message et c est le trans fert du message et non pas des pages individuelles qui sera notifi Num ro de n ud Chaque machine sur le r seau HSL poss de un num ro de n ud Les num ros de n uds sont statiques et assign s l initialisation du r seau par MPC OS Identifiant de message MI Message identifier Chaque message dans le contexte d une communication entre deux n uds poss de un identifiant unique Pour assurer l unicit des MI chaque processus utilisateur sur chaque n ud se voit attribuer un intervalle de MI par MPC OS Me
74. le paquet en memoire Le message a t il le drapeau bis Incr menter le num ro de s quence attendu pour le n ud metteur Premier paquet d un message Initialiser le num ro de a s quence bis pour le Oui n ud metteur RC du paque y correct quence gale la s quence bis attendue LA on Incr menter le num ro Incr menter le num ro de s quence attendu de s quence bis pour le pour le n ud metteur n ud metteur gt F Est ce le dernier paquet Est ce le dernier paquet de la derni re page d un de la derni re page d un message message ACK Non Non R w y gt Placer un accus en file d attente 7 Y gt gt gt Fig 28 comportement du processus Rx Emmanuel Dreyfus 61 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC VI 6 g Comportement du processus d envoi des acquittements Le processus d envoi des acquittements ack lit les accus s de r ception envoyer dans la file d at tente des accus s de r ception Lorsqu un accus est pr t tre envoy Ack est prioritaire sur Tx pour utili ser le constructeur de paquet Pb et envoyer ses acquittements Tx finit donc d envoyer le paquet qu il trai tait puis Ack envoie ses acquittements Une fois que Ack n a plus d acquittements en attente Tx peut
75. lution a des limites cause des difficult s d int gration de circuits de plus en plus miniaturis s La loi de Moore a ainsi commenc a subir une inflexion en 1992 De nos jours pour continuer augmenter la puissance des machines on doit ajouter le parall lisme la miniaturisation L introduction du parall lisme permet d utiliser plusieurs circuits d une puissance donn e en m me temps afin d obtenir une puissance de calcul sup rieure ce qu un seul circuit aurait pu faire Dans les micro ordinateurs on retrou ve le parall lisme un peu partout pipelines et unit s de calcul multiples dans les processeurs contr leurs ou coprocesseurs d chargeants le processeur de certaines t ches syst mes multiprocesseurs etc Pour obtenir plus de parall lisme les approches sont nombreuses Parmi elles la machine parall le de type grappe de PC est assez populaire aujourd hui Dans de tels syst mes on utilise des compatibles PC qui sont des machines peu ch res comme n ud de calcul Chaque n ud poss de sa propre m moire et ex cute ses instructions sur ses donn es propres On est en pr sence d un syst me Multi Instruction Multi Donn es M moire Distribu e MIMD MD Ce choix d architecture permet d viter l utilisation de machines d di es co teuses une machine Single Instruction Multi Donn es SIMD requiert un processeur sp cifique donc cher un syst me m moire partag e demande des m
76. manuel Dreyfus 35 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC Cette valeur potentiellement tr s haute est due au fait qu on ne peut envoyer deux paquets en m me temps de ANI R Cube La seule fa on de la faire diminuer serait de diminuer la taille des paquets En pre nant des paquets de 256 octets par exemple la latence maximum dans le cas id al o le bus PCI est dispo nible tout de suite passe 12us On peut avoir l id e de faire des paquets tr s petits de quelques dizaines d octets mais diminuer autant la taille des paquets ne serait pas raisonnable car le temps pass initier les op rations sur le bus PCI p serait de plus en plus lourd par rapport au temps pass transf rer des donn es Avec une taille de paquet de 256 octets ou plus on maximise le temps pass transf rer des donn es V 7 b D bit En terme de d bit l envoi d un accus de r ception pour chaque message occupe de la bande pas sante Lorsqu il s agit d une topologie fortement connexe il y a forcement un lien non partag entre met teur et r cepteur De deux choses l une e Soit le lien retour n est pas charg dans ce cas on peut envoyer des accus s de r ception dessus sans dimi nuer les performances e Soit le lien retour est charg on pourrait alors placer les accus s de r ception dans les en t te des paquets passant sur le lien retour On ne
77. mission d un autre message L index dans la table n est donc ni le temps ni le num ro du message envoy c est une quantit hybride Pour r soudre ces deux inconv nients on propose l utilisation d une table qui n est pas index e par le temps mais qui contient des champs d ch ances VI 1 b Table des messages en transit avec champ d ch ance La m thode propos e ici est d riv e de la m thode utilis e dans 4 4BSD pour g rer les timeouts dans le syst me BSD Il s agit d utiliser une liste cha n e Chaque l ment de la liste contient une date d ch an ce en temps relatif une action et bien s r des pointeurs vers les l ments suivants et pr c dents de la liste Le champ d ch ance indique combien de temps apr s l entr e pr c dente l entr e courante doit tre trait e Le syst me poss de un pointeur sur la premi re entr e et il sait en regardant le champ d ch ance de la premi re entr e dans combien de temps 1l doit ex cuter son action Une fois la premi re entr e ex cut e elle est supprim e de la liste et on recommence de m me avec la seconde entr e La figure 19 indique com ment marche la liste cha n e te de chaine Action B A executer datis 10 ticks 10 20 30 ticks 10 20 5 35 ticks 10 20 5 5 40 ticks Fig 19 les listes cha n es g rant les timeouts dans 4 4BSD Le tick est l unit de temps Emmanuel Dreyfus 43 17 08 2000 S curisat
78. mitives de communication bas niveau dans une machine parall le de type grappe de PC Index T R Entr e LPE Node LPE W N donc Watchdog dort t 0 ojojojo ojojojojlN ojojojojw ojojojoje ojojojojvi IDX On envoie un message A avec IDX 0 Fin du message on l ajoute dans la table fin me Ssa ee Watchdog commence compter IDX 1 Envoi d un message B avec IDX 1 Le message est fragment en deux paquets Entr e LPE Node LPE IDX X fin Fin du message on l ajoute dans la table message R Index o 1 l2 3 4 5 IDX 2 On envoie un message C avec IDX 2 T 3111010101 0 R LI110 010710 fin mes sage Entr e LPE 0 110 0 070 Fin du message on l ajoute dans la table Node LPE 0 0 0 01 010 8 F t arrive 3 ce qui est l ch ance de l entr e surveill e par YR watchdog pointeur W Le temps est r initialis 0 Tade 011121314153 l entr e point e par W est marqu retransmettre T 0 et T 3111101010 IDX W est increment R 1i 1 lo lolo On ne peut retransmettre le message A tout de suite car un Enu LPeltol113101010 message D avec IDX 3 est en cours d envoi Node LPE 0 0 0 01 010 t 0 ack DXO YR 1 Arriv e de l acquitement du message B IDX 1 Le max MORENIE message B est signal comme recu Comme W pointait
79. moire centrale l l l l l l l l l l l l 32 bits l l l l l l l l l l M moire centrale l l l l l l l l l l l l l l l l l l l l l l l l l i oraaa Machine destination Fig 3 Diff rentes tapes mises en jeu lors du Transfert d un bloc de m moire par la machine MPC Etape 9 optionnelle signalisation de l mission de la page par interruption Une fois l tape 8 termin e les tapes 10 et 11 peuvent tre ventuellement faites sur le r cepteur e Etape 10 optionnelle mise jour de la LMI par PCIDDC Cette mise jour est faite par une op ration de DMA au cours de laquelle l entr e correspondant au message arriv est ajout e la LMI e Etape 11 optionnelle lev e d une interruption pour signaler la machine destination qu un message est arriv L activation des comportements optionnels est assur par des drapeaux dans le champ control On peut trouver plus d informations sur le fonctionnement de PUT dans le manuel du programmeur de MPC 1 MPC IL 6 Primitives de communication de plus haut niveau SLR Nous avons jusqu ici illustr le fonctionnement de la machine lors de l usage de la primitive de plus bas niveau de la machine MPC 1 savoir PUT MPC OS impl mente logiciellement des primitives de plus haut niveau SLR P et SLR V Cette partie d crit rapidement ces deux primitives PUT est une interface de t
80. n es dans le tampon en r ception dont on conna t l adresse sur le n ud destinataire e Soit on n a pas encore re u de message de contr le du n ud destinataire indiquant l emplacement du tam pon de r ception Dans ce dernier cas le send est mis en attente et c est la r ception d un message de contr le d un receive qui va provoquer l mission des donn es par PUT La fig 4 donne un aper u d un change SLR P En r sum le transfert des donn es est fait par le n ud metteur une fois qu il a connaissance des emplacements du tampon d mission et du tampon de r ception Ceci revient la conjonction des deux conditions suivantes e Le n ud metteur a eu un send e Le n ud metteur a re u le message de contr le d au receive sur le n ud r cepteur La fig 4 illustre les deux changes SLR possibles suivant l ordre du receive et du send Emmanuel Dreyfus 17 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC Contr le Machine Machine Temps source destination Fig 4 Echanges SLR dans deux cas en bas le send a t fait avant le receive En haut le receive a t fait avant le send Dans SLR le receive d clenche un message de contr le indiquant o les donn es doivent tre crites L metteur n envoie les donn es qu une fois qu il a 1 re u ce message de contr le et 2 eu un send en a
81. n train d mettre un message ou entre chaque mission de message si il est en train d mettre Ce compteur est synchronis sur les cycles du bus PCI Appelons ce compteur compteur de temps Chaque message envoy porte dans ses en t tes son num ro d index le msg dans les figures de la partie V C est l index du message dans la table des messages en transit Il faut noter que ce num ro d in dex n a rien voir avec l identifiant de message MD utilis dans l API PUT de MPC 1 Contrairement aux MI ce num ro d index est totalement g r par le syst me et l utilisateur n y a pas acc s Le m canisme des MI est parall lement maintenu et il n est utilis nulle part par S PUT Conform ment aux observations concernant le champ MI dans la partie IL 7 c nous le laissons enti rement l utilisateur Lorsque le r cepteur re oit un message il renvoie un accus de r ception Dans cet accus il y place l index du message L metteur du message recevant l accus de r ception prend connaissance du num ro d index IDX du message qui est acquitt Il peut alors aller lire dans la table des messages en transit lin dex IDX l index du descripteur de LPE de la premi re page du message L entr e correspondante dans la table des messages en transit est lib r e et l mission du message est signal e l utilisateur Si aucun accus de r ception n arrive l entr e correspondant au messa
82. nd en charge la totalit des op rations concernant la s curisation La m moire occup e par S PUT dans le FPGA se r partit comme suit Table des messages en transit 2ko Table des s quences transmission 0 5ko Table des s quences r ception 0 5ko Table des s quences auxiliaire 0 5ko File d attente des acquittements lko Total 3 5ko Et par ailleurs les contraintes impos es e Pas de tables de routage adaptatives e Pas plus de 256 n uds avec 65536 n uds on aurait besoin de 387ko de m moire e Le d coupage des messages en paquets est d terministe e L envoi d un message est atomique 1 e on n entrelace pas les paquets de deux messages diff rents Emmanuel Dreyfus 52 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC VI 6 S PUT 1 0 en bref Cette partie synth tise les partie pr c dentes en pr sentant les diff rents processus utilis s par S PUT 1 0 leur comportement les structures de donn es qu ils manipulent Le format des paquets est aussi propos VL 6 a Pr sentation des structures de donn es S PUT utilise les structures de donn es suivantes d crites en langage C pour viter toute confusion define TRANSIT _TABLE_ SIZE 256 taille de la table des messages en transit define MAX_HSL_NODES 256 nombre de n ud maximum sur le r seau define ACK_FIFO_SIZE 128 taille de la file d attente des acquittements
83. nnable e Le num ro de LPE de m me que le champ pr c dent limite la taille de la LPE ce champ limite le nombre de processus pouvant utiliser simultan ment la carte Fast HSL On a choisit de le fixer 12bits ce qui donne un nombre maximum de processus pouvant utiliser la carte gal 4096 tant donn que le nombre de pro cessus fonctionnant sur un syst me UNIX est nettement moins lev que cela ce champ est nettement sur dimensionn Avec ces valeurs une entr e occupe 64 bits On a dit plus haut que l on souhaitait avoir 62 entr es Pour donner au num ro d index dans la table une taille d un nombre entier d octet prenons 256 entr es Ceci nous fait donc une table de exactement 2ko Cette valeur est suffisamment faible pour permettre d embarquer la table dans le FPGA et donc de g rer totalement mat riellement le m canisme de re mission des messages perdus Nous avons donc dans le FPGA bien s r un processus d mission de message mais aussi un proces sus de surveillance des messages non acquitt s Watchdog VI 2 Impl mentation du rejet des doublons les num ros de s quence Int ressons nous maintenant au m canisme de rejet des doublons c est dire des messages re us en double suite un accus de r ception perdu ou en retard Nous avons abord le probl me au V4 et nous savons que ce comportement est assur par les num ros de s quences d crits au V 1 Un point important est qu il ne
84. nt Si on essaye de faire un SLR s curis sur PUT non s curis c est parce qu on esp re qu avec une vision plus haut niveau des changes on pourra faire des optimisations dues des situations par Emmanuel Dreyfus 38 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC culi res Le but est donc de prendre les changes SLR sur PUT s curis et essayer de supprimer des mes sages On constate rapidement qu on ne peut pas faire beaucoup d conomies Dans le cas o le send est avant le receive les ajouts au SLR sur PUT traditionnel sont les accu s s de r ception des donn es ack 1 et ack 2 sur la figure Le ack 2 est indispensable pour permettre l metteur de savoir quand il peut lib rer le tampon d mission et signaliser la compl tion du send Avec une vision de plus haut niveau on pourrait agr ger le ack 1 dans l envoi des donn es msg 2 sur la figure Dans le cas o le send est apr s le receive on a toujours l accus de r ception des donn es ack 4 sur la figure que l on ne peut pas supprimer pour la raison expos e pr c demment pour ack 2 Reste l ac cus de r ception du message de contr le ack 3 sur la figure que l on pourrait esp rer supprimer en l agr geant avec le message de donn es msg 4 sur la figure Ceci n est h las pas possible car rien n impose que le receive et le send soient rapp
85. ntes l architecture de MPC 1 on y tudie les possibilit s de s curisation en enfin la solution propos e pour s curiser les communications de haut niveau MI 1 Rappel des contraintes existantes Rappelons bri vement les contraintes impos es par le mode z ro copies e Lorsque la fin d un envoi est signal e on ne peut plus utiliser le tampon d mission L application a le droit de le modifier loisir Si on relit le tampon on risque de ne plus avoir les donn es initiales e Lorsque la fin d une r ception est signal e on ne peut plus utiliser le tampon en r ception L application a le droit de le modifier et toute nouvelle criture dans le tampon risque d annuler des modifications faites par l application et une contrainte impos e par PCIDDC e est impossible d emp cher le d p t d une page sur le n ud r cepteur IIL 2 S curisation au niveau PUT ou SLR Aucune tentative de s curisation au niveau PUT n a t tent e sur MPC 1 La raison est une question de facilit En effet au niveau PUT la transaction commence par une demande d mission chez l metteur et finit par une signalisation d arriv e de message sur le r cepteur Par contre au niveau SLR la transaction commence par l appel receive sur le r cepteur et se finit par la notification de r ception ou la compl tion du receive si on a choisi un receive bloquant sur ce m me n ud Ceci sugg re que l m
86. nuel Dreyfus 30 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC Timeout MSg A seq 1 bis SEA seq 2 bis MSg A seq 3 bis T Machine Machine emps AE source destination Fig 13 Pas d envoi de messages entre une retransmission et un acquittement Ce proc d permet d viter le probl me d crit la figure 12 r ception d un message lorsque l une ou l autre des deux conditions suivantes est remplie e Le dernier paquet du message a t d pos en m moire e Tous les paquets du message sont arriv s en ayant t d pos s ou non tous avec le drapeau bis Le probl me des conditions d acquittement tant r solu nous devons maintenant proposer un m ca nisme qui permettra au r cepteur de d tecter que tous les paquets d un message sont arriv s tous avec le dra peau bis D tecter que tous les paquets d un message arrivent revient compter les paquets du message Ce probl me serait assez complexe s il n y avait pas l atomicit de l envoi des messages Un n ud n envoie qu un message la fois et il n entrelace jamais les paquets de deux messages diff rents On est donc assur que du point de vue du r cepteur on n aura compter les paquets que d un seul message par n ud metteur Si on rencontre le drapeau bis m me si les paquets ne sont pas d pos s en m moire on va donc contr ler les num ros de s quen
87. num ros de s quence des paquets re us Les paquets ayant un num ro attendu sont d pos s en m moire les autres sont rejet s Lorsque le dernier paquet d un message est d pos en m moire le message est signal comme re u sur le r cepteur et un accus de r ception est envoy l metteur L metteur peut donc d tecter la perte d un paquet dans un message si il ne re oit pas d accus de r ception pass un certain temps On va donc mettre en place un m canisme de timeout une fois un messa ge envoy un compteur de temps est mis en marche Si l accus de r ception arrive avant le temps limite le message est signalis l utilisateur comme re u Sinon le message est r envoy et le compteur de temps pour ce message est remis z ro Pour que le m canisme de num ros de s quence laisse passer le message envoy pour la deuxi me fois il est indispensable de reprendre les num ros de s quences au num ro du premier paquet du message et le d coupage des pages du message en paquets doit tre le m me On demande donc un d coupage d ter ministe des messages La figure 8 pr sente deux transaction l une sans perte de paquet et l autre avec Machine Machine source destination Temps Fig 8 R cup ration sur la perte d un paquet avec des accus s de r ception Pour chaque message envoy un compteur est mis en marche Il est arr t et le message est signal re u au retour
88. onn es sont chang es Et en tout tat de cause ceci repr sente du temps perdu pour le calcul Le circuit routeur R Cube est capable de d biter 1Gb s C est un d bit assez consid rable mais si ce circuit est exploi t avec les m canismes classiques d crits ci dessus on comprend que les performances ne seront pas au ren dez vous car les processeurs seront essentiellement occup s copier des donn es L objectif dans la machine MPC est donc d impl menter des m canismes de communication pr sen tant la propri t suivante les donn es transf rer ne doivent jamais tre copi es par le processeur On parle de mode z ro copie Pour arriver cet objectif on va faire appel la DMA Direct Memory Access La DMA est un m ca nisme permettant un p riph rique d avoir un acc s direct en lecture ou en criture la m moire centrale de l ordinateur sans passer par le processeur On a donc adjoint R Cube un second composant mat riel nomm PCIDDC impl mentant une pri mitive d criture dans la m moire centrale d un n ud de calcul distant protocole DDSLRP Direct Deposit StateLess Receiver Protocol La DMA est utilis e au d part et l arriv e pour viter les recopies m moires par le processeur PCIDDC r alise l interm diaire entre le bus PCI de la machine h te et le routeur R Cube Les couches logicielles n ont qu indiquer PICDDC l adresse source et la longueur du bloc transf
89. pace de m moire virtuelle du noyau Dans cet espace se trouvent des registres de contr le et de statut qui servent contr ler la carte lors du fonctionnement courant On les manipule alors par acc s m moire La carte FastHSL pr sente une particularit dans son usage des registres de configuration il n y a pas de m moire d ent e sortie sur la carte et les registre de statut et de commande de PCIDDC sont acces sibles dans l espace de configuration de la carte et ceci durant le mode d op ration normal Au d marrage de la machine le syst me d exploitation remappe les espaces de configuration des cartes PCI dans la m moire virtuelle du noyau Il suffira donc d aller lire et crire la bonne adresse pour communiquer avec PCIDDC De m me des op rations sur le bus PCI lui m me seront n cessaires et pour cela on agira de la m me fa on sur les registres d tat et de contr le du bus PCI ils sont eux aussi remapp s en m moire virtuelle noyau lors du d marrage du syst me d exploitation II 4 Vocabulaire La sp cification de PCIDDC utilise un certain nombre de termes qu il convient de d finir pr cis ment avant d aborder plus en d tail le fonctionnement de la machine MPC Paquet HSL Unit de donn es transf r e sur le r seau HSL C est PCIDDC de former et d extraire les paquets qu il envoie et re oit de R Cube Page r seau ou page Une page r seau est un espace de m moire virtuel
90. r s bas niveau elle ne permet que d crire dans la m moire d un n ud dis tant Il reste la charge de l utilisateur de PUT de s arranger pour que l metteur place ses donn es dans un Emmanuel Dreyfus 16 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC tampon ad quat sur le r cepteur Du c t du r cepteur l utilisateur doit se d brouiller pour d tecter la com pl tion du transfert D velopper une application parall le bas sur PUT est donc loin d tre quelque chose de trivial Il est donc hautement souhaitable de disposer de deux primitives d envoi et de r ception de plus haut niveau send et receive De telles primitives permettent l envoi de donn es sans avoir se pr occuper sur le n ud metteur de la localisation du tampon de r ception sur le n ud destinataire De plus la d tection de la r ception de donn es est rendue triviale puisqu elle se fait en utilisant la primitive de r ception SLR P et SLR V impl mentent de telles primitives send et receive Ils proposent galement un sys t me de canaux virtuels qui permettent de partager facilement une carte FastHSL entre plusieurs processus diff rents SLR P s appuie sur PUT pour proposer les primitives d envoi et de r ception avec des adresses physiques et SLR V s appuie sur SLR P pour proposer le m me service mais avec des adresses virtuelles Examinons
91. reprendre son travail La synchronisation entre Rx et Ack se fait par deux s maphores ACK R et ACK W utilis s respecti vement pour la lecture et l criture dans la file La figure 29 donne le comportement du processus Ack P ACK R P Pb Envoi de l acquitement Fig 29 comportement du processus Ack Emmanuel Dreyfus 62 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC VIL 6 h Formats des paquets La figure 30 propose les formats des 3 paquets diff rents utilis s par S PUT Il faut noter que dans la proposition d impl mentation on a limit le nombre de n uds 256 pour conomiser de la m moire dans le FPGA et dans les paquets les adresses de n uds sont sur 16 bits La raison en est simple si dans le futur on ajoute de la m moire au FPGA on pourra stoker la table de 256ko n cessaire la gestion de 65536 n uds On pr voit donc des num ros de n uds sur 16 bits partout dans le circuit et on se contente de limiter aujour d hui 8 bits dans les structures de donn es utilis es Ainsi la transition 16 bits sera triviale il suffira d aug menter la taille de la table Le dimensionnement des paquets d accus s de r ception r ponds des n cessit s simples on a besoin des champs System Flags 4 bits Index 8 bits les num ros de n uds source et destination 16 bits cha cun Ceci fait un total de 28 bits A cela i
92. rer ainsi que l adresse destination o il doit tre crit sur le n ud distant Plus d informations sur R Cube R3 et PCIDDC DDC sont disponibles sur le site Internet de MPC Un tel m canisme permet de tirer partie des possibilit s offertes par un routeur haute performance tel que R Cube tout en conservant un maximum de temps pour le calcul sur les n uds Emmanuel Dreyfus 11 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC IL2 Aspects mat riels Les circuits R Cube et PCIDDC sont mont s sur une carte PCI appel e carte FastHSL qui prend place dans un slot d extension du PC Suivant sa r vision la carte FastHSL comprend 7 connecteurs Harting ou 8 connecteurs Lemo sur lesquels on peut brancher des c bles bi coaxiaux Du fait du nombre de connec teurs disponibles 1l est possible de r aliser des r seaux fortement connexes pour des machines parall les de 7 n uds de calcul Pour les cartes 8 connecteurs seuls 7 connecteurs sont utilisables lors de l utilisation dans un PC En effet le routeur R Cube poss de 8 interfaces dont une est utilis e pour la communication avec PCIDDC Le huiti me connecteur permet l utilisation de R Cube comme n ud flottant c est dire non raccord un PC Cette possibilit n a pas t actuellement exploit e Le circuit PCIDDC original PCIDDC first run comptait un certain nombre d erreurs Certain
93. rise sur erreur et n envoyer les messages qu un par un en attendant l acquittement de chaque message pour passer au suivant Dans ces conditions on a plus d envoi parall le des messages et on n a pas besoin de confier au processus Watchdog la d tection des acquittement en retard Un fois qu un message est retransmis le processus d mission attend l arriv e d un acquittement ou bien la dur e du timeout Si apr s ce temps aucun acquittement n est arriv il retransmet nouveau le message Comme ce n est pas le processus Watchdog qui g re le timeout des messages retransmis on peut donc r utiliser la m me entr e pour toutes les retransmissions d un m me message Ce m canisme ne provoque ra pas d interf rences avec le fonctionnement du processus Watchdog puisque l entr e retransmise est situ e derri re le pointeur W dans la table W ne pouvant d passer le pointeur N on est assur que Watchdog ne viendra pas s int resser aux entr es en cours de retransmission g r es enti rement par le processus d mis sion On peut toujours avoir un probl me d acquittement en retard accusant une mauvaise entr e si apr s que le nombre maximum de tentatives d envoi ait t d pass on abandonne l envoi Si l acquittement arri ve apr s cet abandon on peut acquitter la mauvaise entr e dans la table Un tel ph nom ne est peu probable Emmanuel Dreyfus 45 17 08 2000 S curisation des pri
94. roch s dans le temps L accus ack 3 est donc indispensable car il assu re la s curit du message de contr le msg 3 m me si le receive survient plusieurs minutes avant le send S curiser au niveau SLR plut t qu au niveau PUT ne permet donc l conomie que d un accus de r ception Ceci ne permet pas de gagner en latence mais seulement en d bit Il s en suit que la s curisation au niveau SLR plut t que PUT n est pas tr s int ressante du simple point de vue de la s curit On ne gagne rait pas en performances avoir un SLR s curis et impl ment dans le mat riel sur un PUT non s curis plut t qu un SLR mat riel sur un PUT mat riel s curis Par contre il est certain qu une impl mentation des couches SLR g r e par le mat riel plut t que par le logiciel permettrait de gagner beaucoup en performanc es au niveau SLR Reste savoir si SLR est impl mentable dans le mat riel Cette question sort du cadre de la pr sente tude Emmanuel Dreyfus 39 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC VI Proposition d impl mentation de S PUT 1 0 Dans cette partie est d taill e une proposition d impl mentation pour la primitive S PUT Secured PUT Ne doutant pas que cette sp cification aura ses limites et que des modifications devront y tre faite elle porte d j un num ro de version 1 0 Au cours de cette par
95. sommairement le fonctionnement de SLR P Le probl me r soudre est le suivant lorsque l utilisateur fait un send nous connaissons l emplacement des donn es envoyer mais nous n avons pas id e de l endroit o les d poser sur le n ud destination Et quand l utilisateur fait un receive on sait o d poser des donn es on ne sait pas aller les chercher la primitive de bas niveau PUT ne permet pas d aller chercher les donn es elle ne sait que envoyer Il faut attendre que les donn es arrivent suite un PUT effectu sur l metteur Une approche simpliste serait d impl menter le send par un envoi de donn es dans un tampon de r ception situ une adresse bien connue sur le n ud destinataire et ensuite laisser la charge du r cepteur le travail de recopier des donn es dans le tampon de destination Cette approche n est pas tr s bonne car elle s carte du mode z ro copies qui est l objectif dans la machine MPC On doit donc utiliser un m canisme plus ing nieux Lorsqu un processus sur le r cepteur fait un recei ve on va envoyer un message de contr le l metteur en utilisant PUT Ce message de contr le va indi quer l metteur ou est le tampon de r ception sur le n ud destination Lorsqu un processus fait un send sur le n ud metteur deux cas se pr sentent e Soit un message de contr le d un receive a d j t envoy auquel cas on envoie par PUT les don
96. ssage A avec le message B envoy entre les deux transmission de A B est re u en entier et avec le drapeau bis mais on ne doit pas l acquitter pour autant puisque on ne l a pas d pos en m moire Nous introduisons donc un tat de reprise sur erreur sur l metteur Pendant le mode d op ration nor mal l metteur peut envoyer un ou plusieurs messages avant d avoir obtenu l accus de r ception du premier message Lorsqu il fait de la retransmission les messages sont envoy s un par un et on ne peut envoyer un message tant qu on a pas eu accus de r ception du pr c dent Dans ce mode recevoir un message en entier signifie que le message a t d pos En effet la seule fa on pour un message arriv en entier de ne pas tre d pos c est le cas o un paquet a t perdu dans un message pr c dent et o le r cepteur s est bloqu L metteur qui n a pas encore constat le probl me il est en attente de l accus du message ayant subit la perte peut continuer envoyer des messages qui arrivent entier et qui ne sont pas d pos s Une fois qu on est en mode r cup ration sur erreur un message transmis en entier signifie un message d pos enti rement en m moire Cet tat de reprise sur erreur de L metteur a consid rablement simplifi la situation On peut ainsi donner une r gle d envoi d accus de r ception qui conduira une signalisation correcte on doit accuser Emma
97. ssage court SM Short Messages Pour transmettre des messages de moins de 8 octets PCIDDC pro pose un m canisme de messages courts qui vitent un certain nombre d tapes dans le transfert ILS5 Fonctionnement global de la primitive PUT PCIDDC maintient dans la m moire centrale de l ordinateur deux tables essentielles au fonctionne ment de la primitive de plus bas niveau de MPC PUT e la liste des pages mettre LPE List of Page to Emit e la liste des messages re us LMI List of Message Identifiers L emplacement et la taille de ces deux tables en m moire centrale est indiqu e PCIDDC par un acc s en configuration PCIDDC acc de ensuite aux tables par DMA La table LPE contient des entr es de type lpe entry t d finies ainsi typedef struct lpe entry u short page length Longueur du bloc transf rer u_ short routing part Num ro du n ud destination u_long control Options diverses caddr t PRSA Adresse destination sur n ud cible caddr t PLSA Adresse source sur n ud local lpe entry t Pour envoyer une page de m moire sur un n ud distant il suffit d crire l entr e de la table LPE cor respondante et signaler PCIDDC la pr sence de cette entr e par un acc s en configuration L entr e de LPE contient l adresse locale du bloc transf rer PLSA sa longueur page length le num ro de n ud sur lequel il faut le transf rer routing part
98. st beaucoup plus simple que l utilisation de la table des mes sages en transit Le comportement de l metteur est d utiliser un num ro de s quence croissant pour chaque paquet envoy pour la premi re fois vers un n ud donn Le num ro courant est stock dans la table des s quences en transmission Le num ro du premier paquet du message est conserv dans la table des messages en tran sit Lors d une re mission ce num ro est r cup r et le message est renvoy avec les m mes num ros de s quences que la premi re fois Une fois la re mission achev e l metteur reprend les s quences l o il les avait laiss es Pour sa part le r cepteur ne doit accepter c est dire d poser en m moire en provenance d un n ud donn que les paquets ayant les num ros de s quence attendus Ce m canisme permet de rejeter les doublons mais il a un effet de bord important en cas de paquet perdu le r cepteur va voir arriver beaucoup de paquets n ayant pas le num ro de s quence attendu avant la r exp dition du message posant probl me Eventuellement des paquets appartenant plusieurs autres messages seront bloqu s Pendant un temps gal au d lai de retransmission A le r cepteur n acceptera plus aucune donn es Il nous faut dimensionner les num ros de s quences Le point important est que pendant un certain intervalle de temps le m me num ro de s quence ne soit pas utilis pour designer des paquets
99. st le prix de la s curit nous devons attendre la confirmation de la bonne r ception d un paquet avant de le signaliser comme envoy chez l metteur et donc lib rer le tampon d mission Ceci donne lieu une augmentation de latence correspon dant un aller retour sur le r seau Toutefois l augmentation de latence peut se r v ler parfois plus importante Dans le calcul pr c dent nous n avons pas compt le temps n cessaire au n ud r cepteur pour avoir son processus d mission dispo nible Nous avons suppos que le r cepteur n tait pas lui m me en train d envoyer des donn es et donc qu il pouvait imm diatement envoyer l accus Comptons maintenant ce qu il se passe si le processus metteur du n ud r cepteur est en train d envoyer des donn es On va choisir de donner aux accus s de r ception une priorit maximum et donc de permettre une mission des accus s de r ceptions entre chaque mission de paquet Si l on limite la taille des paquets 4ko cette valeur correspond une page pour le syst me de m moire virtuelle il nous faut au pire attendre le temps de transfert de 4ko pour pouvoir envoyer un accus de r ception Dans la machine MPC 1 le goulot d tranglement est le lien entre PCIDDC et R Cube mais il est probable que cette limitation sera lev e dans MPC 2 On va donc supposer un goulot d tranglement au niveau du bus PCI lui m me D terminons donc le temps n cess
100. sur T oli li lololo le message qui vient d tre recu il passe l entr e suivante R l l lololo r et re initialise t 0 Entr e LPE 0 1 3 0100 In Message Node LPE 0 0 0 0 0 0 Le message D a fini d tre transmis on ajoute l entr e Y correspondante dans la table 2 IDX i zi fin message Retransmission du message A avec IDX 4 3 5 Fin du messsage on l ajoute dans la table C est une retransmission R est egal 2 maintenant g On incr mente F car la derniere entr e est invalid e t arrive 1 ce qui est l echeance de l entr e point e par W Le message C va donc tre en timeout C est retransmis avec IDX 5 in Message y Machine Machine Temps source destination Fig 20 Exemples de manipulation sur la table des messages en transit avec champs d ch ances L chelle de temps n est pas respect e On a pris un timeout de 3 ticks Pour repr senter clairement tous les cas possibles les comportements d crits au V5 ne sont pas respect s ici Emmanuel Dreyfus 46 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC t 0 XR 0 Index 0 1 213 41 5 A T 0010101010 W N donc Watchdog dort t 0 R 010101010710 Entr e LPE 0
101. t ressante On va donc pr f rer travailler au niveau message Il faut maintenant d terminer si l on va utiliser des accus s de r ception ou de non r ception La perte d un paquet sur le r seau HSL tant un v nement rare l utilisation d accus de non r ception para t un bon choix car il va conomiser le nombre de paquets dus la signalisation La figure 7 donne un exemple de tran sactions utilisant des accus s de non r ception Emmanuel Dreyfus 25 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC 1 attendu OK 2 attendu Ok 3 attendu Ok 4 attendu 4 attendu 5 recu erreur 4 perdu anoi dA 4 attendu paquet perdu 4 recu 5 attendu 4 recu reprise 5 Ok 6 attendu Ok 7 attendu Machine Machine Temps source destination Fig 7 Perte de paquet et r cup ration sur erreur avec un accus de non r ception Chaque message est compos d un seul paquet On note une phase de r cup ration sur erreur sur l metteur A et sur le r cep teur B Cette phase est termin e par un accus de r ception du paquet perdu NB le cas de la perte d un accus n est pas abord ici Plusieurs probl mes apparaissent dans cet exemple e Si le paquet perdu est le dernier d un change aucun paquet portant un num ro de s quence inattendu ne sera re u par le r cepteur Il ne demandera donc pas r exp dition des informations
102. t de la re mission du message A chaque retransmission de message le compteur du nombre de tentatives d envoi de l entr e doit tre incr ment Ceci permet l arret des tentatives d envoi du message au bout d un certain nombre de ten tatives et de signaler l utilisateur un probl me important probablement une machine inaccessible La figure 18 illustre l volution de la table des messages en transit lors d un change avec perte d un message Le cas de la perte de l accus de r ception est similaire au cas de la perte d un paquet Les traitements effectuer sur la table des messages en transit sont extr mement simples On peut les impl menter mat riellement condition que la table elle m me ne soit pas de taille trop importante Cette m thode pr sente l avantage qu un message retransmis a le m me index dans la table que le message original Si un accus de r ception arrive tr s en retard apr s la re mission du message c est tout de m me le bon message qui sera acquitt Deux inconv nients sont noter e La taille de la table doit tre adapt e la dur e du timeout Ceci pose un gros probl me car on ne peut pas jouer sur la dur e du timeout comme on le voudrait sans agrandir consid rablement la table e Pour ne pas sauter des entr es on doit arr ter l avanc e dans la table pendant l emission d un message parce qu on ne peut pas r mettre un message pendant l
103. te au bloc que l on souhaite transf rer e Etape 2 acc s en configuration PCIDDC pour lui signaler la pr sence d une nouvelle entr e traiter e Etape 3 PCIDDC lit l entr e de LPE par DMA e Etape 4 PCIDDC lit la page de m moire transf rer par DMA e Etape 5 transfert des donn es acheminer de PCIDDC R Cube Si la page est de taille importante elle sera fragment e en plusieurs paquets HSL e Etape 6 transfert des donn es d un routeur R Cube l autre travers le r seau HSL Il serait possible durant cette tape de traverser des routeurs R Cube interm diaires e Etape 7 transfert des donn es de R Cube PCIDDC sur le n ud destination e Etape 8 transfert des donn es de PCIDDC vers la m moire centrale sur le n ud destination Une fois de plus la DMA est utilis e pour viter les recopies m moires Les tapes 4 8 se d roulent en r alit en m me temps elles forment un pipeline Une fois l tape 4 termin e l tape 9 peut ventuellement tre faite sur le n ud metteur Emmanuel Dreyfus 15 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC ra RSI as PO AUS ei ET DU ee ia NS pate A de E S 71 Fe es ST nd Cp te En l 7 liens HSL s rie 1GHz um LPE PCIDDC Bige o o Adresse destination Bloc transf rer M
104. tie on reprends les besoins propos s dans la partie pr c dente et on tudie la fa on dont on pourrait les impl menter logiciellement ou mat riellement Son abord s le m canisme de renvoi des messages non acquitt s l utilisation des num ros de s quences sur les paquets ainsi que les condition et les m canismes d envoi des accus s de r ception Enfin le VI 6 pro pose une syth se de S PUT r sumant de fa on succinte les m canismes et comportement mis en place jusque l VL I1 Impl mentation des renvois la table des messages en transit Nous avons dans la partie pr c dente identifi un besoin sur l metteur celui de re envoyer les mes sages non acquitt s par le r cepteur apr s un certain temps Avant de nous int resser la r partition des t ches entre logiciel et mat riel pr cisons plus avant la fa on dont un tel m canisme peut tre mis en place Ce dont nous avons besoin c est un compteur de temps pour chaque message envoy Un accus de r ception arr te le compteur et si le compteur atteint une valeur maximum 1l faut re envoyer le message Evaluons le nombre de compteurs dont nous pouvons avoir besoin simultan ment Pour cela nous devons dimensionner la dur e du timeout Cette dur e d pends du temps que met un accus de r ception arriver apr s que l metteur ait envoy le dernier octet d un paquet Nous avons va lu ce temps environ 850ns dans le V 7 a Une premi re i
105. tte deuxi me partie correspond au travail de DEA dont le pr sent rapport rend comp te Le sujet en est la s curisation des primitives de communications bas niveaux dans la machine MPC MPC 1 a t con u dans la croyance d une fiabilit extr mement lev e du lien un temps entre deux erreurs de l ordre du milliard de secondes en th orie L exp rience nous a r v l que cette supposition tait erron e Diff rents probl mes au niveau des connecteurs des c bles et au niveau du circuit R Cube lui m me font que le temps entre deux fautes n est que de l ordre de quelques heures Les fautes elles m mes sont assez mineures perte d un ou deux paquets mais comme MPC 1 a t con ue l origine sans m canismes de reprise sur erreur l utilisation de la machine est fortement compromise par ce probl me Des travaux ont t r alis s par Alexandre Feny au cours de sa th se pour corriger ces probl mes et assurer la s curisation des communications dans MPC 1 AF Les composants mat riels de MPC 1 n tant pas reprogrammables cette s curisation ne pouvait tre que logicielle On ne pouvait que faire avec le mat riel et trouver un moyen d obtenir une communication s curis e Le r sultat de ce travail est SCP un proto cole impl ment logiciellement s curisant l API Application programming Interface SLR qui corresponds la primitive de communication de haut niveau de la machine MPC 1 La s
106. ttente SLR V fonctionne en utilisant SLR P La diff rence essentielle est que le message de contr le n a pas simplement a v hiculer l adresse et la longueur d un tampon comme dans SLR P mais toute une liste de pages de m moires virtuelles le tampon de r ception pouvant tre fragment dans la m moire physique SLR permet donc d avoir une API assez g n rique de passage de message Ceci rends le portage d ap plications parall les sur MPC 1 plus facile mais a un co t important en termes de performances la latence SLR est beaucoup plus importante que la latence au niveau PUT IL 7 Limitations de la machine MPC 1 La machine MPC 1 conna t un certain nombre de probl mes Examinons les plus en d tail IL7 a MTBF du lien HSL plus faible que pr vu Comme cela a t voqu au I 3 la machine MPC 1 a t con ue en imaginant que la fiabilit des liens HSL tait extr mement lev e Les chiffres th oriques promettent un bit erron tous les 1018 bits Le lien HSL fonctionnant 1Gb s ceci nous fait une erreur tous les milliard de secondes Exprim dans une unit plus raisonnable cela nous fait un temps moyen entre deux fautes MTBF Mean Time Between Failures de plus de 30 ans Il est clair qu avec une telle fiabilit on peut se dispenser de g rer la r cup ra tion sur erreur Un MTBF de 30 ans est tr s grand devant les MTBF de la plupart des autres constituants de la machine H las le MTBF r el est b
107. ue l on peut envoyer en un temps A On a vu que la vitesse d mission des messages tait major e par la vitesse d mission des messages de 1ko soit un message tous les 8us En 500us 62 messages peuvent tre envoy s Ceci implique que l on doit tre capable de faire tourner 62 comp teurs la fois Que les compteurs soient g r s en logiciel ou en mat riel il n est pas question de faire fonctionner tant de compteurs la fois cela occuperait trop de ressources Au lieu de a on va exploiter le fait que tous ces compteurs ont un point commun c est le temps qui les fait avancer tous au m me rythme On va donc pouvoir les remplacer par un compteur unique Deux solutions d impl mentations sont disponibles une table index e par le temps ou une table contenant des champs d ch ance VL L a Table des messages en transit index e par le temps Lorsque l metteur traite une entr e de LPE l instant t il va placer les informations relatives cette entr e l index t dans la table des messages en transit Voici les champs composant une entr e e Le num ro de l entr e de LPE trait e e Le num ro de LPE si on a des LPE multiples e Le num ro de s quence du premier paquet du message e Le nombre de tentatives d envoi de l entr e Par ailleurs l metteur maintient un compteur qui est incr ment toutes les 240ns c est le temps minimum n cessaire pour lire une entr e lorsqu il n est pas e
108. ue le processus d mission sait quand il peut retourner l mission des entr es normales lorsque XR 0 Pour les raisons d velopp es au V 5 pen dant les retransmissions le processus metteur attend l accus de r ception de chaque message avant de transmettre le suivant La figure 20 donne un exemple d utilisation de cette deuxi me version de la table des messages en transit avec les diff rentes op rations possibles envoi original d passement de d lai de retransmission acquittement et retransmission Pour d tailler tous les comportements possibles avec clart on n a pas res pect sur cette figure les r gles d crites au V S imposant l metteur d envoyer les messages un par un en attendant les acquittements pendant les phases de retransmissions Cette deuxi me approche pr sente un avantage par rapport la premi re on peut maintenant r gler la valeur du timeout comme on le d sire sans avoir augmenter la taille de la table Par contre on perd une propri t int ressante lors des retransmissions le num ro d index utilis n est pas le m me on voit d ailleurs cela assez bien dans la figure 20 Mais si on int gre les comportements d crits au V5 on peut garantir la propri t de r utilisation de la m me entr e pour le m me message retransmis Au V 5 nous avons pr vu que lorsque l metteur constatait qu un acquittement n tait pas arriv il devait passer en mode rep
109. un accroissement de 0 38ns par rapport la situation sans erreur o la latence tait de Sus C est un chiffre satisfaisant VIL b D bit Pour calculer le d bit on va supposer l envoi en continu de messages de taille identique Dans le cas d un message perdu on va avoir une p riode o tous les messages seront rejet s et o aucune communica tion ne sera possible Cette p riode dure Ti 505us comme on l a expliqu dans le paragraphe concernant la latence Ensuite vient la p riode o l on retransmet les messages non acquitt s un par un Si les messages ont une taille N on a mis Tm 30 12 E N 4 nanosecondes pour les envoyer A ceci il faut ajouter un temps Tack d une microseconde pour l arriv e de l acquittement Pendant la dur e du d lai de retransmission A 500us on a pu envoyer A Tm messages qui doi vent tre retransmis au rythme de un message tous les Tm Tack Cette op ration prend donc A Tm x Tm Tack On a donc un temps Te Ti A Tm x Tm Tack pendant lequel sont envoy s Tm messages de N octets soit un d bit De Tm N Ti A Tm x Tm Tack Avec un MTBF de deux minutes on a un d bit maximum pendant deux minutes puis un temps Te pendant lequel le d bit est gal D Si on prend des messages assez grands par exemple 64ko le d bit sans faute est celui du bus PCI 132Mo s Si on fait la moyenne on obtient une perte de d bit par rapport au cas sans fa
110. un message Cette seconde op ration est prioritaire sur la premi re Tant qu il y a des messages en retard le processus Tx doit les r mettre avant de pouvoir envoyer un nouveau message C est le processus Wd qui indique au processus Tx qu un message doit tre retransmis La communication entre Wd et Tx se fait par la variable R qui indique le nombre de messages en retard traiter Wd l incr mente quand il d couvre un message en retard et Tx la d cr mente lorsqu il a ren voy un message Tx ne peut donc pas faire des envois originaux de messages tant que R n est pas nul L op rateur PCI est un esclave sur le bus PCI C est lui qui demande Tx l envoi de nouveaux mes sages Tx prend en charge les missions command es par PCI si R 0 Tx a donc 3 tats de fonctionnements Idle Insert et Replay correspondant respectivement l inac tivit l envoi original de message et la retransmission de message La figure 24 d crit l automate tats avec les conditions pour passer d un tat l autre Fig 24 Automate d tats de Tx XR indique des messages retransmettre tat Replay et PCI indique des envois originaux de messages faire tat Insert La figure 25 d crit l op ration commune aux tats Insert et Replay savoir l mission d un messa ge La figure 26 d crit l tat Insert et l tat Replay Emmanuel Dreyfus 57 17 08 2000 S curisation des primitives
111. unication bas niveau dans une machine parall le de type grappe de PC V S curisation au niveau PUT dans MPC 2 Dans cette partie on propose les grandes lignes d un m canisme permettant la s curisation de la pri mitive PUT pour la machine MPC 2 Les diff rentes options possibles sont d abord examin es type et niveau de la signalisation des erreurs sur le r seau puis on tudie la r ponse de la solution retenue des v nements tels que la perte d un paquet ou la perte d un acquittement On aborde ensuite un passage en revue des diff rents cas particuliers posant un probl me ainsi que les possibilit s de correction des dits probl mes Enfin cette partie se termine par l tude de l impact en termes de performances des solutions retenues et une tude rapide de la s curisation de SLR dans MPC 2 V 1 D tection des pertes de paquets Il n existe pas dans MPC 1 de moyen permettant au r cepteur de d tecter coup sur la perte d un paquet Nous devons donc introduire un tel m canisme Pour obtenir la d tection des paquets perdus il nous faut introduire des num ros de s quences lors qu un n ud envoie des donn es il place dans l en t te de chaque paquet un num ro de s quence croissant unit par unit De son c t le n ud r cepteur attend le bon num ro de s quence pour chaque paquet venant d un autre n ud On a ainsi le moyen de d tecter lorsqu un paquet est perdu le r cepteur peut
112. ur t v Mise z ro du champ cheance de l entr e point e par W et incr menter R Y gt Avancer W jusqu la prochaine entr e valide ou jusqu ce que W N Fig 27 Comportement du processus Wd N et W sont les pointeurs dans le table des messages en transit respectivement sur l entr e surveill e et sur la premi re entr e libre Emmanuel Dreyfus 60 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC VI 6 f Comportement du processus de r ception Le processus de r ception Rx r cup re les paquets extraits par l op rateur Px Son comportement varie ensuite suivant le type du paquet Les acquittements donnent lieu une op ration sur la table des mes sages en transit et les paquets appartenant des messages courts ou normaux sont d pos s en m moire si le num ro de s quence est correct La figure 28 d taille le comportement du processus Rx Y E 4 y Lecture d un paquet y D tecter le type du paquet F Px Supprimer l entr e du message de la table des messages en transit Le num ro de s quence est il elui attendu de s quence est il celui attendu Le message a t il le drapeau bis D poser les donn es dans la LMI Lire et ignorer tout le reste du paquet D poser
113. ute gal 1 1ko s ce qui est aussi un chiffre satisfaisant Emmanuel Dreyfus 64 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC Ces calculs aussi bien pour le d bit que pour la latence sont assez grossiers Pour obtenir des r sul tats plus satisfaisants une tude probabiliste serait n cessaire On pourrait alors proposer un mod le d arri v e des messages correspondant plus la r alit qu un flux ininterrompu de messages de tailles toujours iden tique L int r t des ces calculs rapide de latence et de d bit est de donner une id e de l ordre de grandeur de la d gradation des performances due la r cup ration sur erreur VILc MTBF On peut s int resser au MTBF Le but de cette partie n est pas de calculer sa nouvelle valeur due l utilisation de S PUT mais de donner une id e des erreurs que ne corrigent pas S PUT et qui devraient tre prises en compte pour calculer le MTBF de la machine MPC utilisant S PUT On aura des fautes dans les cas suivants e Une erreur se glisse dans un paquet sans qu elle soit d tect e par le CRC On a un CRC sur 56 bits sur les paquets des messages et tous les champs sont en doubl s dans les accus s de r ception e Si on a choisi de signaler un chec de transmission apr s un certain nombre de tentatives alors on peut avoir une faute si un accus arrive alors que l metteur a abandonn l en
114. voi Si on envoie un message 16 fois cela signifie que l accus a mis 16 1 8ms a traverser le r seau ou bien qu il a subit une hexad cuple faute Tous les autres probl mes sont priori couverts par S PUT Une tude probabiliste permettrait de cal culer le nouveau MTBF qui devrait avoir une valeur tr s grande devant les deux minutes actuelles Emmanuel Dreyfus 65 17 08 2000 S curisation des primitives de communication bas niveau dans une machine parall le de type grappe de PC VIII Conclusions Au cours de ce stage j ai tent de concevoir un syst me de s curisation de la primitive de communi cation bas niveau de la machine MPC Le but tait d augmenter le MTBF initialement de deux minutes une valeur plus acceptable id alement l infini Cette t che passait par l laboration d un protocole et par la r flexion sur la r partition des t ches entre le mat riel et le logiciel Apr s tude approfondie il s av re que la s curisation est possible au prix d une modification de la s mantique de la primitive de communication bas niveau Avec PUT on signale sur l metteur la fin de l envoi des pages Avec S PUT on signale sur l metteur la r ception des messages par le n ud destinataire La conclusion la plus importante de cette tude est sans doute que la totalit du m canisme de s cu risation peut tre impl ment mat riellement un co t raisonnable Ceci nous permet de ne pas trop d

Download Pdf Manuals

Related Search

Related Contents

Samsung HM SBS with Twin Cooling, 506 L, Real Stainless Brugervejledning  TLT-12 - Tru-line Wheel Alignment  Samsung DVD 5.1 Sistema de Cinema em Casa HT-TX725T manual de utilizador  Klipsch RW-5802 User's Manual  Hw Manual_V2.1(Eng)  SDS - 医学生物学研究所  Descargar  Philips PAL connector ends SWV2142W  Telis 6 Chronis RTS  BEDIENUNGSANLEITUNG / USER MANUAL  

Copyright © All rights reserved. Failed to retrieve file