Como mencionado anteriormente, faremos o uso de transformações unimodulares. Esta classe de transformações provoca uma alteração na timing function T, que pode ser vista como uma forma diferente de proceder-se à varredura do espaço de iterações.

Com o intuito de facilitar a exposição de conceitos sobre a transformação, particularizaremos a análise para o caso das dependências que existem em um programa de multiplicação de matrizes, o qual será posteriormente objeto do exemplo de implementação do algoritmo completo proposto.

Dado a seguinte estrutura de loops:

for (i1=0; i1<N1; i1++)
  for (i2=0; i2<N2; i2++)
    for (i3=0;i3<N3; i3++)
      A[iA(1)][iA(2)]=A[iA(1)][iA(2)]+B[iB(1)][iB(2)]*C[iC(1)][iC(2)]

		hA(i1,i2,i3) = (iA(1), iA(2))
		hB(i1,i2,i3) = (iB(1), iB(2))
		hC(i1,i2,i3) = (iC(1), iC(2))

I' = I U

onde U é a matriz unimodular, I é o vetor com ordenamento original dos índices dos loops e I' é o vetor resultante da transformação aplicada.

Definamos a matriz de mapeamento M como:

h = I M

ou seja, a matriz M é aquela que multiplicada pelo vetor de índices fornece o vetor de mapeamento h.

O processo de transformação do ordenamento dos loops deve manter, contudo, o mapeamento em cada dependência, uma vez que é necessário a manutenção da semântica do programa. Assim, procedido à transformação, o mapeamento h calcula-se por:

h = I U U-1 M = I' M'

onde U-1 M = M' é a nova matriz de mapeamento.

Dispondo-se dessas definições podemos montar um algoritmo de otimização da localidade de dados, tendo como critério, a obtenção do menor custo da janela de referência:

Algoritmo: Otimização integrada de paralelismo e localidadade de dados

Entrada:

	número de loops K
	vetores de dependências D
	mapeamentos PI

{
/* determina o custo de cada uma das permutações permitidas dos loops */
for ( cada uma das permutações )
    if (transformação válida )
        determina custo em termos de acessos à memória
      else
        marca transformação com inválida
ordena as permutações válidas em ordem de custo
for ( cada uma das permutações )
    {
    obtém novos vetores de dependências
    if ( é possível paralelizar loop externo )
        break;   /* achou transformação adequada */
    }
if ( não é possível paralelizar loop externo )
    obtém transformação que paraleliza loop interno
obtém novos mapeamentos
re-otimiza loops internos em termos de memória
retorna versão do programa com o menor custo
}

Laboratory of Integrated Systems