UNIVERSIDADE FEDERAL DE SANTA MARIA
CENTRO DE TÉCNOLOGIA
CURSO DE CIÊNCIA DA COMPUTAÇÃO
MPI - COMUNICAÇÃO COLETIVA
VERSUS PONTO-A-PONTO
Cristiano Reis dos Santos
2813230
Professora: Profª Andrea Schwertner Charão.
Disciplina: Programação Paralela.
1. Objetivo
O objetivo deste trabalho é implementar e comparar 2 programas equivalentes, um deles
utilizando comunicação ponto-a-ponto e outro utilizando comunicação coletiva.
2. Série de Taylor Para a Função Seno
A série de Taylor é uma fórmula que calcula o valor de uma função num ponto, x, a partir do
valor em outro ponto, a. A série, quando definida, transforma qualquer função numa soma de
polinómios. A série nem sempre converge. Aos valores de x para os quais há convergência
chama-se região de convergência.
−
= + !
Equação 1 – Série de Taylor para a função seno
3. Estratégia de Implementação
Os programas foram codificados em C++. Usou-se a série de Taylor para aproximar uma função
seno. Calcula-se o seno para o intervalo do ângulo de 1 a 180. Repete-se essa operação 250
vezes, para que se possa calcular o tempo de execução.
4. Versão Ponto-a-Ponto
A versão ponto a ponto foi desenvolvida utilizando o modelo mestre-escravo. Onde
o mestre apenas coordena a execução do programa e os escravos realizam toda a parte do
cálculo.
O mestre distribui o processamento da série de Taylor para a função seno entre os
processos, onde cada processo é responsável por avaliar um intervalo especifico do número de
termos e retornar o resultado ao mestre que soma todas as respostas recebidas gerando uma
aproximação para o ângulo calculado.
5. Versão Coletiva
A versão coletiva utilizou a primitiva de comunicação coletiva MPI_Reduce. Essa primitiva é
responsável por realizar uma operação pré-definida sobre dados localizados em todos os processos do
grupo e retorna o resultado desta operação em um único processo.
Na versão coletiva utilizando a primitiva MPI_Reduce o algoritmo implementado distribui para cada
processo um intervalo de termos que ele será responsável por calcular aquela parcela do valor final do
seno. A primitiva MPI_Reduce soma todas essas parcelas e gera o valor aproximado do seno para aquele
ângulo.
6. Análise
Para analisar as duas versões do programa foram definidos teste com 1,2, 5 e 8 processos para MPI
coletiva, e 2,5 e 8 processos. Onde o número de interações foi de 40, 80 e 120. Os gráficos abaixo
apresentam o valor do speedup, eficiência e tempo de execução. As visualizações da execução com a
ferramenta Jumpshot então disponibilizadas na pagina do trabalho para download.
Speedup
1.800
1.600
1.400
speedup
1.200
1.000
0.800
Coletiva - Reduce
0.600
Ponot-a-Ponto
0.400
0.200
0.000
1
2
5
Número de Threads
Figure 1 - Número de termos: 40
8
3.000
2.500
speedup
2.000
1.500
Coletiva - Reduce
Ponto-a-Ponto
1.000
0.500
0.000
1
2
5
8
Número de Threads
Figure 2 - Número de termos: 80
3.500
3.000
speedup
2.500
2.000
Coletiva - Reduce
1.500
Ponto-a-Ponto
1.000
0.500
0.000
1
2
5
Número de Threads
Figure 3 - Número de termos: 120
8
Eficiência
1.200
1.000
Eficiência
0.800
0.600
Coletiva - Reduce
Ponto-a-Ponto
0.400
0.200
0.000
1
2
5
8
Número de Threads
Figure 4 - Número de termos: 40
1.200
1.000
Eficiência
0.800
0.600
Coletiva - Reduce
Ponto-a-Ponto
0.400
0.200
0.000
1
2
5
Número de Threads
Figure 5- Número de termos: 80
8
1.200
1.000
Eficiência
0.800
0.600
Coletiva - Reduce
Ponto-a-Ponto
0.400
0.200
0.000
1
2
5
8
Número de Threads
Figure 6 - Número de termos: 120
Tempo de execução
5.000
4.500
4.000
Eficiência
3.500
3.000
2.500
Coletiva - Reduce
2.000
Ponto-a-Ponto
1.500
1.000
0.500
0.000
1
2
5
Número de Threads
Figure 7 - Número de termos: 40
8
4.000
3.500
Eficiência
3.000
2.500
2.000
Coletiva - Reduce
1.500
Ponto-a-Ponto
1.000
0.500
0.000
1
2
5
8
Número de Threads
Figure 8 - Número de termos: 80
8.000
7.000
Eficiência
6.000
5.000
4.000
Coletiva - Reduce
3.000
Ponto-a-Ponto
2.000
1.000
0.000
1
2
5
Número de Threads
Figure 9 - Número de termos: 120
8
7. Programas
a. Versão Ponto-a-Ponto – Mestre-Escravo
#include
#include
#include
#include
#include
static
static
static
static
static
<mpi.h>
<stdio.h>
<stdlib.h>
<iostream>
"util.h"
int MPI_MASTER = 0;
int MPI_KILL = -1;
int MAX_STEP = 500;
double PI = 3.141592654;
double MAX_ANGLE = 360;
double getValue(int id , int interaction , double angle){
double result = 0.0;
int number = 0;
angle = (angle*PI)/180;
for (int i = id*interaction ; i < (id*interaction + interaction) ; i++){
number = 2*i + 1;
double fatorial = 1.0f , expoente = 1.0f;
if((number == 0) || (number == 1))
fatorial = 1.0f;
for(int k = number ; k > 1 ; k--)
fatorial *= k;
for(int k = 0 ; k < number ; k++)
expoente *= angle;
if((i % 2) == 0)
result += ((expoente / fatorial));
else
result += (-1*((expoente / fatorial)));
}
return result;
}
int main (int argc, char *argv[]) {
int rank = 0 , numProcess = 0 , interaction = 0;
double value;
double startTime, endTime , diffTime;
if(argc == 2){
interaction = toInterger(argv[1]);
} else {
interaction = 150;
}
MPI_Status status;
MPI::Init(argc , argv);
MPI_Comm_rank(MPI_COMM_WORLD , &rank);
MPI_Comm_size(MPI_COMM_WORLD , &numProcess);
if(rank == MPI_MASTER)
startTime = MPI_Wtime();
int step = 0;
interaction /= (numProcess - 1);
while(step < MAX_STEP){
if (rank == MPI_MASTER) {
double angle = 1;
while(angle <= MAX_ANGLE){
for (int i = 1 ; i < numProcess ; i++){
MPI_Send(&i, 1 , MPI_INT, i , 0 , MPI_COMM_WORLD);
MPI_Send(&interaction , 1 , MPI_INT , i , 0 ,
MPI_COMM_WORLD);
MPI_Send(&angle, 1 , MPI_DOUBLE, i , 0 , MPI_COMM_WORLD);
}
double result = 0.0f , sineValue = 0.0f;
for (int i = 1 ; i < numProcess ; i++){
MPI_Recv(&result , 1 , MPI_DOUBLE , MPI_ANY_SOURCE ,
MPI_ANY_TAG , MPI_COMM_WORLD , &status);
sineValue += result;
}
if(angle == 270)
std::cout <<"Sine "<<angle<< " = " << sineValue << "."
<<std::endl;
angle++;
}
for (int i = 1 ; i < numProcess ; i++){
MPI_Send(&MPI_KILL, 1 , MPI_INT, i , 0 , MPI_COMM_WORLD);
}
} else {
int idProcess, interaction;
double angle;
while( true ){
MPI_Recv(&idProcess , 1, MPI_INT , MPI_MASTER , MPI_ANY_TAG ,
MPI_COMM_WORLD , &status);
if (idProcess == MPI_KILL) break;
MPI_Recv(&interaction , 1, MPI_INT , MPI_MASTER , MPI_ANY_TAG ,
MPI_COMM_WORLD , &status);
MPI_Recv(&angle , 1 , MPI_DOUBLE , MPI_MASTER , MPI_ANY_TAG ,
MPI_COMM_WORLD , &status);
double result = getValue(idProcess - 1 , interaction , angle);
MPI_Send(&result , 1 , MPI_DOUBLE , MPI_MASTER , 0 ,
MPI_COMM_WORLD);
}
}
step++;
}
if(rank == MPI_MASTER){
endTime = MPI_Wtime();
diffTime = (endTime - startTime);
std::cout << "Time " << diffTime <<std::endl;
}
std::cout << "FINALIZE." << std::endl;
MPI_Finalize();
}
b. Versão Coletiva – Primitiva Reduce
#include
#include
#include
#include
#include
static
static
static
static
<mpi.h>
<stdio.h>
<stdlib.h>
<iostream>
"util.h"
int MPI_MASTER = 0;
int MAX_STEP = 500;
double PI = 3.141592654;
double MAX_ANGLE = 360;
int main (int argc, char *argv[]) {
int rank = 0 , numProcess = 0 , interaction = 0 , number = 0;
double startTime, endTime , diffTime;
double sineValue = 0.0f , result = 0.0f;
if(argc == 2){
interaction = toInterger(argv[1]);
} else {
interaction = 10;
}
MPI_Status status;
MPI_Init(&argc , &argv);
MPI_Comm_rank(MPI_COMM_WORLD , &rank);
MPI_Comm_size(MPI_COMM_WORLD , &numProcess);
if(rank == MPI_MASTER)
startTime = MPI_Wtime();
int step = 0;
while(step < MAX_STEP){
double angle = 1;
while(angle <= MAX_ANGLE){
double angleEvaluate = (angle*PI)/180;
result = 0;
for (int i = rank*(interaction/numProcess) ; i < (
rank*(interaction/numProcess) + (interaction/numProcess)) ; i++){
number = 2*i + 1;
double fatorial = 1.0f , expoente = 1.0f;
if((number == 0) || (number == 1))
fatorial = 1.0f;
for(int k = number ; k > 1 ; k--)
fatorial *= k;
for(int k = 0 ; k < number ; k++)
expoente *= angleEvaluate;
if((i % 2) == 0)
result += ((expoente / fatorial));
else
result += (-1*((expoente / fatorial)));
}
MPI_Reduce(&result , &sineValue , 1 , MPI_DOUBLE , MPI_SUM ,
MPI_MASTER , MPI_COMM_WORLD);
if(rank == MPI_MASTER && angle == 270)
std::cout <<"Sine "<<angle<< " = " << sineValue << "."
<<std::endl;
angle++;
}
step++;
}
if(rank == MPI_MASTER){
endTime = MPI_Wtime();
diffTime = (endTime - startTime);
std::cout << "Time " << diffTime <<std::endl;
}
std::cout << "FINALIZE." << std::endl;
MPI_Finalize();
return 0;
}