MAC 741 - Introdução a Algoritmos e Arquiteturas Paralelas


Lista de exercícios 5

Considere o problema de avaliação (calcular o valor) de um polinômio P$(x)$, de grau $n$, nos pontos $x = x_0, x_1, \ldots, x_k$, com $k >> n$.

$$\mbox{P}(x) = c_0 x^n + c_1 x^{n-1} + \ldots + c_{n-1} x + c_n$$

Com base na fórmula equivalente (regra de Horner):

$$\mbox{P}(x) = ( \ldots (( c_0 x + c_1) x + \ldots + c_{n-1}) x + c_n$$

e usando a idéia de ``pipeline'' (linha de montagem), escreva um algoritmo paralelo para um anel de $n + 1$ processadores.

Para simplificar, suponha que o processador 0 do anel tenha também o papel de gerar os pontos $x$ e imprimir os resultados.