-
Notifications
You must be signed in to change notification settings - Fork 0
/
mestre_escravo_copia.c
266 lines (209 loc) · 8.19 KB
/
mestre_escravo_copia.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
#include <mpi.h>
#include <stdio.h>
#include <sys/time.h>
#include <time.h>
#include <stdlib.h>
#include <string.h>
void salva_txt(int *vetor_ordenado, int TAM);
void imprime_tempo(struct timeval ti, struct timeval tf);
void le_arquivo(int *vetor_lido,char arquivo_entrada[100],int TAM);
void merge(int array[], int begin, int mid, int end);
void ranksort(int *vetor_escravo, int *vetor_lido, int posicao_incial,int posicao_final);
int main(int argc, char **argv)
{
int TAM = atoi(argv[2]); // TAM será o tamanho de elementos a ordenar
//Validacao do numero de elementos a ordenar
if (TAM < 1)
{
printf("Erro: Numero de elementos tem que ser maior que 0 ou Argumento invalido \n");
return (1);
}
int size, rank, tag=0; // Variávis do MPI
struct timeval ti, tf; // Para imprimir tempo
int vetor_lido[TAM]; // Vetor que vai ser lido
int vetor_ordenado[TAM]; // Vetor que vai ser ordenado
int numero_escravos; // Numero de escravos
int numero_tarefas; // Numero de tarefas
int tamanho_tarefa; // Tamanho a ser ordenado por cada escravo
int posicao_inicial=0; // Inicio do pedaco a ser ordenado
int posicao_meio=0; // Posição do meio passada para a função merge
int posicao_final=0; // Fim do pedaco a ser ordenado
int cont=0; // Controle do vetor principal
int escravo; // rank recebido
int send=0; // Quantidade de vezes que foi enviado para escravo
int receive=0; // Quantidade de vezes que retornou para o mestre
int i, j; // Auxiliares para for
//Inicialização MPI
MPI_Status status;
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &rank); // Numero do processo.
MPI_Comm_size(MPI_COMM_WORLD, &size); // Numero total de processos(Processadores).
numero_escravos = size - 1;
numero_tarefas = 4*numero_escravos;
tamanho_tarefa = TAM / numero_tarefas; // Tamanho a ser ordenado para cada escravo (np-1)
int vetor_escravo[tamanho_tarefa]; // Vetor que vai ser recebido pelo mestre
if( ((TAM%tamanho_tarefa)!=0) || (TAM<numero_tarefas) ) //Validação se numero de elementos é divisivel com 4*numero_escravos
{
printf("Erro: Numero de elementos dividido por 4*numero_escravos nao inteiro \n");
return (1);
}
if (strlen(argv[1])>100)
{
printf("Erro: nome do arquivo de entrada maior que 100 caracteres \n");
return (1);
}
else
{
le_arquivo(vetor_lido,argv[1], TAM); // Recebe os valores do arquivo texto e armazena nos vetores
}
//Mestre
if (rank == 0)
{
gettimeofday(&ti, NULL); // Início da contagem do tempo
// Envia uma vez pra todos os escravos
for(escravo=1; escravo<=numero_escravos; escravo++)
{
posicao_inicial = (tamanho_tarefa * cont); //Início do pedaco do vetor
MPI_Send(&posicao_inicial, 1, MPI_INT, escravo, tag, MPI_COMM_WORLD); //Envia início do pedaco do vetor
cont++;
}
send=cont; // Guardando quantas tarefas foram enviadas
// Mestre recebe valores ordenados pelo escravo e os armazena no vetor_ordenado
while (numero_tarefas > 0)
{
//Receive
MPI_Recv(vetor_escravo, tamanho_tarefa, MPI_INT, MPI_ANY_SOURCE, tag, MPI_COMM_WORLD, &status); // Recebe vetor de um dos escravo enviou ordenado
escravo = status.MPI_SOURCE; // Identificador de que escravo ele recebeu
posicao_meio=receive*tamanho_tarefa; // Primeira posição do vetor recebido do escravo
receive++; // Acumulador número de tarefas finalizadas
// Recebe do escravo e coloca no vetor ordenado
for(i=0; i<tamanho_tarefa; i++)
{
vetor_ordenado[(posicao_meio+i)] = vetor_escravo[i];
}
if(receive>1)
merge(vetor_ordenado, 0, posicao_meio, (posicao_meio + tamanho_tarefa) ); //Compara resultado ordenado com o restante do vetor
//Verifica se já enviou todas as tarefas
if(send < numero_tarefas)
{
posicao_inicial = (tamanho_tarefa * cont); //Início do pedaco do vetor
MPI_Send(&posicao_inicial, 1, MPI_INT, escravo, tag, MPI_COMM_WORLD); //Envia início do pedaco do vetor
cont++;
}
numero_tarefas--; //Se chegar a zero para de receber
}
// Enviando valor -1 para todos os escravos para final
posicao_inicial = -1;
for (escravo=1; escravo<=numero_escravos; escravo++)
{
MPI_Send(&posicao_inicial, 1, MPI_INT, escravo, tag, MPI_COMM_WORLD);
}
gettimeofday(&tf, NULL); // Final da contagem do tempo
imprime_tempo(ti, tf); // Imprime tempo
salva_txt(vetor_ordenado, TAM); // Salva vetor ordenado em arquivo
}
else // Escravo
{
int terminou = 0; // Indica que programa terminou
int x=0; // variavel para o ranksort
// executa ainda enquanto o mestre não terminar
while (terminou==0)
{
MPI_Recv(&posicao_inicial, 1, MPI_INT, 0, tag, MPI_COMM_WORLD, &status); // Receber do mestre posição inicial do vetor lido à ordenar
if (posicao_inicial < 0) // Mestre terminou (escravo recebeu -1)
terminou = 1;
else // Ainda tem trabalho
{
posicao_final = posicao_inicial + tamanho_tarefa - 1; // Calcula a posição final pelo tamanho da tarefa
// Ordenação do vetor para cada número do intervalo pelo algoritimo Rank Sort
ranksort(vetor_escravo,vetor_lido,posicao_inicial,posicao_final);
MPI_Send(vetor_escravo, tamanho_tarefa, MPI_INT, 0, tag, MPI_COMM_WORLD); // Envia vetor escravo e seu tamanho
}
}
}
MPI_Finalize();
return 0;
}
//Funcao utilizada para a ordenacao dos vetores em cada escravo.
void ranksort(int *vetor_escravo, int *vetor_lido, int posicao_incial,int posicao_final)
{
int i,j,x;
for (i = posicao_incial; i <= posicao_final; i++)
{
x = 0;
for (j = posicao_incial; j <= posicao_final; j++) //Conta quantos números são menores que ele
if (vetor_lido[i] > vetor_lido[j])
x++;
vetor_escravo[x] = vetor_lido[i]; //Copia no lugar correto do pedaço enviado
}
}
void merge(int array[], int begin, int mid, int end)
{
int ib = begin;
int im = mid;
int j;
int size = end-begin;
int b[size];
// Enquanto existirem elementos na lista da esquerda ou direita
for (j = 0; j < (size); j++)
{
if (ib < mid && (im >= end || array[ib] <= array[im]))
{
b[j] = array[ib];
ib = ib + 1;
}
else
{
b[j] = array[im];
im = im + 1;
}
}
for (j=0, ib=begin; ib<end; j++, ib++) array[ib] = b[j];
}
void le_arquivo(int *vetor_lido,char arquivo_entrada[100],int TAM)
{
int i;
FILE *fp;
fp = fopen(arquivo_entrada, "r");
if(fp == NULL)
{
printf("Error ao tentar rquivo :%s",arquivo_entrada);
exit(EXIT_FAILURE);
}
for(i=0; i<TAM; i++)
{
vetor_lido[i] = 0;
fscanf(fp, "%d", &vetor_lido[i]);
}
fclose(fp);
}
void imprime_tempo(struct timeval ti, struct timeval tf) // rotina que calcula o tempo gasto
{
int secs, msecs, usecs;
msecs = (int) (tf.tv_usec-ti.tv_usec)/1000;
usecs = (int) (tf.tv_usec-ti.tv_usec)%1000;
secs = (int) (tf.tv_sec - ti.tv_sec);
if (msecs < 0)
{
secs--;
msecs = 1000+msecs;
}
if (usecs <0)
{
msecs--;
usecs = 1000+usecs;
}
printf("Tempo Gasto: %ds%dms%dus\n", secs, msecs, usecs);
}
void salva_txt(int *vetor_ordenado, int TAM) // utilizada para salvar o vetor ordenado
{
int i;
FILE *arq;
remove("SAIDA.txt"); // Remove arquivo antigo.
//Imprime novo arquivo
arq = fopen ("SAIDA.txt", "a+");
for (i = 0; i < TAM; i++)
fprintf(arq, "%d\n", vetor_ordenado[i]);
fflush(arq);
fclose(arq);
}