Exercícios 01 (Gabarito) PPD

Prévia do material em texto

Exercícios: 
1. Escreva um algoritmo paralelo no modelo CGM, com p processadores, para determinar o 
número de vezes que um inteiro x ocorre em um vetor A com n elementos. 
Entrada: o número do processador i; o número p de processadores; B = A((i-1)r+1:ir), r = n/p; 
o número inteiro x. 
Saída: Pi calcula z, onde z corresponde ao número de ocorrências de x em B, e envia z para P1; 
P1 calcula S = z1+...+zp. 
 
1) z  0; 
para j de 1 até r faça 
 se B[j] = x então 
 z  z + 1; 
 
2) se i ≠ 1 então 
send(z,P1); 
 senão 
para j de 2 até p faça 
receive(Z[j],Pj); 
 
3) se i = 1 então 
S  z; 
para j de 2 até p faça 
S  S + Z[j]; 
 
 
2. Escreva um algoritmo paralelo que encontre o maior e o menor valor de um conjunto S de n 
elementos no modelo CGM com p processadores. Cada processador deve conter n/p elementos 
de S. 
 
Entrada: o número do processador i; o número p de processadores; B = A((i-1)r+1:ir), r = n/p. 
Saída: Pi calcula x e y, onde x é o maior elemento de B e y o menor elemento de B, e envia x e 
y para P1; P1 calcula W e Z, onde W é o maior elemento X = (x1, ..., xp) e Z o menor elemento Y 
= (y1, ..., yp). 
 
1) x  B[1]; 
y  B[1]; 
para j de 2 até r faça 
 se B[j] > x então 
 x  B[j]; 
 senão 
 se B[j] < y então 
 y  B[j]; 
UEMS – UNIVERSIDADE ESTADUAL DE MATO GROSSO DO SUL 
Disc.: Programação Paralela e Distribuída 
Profº: Marcos Alves Mariano 
Curso: Ciência da Computação 
 
2) se i ≠ 1 então 
send(x, P1); 
send(y, P1); 
 senão 
 para j de 2 até p faça 
 receive(X[j], Pj); 
 receive(Y[j], Pj); 
 
3) se i = 1 então 
W  x; 
Z  y; 
para j de 2 até p faça 
 se X[j] > W então 
 W  X[j]; 
se Y[j] < Z então 
 Z  Y[j]; 
 
 
3. Desenvolva um algoritmo paralelo no modelo CGM, com p processadores, na qual determine o 
fatorial de um número n, onde n mod p = 0. 
Entrada: o número do processador i; o número p de processadores; o número n. 
Saída: Pi calcula x, onde x = (i-1)r+1* ... * ir, onde r = n/p, e envia x para P1; P1 calcula F = x1 * 
.... * xp. 
 
1) x  1; 
para j de (i-1)*r+1 até i*r faça 
x  x * j; 
 
2) se i ≠ 1 então 
send(x, P1); 
 senão 
 para j de 2 até p faça 
 receive(X[j], Pj); 
 
3) se i = 1 então 
F  x; 
para j de 2 até p faça 
 F  F * X[j];