MAC 741 - Introdução a Algoritmos e Arquiteturas Paralelas
Lista de exercícios 4
(4 pontos)
Escreva um algoritmo paralelo para computar o OU lógico de
n bits armazenados num vetor B, dentro da memória global
de uma PRAM. Lembre que o OU lógico é 1 se pelo menos um
dos bits é 1; caso contrário ele vale zero.
Suponha que você tem n processadores disponíveis.
(a) considere um modelo com escrita exclusiva.
(b) considere um modelo com escrita concorrente.
(c) qual a complexidade de tempo nos dois casos.
(2 pontos)
Escreva um algoritmo paralelo para o mesmo problema acima, num
hipercubo de processadores.
(2 pontos)
Vimos a técnica de ``pointer jumping'' para resolver o problema
de soma prefixa numa árvore orientada com raiz. Use a mesma
idéia para resolver o seguinte problema: dada uma árvore orientada
com raiz, obter para cada vértice i um valor que indica a
sua distância da raiz, isto é, o número de arestas que o separa da
raiz.
(2 pontos)
Use a divisão-e-conquista para resolver o problema de
achar o máximo de n números.
Qual a sua complexidade paralela?
processadores.
que indica a
sua distância da raiz, isto é, o número de arestas que o separa da
raiz.