fig 6.12

fig 6.24

fig 6.22

fig 6.31

fig 6.32

fig 6.34

sub $2, $1, $3

and $4, $2, $5

or $8, $2, $6

add $9, $4, $2

slt $1, $6, $7

fig 6.41

fig 6.42

fig 6.44

fig 6.47

fig 6.48

fig 6.50

fig 6.51

fig 6.53

fig pag 344

fig 6.55

Sugestão:

1.Analise o significado e consequência da não existência das unidades de forward e de hazard detection, bem como do facto de a operação dewrite back em registo ser efectuada na 1ª metade do ciclo, permitindo a leitura do conteúdo dos registos na 2ª metade; com base neste conhecimento, é possível calcular quantas instruções deverão estar entre 2 instruções com dependências críticas de dados (que no caso deste MIPS são as de RAW).

2. Analise o significado e consequência do pipeline stall em instruções de salto, i.e., da inserção de bolhas após a execução de qualquer instrução de salto (absoluto e relativo), logo após a sua descodificação; com base neste conhecimento, é possível calcular quantas bolhas são automaticamente inseridas por salto.

3. Considere uma cache "quente" aquela que já contém toda a informação que o programa necessita para a sua execução (neste caso o código do programa e a área dos dados); e se considerar ainda que ela tem dimensão infinita, então tem a certeza que toda essa informação coube na cache, e que nenhum acesso à cache de instruções ou de dados será penalizado no funcionamento do pipeline.

4. Conte agora o número de instruções x que são precisas executar para concluir o especificado.

6. Identifique todas as dependências de dados entre as instruções, e veja, instrução a instrução, quantas "bolhas" são inseridas, quer através da execução de nops gerados pelo compilador para resolução das dependências de dados, quer ainda inseridas pela unidade de controlo de saltos no hardware ; daqui pode contar e estimar o nº total de ciclos de clock para executar este programa; usando como nº total de instruções a ser executadas no processador o valor x calculado em 4. (que não é o correcto; porquê?), calcule agora o CPI efectivo.

b) Reordenando as instruções, reescreva o programa para minimizar o tempo de execução; calcule o tempo de execução do novo programa, em ciclos de clock. Compare com o valor obtido em a) e comente.

Sugestão: altere a ordem de execução de instruções de modo a remover ao máximo as dependências de dados; de notar que cada instrução que escreve num registo obriga à inserção de 2 nops caso a instrução que se lhe segue precise de ler o conteúdo desse registo; portanto, se se conseguir alterar a ordem de execução de instruções de modo a existirem 2 instruções sem dependência de dados após uma operação que escreve num registo, a utilização do pipeline é melhorada; apenas com a simples reordenação de instruções deve conseguir eliminar pelo menos 3 instruções de nop (com um truque adicional - e que não compromete evoluções da microarquitectura - poderá ainda eliminar mais um nop...).

c) Mostre o conteúdo do registo ID/Ex no início do 6º ciclo de clock.

Sugestão: identifique primeiro qual a instrução que no 5º ciclo se encontra no nível ID, sem se esquecer que na alínea anterior se conseguiu eliminar os nops no início do programa; agora consulte os apontamentos para construir essa instrução em binário e confirmar quais os sinais de controlo que a unidade de controlo gera nesse ciclo; o resto faz-se olhando apenas para a fig. 6.24.

d) Considere agora que o compilador usa a técnica de loop unroll (para além das melhorias introduzidas em b)). Use-a para processar 4 elementos de cada vez, e reescreva o código de modo a minimizar o tempo de execução. Calcule o tempo de execução do novo programa, em ciclos de clock. Compare com o valor obtido em b) e comente.

Sugestão:

1. A técnica de loop unroll serve essencialmente 2 objectivos: minimizar as penalizações resultantes das instruções de controlo de execução do ciclo,e espaçar mais as instruções que obrigam à inserção de "bolhas" no pipeline devido a dependências de dados.

2. Identifique as penalizações no funcionamento do pipeline resultantes das instruções de controlo de execução do ciclo (serão só as instruções de salto?...).

3. Reordene as instruções do novo corpo do ciclo - que processa agora 4x mais dados por cada iteração - usando, se necessário, mais registos (e verificando se dispõe do nº extra de registos que são precisos) e modificando eventualmente o próprio código do programa.

4. Use estas dicas na reescrita do código; se conseguir que cada instanciação do ciclo não tenha mais de 18 instruções úteis e 2 nops, então chegou a um resultado excelente!

e) Considere agora que a arquitectura possui forward unit e hazard detection unit. Modifique a solução obtida em b) e calcule o tempo de execução do novo programa, em ciclos de clock. Compare com os valores obtidos em b) e c) e comente.

f) Se o valor de CPI obtido nos programas resultantes da resolução de d) e de e) fossem iguais, que conclusões tiraria quanto ao desempenho do processador na execução deste programa? (Mesmo desempenho ou distinto, e porquê.)

Sugestão: lembre-se que a principal medida do desempenho do processador na execução deste programa é o tempo que ele necessita para o executar (em ciclos de clock), e um bom tempo não depende apenas de uma boa "máquina" - o processador - mas também de um bom "condutor" - o código gerado pelo compilador; com base nesta informação e na fórmula que nos relaciona o tempo de execução de um programa com os parâmetros da arquitectura, pode responder à questão...

g) Considere ainda a execução atrasada da instrução de salto, i.e., a arquitectura introduz um branch delay slot (para além dos melhoramentos já introduzidos na arquitectura em alíneas anteriores). Reescreva o código de modo a minimizar o tempo de execução e calcule esse tempo, em ciclos de clock. Compare com o valor mínimo obtido em a) e a melhor optimização que tinha conseguido em e), e comente.

Sugestão: por execução atrasada de uma instrução - de salto ou de load - entende-se que uma instrução só é efectivamente executada após a instrução que a segue; no caso da instrução de salto, isto significa que, quer o salto se concretize ou não, a instrução que se encontra na palavra seguinte da memória de instruções é sempre carregada e executada; como consequência para este processador, verifica-se que, em vez da arquitectura inserir 3 bolhas após a descodificação de um branch (ou 1 bolha após um jump), a unidade de controlo deixa executar a instrução que está imediatamente a seguir e apenas introduz 2 bolhas (no caso dum branch, e 0 no caso dum jump)

h) Considere ainda uma nova optimização da arquitectura relativamente a g): uma previsão estática de saltos - nunca salta. Reescreva o código de modo a minimizar o tempo de execução e calcule esse tempo, em ciclos de clock.

Sugestão: mesmo com branch delay slot cada instrução de salto condicional pode ainda desperdiçar 2 instruções (bolhas) quando a previsão estática falha; mas com saltos incondicionais isto já não acontece; estas dicas servem para alguma coisa?

i) Considere agora como alternativa a h) uma previsão dinâmica de saltos (com 1 bit): se da vez anterior saltou, também salta agora e para o mesmo endereço, se não saltou, também não salta. Reescreva o código de modo a minimizar o tempo de execução e calcule esse tempo, em ciclos de clock. Compare com o valor obtido em h) e comente.

j) Considere agora a versão optimizada do pipeline conforme descrita em h), mas com a seguinte hierarquia de memória: cache (I+D) de mapeamento directo, com 128 linhas de 4 palavras cada, com tempo de acesso à memória para leitura de 12 ciclos de clock, e com um barramento de 32 bits para aceder à memória. Considere ainda que a unidade de controlo está preparada para empatar o pipeline sempre que ocorre um miss, e que a estratégia de escrita na memória é de write back. Calcule o hit rate da cache e o novo valor do tempo de execução do programa proposto em h). Compare com o valor obtido em h) e comente.

Sugestão:

1. Leia com muita atenção este enunciado, e explicite todos os pressupostos que considere e que não tenham sido explicitados no enunciado, de preferência numa versão menos optimizada; por ex., considere que sempre que ocorrer um miss na leitura ou escrita, é preciso esperar que a linha toda seja lida da memória antes de o CPU poder aceder a uma palavra dessa linha .

2. Considere também que a linha da cache que está a substituir não precisa de ser escrita na memória, ou que, se precisar, não existe penalização temporal por tal.

3. Não se esqueça que cada vez que tem de ir à memória ir buscar uma linha da cache, isso é uma operação que contém 4 acessos à memória na arquitectura deste problema.

4. Faça um mapa da cache e verifique ainda em que linhas se encontram as instruções e os dados, uma vez que está a trabalhar com memória de mapeamento directo; isto não sugere nada?

5. No cálculo do hit rate não se esqueça de contabilizar todos os acessos à hierarquia de memória que o CPU tem de efectuar, quer para ir buscar as instruções, quer para ler ou escrever dados.

l) Apresente propostas distintas e complementares para: melhorar a latência, e a largura de banda no acesso à memória. Calcule, para a proposta com maior impacto no desempenho, o novo valor do tempo de execução do programa proposto em h). Compare com os valores obtidos em h) e j) e comente.