|
|||||||||||||||||||||||
En utilisant la bibliothèque PVM, écrire un programme C qui affiche la suite des nombres premiers par la méthode du crible d'Erathostène: un processus est chargé de générer les entiers naturels, dont on élimine d'abord les multiples de 2, puis 3, 5 etc. au moyen de processus filtrants successifs.
On recommande chaudement de montrer le programme (qui compile néanmoins) à un chargé de TP avant de l'essayer...
|
|
|
On considère un schéma explicite en temps et une discrétisation explicite d'ordre deux en espace. On approxime donc u par ses valeurs discrétisées en les sommets (i,j) d'une grille régulière de pas h (en abscisse et ordonnée), et en des temps n (pas de temps Dt ), soit ui,jn . L'équation discrétisée est maintenant:
|
|
| 4kDt
rch2 |
= | 1
2 |
et on choisira h .
On souhaite écrire un programme maître/esclave permettant de calculer le schéma précédent,
Remarque:
Ceci est un exercice un peu académique dans le sens où certains de ces algorithmes dits de ``réduction'' sont déjà implémentés sous PVM.
Rappel:
int numt; numt=pvm_spawn(char *task,char **argv,int flag,char *where,int ntask,int *tids);
Calcul récursif d'une transformée de fourier rapide (les sources sont accessibles sur la page web du cours, dans la section ``corrigés'').
``fft-startup'' est à la racine de l'arbre des appels récursifs:
#include <stdlib.h>
#include <stdio.h>
#include "pvm3.h"
#define RESULT_TAG 1
#define MAX_LENGTH 128
main(argc, argv)
int argc;
char *argv[];
{
/* argv[i] is the unidimensional complex signal to be processed */
/* format is fft Re(x_1) Im(x_1) Re(x_2) ... Re(x_n) Im(x_n) */
int i,bufid,mtid,tid,numt;
float R[MAX_LENGTH];
if ((mtid=pvm_mytid())<0)
{
printf("unexpected error occured!\n");
exit(1);
}
setlinebuf(stdout);
if (argc < 5)
{
printf("wrong number of parameters\n");
exit(1);
}
numt = pvm_spawn("fft",&argv[1],PvmTaskDefault,"",1,
&tid);
if (numt != 1)
{
printf("could not spawn fft\n");
exit(1);
}
bufid = pvm_recv(tid, RESULT_TAG);
pvm_upkfloat(&R[0],argc-1,1);
for (i=0;i<(argc-1)/2;i++)
{
printf(" %g %g",R[i],R[i+(argc-1)/2]); }
printf("\n");
pvm_exit();
exit(0); }
Le programme récursif ``fft'' se charge du calcul effectif:
#include <math.h>
#include <stdio.h>
#include "pvm3.h"
#define RESULT_TAG 1
#define SIZE 64
#define MAX_LENGTH 128
#define PI 3.14159265358
main(argc, argv)
int argc;
char *argv[];
{
/* argv[i] is the unidimensional complex signal to be processed */
/* format is fft Re(x_1) Im(x_1) Re(x_2) ... Re(x_n) Im(x_n) */
/* sends to his parent an array of float with RESULT_TAG equal to 1 */
int i,numt,bufid,mtid,ptid,lstid,rstid;
float wr,wi;
float Rr[MAX_LENGTH],Ri[MAX_LENGTH];
float Xr[MAX_LENGTH];
float Xi[MAX_LENGTH];
float T1[MAX_LENGTH],T2[MAX_LENGTH];
char *fargv1[MAX_LENGTH+1],*fargv2[MAX_LENGTH+1];
if ((mtid=pvm_mytid())<0)
{
printf("unexpected error occured!\n");
exit(1);
}
ptid=pvm_parent();
setlinebuf(stdout);
for (i=0;i<(argc-1)/2;i++)
{
sscanf(argv[2*i+1],"%g",&Xr[i]);
sscanf(argv[2*(i+1)],"%g",&Xi[i]);
if (i%2 == 0)
{
fargv1[i]=argv[2*i+1];
fargv1[i+1]=argv[2*(i+1)];
}
else
{
fargv2[i-1]=argv[2*i+1];
fargv2[i]=argv[2*(i+1)];
}
}
fargv1[(argc-1)/2]=NULL;
fargv2[(argc-1)/2]=NULL;
if (argc==5)
{
Rr[1]=(Xr[0]-Xr[1])/2;
Ri[1]=(Xi[0]-Xi[1])/2;
Rr[0]=(Xr[0]+Xr[1])/2;
Ri[0]=(Xi[0]+Xi[1])/2;
}
else
{
numt = pvm_spawn("fft",&fargv1[0],PvmTaskDefault,"",1,
&lstid);
if (numt != 1)
{
printf("could not spawn left son\n");
exit(1);
}
numt = pvm_spawn("fft",&fargv2[0],PvmTaskDefault,"",1,
&rstid);
if (numt != 1)
{
printf("could not spawn right son\n");
exit(1);
}
bufid = pvm_recv(lstid, RESULT_TAG);
pvm_upkfloat(&T1[0],(argc-1)/2,1);
bufid = pvm_recv(rstid, RESULT_TAG);
pvm_upkfloat(&T2[0],(argc-1)/2,1);
for (i=0;i<(argc-1)/4;i++)
{
wr=cos(-4*PI*i/(argc-1));
wi=sin(-4*PI*i/(argc-1));
Rr[i]=(T1[i]+wr*T2[i]-wi*T2[i+(argc-1)/4])/2;
Ri[i]=(T1[i+(argc-1)/4]+wr*T2[i+(argc-1)/4]+wi*T2[i])/2;
Rr[i+(argc-1)/4]=(T1[i]-wr*T2[i]+wi*T2[i+(argc-1)/4])/2;
Ri[i+(argc-1)/4]=(T1[i+(argc-1)/4]-wr*
T2[i+(argc-1)/4]-wi*T2[i])/2;
}
}
pvm_initsend(PvmDataDefault);
pvm_pkfloat(&Rr[0],(argc-1)/2,1);
pvm_pkfloat(&Ri[0],(argc-1)/2,1);
pvm_send(ptid,RESULT_TAG); pvm_exit(); exit(0); }
Remarque:
Cela peut servir entre autres à faire de l'équilibrage de charge ``centralisé'' où les clients demandent sitôt qu'il ont fini un calcul sur un sous-domaine d'autres calculs à effectuer au serveur.
Annexe:
Réception non-bloquante:
int bufid; bufid=pvm_nrecv(int tid,int msgtag);
int info; info=pvm_bufinfo(int bufid,int *bytes,int *msgtag,int *tid);
#include <stdio.h>
#include <pvm3.h>
#define MSG 1
main()
{
int mtid,ctid,bufid,ok,i;
if ((mtid=pvm_mytid())<0) { pvm_exit();
exit(1); }
pvm_spawn("async2",(char **) 0,PvmTaskDefault,
(char *) 0,1,&ctid);
fprintf(stdout,"I am spawning one child\n");
fflush(stdout);
ok = 0;
i = -1;
while (!ok)
{ i++;
bufid = pvm_nrecv(ctid,MSG);
if (bufid < 0) { pvm_perror("Pb with nrecv");
pvm_exit(); exit(1); }
if (bufid != 0) ok=1;
else if ((i % 60000) == 0)
{ fprintf(stdout,"I am computing...\n");
fflush(stdout);
} }
pvm_upkint(&i,1,1);
fprintf(stdout,"I have received %d\n",i);
fflush(stdout);
pvm_exit();
exit(1);
}
Esclave ``async2'':
#include <stdio.h>
#include <pvm3.h>
#define MSG 1
main()
{
int i=42;
sleep(4);
fprintf(stdout,"I'm sending a message to my parent\n");
fflush(stdout);
pvm_initsend(PvmDataDefault);
pvm_pkint(&i,1,1);
pvm_send(pvm_parent(),MSG);
pvm_exit();
exit(1);
}
pvm> spawn -1 -> async1 [11] 1 successful t40021 pvm> [11:t40021] I am spawning one child [11:t40021] I am computing... [11:t40021] I am computing... [11:t40021] I am computing... [11:t40021] I am computing... [11:t40021] I am computing... [11:t40022] I am sending a message to my parent [11:t40022] EOF [11:t40021] I have received 42 [11:t40021] EOF [11] finished
Soit donc à résoudre le système triangulaire supérieur
|
|
et Ui,i ¹ 0 pour tout 1 £ i £ n .
On procède par ``remontée'' c'est à dire que l'on
calcule successivement,
|
pour i = n-1,n-2,¼,1 .
On écrit les équations précédentes en pseudo-code C de la façon suivante:
x[n]=b[n]/U[n,n];
for (i=n-1;i>=1;i--)
{
x[i]=0;
for (j=i+1;j<=n;j++)
L: x[i]=x[i]+U[i,j]*x[j];
x[i]=b[i]-x[i]/U[i,i];
}
où n est la taille de la matrice U représentée
par le tableau U[i,j], où x[i] (i entre
1 et n) représente le vecteur ``inconnu'' x et b[i],
le vecteur second membre du système d'équations linéaires.
Programmer le code de remontée correspondant en PVM. On supposera que Pn est le maître qui contient au début tout le tableau U et le tableau b et crée ses esclaves P1 , ¼, Pn-1 . On pourra comme dans le cas séquentiel commencer par calculer x[n]. Ensuite, l'idée sera de placer chacune des composantes des tableaux rentrant en compte pour le calcul de la ième équation linéaire ( 1 £ i £ n-1 )1 sur le ième processeur Pi . On pourra donc propager les valeurs déjà résolues des x[j], j ³ i+1 aux processeurs Pk , k £ i, qui effectueront une même étape de sommation élémentaire. A la fin il doit attendre le résultat de tous ses esclaves.