Transformações Unimodulares
Utilizaremos, de forma a otimizar o programa de entrada em nosso sistema uma classe de transformações conhecidas como transformações unimodulares, apresentamos a seguir as definições necessárias, e as transformações presentes nesta classe de transformacões.

Como base para nosso estudo de transformações unimodulares, tomamos o programa genérico, que contém K loops perfeitamente alinhados:

for(I1=n1;I1<=N1;I1++)
	for(I2=n2;I2<=N2;I2++)
		(.....)
			for(Ik=nk;Ik<=Nk;Ik++)
				{
				(Corpo do loop)
				}

Uma das formas de se transformar um conjunto de K loops perfeitamente alinhados é obter novas variáveis de loop a partir de combinações lineares das anteriores, tal transformação pode ser representada na forma de matriz. Por exemplo, tomando K loops, nas variáveis (I1,I2,...,IK) pode-se, multiplicando o vetor das variáveis de loop por uma matriz, obter-se novas variáveis (J1,J2,...,JK) de forma que:

J=I.M
Onde M é a matriz que representa a transformação aplicada ao conjunto de loops (I1,I2,...,IK), utilizamos matrizes apenas com elementos inteiros pois as variáveis de loop, supostamente, assumem apenas valores inteiros; portanto, utilizando uma matriz de transformação inteira, obtemos novas variáveis de loop que também assumem apenas valores inteiros.

Temos, porém, outro problema, no corpo do loop são referenciadas as variáveis (I1,I2,...,IK) devemos, portanto, alterar as referências as variáveis antigas, de forma a obter-se um programa com a mesma estrutura lógica, a princípio, tomando a transformação inversa, tem-se:

I=J.M-1
Porém, o problema não pode ser encarado de forma tão simples. A matriz inversa de uma matriz inteira não é necessariamente inteira, é razoavelmente intuitivo que, se det(M) for um inteiro diferente de zero a matriz M-1 é também uma matriz inteira, portanto para qualquer valores inteiros de (I1,I2,...,IK) aplicando-se a transformação M obtém-se um novo conjunto de variáveis (J1,J2,...,JK) também inteiros, e aplicando-se a transformação inversa, M-1 obteríamos novamente (I1,I2,...,IK) de forma a guiar as alterações necessárias no corpo do loop.

Embora não de forma tão explícita, assumimos também que o incremento dado a variável Ix para uma nova iteração do loop X é positivo e unitário, (pois qualquer loop com variável de loop inteira pode ser facilmente reduzido a esta forma) se tomarmos uma matriz M, apenas inteira, como matriz de transformação de nosso conjunto de loops, obteríamos um novo conjunto de loops perfeitamente alinhados cujo incremento não deve ser, necessariamente, unitário, como exemplo tomemos a seguinte transformação:


K=2

M=[ 2 0 ]
  [ 0 1 ]
Aplicada ao programa:


for(I1=1;I1<=10;I1++)
	for(I2=1;I2<=10;J1++)
		{
		(Corpo do loop)
		}
Que resulta no programa: 

for(J1=2;J1<=20;J1+=2)
	for (J2=1;J2<=10;J2++)
		{
		(Novo corpo do loop)
		}
Esta transformação, embora muito simples, esclarece porque é conveniente não tomar como matriz de transformação uma matriz apenas inteira, é possível provar que se tomarmos uma matriz inteira com determinante em módulo igual a um obtemos um programa transformado tal que o incremento necessário a cada variável, a cada nova iteração do seu respectivo loop é unitário.

Definição: Matrizes unimodulares são matrizes compostas apenas de elementos inteiros e cujo determinante tem módulo unitário.

Matrizes unimodulares podem representar transformações já bastante conhecidas, por exemplo a transformação "loop interchange" pode ser representada, no caso de apenas dois loops, pela matriz:


M=[ 0 1 ]
  [ 1 0 ]
No caso, as novas variáveis de loop são iguais as anteriores mas o loop mais externo do programa original torna-se o mais interno no programa transformado, e vice-versa. A matriz de transformação M é claramente unimodular.

Uma generalização da transformação "loop interchange" para K loops, conhecida como "loop permutation", que consiste em permutar a ordem de um número qualquer de loops perfeitamente alinhados dentre um conjunto de K loops, pode ser representada através de uma transformação unimodular. para obter a matriz que representa tal transformação basta permutar as linhas da matriz identidade Ik da mesma forma que se deseja permutar os loops, ou seja, se substituirmos a linha lx da matriz identidade pela linha ly, e vice-versa, estaremos representando a troca de posição entre o loop x e o loop y no conjunto de k loops. Repetindo este procedimento o número de vezes necessário, obtemos a matriz unimodular que representa a transformação "loop permutation" desejada.

Outra transformação que também pertence à classe de transformações unimodulares é a transformação "loop reversal". esta transformação consiste em inverter a ordem de execução das iterações de um dado loop x contido em um conjunto de k loops perfeitamente alinhados. Por exemplo tomemos a seguinte transformação:

K=2

M=[ -1 0 ]
  [  0 1 ]
Aplicada ao programa:


for(I1=1;I1<=10;I1++)
	for(I2=1;I2<=10;J1++)
		{
		(Corpo do loop)
		}
Que resulta no programa:


for(J1=-10;J1<=-1;J1++)
	for (J2=1;J2<=10;J2++)
		{
		(Novo corpo do loop)
		}
A transformação aplicada inverteu a ordem de execuções das iterações do loop externo, pois temos que I1=-J1.

Como terceira transformação presente nesta classe de transformações temos a transformação "inner-loop skewing" que consiste em se somar à variável de um loop mais interno uma constante multiplicada por uma variável de um loop mais interno, tal transformação não altera a ordem das iterações quando aplicada individualmente, mas é uma transformação interessante quando aplicada em conjunto com as anteriores. Uma matriz unimodular genérica que representa tal transformação é da forma:


M=[1 0 0 ... 0 ... 0 ... 0 ]
  [0 1 0 ... 0 ... 0 ... 0 ]
  [         (...)          ]
  [0 0 0 ... 1 ... 0 ... 0 ] (linha X)
  [         (...)          ]
  [0 0 0 ... 0 ... 0 ... 1 ]
               (coluna Y)
Esta transformação consiste em se somar a variável de loop Ix uma constante multiplicada pela variável de loop I(K-Y). A constante é chamada de "skewing factor".

É interessante limitar a classe de transformações unimodulares as três transformações anteriores pois é intuitivo que, para obter a matriz que representa uma seqüência qualquer de transformações de loops, basta multiplicar as matrizes de cada transformação individual, na mesma ordem com que foram executadas as transformações, e se cada transformação individual for unimodular, a transformação gerada pela composição das transformações executadas é também unimodular (det(A.B)=det(A).det(B), recursivamente aplicada). Outro ponto inportante é que, qualquer matriz unimodular pode ser obtida pelo produto das matrizes que representam as transformações "loop permutation", "loop reversal" e "inner-loop skewing" ou seja, qualquer transformação unimodular pode ser obtida pela aplicação sucessiva de transformações do tipo "loop permutation", "loop reversal" e "inner-loop skewing", pode-se portanto dizer que as transformações mencionadas anteriormente são as três únicas presentes na classe de transformações unimodulares pois todas as demais podem ser obtidas a partir destas.
Pedro Vaz Artigas
E-mail: artigas@lsi.usp.br

LSI Laboratory of Integrated Systems