Paralelismo no nível de laço e Reduções

Prévia do material em texto

Arquiteturas de Computadores
Fontes dos slides: Livro Patterson e Hennessy, Quantitative 
Approach
Paralelismo no nível de laço
Copyright © 2012, Elsevier Inc. All 
rights reserved.
Paralelismo no nível de laço
 Determinar se o acesso a dados em iterações posteriores 
depende dos valores de dados produzidos em iterações 
anteriores
 Dependência no laço 
 Exemplo 1:
for (i=999; i>=0; i=i-1)
x[i] = x[i] + s;
 Sem dependência no laço
Copyright © 2012, Elsevier Inc. All 
rights reserved.
Paralelismo no nível de laço
 Exemplo 2:
 S1 e S2 usam valores calculados por S1 na iteração 
anterior: dependência de laço
 S2 usa o valor calculado por S1 na mesma iteração: 
não é dependência de laço
Copyright © 2012, Elsevier Inc. All 
rights reserved.
Paralelismo no nível de laço
 Exemplo 3:
for (i=0; i<100; i=i+1) {
A[i] = A[i] + B[i]; /* S1 */
B[i+1] = C[i] + D[i]; /* S2 */
}
 S1 usa o valor calculado por S2 na iteração anterior, mas a dependência não é
circular, portanto, o laço é paralelo
 Transforme para:
A[0] = A[0] + B[0];
for (i=0; i<99; i=i+1) {
B[i+1] = C[i] + D[i];
A[i+1] = A[i+1] + B[i+1];
}
B[100] = C[99] + D[99];
Copyright © 2012, Elsevier Inc. All 
rights reserved.
Paralelismo no nível de laço
 Exemplo 4:
for (i=0;i<100;i=i+1) {
A[i] = B[i] + C[i];
D[i] = A[i] * E[i];
}
 Exemplo 5:
for (i=1;i<100;i=i+1) {
Y[i] = Y[i-1] + Y[i];
}
Copyright © 2012, Elsevier Inc. All 
rights reserved.
Encontrando dependências
 Suponha que os índices sejam afins:
 a x i + b (i um índice de laço)
 Assumir:
 Armazene em a x i + b, depois
 Carregue de c x i + d
 i varia de m para n
 Existe dependência se:
 Dado j, k tal que m ≤ j ≤ n, m ≤ k ≤ n
 Armazene em a x j + b, carregue de a x k + d e a
x j + b = c x k + d
Copyright © 2012, Elsevier Inc. All 
rights reserved.
Encontrando dependências
 Geralmente não pode ser determinada em tempo 
de compilação
 Teste para ausência de dependência: 
 Teste MDC:
 Se existe uma dependência, MDC(c,a) deve dividir
exatamente (d-b)
 Exemplo:
for (i=0; i<100; i=i+1) {
X[2*i+3] = X[2*i] * 5.0;
}
a=2, b=3, c=2, e d=0, então MDC(a,c)=2, e d−b=−3. Como
2 não divide −3, não é possível ter dependência.
Copyright © 2012, Elsevier Inc. All 
rights reserved.
Encontrando dependências
 Exemplo 2:
for (i=0; i<100; i=i+1) {
Y[i] = X[i] / c; /* S1 */
X[i] = X[i] + c; /* S2 */
Z[i] = Y[i] + c; /* S3 */
Y[i] = c - Y[i]; /* S4 */
}
 Dependências verdadeiras:
 S1 para S3 e S1 para S4 devido a Y[i], não é dependência de laço
 Anti-dependência:
 S1 para S2 devido a X[i] e S3 para S4 devido a Y[i]
 Dependência de saída:
 S1 para S4 baseado em Y[i]
Copyright © 2012, Elsevier Inc. All 
rights reserved.
Encontrando dependências
 Exemplo 2:
for (i=0; i<100; i=i+1) {
Y[i] = X[i] / c; /* S1 */
X[i] = X[i] + c; /* S2 */
Z[i] = Y[i] + c; /* S3 */
Y[i] = c - Y[i]; /* S4 */
}
Copyright © 2012, Elsevier Inc. All 
rights reserved.
Reduções
 Operação de redução:
for (i=9999; i>=0; i=i-1)
sum = sum + x[i] * y[i];
 Transforme para
for (i=9999; i>=0; i=i-1)
sum [i] = x[i] * y[i];
for (i=9999; i>=0; i=i-1)
finalsum = finalsum + sum[i];
 Execute em p processadores:
for (i=999; i>=0; i=i-1)
finalsum[p] = finalsum[p] + sum[i+1000*p];
 Nota: assuma associatividade!