Custo e Benefício de uma Janela de Referência

O custo de uma janela de referência associada à dependência x é definida como:

Cost(W(x)) = maxt |Wt(x)|

onde |Wt(x)| denota o número de elementos distintos de Wt(x).

O benefício Ben(W(x)) de uma janela de referência, associada à uma dependência x, é definida como número máximo de referências à dados realizados por S2 que podem ser executados da memória local ao invés da memória principal.

Janela Aproximada

Uma janela aproximada associada à janela de referência Wt(x) é uma dupla constituída de um mapeamento m de Zk em Zd e um subconjunto W de Zd tal que:

t, Wt=I(x) {X(J) | J m(I) + W}

O número de elementos de W é chamado de custo da janela aproximada (denotado Cost(W)).

A idéia de se formular a janela aproximada é que a janela fica enquadrada numa estrutura móvel com forma e tamanho constantes. Deste modo, simplifica-se bastante a avaliação do espaço de memória necessária para conter a janela. Então, o impacto da transformação de programa pode facilmente ser analizada, e a tarefa de selecionar a transformação mais apropriada se torna muito mais fácil.

Resultado

Nesta seção apresentaremos o resultado para o caso em que h: Zk -> Zd.

Teorema 3: Consideremos o seguinte aninhamento de k loops:

for (i1=1; i1<=N1; i1++)
  for (i2=1; i2<=N2; i2++)
            ...
        for (ik=1; ik<=Nk; ik++)
	   	... 
              a(i(1),i(2),...,i(k))
                ...

A função h é definida por h(i1,i2,...,ik) = (i(1),i(2),...,i(k))

Então, chega-se à seguinte aproximação, provada em [EISE90]:

Cost(W) =

É este o resultado que utilizaremos para quantificar a localidade de dados no estudo de caso descrito mais adiante.

Laboratory of Integrated Systems