CES-41
COMPILADORES
Capítulo Extra
Compiladores Paralelos
Capítulo Extra
Compiladores Paralelos
E.1 – Linguagens para processamento paralelo
E.2 – Componentes de um compilador paralelo
E.3 – Análise de dependências de dados
E.4 – O processo de paralelização de programas
E.1 – Linguagens para
processamento paralelo
E.1.1 - Conceito de processamento paralelo

Supercomputadores: computadores com milhares de
processadores e milhares de módulos de memória

Multiprocessamento: execução simultânea de vários
programas

Processamento paralelo: execução simultânea de vários
trechos de um mesmo programa
E.1.2 - Alternativas para linguagens

As linguagens utilizadas em processamento paralelo se
classificam em:
–
–
–

Linguagens paralelas
Linguagens convencionais ampliadas
Linguagens sequenciais
Linguagens paralelas e convencionais ampliadas:
–
–
–
Exigem recodificação de todos os programas sequenciais
de interesse, escritos até hoje
Há mais de 50 anos de programação sequencial
Obrigam muitos cientistas e pesquisadores a aprendê-las

Linguagens sequenciais: alternativa muito pesquisada na
programação de computadores paralelos:
–

Desobrigam do aprendizado de novas linguagens (inércia
dos cientistas e pesquisadores)
A utilização de linguagens sequenciais em máquinas paralelas
exigem do compilador a detecção automática de
paralelismo dos programas

Outras utilidades da detecção automática de paralelismo:
–
Em linguagens paralelas, para descobrir paralelismo não
explícito pelo programador
–
Quanto menor o nível de paralelismo, mais difícil
expressá-lo (iterações paralelas de laços, comandos
paralelos internos às iterações, paralelismo intracomandos)
–
Para adequar o paralelismo dos programas ao potencial
de paralelismo da máquina
E.1.3 - Paralelismo em programas sequenciais

Programas sequenciais apresentam muito paralelismo
implícito
–

Uma das maiores fontes de paralelismo é o laço
sequencial
Exemplos:
1)
C1:
C2:
for (i  1; i  5; i++) {
A[i]  B[i] + C[i];
D[i]  E[i] + F[i];
}
Todas as instâncias de C1 e de C2 podem ser executadas
simultaneamente
2)
C1:
C2:
for (i  1; i  5; i++) {
A[i]  B[i] + C[i];
D[i]  A[i] + E[i];
}
C1[1]
C1[2]
C1[3]
C1[4]
C1[5]
C2[1]
C2[2]
C2[3]
C2[4]
C2[5]
Todas as iterações podem ser executadas simultaneamente

Alguns laços não apresentam paralelismo

Exemplo:
C1:
C2:
for (i  1; i  5; i++) {
A[i]  B[i] + C[i];
B[i+1]  A[i] + D[i];
}
C1[1]
C1[2]
C1[3]
C1[4]
C1[5]
C2[1]
C2[2]
C2[3]
C2[4]
C2[5]
Há dependências intra e inter iterações
As iterações e os seus comandos internos são sequenciais

Há comandos a princípio sequenciais, mas que podem ser
transformados de forma a apresentar paralelismo

Exemplo: seja o seguinte laço:
C1:
C2:
for (i  1; i  5; i++) {
A[i]  B[i] + C[i];
D[i]  A[i] + A[i+1];
}
C1[1]
C1[2]
C1[3]
C1[4]
C1[5]
C2[1]
C2[2]
C2[3]
C2[4]
C2[5]
Há uma dependência de fluxo de C1[i] para C2[i] e uma
antidependência de C2[i] para C1[i+1]

Há comandos a princípio sequenciais, mas que podem ser
transformados de forma a apresentar paralelismo

Exemplo: seja o seguinte laço:
C1:
C2:
for (i  1; i  5; i++) {
A[i]  B[i] + C[i];
D[i]  A[i] + A[i+1];
}
C1[1]
C1[2]
C1[3]
C1[4]
C1[5]
C2[1]
C2[2]
C2[3]
C2[4]
C2[5]
Novamente as iterações e os comandos delas internos são
sequenciais
C1:
C2:
for (i  1; i  5; i++) {
A[i]  B[i] + C[i];
D[i]  A[i] + A[i+1];
}
No entanto, pode-se alterar o escopo do laço de forma a
introduzir nele paralelismo:
C2’:
C1:
C2:
for (i  1; i  5; i++) {
T[i]  A[i+1];
A[i]  B[i] + C[i];
D[i]  A[i] + T[i];
}
O laço pode ser decomposto em dois:
C2’:
C1:
C2:

for (i  1; i  5; i++)
T[i]  A[i+1];
for (i  1; i  5; i++) {
A[i]  B[i] + C[i];
D[i]  A[i] + T[i];
}
Em cada laço, todas as
iterações podem ser
executadas
simultaneamente
Assim, um compilador de uma linguagem sequencial para
processamento paralelo deve fazer:
–
Análise de dependências do programa fonte
–
Transformações no programa fonte, introduzindo-lhe
mais paralelismo
E.2 – Componentes de um
compilador paralelo

Grosso modo, um compilador paralelo de linguagens
sequenciais deve ter os seguintes componentes:
1. Analisador sintático e semântico, armazenando o
programa fonte numa estrutura adequada
2. Construtor do grafo de dependências do programa, fonte
de consultas para as transformações subsequentes
3. Eliminador de dependências e redutor de seus ciclos,
visando aumentar o potencial de paralelismo do programa
fonte
E.2 – Componentes de um
compilador paralelo

Grosso modo, um compilador paralelo de linguagens
sequenciais deve ter os seguintes componentes:
4. Reorganizador de laços, tornando-os tratáveis pelo passo 6
5. Alocador de memória, visando boa utilização de memória
local e global
6. Paralelizador propriamente dito, transformando os
comandos e laços sequenciais em equivalentes paralelos
7. Gerador de código intermediário e objeto
E.3 – Análise de Dependências de
Dados
E.3.1 – Tipos de dependências
a) Dependência de fluxo:

Um comando produz um valor e outro o utiliza

Exemplo:
C1:
C2:
A  B + C;
D  A + E;
Simbologia: a dependência é expressa por (C1 f C2)
b) Antidependência:

Um comando usa o valor de uma variável e outro o altera

Exemplo:
C1:
C2:
A  B + C;
B  D + E;
Simbologia: a dependência é expressa por (C1 a C2)
c) Dependência de saída:

Um comando produz um valor para uma variável e depois
outro lhe produz outro valor

Exemplo:
C1:
C2:
A  B + C;

A  D + E;
Simbologia: a dependência é expressa por (C1 s C2)
d) Dependência condicional:

O resultado da condição de um comando determina se
outro comando será ou não executado

Exemplo:
C1:
C2:
if (A < B)
C  D + E;
Simbologia: a dependência é expressa por (C1 c C2)
E.3.2 – Grafos de dependências

O conceito de dependência pode ser estendido para o
escopo de laços

Exemplo: um laço e a lista de suas dependências:
for (i  1; i  n; i++) {
C1:
a  X[i] + X[i-1];
C2:
Z[i]  a ** 2;
C3:
X[i]  X[i-1] + B[i];
}

Dependências:
(C1
(C1
(C1
(C2
(C3
(C3
s
f
a
a
f
f
C1)
C2)
C3)
C1)
C1)
C3)
Concebe-se o grafo de dependências: nível de comandos,
nível de instância e nível atômico
for (i  1; i  n; i++) {
C1:
a  X[i] + X[i-1];
C2:
Z[i]  a ** 2;
C3:
X[i]  X[i-1] + B[i];
}

Dependências:
(C1
(C1
(C1
(C2
(C3
(C3
s
f
a
a
f
f
C1)
C2)
C3)
C1)
C1)
C3)
Nível de comandos:
Todas as dependências
estão num só ciclo;
ciclos têm difícil solução
paralela
for (i  1; i  n; i++) {
C1:
a  X[i] + X[i-1];
C2:
Z[i]  a ** 2;
C3:
X[i]  X[i-1] + B[i];
}

Nível de instâncias:
Dependências:
(C1
(C1
(C1
(C2
(C3
(C3
s
f
a
a
f
f
C1)
C2)
C3)
C1)
C1)
C3)
for (i  1; i  n; i++) {
C1:
a  X[i] + X[i-1];
C2:
Z[i]  a ** 2;
C3:
X[i]  X[i-1] + B[i];
}

Nível atômico:
Mostra os elementos de
variáveis responsáveis
pelas dependências
Dependências:
(C1
(C1
(C1
(C2
(C3
(C3
s
f
a
a
f
f
C1)
C2)
C3)
C1)
C1)
C3)
E.3.3 – Definições para dependências

Existe uma dependência de dados (excluída a dependência
condicional) de um comando C1 para outro não
necessariamente distinto C2, simbolicamente (C1  C2), se e
somente se existirem instâncias C1’ e C2’ de C1 e C2 e uma
posição M de memória tais que:
1. C1’ e C2’ fazem referência a M e pelo menos uma dessas
referências é uma escrita
2. C1’ é executada antes de C2’
3. M não recebe escrita entre C1’ e C2’
1.
C1’ e C2’ fazem referência a M e pelo menos uma dessas
referências é uma escrita
2. C1’ é executada antes de C2’
3. M não recebe escrita entre C1’ e C2’





C1: fonte da dependência;
C1’: instância fonte
C2: destino da dependência; C2’: instância destino
Dependência de fluxo: C1’ é escrita e C2’ é leitura em M
Antidependência: C1’ é escrita e C2’ é leitura em M
Dependência de saída: C1’ e C2’ são escritas em M
Obs.: algumas referências bibliográficas incluem
o item 3 apenas para as dependências de fluxo
1.
C1’ e C2’ fazem referência a M e pelo menos uma dessas
referências é uma escrita
2. C1’ é executada antes de C2’
3. M não recebe escrita entre C1’ e C2’

Item 1: C1’ e C2’ fazem referência a M:
–
Para variáveis escalares é trivial: basta referenciarem a
mesma variável
–
Para variáveis indexadas não basta: é necessária uma
análise de seus subscritos
1.
C1’ e C2’ fazem referência a M e pelo menos uma dessas
referências é uma escrita
2. C1’ é executada antes de C2’
3. M não recebe escrita entre C1’ e C2’

Item 2: C1’ é executada antes de C2’; seja o seguinte laço:
C2:
C1:
for (j  1; j  n; j++) {
for (i  1; i  n; i++) {
D[i]  A ** 2;
A  E[i] + F[i];
}
A  B[j] + C[j];
}
A dependência
(C1 f C2) existe
Se o laço j não existisse
a dependência não
existiria
1.
C1’ e C2’ fazem referência a M e pelo menos uma dessas
referências é uma escrita
2. C1’ é executada antes de C2’
3. M não recebe escrita entre C1’ e C2’

Item 3: M não recebe escrita entre C1’ e C2’; seja o seguinte
laço:
C2:
C1:
C3:
}
for (i  1; i  n; i++) {
C[i]  A ** 2;
A  D[i] + E[i];
F[i]  A ** 3;
A  G[i] + H[i];
A dependência (C1 f C2)
não existe
Se o comando C3 fosse
condicional, a dependência
existiria

Dentro de laços, dependências têm direção e distância

Exemplos: sejam os seguintes laços:
1)
for (i  1; i  n; i++) {
A[i]  B[i] + 5;
C[i]  A[i] * 2;
}
A dependência (C1 f C2)
é interna à iteração i
for (i  1; i  n; i++) {
A[i]  B[i] + 5;
C[i]  A[i-3] * 2;
}
A dependência (C1 f C2)
vai da iteração i até a i+3
C1:
C2:
2)
C1:
C2:
Direção:
Distância:
Direção:
Distância:
‘=’
zero
‘<’
3

Dentro de laços, dependências têm direção e distância

Exemplos: sejam os seguintes laços:
3)
C1:
C2:
for (i  1; i  n; i++)
for (j  1; j  n; j++) {
A[i, j]  B[i, j] + C[i, j] ;
D[i, j]  A[i-2, j+1] + E[i, j];
}
A dependência (C1 f C2) vai da
iteração (i, j) até a (i+2, j-1)
Vetor-direção:
Vetor-distância:
(‘<’, ‘>’)
(2, -1)
E.3.4 – Detecção de dependências

A detecção de dependências entre variáveis escalares pode
utilizar análise de fluxo de dados aplicada em otimização
de código, na construção de compiladores

Entre variáveis indexadas, além disso, é necessária uma
análise dos subscritos dessas variáveis

Seja o aninhamento a seguir
for (I1  P1; I1  Q1; I1 ++) {
Laços de C1:
for (I2  P2; I2  Q2; I2 ++) {

I1, I2, ... , Id, Id+1, ... , Ie
for (Id  Pd; Id  Qd; Id ++) {
for (Id+1  Pd+1; Id+1  Qd+1; Id+1 ++) {
Laços de C2:

I1, I2, ... , Id, Ie+1, ... , In
for (Ie  Pe; Ie  Qe; Ie ++) {
C1:
. . . V[expr1,1, expr1,2, … , expr1,m,] . . .
A dependência (C1  C2)
}
existe se e somente se

existirem instâncias
}
for (Ie+1  Pe+1; Ie+1  Qe+1; Ie+1 ++) {
C1(i1, i2, ... , id, id+1, ... , ie) e

C2(j1, j2, ... , jd, je+1, ... , jn)
for (In  Pn; In  Qn; In ++) {
C2:
. . . V[expr2,1, expr2,2, … , expr2,m,] . . .
tais que:
}
1. k | (1  k  m), expr1,k = expr2,k

}
2. k | (1  k  n), Pk  ik, jk  Qk
}

3. A instância de C1 é executada antes da instância de C2
}
}
1.
k | (1  k  m), expr1,k = expr2,k
2.
k | (1  k  n), Pk  ik, jk  Qk
3.
A instância de C1 é executada antes da instância de C2
Item 1: sistema de m equações com as incógnitas:
i1, i2, ... , id, id+1, ... , ie, j1, j2, ... , jd, je+1, ... , jn
Item 2 e 3: inequações com as mesmas incógnitas

Se esse sistema de equações e inequações tiver solução, a
dependência existe; caso contrário, não existe

Quando esse sistema é linear a literatura apresenta vários
métodos de solução
E.4 – O Processo de Paralelização
E.4.1 – Um programa tipicamente sequencial

Seja o seguinte programa sequencial a ser paralelizado e seu
grafo de dependências:
for (i  1; i  100; i++)
for (j  1; j  100; j++) {
C1:
a  X[i, j] + X[i, j-1];
C2:
Z[i, j]  a ** 2;
C3:
X[i, j]  X[i, j-1] + B[j];
}
Todos os comandos e dependências
estão num só ciclo do grafo
Não é possível nenhuma paralelização
E.4.2 – Expansão de variáveis escalares
for (i  1; i  100; i++)
C1:
C2:
C3:

for (j  1; j  100; j++) {
a  X[i, j] + X[i, j-1];
Z[i, j]  a ** 2;
X[i, j]  X[i, j-1] + B[j];
}
A variável a é a causa das seguintes dependências: (C1 s
C1), (C1 f C2) e (C2 a C1)

Seu local é utilizado por todas a iterações

Substituindo-a dentro do aninhamento pela variável
indexada AA, cada iteração referencia um local diferente
for (i  1; i  100; i++)
C1:
C2:
C3:
for (j  1; j  100; j++) {
a  X[i, j] + X[i, j-1];
Z[i, j]  a ** 2;
X[i, j]  X[i, j-1] + B[j];
}
C1:
C2:
C3:
for (i  1; i  100; i++)
for (j  1; j  100; j++) {
AA[i,j]  X[i, j] + X[i, j-1];
Z[i, j]  AA[i,j] ** 2;
X[i, j]  X[i, j-1] + B[j];
}
a  AA[100, 100];
C4:

O comando C2 ficou fora do ciclo
E.4.3 – Reordenação de comandos de atribuição

Os comandos C2 e C3 podem trocar de posição:
for (i  1; i  100; i++)
C1:
C3:
C2:

for (j  1; j  100; j++) {
AA[i,j]  X[i, j] + X[i, j-1];
X[i, j]  X[i, j-1] + B[j];
Z[i, j]  AA[i,j] ** 2;
}
O comando C2 pode ser vetorizado
O comando C4 foi
omitido, mas será
reconsiderado no final
E.4.4 – Vetorização de laços

É a geração de comandos vetoriais
for (i  1; i  100; i++) {
C1:
C3:
C2:
}
for (j  1; j  100; j++) {
AA[i,j]  X[i, j] + X[i, j-1];
X[i, j]  X[i, j-1] + B[j];
}
Z[i, 1: 100]  AA[i, 1: 100] ** 2

Os elementos Z[i, 1], Z[i, 2], ... , Z[i, 100] podem ser
calculados simultaneamente

O ciclo (C1 C3) pode ser quebrado
E.4.5 – Fissão de comandos

Um ciclo contendo antidependências pode ser quebrado
com a introdução de variáveis temporárias
for (i  1; i  100; i++) {
for (j  1; j  100; j++) {
C1:
C3:
C2:
}
AA[i, j]  X[i, j] + X[i, j-1];
X[i, j]  X[i, j-1] + B[j];
}
Z[i, 1: 100]  AA[i, 1: 100] ** 2
E.4.5 – Fissão de comandos

Um ciclo contendo antidependências pode ser quebrado
com a introdução de variáveis temporárias
for (i  1; i  100; i++) {
C11:
C12:
C3:
C2:
}
for (j  1; j  100; j++) {
T[i, j]  X[i, j];
AA[i, j]  T[i, j] + X[i, j-1];
X[i, j]  X[i, j-1] + B[j];
}
Z[i, 1: 100]  AA[i, 1: 100] ** 2
E.4.5 – Fissão de comandos

E, para a vetorização de C11 e C12, é necessária nova
reordenação:
for (i  1; i  100; i++) {
C11:
C12:
C3:
C2:
}
for (j  1; j  100; j++) {
T[i, j]  X[i, j];
AA[i, j]  T[i, j] + X[i, j-1];
X[i, j]  X[i, j-1] + B[j];
}
Z[i, 1: 100]  AA[i, 1: 100] ** 2
E.4.5 – Fissão de comandos

E, para a vetorização de C11 e C12, é necessária nova
reordenação:
for (i  1; i  100; i++) {
C11:
C3:
C12:
C2:
}
for (j  1; j  100; j++) {
T[i, j]  X[i, j];
X[i, j]  X[i, j-1] + B[j];
AA[i, j]  T[i, j] + X[i, j-1];
}
Z[i, 1: 100]  AA[i, 1: 100] ** 2
E.4.5 – Fissão de comandos

E, para a vetorização de C11 e C12, é necessária nova
reordenação:
for (i  1; i  100; i++) {
C11:
C3:
C12:
C2:
}
T[i, 1: 100]  X[i, 1: 100];
for (j  1; j  100; j++)
X[i, j]  X[i, j-1] + B[j];
AA[i, 1: 100]  T[i, 1: 100] + X[i, 0: 99];
Z[i, 1: 100]  AA[i, 1: 100] ** 2
E.4.6 – Decomposição parcial de laços

Um laço contendo vários comandos em seu escopo pode ser
decomposto num conjunto de laços menores

Geralmente a paralelização de laços pequenos é mais simples
que a de laços grandes

Assim o laço do programa anterior pode ser decomposto
conforme o programa logo a seguir
E.4.6 – Decomposição parcial de laços
C11:
for (i  1; i  100; i++)
T[i, 1: 100]  X[i, 1: 100];
C3:
for (i  1; i  100; i++)
for (j  1; j  100; j++)
X[i, j]  X[i, j-1] + B[j];
C12:
C2:

for (i  1; i  100; i++) {
AA[i, 1: 100]  T[i, 1: 100] + X[i, 0: 99];
Z[i, 1: 100]  AA[i, 1: 100] ** 2;
}
Neste grafo de dependências, cada aninhamento tem seu
grafo particular
E.4.7 – Paralelização total das iterações dos laços

No programa anterior, os grafos do 1o e do 3o aninhamentos
não apresentam ciclos

No grafo do 2o aninhamento, a dependência é interna à
iteração do laço externo (=, <)

Todos esses laços podem ser transformados em comandos
DoAll, conforme o programa a seguir

Todas a iterações de um DoAll são executadas
simultaneamente
E.4.7 – Paralelização total das iterações dos laços
E.4.9 – Resultado da paralelização

Resumindo o que foi feito, o comando sequencial,
desprovido de paralelismo:
for (i  1; i  100; i++)
for (j  1; j  100; j++) {
C1:
a  X[i, j] + X[i, j-1];
C2:
Z[i, j]  a ** 2;
C3:
X[i, j]  X[i, j-1] + B[j];
}

Foi transformado no programa paralelo a seguir
DoAll i = 1, 100
T[i, 1: 100]  X[i, 1: 100];
EndDoAll
DoAll (i  1; i  100; i++)
for (j  1; j  100; j++)
X[i, j]  X[i, j-1] + B[j];
EndDoAll
DoAll i = 1, 100
AA[i, 1: 100]  T[i, 1: 100] + X[i, 0: 99];
Z[i, 1: 100]  AA[i, 1: 100] ** 2;
EndDoAll
a = AA[100, 100];
Suponha que este programa seja
executado numa máquina com 100
processadores e que cada um deles
seja um processador matricial de
100 processadores síncronos
Tal máquina tem na realidade o
equivalente a 10000 processadores
escalares
Suponha também, grosso modo,
que cada comando de atribuição
seja executado num tempo igual a
t unidades de tempo
DoAll i = 1, 100
T[i, 1: 100]  X[i, 1: 100];
EndDoAll
DoAll (i  1; i  100; i++)
for (j  1; j  100; j++)
X[i, j]  X[i, j-1] + B[j];
EndDoAll
DoAll i = 1, 100
AA[i, 1: 100]  T[i, 1: 100] + X[i, 0: 99];
Z[i, 1: 100]  AA[i, 1: 100] ** 2;
EndDoAll
a = AA[100, 100];
A seguinte tabela mostra o tempo
de execução do laço sequencial e
das várias tarefas do programa
paralelo
DoAll i = 1, 100
T[i, 1: 100]  X[i, 1: 100];
EndDoAll
DoAll (i  1; i  100; i++)
for (j  1; j  100; j++)
X[i, j]  X[i, j-1] + B[j];
EndDoAll
DoAll i = 1, 100
AA[i, 1: 100]  T[i, 1: 100] + X[i, 0: 99];
Z[i, 1: 100]  AA[i, 1: 100] ** 2;
EndDoAll
a = AA[100, 100];
A baixa eficiência se deve à tarefa
T2, que utiliza somente 100 dos
10000 processadores, deixando
ociosos os outros 9900.
Se o ganho de 300 for
imprescindível, não importa essa
baixa eficiência.
DoAll i = 1, 100
T[i, 1: 100]  X[i, 1: 100];
EndDoAll
DoAll (i  1; i  100; i++)
for (j  1; j  100; j++)
X[i, j]  X[i, j-1] + B[j];
EndDoAll
DoAll i = 1, 100
AA[i, 1: 100]  T[i, 1: 100] + X[i, 0: 99];
Z[i, 1: 100]  AA[i, 1: 100] ** 2;
EndDoAll
a = AA[100, 100];
Porém se essa eficiência de 3% for
inaceitável, pode-se usar uma
arquitetura em que os 100
processadores não sejam
matriciais
Assim a tabela dos tempos de
execução será a seguinte: