Mais detalhes e exemplos de
arquitecturas com o Pipeline
Analisou-se já a arquitectura interna dum
CPU RISC - tomando como exemplo o MIPS - e respectivas implementações usando
apenas um ciclo de clock para a execução de cada instrução, ou em
ambiente multi-ciclo (resumo em 13.1). Introduz-se agora o ambiente encadeado
de execução de instruções (uma forma de paralelismo de execução, ao nível da
instrução: paralelismo temporal). Analisam-se em 13.2 as modificações a
introduzir ao nível do datapath e da unidade de controlo, com estudo
detalhado de um exemplo com uma sequência de instruções. Este assunto é tratado
com detalhe no texto de apoio (ver 6.3).
Qualquer arquitectura com pipeline
apresenta, no entanto, alguns problemas que podem ter resolução complexa,
nomeadamente para garantirem um funcionamento correcto na ocorrência de
inter-dependência entre instruções. Em 13.3 analisam-se os data hazards
resultantes da dependência de dados (leitura de registos após a sua escrita em
operações lógicas/aritméticas ou de acesso à memória), e as abordagens e
implementações para a sua resolução. Este assunto é tratado com detalhe no
texto de apoio (ver 6.4).
Em 13.4 analisam-se os control hazards
resultantes da dependência de controlo (em instruções de salto
condicional/incondicional, e em excepções/interrupções), e as abordagens e
implementações para a sua resolução. Este assunto é tratado com detalhe no
texto de apoio (ver 6.5 e 6.6).
Feito o estudo detalhado duma arquitectura
de processador com 5 níveis de pipeline, e respectivas técnicas de
implementação e melhoria da unidade de controlo para suporte a um determinado datapath
(que implementa um subconjunto de instruções do MIPS), a secção 13.5 destina-se
a apresentar um exemplo detalhado da execução dum programa, ciclo a ciclo do clock,
consoante se vão considerando as várias estratégias de optimização no pipeline,
e considerando ainda os conceitos adquiridos no Cap. 11 (organização de memória
e cache). Em resumo, o exemplo cobre a matéria exposta na bibliografia
de referência nos capítulos 6 e 7.
Em todos os capítulos apresentados até este
ponto, a ênfase no modelo de referência foi sempre colocada numa versão
simplificada dum processador comercial: a 1ª versão comercial do processador
MIPS, com a designação de MIPS R2000. Para fins pedagógicos - e para melhor se
entender muitos dos detalhes de implementação - optou-se ainda por uma versão
simplificada dessa mesma arquitectura. Esta abordagem permitiu, de certa
maneira, apresentar um modelo de referência para arquitecturas RISC que se
adapta à grande maioria das arquitecturas actualmente existentes. Contudo, o
tema da Arquitectura de Computadores não ficaria completo se não fosse feita
alguma referência a processadores reais disponíveis no mercado: os
processadores Alpha da Digital, Pentium da Intel, as novas linhas do MIPS, os
PowerPC da IBM/Motorola/Apple, os SPARC da Sun, ...
Uma mera apresentação descritiva de cada uma
das arquitecturas não iria certamente contribuir para a valorização/formação
científica e, pior ainda, arriscava-se a tornar-se obsoleta ainda antes da
conclusão da licenciatura por parte de cada uma dos potenciais interessados no
assunto. Como alternativa, a metodologia adoptada para introduzir a tecnologia
actual num contexto de auto-actualização foi a seguinte: identificar um
conjunto de itens que permitem caracterizar e comparar as arquitecturas de
processadores existentes ou em projecto, e apresentar alguns processadores à
luz desse mapa comparativo. É este o modelo proposto em 13.6, fechando assim o
capítulo.
Análise
dos níveis de pipeline num processador (MIPS)
Nota: datapath
equivalente ao da arquitectura de ciclo simples
1. Busca da
instrução e incremento do PC/IP IF
2.
Descodificação da instrução e selecção de registos ID
3. Execução:
operação aritmética/lógica ou cálculo do endereço de memória ou
teste de condição em instrução de salto Ex
4. Acesso à
memória Mem
5. Escrita de
resultado (da ALU ou da Mem) em
registo WB
| IF |
| ID |
| Ex |
| Mem |
| WB |
Exemplo de
sequência de instruções (fig.
lw $10, 9 ( $1 )
sub $11, $2, $3
1. Exemplo de
sequência de instruções
lw $10, 9 ( $1 )
sub $11, $2, $3
and $12, $4, $5
or $13, $6, $7
add $14, $8, $9
2. Análise
ciclo-a-ciclo (análise nível a nível
de pipeline ; preparação dos valores a carregar no registo de pipeline
no início do ciclo seguinte;
Ciclo 1: IF lw... Reg IF/ID: 32
(PC_lw+4) + 32 (<instr_lw>)
ID/Ex/Mem/WB ????
Ciclo 2: IF sub... Reg IF/ID: 32
(PC_sub+4) + 32 (<instr_sub>)
ID lw... Reg ID/Ex: 2 (WB; 11b) + 3 (Mem;
010b) +
4 (Ex; 0001b) + 32 (PC_lw+4) + 32 (<$1>) +
32 (<$10>) + 32 (Imm/rd; +9) + 5 (rt; 10)
Ex/Mem/WB ???
Ciclo 3: IF and... Reg IF/ID: 32
(PC_and+4) + 32 (<instr_and>)
ID sub... Reg ID/Ex: 2 (WB; 10b) + 3 (Mem;
000b) +
4 (Ex; 1100b) + 32
(PC_sub+4) + 32 (<$2>) +
32 (<$3>) +
32 (Imm/rd; 11) + 5 (rt; 3)
Ex lw... Reg Ex/Mem: 2 (WB; 11b) + 3 (Mem; 010b)
+
32 (PC_lw+4) + 1 (Zero; 0) + 32 (ALUresult;
<$1>+9) +
32 (<$10>) + 5 (rt; 10)
Mem/WB ??
Ciclo 4: IF or... Reg IF/ID: 32 (PC_or+4)
+ 32 (<instr_or>)
ID and... Reg ID/Ex: 2 (WB; 10b) + 3 (Mem;
000b) +
4 (Ex; 1100b) + 32 (PC_and+4) + 32 (<$4>) +
32 (<$5>) + 32 (Imm/rd; 12) + 5 (rt; 5)
Ex sub... Reg Ex/Mem: 2 (WB; 10b) + 3 (Mem; 000b)
+
32 (PC_sub+4) + 1
(Zero;0) +32 (ALUresult; <$2-$3>)+
32 (<$3>) +
5 (rt; 10)
Mem lw... Reg Mem/WB: 2 (WB; 11b) + 32
(Mem[<$1>+9]) + 32 (ALUresult; <$1>+9) + 5 (rt; 10)
WB ?
Ciclo 5: ...
Dependência
de dados numa arquitectura com pipeline (MIPS)
responsabilidade
do compilador garantir que não existem dependências
empatar
o funcionamento do pipeline (pipeline stall ) encaminhar o valor
para o nível seguinte (data forward)
Condições de
teste para detecção de data hazards
Ex-hazard:
RegIF/ID(ReadReg1 / 2) = RegID/Ex(rt
ou rd) Nota: para saber se rt ou rd usar RegDest
Mem-hazard:RegIF/ID(ReadReg1 / 2) = RegEx/Mem(WriteReg)
WB-hazard:RegIF/ID(ReadReg1 / 2) = RegMem/WB(WriteReg)
sub $2, $1, $3
and $4, $2, $5
or $8, $2, $6
add $9, $4, $2
slt $1, $6, $7
Data
forwarding nas instruções do
tipo-R
Acrescentando
uma unidade de forwarding
Condições de
teste para fazer data forwarding (instruções tipo-R)
Ex-hazard:
RegEx/Mem(RegWrite) = 1 e
RegID/Ex(ReadReg1 / 2) = RegEx/Mem(WriteReg) => ALUSelA / B =
01 Nota: RegID/Ex(ReadReg1 / 2) é novo
Mem-hazard:
RegMem/WB(RegWrite) = 1 e
RegID/Ex(ReadReg1 / 2) = RegMem/WB(WriteReg) => ALUSelA / B =
10
WB-hazard: não há, desde que a leitura do Reg se faça no mesmo
ciclo, após a escrita
Resolução de problemas em operações de acesso à
memória
não
é possível antes de Mem (instruções lw)
(instruções
lw)
Ex-hazard: RegID/Ex (RegWrite) = 1 e RegID/Ex
(RegDest) =
RegIF/ID(ReadReg1 / 2) = RegID/Ex(WriteReg)
=> stall
Dependência
de controlo numa arquitectura com pipeline (MIPS)
- saltos
condicionais
- saltos
incondicionais
1. Empatar o pipeline
(stall)
2. Previsão
estática: o salto não ocorre
Condições para
detectar que salta em beq:
[ RegEx/Mem(Branch) e RegEx/Mem(Zero) ] = 1
Acções: flush
IF7ID, ID/Ex e Ex/Mem
3. Atrasar
execução do salto (branch delay
slot )
E as instruções
de jump ?
Causas de
excepções/interrupções no MIPS
Alterações ao
MIPS para suportar arithmetic overflow
Análise
de desempenho numa arquitectura com pipeline e com cache (MIPS)
Considere o modelo
de uma arquitectura RISC com o pipeline da fig. 6.24, sem forward unit,
sem hazard detection unit, com write back na primeira metade do
ciclo, com pipeline stall em instruções de salto e com cache "quente"
e de dimensão infinita. Considere agora o seguinte programa em linguagem
máquina simbólica, cujo ficheiro executável irá ser carregado na memória com
início no endereço 0x8000.
mov $s1, $0
mov $s2, $0
mov $s0, -1024
sum: lw $t0, 0xC400($s0)
addu $s1, $s1, $t0
sw $s1,
0xE400($s0)
addu $s2, $s2, $s1
addiu $s0, $s0, +4
bne $s0, $0, sum
mov $s1, $0
a) Identifique todas as dependências de dados neste
programa e introduza as instruções nop necessárias para que a execução
do programa esteja correcta. Calcule o CPImin e o CPI efectivo, na execução
deste programa neste processador. Comente os resultados.
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.
5. Supondo que o pipeline
estará sempre ocupado com tarefas úteis (modelo óptimo de arquitectura),
verifique quantos ciclos de clock são precisos para completar a execução
(devará dar mais 4 que o nº de instruções, devido à latência de execução da 1ª
instrução); com base nos cálculos efectuados em 4. e 5. pode-se obter o CPImin
- que deverá ser (x +4)/x .
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:
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.
Sugestão:
lembre-se que a introdução da forward unit vai permitir eliminar as
bolhas nas dependências de dados críticas que ocorrem após a execução de
operações aritméticas/lógicas; contudo, nas operações de load continua a
haver a necessidade de o compilador inserir um nop ; mas, se a
arquitectura possuir uma hazard detection unit, é a própria unidade de
controlo da arquitectura que se encarrega de introduzir uma bolha nesses casos
de dependência crítica de dados, simplificando a tarefa de geração de código do
compilador (mas não melhorando o desempenho na execução...)
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.