Parte III
Usando o Pro64 para Pesquisa e
Desenvolvimento em Compiladores
Estudos de Caso
José Nelson Amaral
University of Alberta
Edmonton, AB, Canada
http://www.cs.ualberta.ca/~amaral
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
1
Conteúdo
Comentários Gerais
 Estudo de Caso I: Integração de um novo
algoritmo de reordenamento de instruções
para minimizar uso de registradores
[Govind,Yang,Amaral,Gao2000]
 Estudo de Caso II: Projeto e avaliação de
um algoritmo para prefetching de ponteiros
indutivos [Stouchinin,Douillet,Amaral,Gao2000]
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
2
Advançado
Para -O0
Adaptação do Pro64 para
um Novo Processador
Crie uma nova targ_info
Ajuste o arquivo de configuração
para a Application Binary Interface
(ABI)
Crie um novo WHIRL-to-CG-lower
para seleção de instruções
Ajuste funções de utilidade do CG
(p.e., predicação, padrões EBO,
Workshop em Sistemas
custos de
SWP,de etc.)
Computacionais
Alto
Desempenho, Setembro 2001
3
Caso I
Introdução do problema MRIS
problem e solução proposta
Formulação do problem
O algoritm proposto
Experiência com o Pro64
Onde começar?
Como começar?
Resultados
Resumo
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
4
Pesquisadores
R. Govindarajan (Indian Inst. Of Science)
Hongbo Yang (Univ. of Delaware)
Chihong Zhang (Conexant)
Jose Nelson Amaral (Univ. of Alberta)
Guang R. Gao (Univ. of Delaware)
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
5
Motivação
Processadores com o estilo da IA-64
Redução de spills na fase de alocação local de
registradores
Redução de pedidos do Alocador Local de
Registradores (LRA)
Redução da pressão por registradores em cada função
Processadores com Execução fora de ordem
Buffer reordenador de instruções
Renaming de registradores
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
6
Problema de Sequenciamento de
Instruções para Minimizar Uso de
Registradores (MRIS)
Dado um Grafo de Dependência de Dados G para
um bloco básico, encontre uma seqüência de
instruções S para G que é ótima no sentido de que
o uso de registradores seja mínimo.
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
7
Problema de Sequenciamento de
Instruções para Minimizar Uso de
Registradores (MRIS)
Dado um Grafo de Dependência de Dados G para
um bloco básico, encontre uma seqüência de
instruções S para G que é ótima no sentido de que
o uso de registradores seja mínimo.
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
8
Bloco Básico: Exemplo
begin
k := 10;
i := 1;
do begin
if(i=k)
y = (x+4)*(x*8)*((x-4)-x/2)
i = i +1
end
while i <= 20
end
…
Código Fonte
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
(11)
(12)
(13)
(12)
k := 10
i := 1;
if i  k goto (13)
t1 := ld(x);
t2 := t1 + 4;
t3 := t1 * 8;
t4 := t1 - 4;
t5 := t1 / 2;
t6 := t2 * t3;
t7 := t4 - t5;
t8 := t6 * t7;
st(y,t8);
i := i + 1;
if i  20 goto (3)
Código de Tres Endereços
9
Bloco Básico: Exemplo
B1
begin
k := 10;
i := 1;
do begin
if(i=k)
B2
(1) k := 10
(2) i := 1;
(3) if i  k goto (13)
B3
(4)
(5)
(6)
(7)
(8)
(9)
(10)
(11)
(12)
y = (x+4)*(x*8)*((x-4)-x/2)
i = i +1
end
while i <= 20
end
…
B4
Código Fonte
t1 := ld(x);
t2 := t1 + 4;
t3 := t1 * 8;
t4 := t1 - 4;
t5 := t1 / 2;
t6 := t2 * t3;
t7 := t4 - t5;
t8 := t6 * t7;
st(y,t8);
(13) i := i + 1;
(14) if i  20 goto (3)
Workshop em Sistemas
Computacionais de Alto B5
Desempenho, Setembro 2001 (15) ...
Grafo de 10
Fluxo
de Controle
Problema de Sequenciamento de
Instruções para Minimizar Uso de
Registradores (MRIS)
Dado um Grafo de Dependência de Dados G para
um bloco básico, encontre uma seqüência de
instruções S para G que é ótima no sentido de que
o uso de registradores seja mínimo.
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
11
Grafo de Dependência de
Dados
B3
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)
t1 := ld(x);
t2 := t1 + 4;
t3 := t1 * 8;
t4 := t1 - 4;
t5 := t1 / 2;
t6 := t2 * t3;
t7 := t4 - t5;
t8 := t6 * t7;
st(y,t8);
a
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
12
Grafo de Dependência de
Dados
B3
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)
t1 := ld(x);
t2 := t1 + 4;
t3 := t1 * 8;
t4 := t1 - 4;
t5 := t1 / 2;
t6 := t2 * t3;
t7 := t4 - t5;
t8 := t6 * t7;
st(y,t8);
a
b
c
d
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
e
13
Grafo de Dependência de
Dados
B3
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)
t1 := ld(x);
t2 := t1 + 4;
t3 := t1 * 8;
t4 := t1 - 4;
t5 := t1 / 2;
t6 := t2 * t3;
t7 := t4 - t5;
t8 := t6 * t7;
st(y,t8);
a
b
c
d
e
f
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
14
Grafo de Dependência de
Dados
B3
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)
t1 := ld(x);
t2 := t1 + 4;
t3 := t1 * 8;
t4 := t1 - 4;
t5 := t1 / 2;
t6 := t2 * t3;
t7 := t4 - t5;
t8 := t6 * t7;
st(y,t8);
a
b
c
d
f
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
e
g
15
Grafo de Dependência de
Dados
B3
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)
t1 := ld(x);
t2 := t1 + 4;
t3 := t1 * 8;
t4 := t1 - 4;
t5 := t1 / 2;
t6 := t2 * t3;
t7 := t4 - t5;
t8 := t6 * t7;
st(y,t8);
a
b
c
d
f
e
g
h
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
16
Grafo de Dependência de
Dados
B3
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)
t1 := ld(x);
t2 := t1 + 4;
t3 := t1 * 8;
t4 := t1 - 4;
t5 := t1 / 2;
t6 := t2 * t3;
t7 := t4 - t5;
t8 := t6 * t7;
st(y,t8);
a
b
c
d
f
e
g
h
i
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
17
Problema de Sequenciamento de
Instruções para Minimizar Uso de
Registradores (MRIS)
Dado um Grafo de Dependência de Dados G para
um bloco básico, encontre uma seqüência de
instruções S para G que é ótima no sentido de que
o uso de registradores seja mínimo.
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
18
Seqüência de Instruções
B3’
B3
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)
t1 := ld(x);
t2 := t1 + 4;
t3 := t1 * 8;
t4 := t1 - 4;
t5 := t1 / 2;
t6 := t2 * t3;
t7 := t4 - t5;
t8 := t6 * t7;
st(y,t8);
Seqüência 1
a
b
c
d
f
e
g
h
i
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
(a) t1 := ld(x);
(d) t4 := t1 - 4;
(e) t5 := t1 / 2;
(g) t7 := t4 - t5;
(b) t2 := t1 + 4;
(c) t3 := t1 * 8;
(f) t6 := t2 * t3;
(h) t8 := t6 * t7;
(i) st(y,t8);
Seqüência 2
B3’’
(a) t1 := ld(x);
(b) t2 := t1 + 4;
(c) t3 := t1 * 8;
(f) t6 := t2 * t3;
(d) t4 := t1 - 4;
(e) t5 := t1 / 2;
(g) t7 := t4 - t5;
(h) t8 := t6 * t7;
(i) st(y,t8);
19
Seqüência 3
Problema de Sequenciamento de
Instruções para Minimizar Uso de
Registradores (MRIS)
Dado um Grafo de Dependência de Dados G para
um bloco básico, encontre uma seqüência de
instruções S para G que é ótima no sentido de que
o uso de registradores seja mínimo.
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
20
Uso de Registradores
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)
t1 := ld(x); t1
t2 := t1 + 4;
t2
t3 := t1 * 8;
t3
t4 := t1 - 4;
t4
t5 := t1 / 2;
t5
t6 := t2 * t3;
t6
t7 := t4 - t5;
t7
t8 := t6 * t7;
t8
st(y,t8);
(a)
(d)
(e)
(g)
(c)
(b)
(f)
(h)
(i)
t1 := ld(x); t1
t4 := t1 - 4;
t4
t5 := t1 / 2;
t5
t7 := t4 - t5;
t7
t3 := t1 * 8;
t3
t2 := t1 + 4;
t2
t6 := t2 * t3;
t6
t8 := t6 * t7;
t8
st(y,t8);
Seqüência 1
Seqüência 2
Uso de Registradores = 4
Uso de Registradores = 3
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
21
Problema de Sequenciamento de
Instruções para Minimizar Uso de
Registradores (MRIS)
Dado um Grafo de Dependência de Dados G para
um bloco básico, encontre uma seqüência de
instruções S para G que é ótima no sentido de que
o uso de registradores seja mínimo.
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
22
Intuição para Nossa
Solução
Quais instruções podem/não podem
compartilhar registradores neste grafo?
a
b
c
d
f
e
Podemos usar o mesmo registrador
para os valores produzidos por b e f?
g
h
i
Grafo de Dependência
de Dados
Sim, em qualquer seqüência, b e f podem
compartilhar o mesmo registrador porque
f é o único uso do valor produzido por b.
e e g podem compartilhar registradores?
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
23
Intuição para Nossa
Solução
a
b
c
d
f
e
g
h
i
Grafo de Dependência
de Dados
E as instruções f e g?
f e g podem compartilhar
o mesmo registrador?
Não, não existe seqüência legal em
que f e g possam compartilhar
o mesmo registrador porque
h usa os valores de f e g
ao mesmo tempo.
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
24
Intuição para Nossa
Solução
a
b
c
d
f
e
E as instruções c e d podem
compartilhar o mesmo registrador?
g
h
i
Grafo de Dependência
de Dados
Depende da seqüência, para que c e d
possam compatilhar o mesmo registrador,
nós temos que ou escalar
f antes de d, ou g antes de c.
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
25
Intuição para Nossa
Solução
a
b
c
d
f
e
g
h
i
Nossa intuição é encontrar
subconjuntos de instruções que
podem definitivamente compartilhar
um registrador. Esta informação é
então usada para guiar o
algoritmo de geração de seqüências.
Grafo de Dependência
de Dados
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
26
Intuição para Nossa
Solução
a
b
c
d
f
e
g
h
i
Grafo de Dependência
de Dados
Uma lineagem de instruções é uma
seqüência de instruções em que um
único registrador é passado de uma
instrução a outra (exceto a última
instrução da lineage).
L1 = [a, b, f, h, i)
Como podemos assegurar que
as instruções a, b, f, e h poderão
compartilhar o mesmo registrador?
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
27
Arcos de Seqüenciamento
a
b
c
d
f
e
g
h
i
Grafo de Dependência
de Dados Aumentado
A formação de lineagens impõe uma
restrição no escalonamento do DDG:
o herdeiro escolhido de uma instrução
tem que ser a última instrução listada
entre sues irmãos.
L1 = [a, b, f, h, i)
Portanto, a formação de lineagens
insere arcos de seqüenciamento
no DDG.
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
28
Altura de uma Instrução
L1 = [a, b, f, h, i)
a
b
c
d
f
e
g
h
i
Grafo de Dependência
de Dados Aumentado
Se um arco de seqüenciamento
produzisse um ciclo no DDG,
seria impossível encontrar uma
seqüência legal de instruções.
Portanto nós usamos a altura da
instrução, recomputada após cada
formação de lineagem, para selecionar
o herdeiro. Desempates são arbitrários.
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
29
Formação de Lineagens
a
b
c
d
f
e
g
h
i
Grafo de Dependência
de Dados Aumentado
L1 = [a, b, f, h, i)
Para a próxima lineagem, as
instruções mais altas que ainda não
estão em lineagem são: c, d, e,
todas com uma altura de 5.
L2 = [c, f)
L3 = [e, g, h)
L4 = [d, g)
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
30
Interferência Entre
Lineagens
a
b
c
d
f
e
L1 = [a, b, f, h, i)
L2 = [c, f)
L3 = [e, g, h)
L4 = [d, g)
g
h
i
Grafo de Dependência
de Dados Aumentado
Duas lineagens Lu = [u1, u2, …, um) e
Lv = [v1, v2, …, vm) definitivamente interferem se:
(i) u1 alcança vn, e
(ii) v1 alcança um.
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
31
Grafo de Interferência de
Lineagens
a
b
c
d
f
e
g
h
L1 = [a, b, f, h, i)
L2 = [c, f)
L3 = [e, g, h)
L4 = [d, g)
Quais lineagens definitivamente
interferem entre si?
L1
L4
L2
L3
i
Grafo de Dependência
de Dados Aumentado
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
32
Grafo de Interferência de
Lineagens
a
b
c
d
f
e
g
h
L1 = [a, b, f, h, i)
L2 = [c, f)
L3 = [e, g, h)
L4 = [d, g)
Quais lineagens definitivamente
interferem entre si?
L1
L4
L2
L3
i
Grafo de Dependência
de Dados Aumentado
Workshop em Sistemas
Grafo de Interferência
Computacionais de Alto
Desempenho, Setembro 2001
de Lineagens
33
Grafo de Interferência de
Lineagens
L1 = [a, b, f, h, i)
L2 = [c, f)
L3 = [e, g, h)
L4 = [d, g)
a
b
L1
L4
h
L2
L3
Lineagens
Grafo de Interferência
de Lineagens
Com as restrições de escalonamento impostas
pela formação de lineagens, todas as instruções
de uma linagem podem compartilhar o mesmo
registrador.
i
Seria possível que múltiplas lineagens
compartilhassem of mesmo registrador?
c
d
f
e
g
Grafo de Dependência
de Dados Aumentado
Como podemos encontrar o número mínimo
de registradores
Workshop
em Sistemas se nós considerarmos todas
as seqüências
legais para o DDG aumentado?
Computacionais
de Alto
Desempenho, Setembro 2001
34
Grafo de Interferência de
Lineagens
L1 = [a, b, f, h, i)
L2 = [c, f)
L3 = [e, g, h)
L4 = [d, g)
a
Lineagens
b
c
d
f
e
g
h
L1
L4
L2
L3
Grafo de Interferência
de Lineagens
Nós podemos colorir of grafo de interferência de
lineagens para encontrar um Limite Heurístico
de Registradores (HRB) para o DDG.
i
Grafo de Dependência
de Dados Aumentado
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
35
Colorindo o Grafo de
Interferência de Lineagens
L1 = [a, b, f, h, i)
L2 = [c, f)
L3 = [e, g, h)
L4 = [d, g)
a
Lineagens
b
c
d
f
e
g
h
i
Grafo de Dependência
de Dados Aumentado
L1
L4
L2
L3
Grafo de Interferência
de Lineagens
Nós podemos colorir of grafo de interferência de
lineagens para encontrar um Limite Heurístico
de Registradores (HRB) para o DDG.
Nós conseguimos colorir o grafo com três cores,
portanto devemos encontrar uma seqüência de
instruções que usa três registradores.
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
36
Condição para Fusão de
Lineagens
L1 = [a, b, f, h, i)
L2 = [c, f)
L3 = [e, g, h)
L4 = [d, g)
a
Lineagens
b
c
d
f
e
g
h
L1
L4
L2
L3
Grafo de Interferência
de Lineagens
Duas lineagens
Lu = [u1, u2, …, um) e
Lv = [v1, v2, …, vn) podem ser fundidas
em uma única lineagem se:
i
Grafo de Dependência
de Dados Aumentado
(i) u1 alcança vn, e
(ii) v1 não alcança um.
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
37
Condição para Fusão de
Lineagens
L1 = [a, b, f, h, I)
L2 = [c, f)
L3 = [e, g, h)
L4 = [d, g)
a
Lineagens
b
c
d
f
e
g
h
L1
L4
L2
L3
Grafo de Interferência
de Lineagens
No exemplo, quais lineagens
podem ser fundidas?
d alcança f, e c não alcança g
i
Grafo de Dependência
de Dados Aumentado
Portanto L4 pode ser fundida com L2 para formar
L5 = [d, g)  [c, f)
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
38
Fusão de Lineagens
L1 = {a, b, f, h, i}
L2 = {c, f}
L3 = {e, g, h}
L4 = {d, g}
a
Lineagens
b
c
d
f
e
g
L1
L4
L2
L3
Grafo de Interferência
de Lineagens
Quando Lu = [u1, u2, …, um) e
Lv = [v1, v2, …, vn) são fundidas:
h
i
Grafo de Dependência
de Dados Aumentado
(1) um arco de seqüenciamento de um a v1
é introduzido no DDG aumentado
(2) Lu e Lv são removidos do LIG
(3) uma nova lineagem Lw = Lu  Lv
Workshop
em Sistemas
é inserida
no LIG
Computacionais de Alto
Desempenho, Setembro 2001
39
Fusão de Lineagens
L1 = [a, b, f, h, I)
L3 = [e, g, h)
L5 = [d, g)  [c, f)
a
Lineagens
b
c
d
f
e
g
h
i
Grafo de Dependência
de Dados Aumentado
L1
L5
L3
Grafo de Interferência
de Lineagens
Portanto a fusão de L4 com L2 resulta em
L5 = [d, g)  [c, f)
Quantas cores nós precisamos para
colorir o LIG?
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
40
Fusão de Lineagens
L1 = [a, b, f, h, I)
L3 = [e, g, h)
L5 = [d, g)  [c, f)
a
Lineagens
b
c
d
f
e
L1
L5
L3
Grafo de Interferência
de Lineagens
g
Nós ainda precisamos de três cores.
h
i
Grafo de Dependência
de Dados Aumentado
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
41
Sequenciamento Usando
Escalonamento de Lista
a
b
c
L1
d
f
e
g
L1 = [a, b, f, h, I)
L3 = [e, g, h)
L5 = [d, g)  [c, f) L5
Lineagens
L3
Grafo de Interferência
de Lineagens
RA
RB
RC
Registradores
h
i
Grafo de Dependência
de Dados Aumentado
Seqüência
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
42
Sequenciamento Usando
Escalonamento de Lista
a
b
c
L1
d
f
e
g
L1 = [a, b, f, h, I)
L3 = [e, g, h)
L5 = [d, g)  [c, f) L5
Lineagens
L3
Grafo de Interferência
de Lineagens
RA
RB
RC
Registradores
h
i
Grafo de Dependência
de Dados Aumentado
a
Seqüência
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
43
Sequenciamento Usando
Escalonamento de Lista
a
b
c
L1
d
f
e
g
L1 = [a, b, f, h, I)
L3 = [e, g, h)
L5 = [d, g)  [c, f) L5
L3
Grafo de Interferência
de Lineagens
Lineagens
RA
RB
RC
Registradores
h
i
Grafo de Dependência
de Dados Aumentado
a
d
Seqüência
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
44
Sequenciamento Usando
Escalonamento de Lista
a
b
c
L1
d
f
e
g
L1 = [a, b, f, h, I)
L3 = [e, g, h)
L5 = [d, g)  [c, f) L5
L3
Grafo de Interferência
de Lineagens
Lineagens
RA
RB
RC
Registradores
h
i
Grafo de Dependência
de Dados Aumentado
a
d
e
Seqüência
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
45
Sequenciamento Usando
Escalonamento de Lista
a
b
c
L1
d
f
e
g
L1 = [a, b, f, h, I)
L3 = [e, g, h)
L5 = [d, g)  [c, f) L5
L3
Grafo de Interferência
de Lineagens
Lineagens
RA
RB
RC
Registradores
h
i
Grafo de Dependência
de Dados Aumentado
a
d
e
g
Seqüência
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
46
Sequenciamento Usando
Escalonamento de Lista
a
b
c
L1
d
f
e
g
L1 = [a, b, f, h, I)
L3 = [e, g, h)
L5 = [d, g)  [c, f) L5
L3
Grafo de Interferência
de Lineagens
Lineagens
RA
RB
RC
Registradores
h
i
Grafo de Dependência
de Dados Aumentado
a
d
e
g
c
Seqüência
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
47
Sequenciamento Usando
Escalonamento de Lista
a
b
c
L1
d
f
e
g
L1 = [a, b, f, h, I)
L3 = [e, g, h)
L5 = [d, g)  [c, f) L5
L3
Grafo de Interferência
de Lineagens
Lineagens
RA
RB
RC
Registradores
h
i
Grafo de Dependência
de Dados Aumentado
a
d
e
g
c
b
Seqüência
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
48
Sequenciamento Usando
Escalonamento de Lista
a
b
c
L1
d
f
e
g
RA
RB
RC
L1 = [a, b, f, h, I)
L3 = [e, g, h)
L5 = [d, g)  [c, f) L5
Lineagens
L3
Grafo de Interferência
de Lineagens
Registradores
e
f
h
i
Grafo de Dependência
de Dados Aumentado
a
d
g
c
b
Seqüência
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
49
Sequenciamento Usando
Escalonamento de Lista
a
b
c
L1
d
f
e
g
RA
RB
RC
L1 = [a, b, f, h, I)
L3 = [e, g, h)
L5 = [d, g)  [c, f) L5
Lineagens
L3
Grafo de Interferência
de Lineagens
Registradores
e
f
h
i
Grafo de Dependência
de Dados Aumentado
a
d
g
c
b
h
Seqüência
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
50
Sequenciamento Usando
Escalonamento de Lista
a
b
c
L1
d
f
e
g
RA
RB
RC
L1 = [a, b, f, h, I)
L3 = [e, g, h)
L5 = [d, g)  [c, f) L5
Lineagens
L3
Grafo de Interferência
de Lineagens
Registradores
e
f
h
i
Grafo de Dependência
de Dados Aumentado
a
d
g
c
b
h
i
Seqüência
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
51
Sumário do Método de
Lineagens
 Um “bom” algoritmo
para construir o LIG
 Um método heurístico
efetivo para calcular
o HRB
 Um método efetivo
para escalonamento
(sem retentativas)
DDG
Grafo de Interfer. de Lineagens (LIG)
Derive HRB
Escalonamento por lista estendido
guiado por HRB
Uma boa seqüência
de instruções
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
52
Experiência
Implementando no Pro64
Projeto e Plano de Execução
Implementação
Depuração e validação
Avaliação
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
53
Implementation
Construção do Grafo de Dependências
Formação de Lineagens
Construção e coloração do LIG
Implementando o algoritmo de
reordenação
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
54
Porting Plan and Design
Entendendo a infra-estrutura do
compilador
Entendendo o modelo de registradores
(descrito nos arquivos targ_info)
p.e.:
classes de registradores: (int, float, predicate, app, control)
convenções para salvar/restaurar registradores: caller/callee
save, valor de retorno, passagem de argumentos, ponteiro
de pilha, etc.
etc.
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
55
Register Allocation
GRA
LRA:
Nível de bloco
Assign_Registers
Sucesso?
Falha?
Re-escalona
movimento local de código
spill registradores globais
spill registradores locais
Fix_LRA_Blues
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
56
Implementação
Construção do DDG: usa rotinas de
serviço nativas: e.g. CG_DEP_Compute_Graph
Colorindo o LIG: usa um pacote
nativo para manipulação de conjuntos
(e.g. bitset.c)
Implementação de Escalonamento:
usa suporte nativo para manipulação
de vetores (e.g. cg_vector.cxx)
Acesso aod grafo de dependências
usa funções nativas: ARC_succs, ARC_preds,
ARC_kind
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
57
Depuração e Validação
Trace file
tt54:0x1. General trace of LRA
tt45: 0x4. Dependence graph
building
tr53. TOP before LRA
tr54. TOP after LRA
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
58
Avaliação
Medidas Estáticas:
Fat point -tt54: 0x40
Medidas Dinâmicas
Hardware counter in R10k perfex
Workshop em Sistemas
Computacionais de Alto
Desempenho, Setembro 2001
59
Performance:
Static Measurements
Compiler Version
HRB
HRB(no fusion)
MIPSPro
Baseline
Benchmark Blocks Average Blocks Average Blocks Average Blocks Average
W/spill Spills W/spill Spills W/spill Spills W/spill Spills
Benchmarks with Low Register Pressure
24
2
27
2
32.5
2
49.5
2
tomcatv
6
1
7
6
4.7
7
3.7
9
swim
9.1
28
10.2
29
9.2
31
11.2
42
su2cor
4.7
3
3.8
5
2.3
13
3.1
20
hydro2d
2.7
3
6.8
4
8.3
3
7.2
5
mgrid
8.95
7.4
9.5
9.2
7.8
11.2
8.95
15.6
Average
Benchmarks with High Register Pressure
17.1
61
18.9
64
16.9
68
23.5
73
applu
11.3
23
11.8
24
10.4
34
13.8
39
turb3d
9.4
54
8.4
68
8.1
87
10.6
118
apsi
73.2
39
67.5
43
59.6
50
62.9
59
fpppp
9.3
62
8.5
79
11.7
111
9.3
146
wave5
21.9
47.8
20.3
55.6
18.5
70.0
8.95
87.0
Average
14 integer registers and 8 FP registers
Performance:
Static Measurements
Compiler Version
Benchmarks Baseline
MIPSPro
HRB(no fusion)
Spills Spills % reduc. Spills % reduc.
Benchmarks with Low Register Pressure
tomcatv
99
65
34.3
54
45.5
swim
33
33
0.18
42
-27.2
su2cor
469
286
39
295
37.1
hydro2d
61
30
50.8
19
68.9
mgrid
36
25
30.6
27
25
Average
140
87.8
37.1
87.4
37.4
Benchmarks with High Register Pressure
applu
1717
1148
33.2
1214
29.3
turb3d
534
355
34.1
284
47.3
apsi
1256
706
43.8
572
54.5
fpppp
3711
2980
19.7
2902
21.8
wave5
1352
1301
3.78
669
50.5
Average
1715
1298
24.3
1128
34.2
14
Workshop em Sistemas
integer
registersde
and
Computacionais
Alto8 FP
Desempenho, Setembro 2001
HRB
Spills % reduc.
48
6
255
14
8
66.2
51.5
81.8
45.6
77
77.8
52.6
1044
260
508
2853
575
1048
39.2
51.8
59.5
23.1
57.5
38.9
registers
61
Performance:
Dynamic Measurements
Compiler Version
Benchmarks Baseline
MIPSPro
HRB(no fusion)
HRB
Time
Time % reduc. Time % reduc. Time % reduc.
Benchmarks with Low Register Pressure
tomcatv
384
380
1.04
377
1.71
371
3.28
swim
319
316
0.78
312
2.21
308
3.52
su2cor
258
248
3.74
258
0.04
252
2.4
hydro2d
615
618
-0.54
620
-0.77
616
-0.11
mgrid
387
395
-2.26
391
-1.25
391
-1.23
Average
392.6 391.6
0.21
391.6
0.21
387.5
1.25
Benchmarks with High Register Pressure
applu
446
441
1.11
446
0.05
442
0.91
turb3d
508
496
2.32
461
9.12
453
10.8
apsi
276
278
-0.52
264
4.47
263
4.78
fpppp
505
471
6.63
463
8.2
465
7.87
wave5
224
220
1.42
216
3.32
218
2.64
Average
391.6 381.3
2.65
370.1
5.5
368.1
6.0
14
Workshop em Sistemas
integer
registersde
and
Computacionais
Alto8 FP
Desempenho, Setembro 2001
registers
62