/*************************************************************************************************************************************/ /* */ /* C A L C U L D E L ' E N S E M B L E D E M A N D E L B R O T */ /* D A N S U N E M E M O I R E V I R T U E L L E D I S T R I B U E E : */ /* */ /* */ /* Author of '$xtc/nCube.22$c' : */ /* */ /* Jean-Francois COLONNA (LACTAMME, AAAAMMJJhhmmss). */ /* */ /*************************************************************************************************************************************/ #include "nCube.21.I"
/*************************************************************************************************************************************/
/* */
/* C A L C U L D E L ' E N S E M B L E D E M A N D E L B R O T */
/* D A N S U N E M E M O I R E V I R T U E L L E D I S T R I B U E E : */
/* */
/* */
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/* * * * ** * * * * * ** * */
/* * * * * * * * * * * * * * * * */
/* * * * * * * * * * * * * * */
/* * * * * * * * * * * * * * * * */
/* * * * * * * * * * * * * * * * */
/* * * * * * * * * * * * * * * * * * */
/* * * * * * * * * * * * * * */
/* * * * * * * * * * * * * * * * */
/* * * * * ** * * * * * ** */
/* * * * * * * * * * * * * * * * * * * * * * * */
/* */
/* */
/* ATTENTION : */
/* */
/* Ce fichier ('$xtc/nCube.22$I') est */
/* reference dans '$xiMd/nCube.22$c.$m4' */
/* a des fins de demonstration 'WWW'. */
/* */
/* Author of '$xtc/nCube.22$I' : */
/* */
/* Jean-Francois COLONNA (LACTAMME, AAAAMMJJhhmmss). */
/* */
/*************************************************************************************************************************************/
/*************************************************************************************************************************************/
/* */
/* F O R M A T D E L ' I M A G E A G E N E R E R : */
/* */
/*************************************************************************************************************************************/
static int dimX=UNDEF;
#define Xmin \
RIEN
#define Xmax \
(Xmin + (dimX-UNITE))
/* Definition des abscisses. */
static int dimY=UNDEF;
#define Ymin \
RIEN
#define Ymax \
(Ymin + (dimY-UNITE))
/* Definition des ordonnees. */
/*************************************************************************************************************************************/
/* */
/* D E F I N I T I O N D E S D O N N E E S E N M E M O I R E V I R T U E L L E : */
/* */
/*************************************************************************************************************************************/
#define FORMAT_PLAN_COMPLEXE \
iLONGUEUR_caractere
#define LONGUEUR_PLAN_COMPLEXE \
(dimX*dimY)
#define PLAN_COMPLEXE \
IMPLANTATION_EN_MEMOIRE_VIRTUELLE((DEBUT_DE_LA_MEMOIRE_VIRTUELLE + LONGUEUR_DEBUT_DE_LA_MEMOIRE_VIRTUELLE) \
,FORMAT_DEBUT_DE_LA_MEMOIRE_VIRTUELLE \
,FORMAT_PLAN_COMPLEXE \
)
#define ACCES_PLAN_COMPLEXE(x,y) \
ADRESSAGE_EN_MEMOIRE_VIRTUELLE(PLAN_COMPLEXE,(((y)*dimX) + (x)))
/* Emplacement du plan complexe dans la memoire virtuelle. */
#define FORMAT_LIGNE_A_TRAITER \
iLONGUEUR_entier
#define LONGUEUR_LIGNE_A_TRAITER \
(dimY)
#define LIGNE_A_TRAITER \
IMPLANTATION_EN_MEMOIRE_VIRTUELLE((PLAN_COMPLEXE + LONGUEUR_PLAN_COMPLEXE) \
,FORMAT_PLAN_COMPLEXE \
,FORMAT_LIGNE_A_TRAITER \
)
#define ACCES_LIGNE_A_TRAITER(y) \
ADRESSAGE_EN_MEMOIRE_VIRTUELLE(LIGNE_A_TRAITER,(y))
/* Emplacement des indicateurs des lignes du plan complexe non encore traitees. */
#define FORMAT_LIGNE_ENTIEREMENT_TRAITEE \
iLONGUEUR_entier
#define LONGUEUR_LIGNE_ENTIEREMENT_TRAITEE \
(dimY)
#define LIGNE_ENTIEREMENT_TRAITEE \
IMPLANTATION_EN_MEMOIRE_VIRTUELLE((LIGNE_A_TRAITER + LONGUEUR_LIGNE_A_TRAITER) \
,FORMAT_LIGNE_A_TRAITER \
,FORMAT_LIGNE_ENTIEREMENT_TRAITEE \
)
#define ACCES_LIGNE_ENTIEREMENT_TRAITEE(y) \
ADRESSAGE_EN_MEMOIRE_VIRTUELLE(LIGNE_ENTIEREMENT_TRAITEE,(y))
/* Emplacement des indicateurs des lignes du plan complexe entierement traitees. */
#define FORMAT_VERROU \
iLONGUEUR_entier
#define LONGUEUR_VERROU \
(UNITE)
#define VERROU \
IMPLANTATION_EN_MEMOIRE_VIRTUELLE((LIGNE_ENTIEREMENT_TRAITEE + LONGUEUR_LIGNE_ENTIEREMENT_TRAITEE) \
,FORMAT_LIGNE_ENTIEREMENT_TRAITEE \
,FORMAT_VERROU \
)
#define ACCES_VERROU \
ADRESSAGE_EN_MEMOIRE_VIRTUELLE(VERROU,CLEAR)
/* Emplacement du verrou d'exclusion des phases critiques. */
/*************************************************************************************************************************************/
/* */
/* D E F I N I T I O N D E S I T E R A T I O N S : */
/* */
/*************************************************************************************************************************************/
#define NOMBRE_MAXIMAL_D_ITERATIONS \
(250) \
/* Definition du nombre maximal d'iterations. */
#define SEUIL \
(4.0)
/* Definition du seuil de fuite a l'infini du module de 'Zn'... */
#define NOIR \
(0)
#define BLANC \
(255)
/* Definition des niveaux extrema. */
#define LIGNE(x) \
(*(ligne + (x))) \
/* Acces a un point de la ligne courante... */
#define IMAGE_EXTERNE(x,y) \
(*(image_externe + (((y)*dimX) + (x)))) \
/* Acces a un point de l'image au format externe. */
#define Cn(n) \
((CHAR)(NOIR + (((FLOTTANT)(n-1)/(FLOTTANT)NOMBRE_MAXIMAL_D_ITERATIONS)*((FLOTTANT)(BLANC-NOIR))))) \
/* Definition de niveaux dans l'image... */
#define store_image(n,x,y) \
{ \
CHAR valeur=n; \
StoreC(ACCES_PLAN_COMPLEXE(x,y),valeur); \
} \
/* Rangement d'un point valide d'une image. */
#define XG \
(-2.00)
#define XD \
(0.50)
/* Extremites Gauche et Droite sur l'axe des 'X'. */
#define YB \
(-1.25)
#define YH \
(1.25)
/* Extremites Bas et Haut sur l'axe des 'Y'. */
/*************************************************************************************************************************************/
/* */
/* D E F I N I T I O N D E S N O M B R E S C O M P L E X E S : */
/* */
/*************************************************************************************************************************************/
typedef struct complexe {
FLOTTANT reelle;
FLOTTANT imaginaire;
} complexe;
/* 'struct' de definition d'un nombre complexe... */
#define Reelle(z) \
(z.reelle)
#define Imaginaire(z) \
(z.imaginaire)
#define Cinit(z,x1,y1) \
{ \
Reelle(z) = x1; \
Imaginaire(z) = y1; \
}
#define Cegal(z,z1) \
{ \
Reelle(z) = Reelle(z1); \
Imaginaire(z) = Imaginaire(z1); \
}
#define Csomme(z,z1,z2) \
{ \
Reelle(z) = Reelle(z1) + Reelle(z2); \
Imaginaire(z) = Imaginaire(z1) + Imaginaire(z2); \
}
#define Cproduit(z,z1,z2) \
{ \
Reelle(z) = (Reelle(z1)*Reelle(z2)) - (Imaginaire(z1)*Imaginaire(z2)); \
Imaginaire(z) = (Reelle(z2)*Imaginaire(z1)) + (Reelle(z1)*Imaginaire(z2)); \
}
#define Cmodule2(z) \
((Reelle(z)*Reelle(z)) + (Imaginaire(z)*Imaginaire(z)))
#define PETIT \
(1.0e-16)
#define GRAND \
(1.0e32)
#define deborde(x) \
{ \
if (((x) < -PETIT) || ((x) > PETIT)) \
{ \
} \
else \
{ \
x = (FLOTTANT)CLEAR; \
} \
\
if ((x) < -GRAND) \
{ \
x = -GRAND; \
} \
else \
{ \
} \
\
if ((x) > GRAND) \
{ \
x = GRAND; \
} \
else \
{ \
} \
}
#define Cdeborde(z) \
{ \
deborde(Reelle(z)); \
deborde(Imaginaire(z)); \
}
/*************************************************************************************************************************************/
/* */
/* C O D E D E T E S T D E S C L I E N T S A V E C L E */
/* C A L C U L D E L ' E N S E M B L E D E M A N D E L B R O T : */
/* */
/* */
/* Benchmark approximatif du 01/10/1993 : */
/* */
/* Celui-ci, pour des raisons de */
/* commodite, est obtenu en faisant */
/* la "difference" de deux commandes */
/* 'date'. Le test a ete conduit avec : */
/* */
/* */
/* LDb */
/* */
/* #define NOMBRE_MAXIMAL_D_ITERATIONS \ */
/* 2500 */
/* */
/* */
/* afin de faire plus de calculs que */
/* d'acces a la memoire virtuelle... */
/* */
/* */
/* ------------------------------------------------------------------------------- */
/* | | | avec | sans | */
/* | | | phase critique | phase critique | */
/* | | | | | */
/* | dimension | nombre | duree | duree | */
/* | de l'hypercube | de clients | (en secondes) | (en secondes) | */
/* | | | | | */
/* |-------------------|-------------------|-------------------|-------------------| */
/* | | | | | */
/* | 01 | 01 | 108 | 109 | */
/* | | | | | */
/* | 02 | 02 | 057 | 057 | */
/* | | | | | */
/* | 03 | 04 | 031 | 053 | */
/* | | | | | */
/* | 04 | 08 | 019 | 036 | */
/* | | | | | */
/* | 05 | 16 | 016 | 023 | */
/* | | | | | */
/* | 06 | 32 | 045 (!) | 015 | */
/* | | | | | */
/* ------------------------------------------------------------------------------- */
/* */
/* */
/* On notera qu'au debut il y a une relation */
/* presque lineaire entre la duree et l'inverse */
/* du nombre de clients, puis qu'il y a un fort */
/* ralentissement, puis enfin, une dramatique */
/* inversion... */
/* */
/* Enfin, la duree d'execution du programme */
/* 'v $xtc/mandel.11$c', dans les memes conditions */
/* a ete de 100 secondes. La version monoprocesseur */
/* de 'v $xtc/nCube.22$c' n'est donc penalisee que de */
/* de 8 secondes, ce qui est peu... */
/* */
/*************************************************************************************************************************************/
static int phase_critique=NOK;
/* Indique si l'acces aux lignes par les processeurs se fait via une phase critique (=OK), */
/* ou en fonction simplement du numero de processeur (#OK). */
client()
{
CHAR *ligne;
/* Definition de la ligne courante a generer... */
int x,y;
/* Definition des coordonnees. */
if (processeur_local == CLIENT_NATUREL(PREMIER_PROCESSEUR))
{
if (CLEAR)
/* Malheureusement, la fonction 'system(...)' n'est pas implementee... */
{
fprintf(stderr,"\n heure de debut sur le client maitre : ");
system("date '+%H:%M:%S'");
fprintf(stderr,"\n");
}
else
{
}
clock();
/* Chronometrage... */
}
else
{
}
Get(dimX,"dimX");
Get(dimY,"dimY");
/* Recuperation des dimensions en 'X' et en 'Y' de l'image a generer. */
unite_d_entrelacage = dimY;
/* L'unite d'entrelacage correspondra a une ligne... */
Malloc(ligne,dimY*iLONGUEUR_caractere);
/* Allocation de la ligne courante a generer... */
for (y=Ymin ; y<=Ymax ; y++)
{
int on_n_a_pas_trouve_de_ligne=OK;
int indicateur=CLEAR;
/* L'initialisation de 'indicateur' est faite sur 'CLEAR' et non point sur 'UNDEF' a cause */
/* du cas ou l'on ne passe pas ci-apres par une phase critique (voir 'phase_critique'). */
if (phase_critique == OK)
{
WaitVerrou(VERROU,phase_critique);
/* Tentative d'entree dans une phase critique de recherche d'une ligne 'y' non encore */
/* traitee par un autre processeur... */
LoadI(ACCES_LIGNE_A_TRAITER(y),indicateur);
if (indicateur == CLEAR)
{
on_n_a_pas_trouve_de_ligne++;
/* Cas ou l'on a trouve une ligne a traiter... */
indicateur++;
StoreI(ACCES_LIGNE_A_TRAITER(y),indicateur);
/* On indique que cette ligne va etre traitee... */
}
else
{
}
ClearVerrou(VERROU,phase_critique);
/* Sortie de la phase critique... */
}
else
{
int Ymin_local;
int Ymax_local;
int lignes_locales=(dimY/nombre_total_de_serveurs);
Ymin_local = Ymin + (lignes_locales*NUMERO_DE_PROCESSEUR__NUMERO_DE_SERVEUR(processeur_local));
Ymax_local = Ymin_local + lignes_locales - UNITE;
if ((y >= Ymin_local) && (y <= Ymax_local))
{
on_n_a_pas_trouve_de_ligne++;
indicateur++;
/* Cas ou l'on a trouve une ligne a traiter... */
}
else
{
}
}
if (on_n_a_pas_trouve_de_ligne != OK)
{
/* Lorsque l'on a trouve une ligne non encore traitee, on la prend et on la traite : */
FLOTTANT xg=((XD+XG)/2) - ((((XD-XG)*dimX)/dimY)/2);
FLOTTANT yb=YB;
FLOTTANT xd=((XD+XG)/2) + ((((XD-XG)*dimX)/dimY)/2);
FLOTTANT yh=YH;
/* Definition de la fenetre de calcul en fonction des proportions de l'image... */
complexe C;
complexe Zn;
complexe zt;
/* Definition de nombres complexes necessaires. */
for (x=Xmin ; x<=Xmax ; x++)
{
int index=UNITE;
int iterer=OK;
/* Variables d'iterations... */
Cinit(C
,((FLOTTANT)x / (FLOTTANT)dimX)*(xd-xg) + xg
,((FLOTTANT)y / (FLOTTANT)dimY)*(yh-yb) + yb
);
/* Initialisation du point complexe courant 'C' sur le point {x,y}. */
Cinit(Zn,0.0,0.0);
/* Initialisation de la suite Zn. */
while (iterer == OK)
{
Cproduit(zt,Zn,Zn);
Csomme(Zn,zt,C);
Cdeborde(Zn);
/* Iteration de la suite Zn. */
if ((index >= NOMBRE_MAXIMAL_D_ITERATIONS) || (Cmodule2(Zn) > SEUIL))
{
LIGNE(x) = Cn(index);
/* Memorisation locale du point courant (x) de la ligne courante (y)... */
iterer++;
/* Et l'iteration courante est terminee... */
}
else
{
index++;
}
}
}
if (unite_d_entrelacage == dimY)
{
MStoreC(ACCES_PLAN_COMPLEXE(Xmin,y),dimY*iLONGUEUR_caractere,LIGNE(Xmin));
}
else
{
for (x=Xmin ; x<=Xmax ; x++)
{
store_image(LIGNE(x),x,y);
}
}
StoreI(ACCES_LIGNE_ENTIEREMENT_TRAITEE(y),indicateur);
/* On indique que cette ligne a ete entierement traitee... */
}
else
{
/* Lorsque l'on a trouve une ligne deja traitee, on va voir la suivante... */
}
}
if (processeur_local == CLIENT_NATUREL(PREMIER_PROCESSEUR))
{
clock_t duree=clock();
CHAR *image_externe;
Malloc(image_externe,(dimY*dimX)*iLONGUEUR_caractere);
/* Definition de l'image a generer... */
if (CLEAR)
/* Malheureusement, la fonction 'system(...)' n'est pas implementee... */
{
fprintf(stderr,"\n heure de fin sur le client maitre : ");
system("date '+%H:%M:%S'");
fprintf(stderr,"\n");
}
else
{
}
fprintf(stderr,"\n duree du calcul sur le client maitre : %d milli-secondes",duree/(CLOCKS_PER_SEC/1000));
fprintf(stderr,"\n");
fprintf(stderr,"\n identite du client 'maitre' = %d",processeur_local);
fprintf(stderr,"\n nombre de serveurs = %d",nombre_total_de_serveurs);
fprintf(stderr,"\n nombre de clients = %d",nombre_total_de_clients);
fprintf(stderr,"\n dimension de l'image = %dx%d",dimX,dimY);
fprintf(stderr,"\n nombre d'iterations = %d",NOMBRE_MAXIMAL_D_ITERATIONS);
if (phase_critique == OK)
{
fprintf(stderr,"\n mode allocation dynamique des lignes (d'ou exclusion de phase critique)");
}
else
{
fprintf(stderr,"\n mode allocation statique des lignes (d'ou un temps de regroupement variable)");
}
if (unite_d_entrelacage == dimY)
{
fprintf(stderr,"\n mode emission bloquee des points de chaque ligne");
}
else
{
fprintf(stderr,"\n mode emission individuelle des points");
}
fprintf(stderr,"\n");
for (y=Ymin ; y<=Ymax ; y++)
{
int indicateur=CLEAR;
while (indicateur == CLEAR)
{
LoadI(ACCES_LIGNE_ENTIEREMENT_TRAITEE(y),indicateur);
/* On regarde si la ligne courante a ete traitee entierement ; si elle ne l'a pas ete, on */
/* attend qu'elle le soit. On notera qu'il ne s'agit pas ici d'une phase critique puisque */
/* l'on ne fait que lire 'ACCES_LIGNE_ENTIEREMENT_TRAITEE(y)'... */
}
if (unite_d_entrelacage == dimY)
{
MLoadC(ACCES_PLAN_COMPLEXE(Xmin,y),dimY*iLONGUEUR_caractere,IMAGE_EXTERNE(Xmin,y));
}
else
{
for (x=Xmin ; x<=Xmax ; x++)
{
LoadC(ACCES_PLAN_COMPLEXE(x,y),IMAGE_EXTERNE(x,y));
}
}
}
fprintf(stderr
,"\n duree du regroupement sur le client maitre : %d milli-secondes"
,(clock()-duree)/(CLOCKS_PER_SEC/1000)
);
/* ATTENTION : cette duree de regroupement des lignes de l'image est bien entendu */
/* independante du nombre de processeurs utilises. Malgre cela, l'impression ci-dessus */
/* donne une indication contradictoire lorsqu'il n'y a pas allocation dynamique des lignes */
/* (phase_critique == NOK). En effet, il apparait que vue la structure de l'ensemble de */
/* Mandelbrot, les processeurs travaillant sur les bandes centrales de l'image ont beaucoup */
/* plus de travail que ceux qui travaillent a la peripherie. Or le processeur maitre qui */
/* fait le regroupement travaille precisemment a la peripherie. Cela signifie que lorsqu'il */
/* a termine ses calculs, il doit attendre les autres ; c'est cette attente qui rend dans ce */
/* cas de non allocation dynamique des lignes, le temps de regroupement croissant lorsque le */
/* nombre de processeurs decroit... */
fprintf(stderr,"\n");
write(STANDARD_OUT,image_externe,dimX*dimY);
/* Sortie de l'image... */
free(image_externe);
}
else
{
}
return(OK);
}