Baixe o app para aproveitar ainda mais
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.
Compartilhar