Baixe o app para aproveitar ainda mais
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!
Compartilhar