Definição: Dada uma iteração (I1,I2,...,IK) em que o corpo dos loops depende de uma iteração anterior (I1-V1,I2 -V2...,IK-VK) definimos o vetor de dependência (V1,V2...,VK).

Como uma dependência é sempre em relação a uma iteração anteriormente executada, as definições a seguir tornam-se claras:

Definição: Um vetor de dependência é dito positivo quando a sua primeira coordenada não nula é positiva.

Definição: Todo vetor de dependência deve ser positivo.

Notamos que, como uma dada coluna de um vetor de dependência representa uma dependência em relação a uma iteração ocorrida Vx iterações antes no loop com índice igual ao da respectiva coluna, nenhum vetor de dependência válido pode ser negativo, segundo a definição de vetor de dependência positivo dada acima, note que segundo a definição dada o vetor (1,-1) é positivo. Tal definição faz sentido pois todas as iterações de qualquer loop mais interno ocorrem dentro de uma única iteração de um loop mais externo, se o corpo do loop necessita de um valor calculado em uma iteração anterior de qualquer loop mais externo em relação a um dado loop mais interno ela, com certeza, já terá sido processada.

Como os vetores de dependência representam dependências no espaço vetorial das iterações dos loops, ao contrário dos mapeamentos , que relacionam dois espaços vetoriais, temos que:

Teorema: Aplicada uma transformação unimodular M a um conjunto de k loops perfeitamente alinhados, os novos vetores de dependência do programa transformado, que representam dependências entre iterações no corpo do loop, são obtidos pós-multiplicando os vetores do programa original pela matriz M. Uma dada transformação é válida se todos os vetores de dependência transformados continuam vetores válidos.

O teorema anterior é de fácil compreensão, pois uma transformação é válida se preserva a semântica do programa, e os vetores de dependência representam esta semântica, no sentido que: Se uma iteração depende de resultados obtidos em uma iteração anterior esta iteração deve, no programa transformado, ocorrer após a iteração da qual ela depende, isto só ocorre se o vetor de dependência que representa aquela dada dependência continuar positivo após a transformação. O próximo teorema tem implicações mais interessantes.

Teorema: Um dado loop x de um conjunto de k loops perfeitamente alinhados pode ser executado em paralelo se alguma das coordenadas anteriores a coordenada x de todos os vetores de dependência for positiva ou se a coordenada x for igual a zero.

Ou seja, se existe uma dependência ou ela já terá sido resolvida por ter sido calculada em iterações anteriores de qualquer loop mais externo, ou ela só existe entre iterações de loops mais internos, supostamente seriais.

Apresentamos, a seguir, um exemplo de transformação de programa válida que permite a obtenção de paralelismo.

Dado o programa, supondo a matriz Matriz declarada com as dimensões necessárias:

for (I1=0;I1<=10;I1++)
	for(I2=0;I2<=10;I2++)
		Matriz(I1,I2)=Matriz(I1-1,I2-1);

M=[  1 0 ]
  [ -1 1 ]

for (J1=-10;J1<=10;J1++)
	for(J2=Máx(-J1,0);J2<=Mín(10-K1,10);J2++)
		Matriz(J1+J2,J2)=Matriz(J1+J2-1,J2-1);

Laboratory of Integrated Systems