P2_2012.2 - Com gabarito

Prévia do material em texto

GABARITO
P2 - Arquiteturas Avançadas de Computadores
Professor: Leandro Marzulo
2012-2
Nome:
Instruções: Esta prova é composta de três questões totalizando 12 (doze) pontos, sendo a nota máxima 10 (dez). 
Responda as questões de forma sucinta e clara. O uso de lápis é permitido, no entanto, pedidos de revisão serão 
considerados apenas para questões respondidas a caneta. BOA PROVA!
1) (6,0) Considere o trecho de código abaixo que faz uma soma vetorial:
LOOP: LW $T0, 0($S0)
LW $T1, 0($S1)
ADD $T0, $T0, $T1
SW $T0, 0($S2)
ADDI $S0, $S0, -4
ADDI $S1, $S1, -4
ADDI $S2, $S2, -4
BNE $S2, $S3, LOOP
Este trecho será executado em um processador MIPS com despacho múltiplo estático que permite a execução em 
paralelo de instruções de acesso a memória (LW e SW) com as demais instruções. Considere que o processador 
implementa um pipeline de 5 estágios com forwarding e que não existe, no processador, a detecção de dependências 
entre instruções que executam em paralelo (como no exemplo do livro). Assuma também que a máquina em questão 
implementa um preditor de desvio perfeito (que sempre acerta o resultado da previsão, não resultando em flushes). 
Responda:
a) (1,5) Supondo que o compilador usado para escalonar o código consiga apenas reordenar instruções e 
identificar pares de instruções escalonáveis (independentes), mas não seja capaz de alterar instruções, 
escalone o código, de forma a obter o melhor desempenho possível neste cenário. Quantas instruções por ciclo 
serão entregues (IPC médio), desconsiderando os ciclos para encher o pipe?
Ciclo Instruções s/ acesso a memória Instruções de acesso a memória
1 LW $T0, 0($S0)
2 ADDI $S0, $S0, -4 LW $T1, 0($S1)
3 ADDI $S1, $S1, -4
4 ADD $T0, $T0, $T1
5 SW $T0, 0($S2)
6 ADDI $S2, $S2, -4
7 BNE $S2, $S3, LOOP
IPC = 8/7 ≈ 1,15
b) (1,5) Suponha agora que o compilador usado, além de reordenar e escalonar instruções, seja capaz de alterar 
instruções (modificar deslocamentos de acesso a memória e imediatos nas instruções ADDI). Qual é o 
escalonamento que proporciona o melhor desempenho? Quantas instruções por ciclo serão entregues (IPC 
médio), desconsiderando os ciclos para encher o pipe?
Ciclo Instruções s/ acesso a memória Instruções de acesso a memória
1 ADDI $S2, $S2, -4 LW $T0, 0($S0)
2 ADDI $S0, $S0, -4 LW $T1, 0($S1)
3 ADDI $S1, $S1, -4
4 ADD $T0, $T0, $T1
5 BNE $S2, $S3, LOOP SW $T0, 4($S2)
IPC = 8/5 = 1,6
c) (2,0) Desenrole o laço para dobrar o número de elementos processados por iteração. Considere que o número 
de iterações do laço original é múltiplo de 2. Mostre o código desenrolado, o melhor escalonamento 
(considerando o mesmo compilador do item b) e o IPC médio (desconsiderando os ciclos para encher o pipe).
LOOP: LW $T0, 0($S0)
LW $T1, 0($S1)
LW $T2, -4($S0)
LW $T3, -4($S1)
ADD $T0, $T0, $T1
ADD $T2, $T2, $T3
SW $T0, 0($S2)
SW $T2, -4($S2)
ADDI $S0, $S0, -8
ADDI $S1, $S1, -8
ADDI $S2, $S2, -8
BNE $S2, $S3, LOOP
Ciclo Instruções s/ acesso a memória Instruções de acesso a memória
1 ADDI $S2, $S2, -8 LW $T0, 0($S0)
2 ADDI $S0, $S0, -8 LW $T1, 0($S1)
3 ADDI $S1, $S1, -8 LW $T2, 4($S0)
4 ADD $T0, $T0, $T1 LW $T3, 4($S1)
5 SW $T0, 8($S2)
6 ADD $T2, $T2, $T3
7 BNE $S2, $S3, LOOP SW $T2, 4($S2)
IPC = 12/7 ≈ 1,71
d) (1,0) Descreva em linhas gerais o que precisaria ser feito caso o número de iterações do laço original não 
fosse múltiplo de 2 e você quisesse desenrolar o laço para dobrar o número de elementos processados por 
iteração.
Suponha um laço com X iterações. Se queremos desenrolar o laço D vezes, e X é múltiplo de D, basta construir 
um novo laço com X div D iterações, como feito no item "c" (a parte fracionária da divisão é descartada o 
número de iterações de um laço tem que ser inteiro) . Como o corpo do novo laço contém o equivalente a D 
iterações do laço original, o trabalho feito permanece o mesmo, pois X div D * D = X. Agora, se X não é 
múltiplo de D, tenho que fazer um laço com X div D iterações (desenrolado) e outro com X mod D iterações 
(sem desenrolar), pois X div D * D + X mod D = X.
Exemplo 1:
for (i=0; i<100; i++)
{
 A[i] = B[i] + C[i];
}
- Loop original com 100 iterações (X=100)
- Queremos desenrolar 4 vezes (D = 4)
Como 100 é múltiplo de 4, só preciso construir um loop desenrolado com 25 iterações:
for (i=0; i<100; i+=4)
{
 A[i] = B[i] + C[i];
 A[i+1] = B[i+1] + C[i+1];
 A[i+2] = B[i+2] + C[i+2];
 A[i+3] = B[i+3] + C[i+3];
}
Temos o mesmo número de operações que no loop original, pois 25*4=100.
Exemplo 2
for (i=0; i<99; i++)
{
 A[i] = B[i] + C[i];
}
- Loop original com 99 iterações (X=99)
- Quero desenrolar 4 vezes (D = 4)
Como 99 não é múltiplo de 4, só preciso construir um loop desenrolado com 24 iterações (99 div 4 = 24):
for (i=0; i<96; i+=4)
{
 A[i] = B[i] + C[i];
 A[i+1] = B[i+1] + C[i+1];
 A[i+2] = B[i+2] + C[i+2];
 A[i+3] = B[i+3] + C[i+3];
}
E um loop (com o mesmo corpo do original) com as 3 iterações restantes (99 mod 4 =3)
for (i=96; i<99; i++)
{
 A[i] = B[i] + C[i];
}
2) (2,0) O que é e para que serve um software DSM? Qual a principal vantagem de usar um sistema como este? E a 
principal desvantagem?
DSM significa Distributed Shared Memory (Memória Compartilhada Distribuída). É um sistema cria a 
abstração de uma memória única em um sistema com memória física distribuída (como um cluster). A 
vantagem é que este sistema permite o uso do modelo de programação com memória compartilhada e suas 
APIs de linguagem (pthread, openMP, etc). A desvantagem é o desempenho. Regiões grandes de memória 
compartilhada onde a troca de informações é frequente tendem a degradar o desempenho. Quando DSM não é 
usado, o programador precisa usar troca de mensagens explícita, o que permite identificar melhor os gargalos 
para otimizar esta troca de informações.
3) (4,0) Considere o problema da paralelização de aplicações usando um modelo híbrido com memória compartilha e 
passagem de mensagem em um grid composto 2 clusters (localizados em pontos geográficos distantes), sendo cada 
cluster composto por nós com 2 chips de processamento (em uma mesma placa mãe), cada chip com 6 cores que 
compartilham a cache L3 e cada par de cores compartilham a cache L2. Discuta a influência de cada item abaixo no 
desempenho da aplicação e no tipo de preocupação que o programador precisa ter ao desenvolver a aplicação:
a) (1,5) A hierarquia de memória e o bom uso da localidade.
O programador precisa saber que threads ou processos que compartilham dados com maior frequência devem 
estar associadas a núcleos de processamento que permitem esse compartilhamento em menor tempo. No 
exemplo dado, dois cores em um mesmo chip que compartilham a cache L2 resultam em uma troca de dados 
mais rápida. Cores que compartilham a L3 estão em segundo lugar, seguidos por cores em chips diferentes (que 
usam a memória principal). Cores em nós diferentes usarão a rede para compartilhamento. A aplicação deve 
ser construída para popular as caches de forma que a maior parte dos dados de um bloco sejam usado em um 
espaço curto de tempo, aproveitando a localidade espacial.
b) (1,5) A latência da rede.
Para cores localizados em máquinas diferentes, a troca de informações é feita pela rede. Quanto mais distante 
forem os nós, mais lenta será a troca de dados. Nós em um mesmo cluster tem custo de comunicação menor que 
nós em clusters diferentes. A latência da rede está relacionada com a distância entre os nós.
c) (1,0) A forma como os dados serão distribuídos para processamento e coletados para exibição de resultados 
finais (incluindo o processo de redução).
A distribuição dos dados influencia nos dois fatores anteriores. Além disso, os dados precisam ser distribuídos 
de forma a gerar uma carga de trabalho homogênea no sistema, ou seja,é desejável que nenhum processador 
fique ocioso enquanto outro processa uma tarefa maior. Um exemplo, dado em sala de aula, é o do somatório 
dos elementos de um vetor. Podemos dividir o vetor igualmente entre todos os cores do sistema e computar 
somas parciais. Se escolhermos um core como líder e este entregar uma mensagem para cada outro core, 
contendo os elementos do vetor a serem somados por cada um, o líder ficará sobrecarregado. Uma estratégia é 
usar uma hierarquia de líderes. Desta forma, no sistema do enunciado, um líder global divide a tarefa para um 
líder em cada cluster, que subdivide a tarefa para um líder em cada nó, que subdivide para um líder em cada 
chip, que subdivide para um líder em cada para de cores (que compartilham L2). O mesmo é feito na coleta de 
resultados, onde cada core passa seu resultado para o líder que delegou a tarefa. Assim, nenhum core ficará 
sobrecarregado com envio e recebimento de mensagens.