C++
Análisis de los sumadores en algoritmos paralelos.
Los procesadores paralelos
se usan para acelerar la resolución de problemas de alto coste computacional, en el caso de que las sumas sean potencialmente
numerosas.
La finalidad principal consiste
en reducir el tiempo de ejecución:
si el tiempo secuencial t(n)
se intentará que usando p
procesadores
el tiempo se reduzca a t(n)/p.
Ver algunas medidas que nos
dan idea de la "bondad" de un algoritmo paralelo.
Tiempo secuencial
• El tiempo de ejecución
de un programa secuencial
depende de: tamaño de la entrada de datos
u operandos, compilador,máquina,programador, ...,
si nos olvidamos de valores
constantes dependientes del sistema (por ejemplo el coste de una operación aritmética como la suma en la máquina donde ejecutamos el programa) podemos considerar el tiempo función del tamaño de la entrada:
t(n).
El tiempo desde que empieza
la ejecución del programa hasta que acaba con la obtención de los resultados
parciales y totales .
Tiempo de ejecución paralelo
• En un programa paralelo
la estimación del tiempo es
más compleja.
Además de los parámetros anteriores,
depende de:
número de procesadores t(n,p),
de la manera en que están
conectados entre sí
(topología) y con los módulos
de memoria
(memoria compartida o distribuida)
• Es el tiempo transcurrido
desde que empieza la
ejecución del primero de los
procesadores con la entrada de datos operandos en array hasta que
acaba el último de ellos.
Tiempo de ejecución paralelo
DIFICULTADES:
• No siempre es fácil
determinar el orden en que los
procesadores empiezan y acaban.
• A lo largo de la ejecución
de un programa de suma en paralelo hay puntos de sincronización de los que no siempre podemos determinar su duración al no
saber en el orden en que van a llegar los distintos procesos a estos puntos.
En la parte teórica
sobre la suma se deben considerar también los siguientes aspectos:
Tiempo de ejecución de la suma en paralelo
t(n,p)=ta(n,p)+tc(n,p)
ta(n,p)
:
suma de los tiempos de las distintas partes de
computación
tc(n,p)
:
suma de los tiempos de las distintas partes de
comunicación
Tiempo de ejecución de suma en paralelo, ejemplo
• Programa paralelo
en dos procesadores:
Computación 1 2 3
Comunicación 1 1 1
Computación 2 3 2
Comunicación 2 1 1
t(n,p)=ta(n,p)+tc(n,p)=7
(si
se hace por separado)
treal(n,p)=ta(n,p)+tc(n,p)+toverhead(n,p)=8
Tiempo de ejecución paralelo, ejemplo
2 3
1
t(n,p)=ta(n,p)+tc(n,p)=15
treal(n,p)=ta(n,p)+tc(n,p)t
solapamiento(n,p)=14
Tiempo de ejecución
• Overhead debido a:
sincronización,
puesta en marcha de los procesos,
sobrecarga de la red de comunicación,
• Se suele considerar:
t(n,p)=ta(n,p)+tc(n,p)+to(n,p)t
s(n,p)
• Minimizar el tiempo
de overhead.
• Maximizar el solapamiento.
Suma de n números en un fichero
• Secuencial: t(n)=n1
• Paralelo con n/2
procesadores,
como mínimo t(n)/(n/2)=2
En cada Pi, i=0,1,...,n/21
inicio=2*i
desplazamiento=1
activo=true
para k=1,2,...,log n
si activo
a[inicio]=a[inicio]+a[inicio+desplazamiento]
desplazamiento=desplazamiento*2
finsi
si i mod desplazamiento <>0
activo=false
finsi
finpara
Suma de n números en un fichero
• Pasos: log n
• Trabajo adicional
(overhead):
Comprobación de si el procesador
trabaja,
Uso de las variables,
Actualización de las variables.
• Con n=64
si cada paso secuencial y
paralelo igual coste:
t(n)@8*t(n,p)
si cada paso secuencial coste
2 y paralelo coste 5:
t(n)@3.5*t(n,p)
• Y en memoria distribuida
problema de acceso a los datos.
Causas de reducción de las prestaciones
• Contención de memoria:
En memoria compartida el acceso
a datos comunes o que están en el mismo bloque de memoria producirá contención.
Si los datos son de lectura
puede no haber ese problema.
En el ejemplo los procesadores
escriben en zonas distintas. No hay problema de coherencia, pero puede haber de contención si hay datos en los mismos bloques
de memoria.
• Código secuencial:
Puede haber parte imposible
de paralelizar, como puede ser la I/O.
En el ejemplo la inicialización
de variables. Además, si los datos están inicialmente en un procesador y hay que difundirlos a todos los procesadores el coste es lineal.
• Tiempo de creación
de procesos:
El programa empieza a ejecutarse
con un proceso que pone en marcha a los demás.
El coste de creación de los
procesos puede ser importante si la granularidad de éstos es pequeña.
Causas de reducción de las prestaciones
• Computación extra:
Si se obtiene programa paralelo
a partir de secuencial, son necesarias computaciones adicionales por:
uso de variables de control,
comprobación de identificadores
de proceso,
cálculos adicionales o comunicaciones
para obtener datos
calculados por otro procesador,
...
• Comunicaciones:
En memoria distribuida, es
tiempo adicional al aritmético.
Pueden implicar trabajo de
procesadores intermedios.
• Tiempo de sincronización:
Cuando un proceso tiene que
esperar a que estén disponibles datos procesados por otro.
Conlleva comunicaciones en
memoria distribuida.
Causas de reducción de las prestaciones
• Desbalanceo de la
carga:
El volumen total de la computación
no se distribuye por igual entre todos los procesadores:
en el ejemplo, en el primer
paso trabajan todos pero en los pasos siguientes va disminuyendo el número de procesadores que trabajan, también es posible
que partamos de una entrada que no se puede balancear, por ejemplo si tenemos 12 datos para 8 procesadores, o que el volumen
de datos varíe a lo largo de la ejecución, con lo que se necesitaría balanceo dinámico.
Granularidad de la computación
• Uso de muchos procesadores
en la suma no es realista:
No dispondremos de tantos
procesadores.
Aunque dispongamos de ellos
hay caída de las prestaciones.
• La granularidad del
sistema (sistema físico+algoritmo) indica la cantidad de computación y datos asignados para la suma a
cada procesador:
Grano fino: si a cada procesador
se asignan pocos datos de los operandos o se realiza poca computación entre comunicaciones.
Grano grueso: si a cada procesador
se asignan muchos operandos y datos o se realiza mucha computación entre comunicaciones.
• Interesa programación
paralela cuando el paralelismo es de grano grueso.
Suma de n números con p procesadores
En cada Pi, i=0,1,...,p1
suma=0
para j=i*n/p, ...,(i+1)*n/p1
suma=suma+a[j]
finpara sincronización
a[i]=suma
inicio=i*2
desplazamiento=1
si i mod 2=0
activo=true
en otro caso
activo=false
finsi
para k=1,2,...,log p1
si activo
a[inicio]=a[inicio]+a[inicio+desplazamiento]
desplazamiento=desplazamiento*2
finsi
si i mod desplazamiento <>0
activo=false
finsi
finpara
Suma, en memoria distribuida
En cada Pi, i=0,1,...,p1
suma=0
para j=0, ...,n/p1
suma=suma+a[j] finpara
si i mod 2=0
recibir en b de i+1 activo=true
en otro caso
enviar suma a i1
activo=false
finsi
desplazamiento=2
para k=1,2,...,log p2
si activo
suma=suma+b
desplazamiento=desplazamiento*2
si i mod desplazamiento <>0
activo=false
enviar suma a idesplazamiento/2
en otro caso
recibir en b de i+desplazamiento/2
finsi
finsi
finpara
si i=0 suma=suma+b finsi
Suma de n números con p procesadores
• En memoria compartida
todas las variables son locales salvo el array a.
• En memoria distribuida
la sincronización por el paso de mensajes.
• El tamaño del problema
de los operandos o de datos (n)
es múltiplo del número de procesadores (p). Se puede generalizar fácilmente.
•
t(n,p)=2*n/p*tc+6*(log p1)*(
ts+tw)
si p<<<n podemos
tener en cuenta sólo los términos de
mayor orden y t(n)/t(n,p)=p, que es
lo mejor que se puede
obtener
para ir 10 veces más rápido:
con ts=2*tw
y
tw=2*tc,
si n=1000000, 100000, 10000,
p=10
con ts=10*tw
y
tw=10*tc, es n=330*p*log
p
si n=1000000 p=10, 100000
p=11, 10000 no posible
Speed-up
• Mide la ganancia de
velocidad que se obtiene con un
programa paralelo.
• Es el cociente entre
el tiempo secuencial y el paralelo:
S(n,p)=t(n)/t(n,p)
•
¿Qué t(n)?
El del mejor algoritmo secuencial que resuelve el
problema de la suma , pero
¿cuál es el “mejor algoritmo secuencial”? el que depende del tamaño de la entrada, distribución de los datos,
método de obtención del bit de acarreo, con complemento , uso de la máquina, ..., y puede no conocerse.
El del mejor algoritmo secuencial sobre suma conocido.
Pero depende de los mismos parámetros anteriores.
Tiempo de ejecución en un procesador del algoritmo
paralelo por propagación o
por generación . Pero puede que el mejor esquema para paralelizar no sea bueno en secuencial.
El tiempo de ejecución de un algoritmo secuencial para la suma “razonablemente
bueno” depende de muchos parámetros de los ya enunciados . Habrá que indicar cuál se usa.
Speed-up
• El speedup
será menor que el número de
procesadores
usado. Si no podría hacerse
un algoritmo secuencial mejor que el que se usa, simulando el algoritmo paralelo.
• En algunos casos puede
haber speedup
superlineal por mejor gestión
de la memoria al usar más procesadores.
• Para un tamaño de
problema fijo se aleja del valor óptimo al aumentar el número de procesadores.
• Para un número de
procesadores fijo aumenta al aumentar el tamaño del problema.
Speed-up, suma con n/2 procesadores
• En memoria compartida:
n/log n®¥
• En hipercubo, y malla
o anillo con comunicaciones
directas:
n/((1+ts+tw)*log
n)®¥
• En malla sin comunicaciones
directas:
n/(log
n+(ts+tw)*2*√n)®¥
• En anillo sin comunicaciones
directas y en red:
n/(log
n+(ts+tw)*n)®1/(ts+tw)
Eficiencia
• Da idea de la porción
de tiempo que los procesadores se
dedican a trabajo útil.
• Es el speedup
partido por el número de procesadores:
E(n,p)=S(n,p)/p=t(n)/(p*t(n,p))
• Valor entre 0 y 1.
• Para un tamaño de
problema fijo se aleja
del valor óptimo (1) al aumentar
el número
de procesadores.
• Para un número de
procesadores fijo aumenta al
aumentar el tamaño del problema.
Eficiencia, suma con n/2 procesadores
• En memoria compartida:
2/log n®0
• En hipercubo, y malla
o anillo con comunicaciones
directas:
2/((1+ts+tw)*log
n)®0
• En malla sin comunicaciones
directas:
2/(log n+(ts+tw)*2*√n)®0
• En anillo sin comunicaciones
directas y en red:
2/(log n+(ts+tw)*n)®0
Speed-up, suma con p procesadores
Con p fijo
• En memoria compartida:
n/(n/p+log p)®p
• En hipercubo, y malla
o anillo con comunicaciones
directas:
n/(n/p+(1+ts+tw)*log
p)®p
• En malla sin comunicaciones
directas:
n/(n/p+log
p+(ts+tw)*2*√p)®p
• En anillo sin comunicaciones
directas y en red:
n/(n/p+log
p+(ts+tw)*p)®p
Eficiencia, suma con p procesadores
Con p fijo
• En memoria compartida:
n/(n+p*log p)®1
• En hipercubo, y malla
o anillo con comunicaciones
directas:
n/(n+(1+ts+tw)*p*log
p)®1
• En malla sin comunicaciones
directas:
n/(n+p*log
p+(ts+tw)*2*p*√p)®1
• En anillo sin comunicaciones
directas y en red:
n/(n+p*log
p+(ts+tw)*p2)®1
Coste
• Representa el tiempo
(el trabajo) realizado por todo el
sistema en la resolución del
problema.
• Es el tiempo de ejecución
por el número de procesadores
usados:C(n,p)=p*t(n,p)
• En algoritmo óptimo
coincidiría con el tiempo secuencial, pero
en general es mayor.
• La diferencia se llama
función overhead:
to(n,p)=C(n,p)t(
n)=p*t(n,p)t(
n)
Es distinto de la idea de
overhead vista anteriormente y
difícilmente medible.
Distribución del trabajo en los procesos de
suma
• Es importante para
mejorar el balanceo.
• En memoria distribuida
puede reducir el coste de las
comunicaciones asignando datos
que se comunican
frecuentemente a procesadores
vecinos.
Evita comunicaciones, congestión
de la red y colisiones.
• En memoria compartida
puede influir en el coste de los accesos a memoria, si procesadores distintos acceden a bloques distintos. Normalmente que
los procesadores accedan a bloques de datos. Esto además mejora el uso de la jerarquía de memoria.
Escalabilidad
• Para un sistema paralelo interesa
que las prestaciones se sigan manteniendo en cierta medida al aumentar el tamaño de sistema.
• No se puede seguir
manteniendo las prestaciones manteniendo el tamaño del problema fijo y aumentando el número de procesadores.
• Se tratará de mantener
las prestaciones al aumentar el tamaño del sistema pero aumentando el tamaño del problema. Los sistemas (físicos o lógicos)
que cumplen esto se dicen escalables.
• La idea es, para un
determinado programa sobre sumatoria , ser capaces de determinar si en el futuro, cuando aumente el número de procesadores
y el tamaño de problemas que se quieren resolver,
se seguirán manteniendo las
prestaciones.
Función de isoeficiencia
• Da idea de cómo debe
crecer la entrada de los operandos de la suma del problema en función del número
de procesadores para mantener la
eficiencia constante.
to(n,p)=p*t(n,p)t(
n)
t(n,p)=(to(n,p)+t(n))/p
E(n,p)=t(n)/(to(n,p)+t(n))
t(n)=(E(n,p)/(1E(
n,p))*to(n,p)=K*to(n,p)
Para obtener cómo debe crecer
n
en
función de p para
mantener la eficiencia constante
basta comparar el tiempo
secuencial con la función
overhead del paralelo.
Isoeficiencia, suma con p procesadores
Sin constantes, pues interesa
la forma en que crece
• En memoria compartida,
hipercubo, y malla o anillo con
comunicaciones directas :
t(n)=n µ to(n,p)=n+p*log
p
Función de isoeficiencia:
p*log
p
• En malla sin comunicaciones
directas:
t(n)=n µ to(n,p)=n+p*log
p+p*√p
Función de isoeficiencia:
p1.5
(la
mayor)
• En anillo sin comunicaciones
directas y en red:
t(n)=n µ to(n,p)=n+p*log
p+ p2
Función de isoeficiencia:
p2
(la
mayor)
Isoeficiencia, suma con p procesadores
Para mantener las prestaciones
al variar de p1 a p2
procesadores, el tamaño debe
aumentar proporcional a
f(p2)/f(p1)
Todos escalables. Unos más
que otros.
En nuestro caso asumimos :
• Esquema del programa paralelo con bit de acarreo anterior:
Computación1. Carga de los
elementos en MEMORIA.
Se carga con ARRAY. ai, bi
o también
Comunicación1 (sincronización
PREPARATORIA para la carga en memoria compartida) Operando1, Operando2.
Computación 2 .Cargar un fichero
para formar bloques y calculo del tamaño de
los bloques
Comunicación 2 ( Mensajes
de Alertas sobre la carga de ficheros en bloque ) .
Computación3 Se hace una Distribución
de Difusión de Uno a todos .
Comunicación3( Mensajes de Alertas de Distribución ).
Computación4 En el caso de
que los bloques no tengan el mismo numero de elementos se enceran, se completan
y se calcula a partir del tamaño del Bloque.
Computación5. Se hace un Scan por bloque, para cada procesador.
Computación6. Scan con últimos
resultados del bloque.
Computación7. Con el resultado
parcial obtenido en cada procesador, se corrige los resultados parciales del
bloque y se obtienen los resultados exteriores del bloque.
Computacion8. Se calcula la suma dependiendo del CARRY del bit anterior a partir del SCAN DEL Pci y Gci EXTERIOR.
Computación9. Con los resultados
del G , P se hace el Scan en forma logarítmica.
MPI.
MPI_Scan( ) reducción
prefija (0,...,i-1 a i)
PROGRAMA
#include
<stdio.h>
#include <mpi.h>
#include <string.h>
int main(int argc, char *argv[])
{
int name, p, source, dest, tag = 0;
char message[n];
MPI_Status status;
MPI_Init(&argc,&argv);
MPI_Comm_rank(MPI_COMM_WORLD,&name);
MPI_Comm_size(MPI_COMM_WORLD,&p);
if (name != 0) {
printf("Processor %d of %d\n",name, p);
sprintf(message,"greetings from process %d!",
name);
dest = 0;
MPI_Send(message, strlen(message)+1,
MPI_CHAR, dest, tag,
MPI_COMM_WORLD);
} else {
printf("processor 0, p = %d ",p);
for(source=1; source < p; source++) {
MPI_Recv(message,100, MPI_CHAR, source,
tag, MPI_COMM_WORLD, &status);
printf("%s\n",message);
}
void Get_data(int my_rank,float *a_ptr,float *b_ptr,int *n_ptr)
{
int root=0;
int count=1;
if(my_rank==0)
{
printf("Enter a, b y n\n");
scanf("%f %f
%d",a_ptr,b_ptr,n_ptr);
};
MPI_Bcast(a_ptr,1,MPI_FLOAT,root,MPI_COMM_WORLD);
MPI_Bcast(b_ptr,1,MPI_FLOAT,root,MPI_COMM_WORLD);
MPI_Bcast(n_ptr,1,MPI_FLOAT,root,MPI_COMM_WORLD);
}
}
MPI_Finalize();
}
{
int rank, size;
Co=0;
Ci=gi;
gi=ai;
gi=ai and bi:
pi=ai or bi;
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
MPI_Comm_size(MPI_COMM_WORLD, &size);
For (i=1,n)
printf("SUMA CON BIT ANTERIOR %d DE ACARREO %d\n", rank, size);
printf("EDGAR GUERRA %d SALAZAR %d\n", rank, size);
MPI_Finalize();
return 0;
}
#include <mpi.h>
#include <stdio.h>
#include <stdlib.h>
#define WORLD MPI_COMM_WORLD
#define WORK_TYPE float
#define WORK_TYPE_FORMAT "%f\n"
#define MPI_WORK_TYPE MPI_FLOAT
#define BLOCK_LOW(id,n,p) (((id)*(n))/(p))
#define BLOCK_HIGH(id,n,p) (BLOCK_LOW((id)+1,n,p)-1)
#define BLOCK_SIZE(id,n,p) (BLOCK_LOW((id)+1,n,p)-BLOCK_LOW(id,n,p))
typedef struct {
WORK_TYPE mss;
WORK_TYPE mis;
WORK_TYPE mcs;
WORK_TYPE ts;
} cuaterna;
inline WORK_TYPE max (WORK_TYPE a, WORK_TYPE b) {
return ((a >= b) ? a : b);
}
inline void op_estrella (cuaterna*
result,
const cuaterna* opn1,
const cuaterna* opn2) {
result->mss = max(max(opn1->mss, opn2->mss), opn1->mcs
+ opn2->mis);
result->mis = max(opn1->mis, opn1->ts + opn2->mis);
result->mcs = max(opn1->mcs + opn2->ts, opn2->mcs);
result->ts = opn1->ts + opn2->ts;
}
void op_estrella_mpi_format (void* in,
void* inout,
int* dim,
MPI_Datatype* wt) {
int main(int argc,char* argv()){
MPI.Init(&argc, &argv);
MPI.Barrier(WORLD);
MPI.Comm_zise(WORLD,&p);
MPI.Comm.rank(WORLD,&id)
int j;
cuaterna* opn1 = (cuaterna*) in;
cuaterna* opn2 = (cuaterna*) inout;
for (j = *dim; j > 0; --j) {
op_estrella(opn2, opn1, opn2);
++opn1;
++opn2;
}
}
WORK_TYPE* carga (int* pn, const int argc, char* const argv[]) {
if (argc != 2) {
printf("Uso: %s <nombre de fichero>\n", argv[0]);
MPI_Type_struct(3,block_lenghts,displacements,typelist,message_type_ptr);
MPI_Type_commit(message_type_ptr);
}
void
Get_data(INDATA_TYPE *indata , int my_rank)
{
MPI_Datatype message_type;
int root=0;
int count=1;
if(my_rank==0)
{
printf("Enter gi, ci y n\n");
scanf("%f %f
%d",&(indata->a),&(indata->b),&(indata->n));
};
Build_derived_type(indata,&message_type);
MPI_Bcast(indata,count,message_type,root,MPI_COMM_WORLD);
}
int
MPI_Type_contiguous( int count,
MPI_Datatype oldtype,
MPI_Datatype *newtype)
}
int
MPI_Type_vector( int count,
int block_lenght,
int stride,
MPI_Datatype element_type,
MPI_Datatype *newtype)
}
int
MPI_Type_indexed( int count,
int *array_of_block_lengths,
int *array_of_displacements,
MPI_Datatype element_type,
MPI_Datatype *newtype)
}
MPI_Comm
my_row_comm;
int
my_row;
my_row=my_rank/q;
MPI_Comm_spli(MPI_COMM_WORLD,my_row,my_rank,&my_row_comm);
}
MPI_Datatype bloque;
……………..
MPI_Type_vector(4,4,10,MPI_FLOAT,&bloque);
MPI_Type_commit(&bloque);
If (myrank==0)
MPI_Send(&(A[0][2]),1,bloque,1,0,
MPI_COMM_WORLD);
else
MPI_Sendrecv(&(A[0][2]),1,bloque,
0, 0, MPI_COMM_WORLD,
&status);
}
MPI_Finalize();
exit(1);
}
else {
FILE* f;
if ((f = fopen(argv[1], "r")) == NULL) {
fprintf(stderr, "Programa %s: error al
intentar abrir el fichero %s\n",
argv[0], argv[1]);
fputs("Se aborta la ejecucion\n", stderr);
MPI_Abort(WORLD, 1);
exit(1);
}
else {
WORK_TYPE* datos;
WORK_TYPE x;
int n;
int j;
fscanf(f, "%i\n", &n);
if ((datos = (WORK_TYPE*) calloc(n,
sizeof(WORK_TYPE))) == NULL) {
fputs("Peticion de memoria para datos denegada\n",
stderr);
fputs("Se aborta la ejecucion\n", stderr);
fclose(f);
MPI_Abort(WORLD, 1);
exit(1);
}
for (j = 0; (fscanf(f, WORK_TYPE_FORMAT, &x)
!= EOF) && (j < n); ++j)
datos[j] = x;
if (j < n) {
fputs("Discrepancia en el cardinal de datos del fichero\n", stderr);
fputs("Se aborta la ejecucion\n", stderr);
fclose(f);
MPI_Abort(WORLD, 1);
exit(1);
}
fclose(f);
*pn = n;
return datos;
}
}
}
WORK_TYPE* distribucion (int* pbs, int id, int n, WORK_TYPE* datos) {
WORK_TYPE* bloque;
int* cnt;
int* dspl;
int block_size;
int p;
MPI_Comm_size(WORLD, &p);
if (id == 0) {
if ((cnt = (int*) calloc(p, sizeof(int))) ==
NULL) {
fputs("Peticion de memoria auxiliar denegada\n",
stderr);
fputs("Se aborta la ejecucion\n", stderr);
MPI_Abort(WORLD, 1);
exit(1);
}
if ((dspl = (int*) calloc(p, sizeof(int))) ==
NULL) {
fputs("Peticion de memoria auxiliar denegada\n",
stderr);
fputs("Se aborta la ejecucion\n", stderr);
MPI_Abort(WORLD, 1);
exit(1);
}
}
MPI_Bcast(&n, 1, MPI_INT, 0, WORLD);
block_size = BLOCK_SIZE(id,n,p);
printf("Proceso %d) tamano de bloque: %d\n", id, block_size);
fflush(stdout);
if ((bloque = (WORK_TYPE*) calloc(block_size, sizeof(WORK_TYPE)))
== NULL) {
fprintf(stderr, "Proceso %d: peticion de memoria denegada\n",
id);
fputs("Se aborta la ejecucion\n", stderr);
fflush(stderr);
MPI_Abort(WORLD, 1);
exit(1);
}
/* MPI_Gather(&block_size,
1, MPI_INT,
cnt, 1, MPI_INT,
0, WORLD); */
if (id == 0) {
int j;
cnt[0] = block_size;
dspl[0] = 0;
for (j = 1; j < p; ++j) {
dspl[j] = dspl[j - 1] + cnt[j - 1];
cnt[j] = BLOCK_SIZE(j,n,p);
}
/*
for (j = 0; j < p; ++j)
printf("%d\n", dspl[j]); */
}
MPI_Scatterv(datos, cnt, dspl, MPI_WORK_TYPE,
bloque, block_size, MPI_WORK_TYPE,
0, WORLD);
if (id == 0) {
free(datos);
free(dspl);
free(cnt);
}
*pbs = block_size;
return bloque;
}
cuaterna reduce_bloque (WORK_TYPE*
bloque, const int n) {
cuaterna acumulador;
int j;
acumulador.mss = bloque[0];
acumulador.mis = bloque[0];
acumulador.mcs = bloque[0];
acumulador.ts = bloque[0];
for (j = 1; j < n; ++j) {
cuaterna opn;
opn.mss = bloque[j];
opn.mis = bloque[j];
opn.mcs = bloque[j];
opn.ts = bloque[j];
op_estrella(&acumulador, &acumulador, &opn);
int.MPI.Scatterv(void*,intcnt,int*dspl,MPI.Datatype,//Envío
void*,int,MPI.Datatype,
int root,
MPI.Comm.)
}
return acumulador;
}
cuaterna reduce_global (cuaterna mss_local, const int root) {
MPI_Datatype ctype;
MPI_Op cop;
cuaterna mss_global;
MPI_Type_contiguous(4, MPI_WORK_TYPE, &ctype);
MPI_Type_commit(&ctype);
MPI_Op_create(op_estrella_mpi_format, 0, &cop);
MPI_Reduce(&mss_local, &mss_global, 1, ctype, cop,
root, WORLD);
MPI_Type_free(&ctype);
MPI_Op_free(&cop);
return mss_global;
}
WORK_TYPE reduccion (WORK_TYPE* bloque, const int n, const int root) {
cuaterna mss_local, mss_global;
mss_local = reduce_bloque(bloque, n);
mss_global = reduce_global(mss_local, root);
return mss_global.mss;
}
int main (int argc, char* argv[]) {
WORK_TYPE* datos;
WORK_TYPE* bloque;
WORK_TYPE mss;
double t_mss;
int id;
int block_size;
int n;
MPI_Init(&argc, &argv);
MPI_Comm_rank(WORLD, &id);
if (id == 0)
datos = carga(&n, argc, argv);
MPI_Barrier(WORLD);
t_mss = -MPI_Wtime();
MPI.Comm.size(WORLD,&P);
MPI.Comm.rank(World,&id);
bloque = distribucion(&block_size, id, n, datos);
mss = reduccion(bloque, block_size, 0);
free(bloque);
t_mss += MPI_Wtime();
MPI_Finalize();
if (id == 0) {
printf("Suma maxima de segmento: ");
printf(WORK_TYPE_FORMAT, mss);
printf("Tiempo total: %10.8f\n", t_mss);
n=ati(argv(1))-1;
}
return 0;
}