OVIPAR : une plate-forme d`initiation au parallélisme sous UNIX
Contents
1. a appel reste bloqu jusqu ce que le message soit transmis La fonction retourne le minimum entre le nombre d octets envoy s et le nombre d octets attendus par le destinataire int send chn msg msgsz chnt chn Channel descriptor char msg Message storage buffer int msgsz Message size 3 6 R CEPTION D UN MESSAGE RCEV Cette fonction permet au processus qui l appelle de recevoir un message mis par un autre processus La fonction prend en param tre le canal par lequel le message sera 409 re u ainsi que l adresse du buffer o il sera stock et le nombre d octets attendus Le processus qui l a appel reste bloqu jusqu ce que le message soit re u La fonction retourne le minimum entre le nombre d actets envoy s et le nombre d octets attendus int recv chn msg msgsz chn_t chn Channel descriptor char msg Storage buffer int msgsz Expected message size 3 7 GESTION DE CANAUX INTERNES CHANGET CHANDEL La prerm re de ces fonction permet de cr er un canal sur un noeud dont la taille donn e correspond au nombre maximal d octets qui pourront transiter par ce canal Si le nombre d octets mis ou le nombre attendus d passent cette taille alors le nombre d octets effectivement transmis sera gal cette taille La deuxi me fonction permet de supprimer un canal chn_t changet sz int SZ Maximum number of bytes which can transit by the channel int chan2. m moire distribu e L architecture est bas e sur des processeurs quatre liens inspir s des transputers de INMOS INM OVIPAR offre lutilisateur la possibilit de cr er un ordinateur virtuel multiprocesseur sur lequel il peut ex cuter des programmes parall les crits en langage C suivant le mod le CSP Les processus communiquent travers des canaux 403 internes chaque noeud ou reliant des noeuds entre eux Les processus d un m me noeud disposent d une zone de m moire partag e OVIPAR a des ambitions plus modestes que PVM Che Gei et MPI Wal D abord il ne fonctionne que sur une seule machine UNIX Il n offre qu une biblioth que de fonctions mettant en oeuvre les principales instructions CSP alors que PVM est un v ritable environnement de programmation L installation et l exploitation d OVIPAR ne n cessitent pas de formation pr alable Il est con u pour s int grer facilement aux environnements UNIX L apprentissage d OVIPAR se fait en quelques minutes sur la base de son manuel d utilisation Alm1 pour quelqu un qui connait CSP L exp rience d utilisation PIAI depuis deux ans par les l ves ing nieurs montre qu OVIPAR est un outil p dagogique simple utiliser Enfin il est gratuit Le reste de ce document d crit dans la premi re partie l architecture d OVIPAR La deuxi me partie donne quelques indications sur sa mise en oeuvre La troisi me et la quatri me parties pr sent
3. La gestion d un processus suit alors le sch ma suivant if fork 0 init_process call process function argc argv exit 0 2 3 GESTION DES CANAUX ET LIENS Les canaux et les liens sont construits avec des segments de m moire partag e Le bout de chaque canal est marqu avec le num ro du processus qui en h rite travers sa fen tre Ce marquage est realis par la fonction init process appel e juste apr s la fonction fork voir 83 2 chaque canal est associ un ensemble de s maphores qui permettent d assurer l exclusion mutuelle Les fonctions de communication exploitent ces informations pour garantir l int grit des canaux et liens Pour reprendre ses droits sur les canaux et liens le processus p re restaure son propre marquage la fin des fils 2 4 M MOIRE PARTAG E Tout comme les canaux la m moire partag e sur chaque noeud est mise en oeuvre sur la base de segments de m moire partag e OVIPAR ne garantit pas l acc s en exclusion mutuelle dans ces segments Leur taille est de un kilo octets chacun 3 BIBLIOTH QUE DE FONCTIONS D OVIPAR La biblioth que d OVIPAR comporte moins d une dizaine de fonctions essentielles 3 1 CR ATION ET CONFIGURATION DE L ORDINATEUR OVIPAR Cette fonction permet de sp cifier la topologie de la machine virtuelle Elle prend en param tre le nombre de noeuds la sp cification du r seau par des connexions point point et un pointeur s
4. appel s composantes et les placent dans les diff rents noeuds de la 408 machine parall le Le programme ayant appel cette fonction se bloque jusqu la fin des processus qui ont t cr s int placedpar sz pdesctab int SZ Size of table pdesctab csp_t pdesctab Table in which each item is a process descriptor These descriptors are created with the function initproc La fonction placedparl est une version de placedpar qui prend en param tre une liste de descripteurs de processus termin e par 0 3 4 CR ATION DE PROCESSUS SUR UN NOEUD PAR Cette fonction prend en param tre une table de descripteurs de processus cr s avec la fonction iitproc et cr e les processus sur le noeud partir duquel elle a t appel e Le processus ayant appel cette fonction se bloque jusqu la fin des processus qui ont t cr s int par sz pdesctab int sZ Size of table pdesctab csp_t pdesctab Table in which each item is a process descriptor These descriptors are created with the function initpdesc La fonction parl est une version de par qui prend en param tre une liste de descripteurs de processus termin e par 0 3 5 EMISSION D UN MESSAGE SEND Cette fonction permet au processus qui l appelle d envoyer un message un autre processus La fonction prend en param tre le canal par lequel le message doit tre envoy ainsi que l adresse du message et sa taille Le processus qui l
5. fils sont synchronis s par le processus arbitre void arbitre int argc char arev chn_1 chnvfl int C lt recv chn_north amp c 1 send chn_south amp c 1 void lire ini argc char argv chn_t chnv int a 0 int c recy chn_ south amp c 1 vpmem amp a sizeof int 0 VP_READ printf Valeur re ue d n a void ecrire int argc char argv chn_t chuv int a printf Entrer une valeur enti re scanf d amp a vpmem ca sizeof int 0 VP_WRITE send chn_north 1 void p re int argc char argv chn tchnvf csp_t p 2 initproc amp p 0 crire CHN_NORTH 0 NULL initproc amp p 1 lire CHN_SOUTH 0 NULL par 2 p void chargement csp_t p 2 initcomp amp p 0 arbitre 1 CHN_NORTH CHN_SOUTH 0 NULL initcorap amp p 1 pere 2 CHN_ NORTH CHN_SOUTH 0 NULL placedpar 2 p main if ovipar 2 IN2N 1525S chargement 0 NULL printf Erreur ovipar n d n vp_errmo 413
6. sizeof int printf New value of the token is od n token void transit int argc char argv chn_t chnv executed by the intermediate nodes int token F expect the token from west channel recy chn_west char token sizeof int token Send the token to the east channel send chn_east char token sizeof int int tokenring Create process descriptors and specify node entries csp_t p 5s initcomp amp p 0 front t CHN_ WEST CHN_EAST NULL 0 NULL initcomp amp p 1 transit 2 CIN WEST CHN_EAST NULL 0 NULL initcomp amp p 2 transit 3 CHN_WEST CHN_EAST NULL 0 NULL initcomp amp p 31 transit 4 CHN_WEST CHN_EAST NULL 0 NULL 412 initproc amp pl4 transit 5 CHN_WEST CHN_EAST NULL 0 NULL retum placedparl 5 p int main Host entry point computer creation and configuration E refers to EAST link and W refers to WEST link ovipar 5 IE2W 2E3W 3E4W 4E5W 5E1W tokenring 0 NULL A 2 PROGRAMMATION D UN PRODUCTEUR CONSOMMATEUR L objectif est de montrer comment deux processus peuvent acc der la m moire paratg e de leur noeud et comment utiliser la fonction par Cet exemple cr e deux processus auxquels sont associ s les fonctions p re et arbitre Le p re cr e deux fils lire crire Pun r cup re dans la m moire partag e une valeur que l autre a incrite Les deux
7. OVIPAR Une Plate forme d Initiation au Parall lisme sous UNIX Antonio ALMEIDA Pierre MOUKELI Institut Africain d Informatique AD B P 2263 Libreville GABON Tel 241 72 00 05 Fax 241 72 00 11 R sum OVIPAR Ordinateur Virtuel Parall le est un outil d aide l apprentissage du parall lisme d velopp sous UNIX en langage C Il s adresse particuli rement aux tudiants et aux chercheurs d sireux de d couvrir ce domaine de l informatique OVIPAR se pr sente comme une biblioth que de fonctions int grer dans un programme C classique Ces fonctions mettent en oeuvre les instructions CSP OVIPAR est en quelque sorte un mod le r duit de PVM avec des ambitions tr s modestes Mots cl s Outils de programmation parall lisme Summary Ovipar is a training platform for learning parallelism It is based on Unix an C It is well suited for students and researchers interested in this domain of computer science Ovipar is designed as a library of functions to be inserted in usual C programs These functions borrow the CSP model Ovipar is a kind of reduced PVM with modest ambitions Key words Programming tools parallelism introduction OVIPAR Ordinateur Virtuel Parall le est une plate forme de programmation destin e l initiation au parall lisme Alm2 Mou Cette plate forme est r alis e en langage C sous le systeme d exploitation UNIX OVIPAR a t mis en oeuvre suivant le mod le MIMD
8. d Reference Manual ORNL TM 12187 Sept 1994 Oak Ridge Tennessee 37831 HNM INMOS The T9000 Transputer Product Overview Manual INMOS First Edition 1991 Mou Mouk li Pierre Parallel Computer Operating Systems 411 African Regional Workshop on Parallel Processing and its Applications 31 July 11 August 1995 Yaound Cameroon 1Wal Walker D W The Design of a Standard Message Passing Interface for Distributed Memory Concurrent Computers Parallel Computing Vol 20 1994 PP 657 673 ANNEXE EXEMPLES DE PROGRAMMES CVIPAR Les programmes d crits dans cette section sont disponibles dans la biblioth que des exemples OVIPAR et doivent tre compil s avec la commande suivante dans laquelle demo c d signe le nom du programme cc 0 demo c lovipar 4 1 PROGRAMMATION D UN ANNEAU Cet exemple montre comment programmer un anneau Il cr e cinq processeurs reli s entre eux par les liens est ouest Sur chaque processeur s ex cute un processus dont le r le est de recevoir un jeton du voisin ouest de le modifier et de le transmettre au voisin est Le premier processus sert de frontal void front int argc char argv chn_t chnv l executed by the front node int token Read the token printf Input an integer scanf d amp token Send the token to the front node send chn_east char token sizeof int expect the token coming back recy chn_west char token
9. de d veloppement 2 EL MENTS DE MISE EN OEUVRE D OVIPAR OVIPAR a t mis en oeuvre en s appuyant sur les m canismes de programmation avanc e du syst me UNIX version 5 i e gestion des processus m moire partag e s maphores et sur les techniques offertes par le langage C fonctions arguments variables vecteurs de param tres du style argv de main Les choix de programmation ont t faits pour tirer au mieux partie de ces m canismes Alm2 2 1 LES PROCESSEURS Un processeur est mis en oeuvre sous la forme d un processus dont les descendants sont les processus du noeud Ce processus initialise une ensemble de variables qui seront h rit es par duplication de l espace des donn es e g num ro de processeur L arr t de la machine correspond la fin de tous ces processus 2 2 GESTION DES PROCESSUS Les processus OVTPAR sont cr s avec la fonction UNIX fork Le processus ainsi cr ex cute comme premi re action une fonction charg e d initialiser la structure de donn es du processus Pour cr er plusieurs processus il suffit de proc der par it ration de ce principe Le processus p re attend la fin des processus fils avec une it ration sur la fonction wait sachant que cette fonction retourne une valeur n gative quand le processus n a plus de fils actif Chaque processus fils doit donc se terminer rair la fonction exit 406 L appel cette fonction est pris en charge par OVIPAR
10. del chn chn t chn Descriptor of the channel to be deleted 3 8 CHOIX GARD D UNE COMMUNICATION ALT La fonction a permet d attendre la pr sence d une communication sur une liste de canaux Si pluszurs communications sont pr sentes la fonction choisit al atoirement l une d elle et retourne le num ro dans la liste du canal associ Sinon elle attend l arriv e de la premi re communication et retourne le num ro du canal associ Cette fonction ne re oit pas le message Le nombre de canaux pass s en param tre est variable Le dernier param tre doit tre O int alt chn chnt chn The first of a list of channels ending by 0 3 9 ACC S LA M MOIRE PARTAG E D UN NOEUD VMEM Cette fonction permet un processus de lire ou crire une valeur dans la m moire partag e du noeud dans lequel il s ex cute L acc s se fait partir d un emplacement donn relativement au d but de la m moire partag e Cette m moire a une taille d un kilo octets int vmein buf sz os cmd char buf Buffer containing the message to be stored in the shared memory or buffer in which the message extracted from the shared memory will be stored 410 int SZ Message size int offset Offset from the beginning of the shared memory int cmd 0 to read and 1 to write CONCLUSION L outil qui vient d tre pr sent est disponible PIAI et est en phase de diffusion Cet outil n est utilisable que da
11. ent la biblioth que des fonctions Une annexe donne quelques exemples de programmes OVIPAR 1 ARCHITECTURE D OVIPAR 1 1 MOTIVATION OVIPAR se d finit comme un outil d aide l apprentissage du parall lisme Il s adresse particuli rement aux tudiants et aux chercheurs d sireux de d couvrir ce domaine de l informatique L Institut Africain d Informatique comme bien d autres structures universitaires africaines ne disposait pas d un ordinateur parall le ni d un environnement de simulation L TAI ayant une vocation de formation professionnelle l enseignement du parall lisme pour tre cr dible ne pouvait pas tre durablement envisag e dans un cadre strictement th orique De plus nos futurs ing nieurs doivent commencer se familiariser avec les ordinateurs parall les leur quotidien de demain Il tait donc indispensable de se doter d une plate forme de programmation parall le L existence l IAI d une technicit cons quente a donc permis de concevoir et r aliser OVIPAR 1 2 MACHINE OVIPAR Une machine OVIPAR est con ue comme tant un ensemble de processeurs reli s entre eux par un r seau de communication Chaque processeur dispose de quatre liens bidirectionnels lui permettant de communiquer avec autant de voisins Chaque noeud offre une m moire d un kilo octet accessible tous les processus qui lui sont associ s La description de fa topologie se fait lors de la cr ation de la machine en
12. ns un cadre strictement acad mique Son principal avantage est le nombre de fonctions r duit qui en facilite apprentissage Nous avons dit qu OVIPAR doit tre arr t par les proc dures habituelles de terminaisons de programmes C Une version am lior e permettrait de terminer proprement OVIPAR la suite d un incident Il s agira en particulier de terminer les processus pendants et de lib rer les s maphores et les segments de m moire partag e La mise en oeuvre d une telle proc dure ne pose pas de probl me particulier en exploitant par exemple un fichier de trace syst me Une autre am lioration possible est de rendre la machine OVIPAR permanente Cela permettrait d ex cuter plusieurs programmes cons cutifs sans arr ter OVIPAR L aussi il n y a pas de probl me majeur tant donn que les techniques de communication entre processus et avec le shell d UNIX sont bien ma tris es R f rences Almi Almeida Antonio OVIPAR Ordinateur Vituel Parall le sous UNIX Manuel d utilisation 1995 LAT BP 2263 Libreville GABON Alm2 Almeida Antonio OVIPAR Conception et Mise en Oeuvre d un Ordinateur Vituel Parall le sous UNIX M moire de Fin de Cycle Ing nieur 1995 LIAI BP 2263 Libreville GABON Che Chergui Jalel Escobar Juan Girou Denis Programmation par Echange de Messages PVM Institut du D veloppement des Ressources en Informatique Scientifique F v 95 Gei Geist Al et al PVM 3 User s Guide an
13. que la fonction main Aucune restriction n est impos e aux facilit s habituelles de programmation C et UNIX pour la conception des processus Un processus peut faire r f rence toutes les fonctions d OVIPAR except s ovipar et placedpar toute r f rence ces deux fonctions choue en dehors du contexte d crit plus haut 405 Le programme parall le doit tre compil en faisant r f rence la librairie d OVIPAR Comme tout environnement bas sur l appel de fonctions OVIPAR n effectue aucun contr le syntaxique et s mantique et se limite ceux qu offre le langage C C est pourquoi le programmeur doit se conformer la syntaxe du manuel d utilisation d OVIPAR 1 5 UTILISATION D OVIPAR Le programme OVIPAR doit tre ex cut comme toute commande UNIX OVIPAR d marre quand la fonction ovipar est ex cut e et s arr te automatiquement d s que tous les processus qu il supporte sont termin s Mettant en oeuvre des techniques de programmation avanc es le programme OVIPAR ne doit pas tre arr t de mani re inopin e Dans sa version actuelle OVIPAR n offre pas de possibilit s de terminaison de programmes autres que celles de C et UNIX Cela peut sembler tre une limitation s v re surtout dans le contexte d apprentissage dans lequel il est cens tre exploit En fait dans un tel contexte des applications lourdes qui peuvent exiger de tels soins ne sont pas con ues OVIPAR n est pas un outil
14. ravers la fen tre de celui ci Le p re recouvre ses droits sur les canaux la terminaison des fils Les communications sont synchrones et binaires Si le nombre n d octets envoy s par un processus et diff rent du nombre n2 qu aitend le destinataire alors le nombre d octets effectivement transf r s sera gal au minimum de n1 et n2 Les fonctions de communication retournent ce minimum Un processus peut cr er plusieurs fils Il sp cifie pour chacun d eux une fen tre de communication Le p re se bloque apr s la cr ation des fils jusqu la terminaison du dernier fils tout moment un processus peut conna tre l identit de processeur sur lequel il s ex cute 1 4 PROGRAMME OVIPAR Un programme OVIPAR est un programme C faisant r f rence aux fonctions de la biblioth que OVIPAR Ce programme doit comporter un appel la fonction ovipar qui constitue le point d entr e du programme parall le Cette fonction sp cifie la topologie de la machine et doit comporter dans ces param tres un pointeur sur une fonction de chargement de la machine La fonction de chargement a pour r le de sp cifier la composante qui sera ex cut e sur chaque noeud Elle doit se terminer par un appel la fonction placedpar qui r alise le placement des composantes sur les noeuds Une composante est le premier processus OVIPAR qui s ex cute sur un noeud Un processus OVIPAR est sp cifi comme une fonction C ayant le m me format
15. sp cifiant des connexions point point entre les liens des diff rents noeuds Chaque noeud peut avoir jusqu quatre voisins compte tenu du nombre de liens Les liens sont nomm s N nord S sud E est et W ouest Une connexion entre deux noeuds se fait en sp cifiant les liens impliqu s Deux noeuds peuvent avoir plus d une interconnexion OVIPAR ne permet pas de sp cifier des noeuds isol s 404 Le nombre de noeuds d OVIPAR ct le nombre de processus par noeud ne sont limit s que par les capacit s de la machine UNIX utilis e e g nombre de processus qu un utilisateur peut cr er 1 3 PROCESSUS OYIPAR Un processus OVIPAR est un processus UNIX disposant d une fen tre de communication avec d autres processus Cette fen tre est constitu e de canaux de communication Elle peut tre constitu e de liens ou de canaux internes au noeud La fen tre d un processus est toujours cr e par le processus p re avec des canaux ou des liens que ce dernier a h rit ou de canaux cr s par le p re lui m me pour ses fils Un processus peut cr er autant de canaux qu il veut Ces canaux sont internes au noeud ne peuvent tre utilis s que par les fils du processus et ses descendants qui en ont herit s tout moment un canal ne peut tre partag que par deux processus Comme le p re se bloque en attendant la fin de ses fils le p re peut transmettre par h ritage ses droits sur un canal un fils t
16. uivant le format de main La sp cification de la fen tre du processus se fait en indiquant les liens et les canaux dont le processus h rite La liste des liens est sp cifi e sous la forme d une somme bocl enne CHN NORTH CHN_SOUTH CHN_EAST CHN_WEST selon les liens utilisables Les canaux sont sp cifi s travers une liste Les param tres de la fonction point d entr e sont sp cifi es comme pour la fonction main Il est recommand d utiliser un tableau pour regrouper tous les descripteurs void initproc pdesc fect node IL chn argc argv csp_t pdesc Empty process descriptor int fct 0 Entry point function of the process It is the first process to be executed on the node It must be written in the format of C main function This function could also be a process model for the par instruction char Il Bitmap specifying the node links to be used chnt chn Internal channel list Only used with par instruction int arge Argument count of fet char argv Argument vector of fct La fonction initcomp fait la m me chose que la fonction inifproc pour cr er les composantes des noeuds Elle admet un param tre suppl mentaire qui est le num ro du noeud sur lequel la composante est cr e 3 3 CHARGEMENT DE LA MACHINE PLACEDPAR Cette fonction de style main permet de charger la machine OVIPAR Elle prend en param tre une table de descripteurs de processus cr s avec la fonction inifproc cr e les processus
17. ur la fonction de chargement avec ses arguments La topologie est d crite sous forme d une cha ne de caract res compos e d une s quence de connexions Chaque connexion se pr sente sous la forme IC 1JC gt tels que I et J sont des num ros de noeuds et C1 et C sont des liens i e N S E W La fonction de chargement dont le pointeur repr sente le troisi me param tre doit tre crite suivant le mod le de la fonction main du langage C Le quatri me param tre est le nombre de param tres de la fonction de chargement Enfin le dernier param tre est un tableau constitu de param tres de la fonction de chargement La fonction ovipar retourne O en cas de succ s int ovipar nodesnum topo fct argc argv int nodesnum Specif the number of nodes char topo Describe the node interconnection topology in 407 term of couples of links to be connected int fct Entry point of the parallel program This function is expected to load the nodes It must be written in the format of C main function int arac Argument count of fct char av Argument vector of fet 3 2 CR ATION D UN DESCRIPTEUR DE PROCESSUS INITPROC Cette fonction permet de cr er un descripteur de processus c est dire une structure de donn es OVIPAR contenant entre autres la fen tre du processus et le pointeur de la fonction point d entr e correspondant au code du processus La fonction point d entr e doit tre crite s
Download Pdf Manuals
Related Search