Prova 2013.1 - P2

Prévia do material em texto

P2 - Arquiteturas Avançadas de Computadores
Professor: Leandro Marzulo
2013-1
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 e de desvio condicional (LW, SW, BEQ e BNE) 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 ADDI $S2, $S2, -4 SW $T0, 0($S2)
6 BNE $S2, $S3, LOOP
 
Outro escalonamento possível:
Ciclo Instruções s/ acesso a memória Instruções de acesso a memória
1 ADDI $S0, $S0, -4 LW $T0, 0($S0)
2 ADDI $S1, $S1, -4 LW $T1, 0($S1)
3
4 ADD $T0, $T0, $T1
5 ADDI $S2, $S2, -4 SW $T0, 0($S2)
6 BNE $S2, $S3, LOOP
 
Nos dois casos: IPC = 8/6 ≈ 1,33
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?
Além dos dois escalonamentos da letra a, este também seria possível (dentre outros):
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 SW $T0, 4($S2)
6 BNE $S2, $S3, LOOP
 
IPC = 8/6 = 1,33
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 SW $T2, 4($S2)
8 BNE $S2, $S3, LOOP
 
IPC = 12/8 ≈ 1,5
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) (3,0) Em linhas gerais, quais questões devem ser consideradas ao desenvolver um protocolo de coerência de cache? 
Nessa resposta, vamos considerar apenas os protocolos de snoopy, pois foram estes os exemplos vistos em sala 
de aula. Os protocolos baseados em diretório envolvem outras questões de projeto. Nos protocolos de snoopy, os 
processadores espiam um barramento comum para receberem informações sobre os eventos de cache ocorridos 
em processadores vizinhos e reagem a estes eventos para manter a coerência. As principais decisões de projeto 
des tipo de protocolos estão associadas ao uso de invalidações ou updates a ao uso de write-through ou write-
back. 
Em caches do tipo write-back blocos modificados só são copiados para a memória principal quando o bloco em 
questão for substituído na cache. Sendo assim, o bloco pode ser escrito diversas vezes pagando apenas o custo 
de acesso da cache e resultando em apenas um acesso a memória quando ocorrer a substituição. Por outro lado, 
essa escolha dificulta um pouco o protocolo de coerência, pois deve ser implementado um mecanismo para que 
os processadores vizinhos (que também possuam uma cópia do mesmo bloco) sejam informados da 
modificação. 
Quando um bloco é modificado, o processador que fez a modificação pode enviar o dado atualizado para todos 
os processadores que possuam uma cópia deste bloco. Embora esse processo beneficie os outros usuários do 
bloco, que terão pronto acesso a modificação, ele é extremamente ineficiente, pois muitos processadores podem 
possuir a cópia do bloco e não mais utilizá-la (a atualização é feita sem necessidade). A outra opção é enviar 
mensagens de invalidação dessas cópias. Quando os demais processadores voltarem a acessar o bloco, terão que 
buscá-lo na memória principal ou na cache do processador que fez a modificação.
3) (3,0) Quais as vantagens de se programar usando o modelo de memória compartilhada? Como é possível programar 
com este modelo em um cluster de computadores?
A programação com memória compartilhada assume que o sistema possui uma memória global que pode ser 
vista por todos os processadores. Sendo assim, a troca de informações é implícita através de leituras e escritas 
em posições compartilhadas. Obviamente, é necessário usar semáforos para garantir o compartilhamento 
correto. Clusters não possuem uma memória física compartilhada, mas esse efeito pode ser criado por um 
software DSM (Distributed Shared Memory). O DSM faz a trocade mensagens entre os nós do cluster para 
manter uma visão única das memórias fisicamente distribuídas. O preço é um custo de comunicação mais alto.