Bacharela

Programação Concorrente e Distribuída
Exercícios do livro – Capítulos 1 e 3

Capítulo 1
1.
my_sum = 0; my_first_i = my_p*(n/p); my_last_i = my_first_i + (n/p); for (my_i = my_first_i; my_i < my_last_i; my_i++) {
. . .

}
* my_p é a identificação do core.
2.
my_first_x = Compute_next_value(. . .); for (my_i = my_first_i; my_i < my_last_i; my_i++) { int *my_x = &my_first_x + my_i; my_sum += my_x;

}
3.
for (int i = 1; i < p; i*=2){ if (my_p % divisor == 0){ my_sum += receive_x_from(my_p + core_difference);
}
else { send_x_to(my_p + core_difference); break; } divisor*=2; core_difference*=2;
}

4. for (i = 1; i < p; i=i n, comm_sz, a, b, h
4.
if (my_rank == 0){ flag = 1; printf("Proc %d of %d > Does anyone have a toothpick?\n", my_rank, comm_sz);
MPI_Send(&flag, 1, MPI_INT, my_rank+1, 0, MPI_COMM_WORLD);
} else if (my_rank = comm_sz-1){
MPI_Recv(&flag, 1, MPI_INT, my_rank-1, 0, MPI_COMM_WORLD,
MPI_STATUS_IGNORE);
printf("Proc %d of %d > Does anyone have a toothpick?\n", my_rank, comm_sz);
} else {
MPI_Recv(&flag, 1, MPI_INT, my_rank-1, 0, MPI_COMM_WORLD,
MPI_STATUS_IGNORE);
printf("Proc %d of %d > Does anyone have a toothpick?\n", my_rank, comm_sz);
MPI_Send(&flag, 1, MPI_INT, my_rank+1, 0, MPI_COMM_WORLD);
}

5. Por indução:
1º - Para d=1 (altura da árvore), temos que n=2 (número de folhas).
Aplicando na fórmula: log2(2) = 1;
- Está correto, uma vez que é uma árvore de altura d=1 tem n=2 folhas. 2º - Assumindo que temos que log2(n) = d; se aumentarmos um nível na árvore, ou seja, fizermos d’ = d+1, temos que o número de nós agora será n’=2n, pois cada nó que antes era uma folha, agora terá duas folhas. Aplicando na equação acima: log2(n’) = d’ -> log2(2n) = d+1 -> log2(2) + log2(n) = d+1
1 + log2(n) = d+1 => log2(n) = d+1 -1 -> log2(n) = d

Está provado por indução que a altura (d) de qualquer folha de uma árvore binária completa é igual a log2(n), sendo n o número de folhas da árvore.
6.