Pipeline_Patterson

Prévia do material em texto

Melhorando o
Desempenho
com PipeliningJ
Enquanto o tempo pctssct,
todas as coisas permanecem,.
noyas coisas qcontecem,
enquanto as antigas envelhecem.
RobeÉ Herrick
llesperidies. C'eremonies lôr (lhristntus Ár,c, 1648
a
6.1
6.2
6.3
6.4
6.5
6.6
6.7
6.8
6.9
6.10
6.11
6.L2
6.13
6.14
Visão gleral de pipelinin§ 27A
Um caminho de dados usando pipeline 289
Gontrole de um pipeline 3OO
Hazards de dados e forwardingl 3O3
Hazards de dados e stalls 311
Hazards de desvio 313
usando uma linguagem de descrição de hardware paÍa descrever e modelar
um pipeline 322
Exceções 3.22
Pilepining avançado: extraindo mais desempenho 926
Vida real: o pipeline do Pentium 4 398
Falácias e armadilhas 34O
Gomentários finais 34L
Perspectiva histórica e leitura adicionat 343
ExercÍcios 3/Hl
Os cinco componentes clássicos de um computador
ü
278 Organização e Projeto de ComputadoÍes ELSEVIER
Nunca perca
tempo.
Provérbio
americano
pipdining Uma técnica
de implementação em
que várias instruçÔes
são sobÍepostas na
execuçã0, semelhante a
uma linha de
montagem.
Visão gleral de pipeliningl
Pipelining é uma técnica de implementação em que várias instruções são sobrepostas na execução.
Hoje, a técnica de pipelining é fundamerrtal paratornar os processadores mais rapidos.
Esta seção uÍilaabastante uma analogi a para dar uma visão geral dos termos e aspectos da técnica
de pipelining. Se você estiver interessado apenas no quadro geral, deverá se concentrar nesta seção e
depois pular para as Seções 6.9 e 6.10, para ver uma introdução às técnicas de pipelining avançadas,
utilizadas nos processadores mais recentes, como o Pentium III e 4. Se estiver interessado em explorar
a anatomia de um computador com pipeline, esta seção é uma boa innodução às Seções de 6.2 a 6.8.
Qualquerumquetenhalavadomuitasroupasintuitivamentejáusoupipelining. Atécnicasempi-
peline para lavar roupas seria
Colocar a trouxa suja de roupas na lavadora.
Quando a lavadora terminar, colocar a trouxa molhada na secadora (se houver).
3. Quando a secadora terminar, colocar a trouxa seca na mesa e passar.
4. Quando terminar de passar, pedir ao seu colega de quarto para guardar as roupas.
Quando seu colega terminar, então comece novamente com a próxima trouxa suja.
A técnica com pipeline leva muito menos tempo, como mostra a Figura 6.1. Assim que a lavadora
terminar com a primeira trouxa e ela for colocada na secadora, você carrega a lavadora com a segun-
da trouxa suja. Quando a primeira trouxa estiver seca, você a coloca na tátbuaparacomeçar a passar e
dobrar, move a trouxa molhadapara a secadora e a próxima trouxa suja para a lavadora. Em seguida,
6PM 7 8 I í0 11 12 1 2AM
Tempo
Ordem
da tareÍa ffiffiffiIffiffi=tffiffiffiIffiffi€r
1.
2.
A
B
c
D
6PM 11't0 2AMferno
-r-frrE
ffiffie!
offiffiEr
ffiffiÉI
FIGURA 6.1 A analogia da lavagem de roupas pra pipclinin§. Ana, Beto, Catarina e Davi possuem roupas su-
jas para serem lavadas, secadas, passadas e guardadas. O lavador. o secador, o passador e o guardador levam 30 minutos
para sua tarefa. A lavagem seqüencial levaria 8 horas para guarro Eouxas de roupas, enquanto a lavagem com pipeline le-
varia apenas 3,5 horas. Mostramos o estágio do pipeline de diferentes trouxas com o passar do tempo mostrando cópias dos
quatro recursos nessa linha de tempo bidimensional, mas na realidade temos apenas um de cada recurso.
A
B
c
D
ffi
ELSEVIER
Melhorando o Desempenho com pipelining 279
você pede a seu colega para guardar a primeira remessa, começa a passar e dobrar a segunda, a seca-dora está com a terceira remessa 
" 
,o.ê coloca a quarta natuuààoru. Nesse ponto, todas as etapas 
-denominadas estógios empipelining 
- 
estão operando simultaneamente. Desde que haja recursos se-parados para cada estágio, podemos rrur r- pipeline para as tarefas.
o paradoxo da técnica.de pipelining é que o tempo desde a colocação de uma única trouxa deroupa suja na lavadora até que ela seja secáda, passada 
" 
gruràudu não é mais 
";;;;r" atécnicade pipelining; o motivo pelo qual alécnicade iipelining"e mais râpidapara muitas trouxas é quetudo está trabalhando em paralelo, de modo que mais tõuxas são terminadas por hora. A técnicade pipelining melhora avazão do sistema de íavanderia sem merhorar o tempo para concluir umaúnica trouxa' Logo, a técnica de pipelining não diminuiria o tempo para concluir uma trouxa deroupas' mas, quando temos muitas trouxas paralavar,a melhoria navazã.odiminui o tempo totalpara concluir o trabalho.
se todos os estágios levarem aproximadamente o mesmo tempo e houver trabalho suficiente pararcalizar' então o ganho de velocidade devido à técnica de pipelining será igual ao número de estágiosdo pipeline, neste caso, quatro: lavar, secar, passar e gru.àui. Assim, a lavanderia com pipeline é po-tencialmente quatro vezes mais ráryidado que a sem pipeli ne:2}trouxas levariam cerca de 5 vezes otempo de 1 trouxa, enquanto 20 trouxas delavagem seqüencial levariam 20 vezeso tempo de 1 trou-xa' o gaúo foi de apenas 2,3 vezes na Figura o. t porque mostramos apenas 4 trouxas. ôbr"*" qr",no início e no final da carga de trabalho na versão com pipeline da Figura 6.1, o pipeline não estácompletamente cheio' Esse efeito no início e no fim afeta oàesempenho quando o número de tarefasnão. é grande em comparação com a quantidade de estágios do fipetine. Se o número de trouxas Ítrrmuito maior que 4, então os estágios estarão cheios .ruiruio, pã;e do tempo e o aumento navazãoserá muito próximo de 4.
os mesmos princípios se aplicam aprocessadores em que usamos pipeline para a execução da ins-trução. As instruções MIpS normarmente exigem cinco ôtapas: 
-
l. Buscar instrução da memória.
2' Lerregistradoresenquanto a instrução é decodificada. o formato das instruções MIps permiteque a leitura e a decodificação ocorram simultaneamente.
3. Executar a operação ou calcular um endereço.
4. Acessar um operando na memória de dados.
5. Escrever o resultado em um registrador.
Logo' o pipeline MIPS que exploramos neste capítulo possui cinco estágios. o exemplo a seguirmostra que a técnica de pipeliningagilizaa execução da instrução, assim como agilizaa lavagem deroupas.
DESEMPENHO DE CICLO ÚNICO YERSUS DESEMPENHO COM PIPELINE
Para tornar esta discussão concreta, vamos criar um pipeline. Neste exemplo, e no restante deste ca-pítuIo, vamos limitar nossa atenção a oito instruções: load word (l w), store word (sw), add (add), sub-tract (sub), and (and), or (or), set_less_than (st tj e branch_on_equal (beq).
compare o tempo mf{io entre as instruções de uma implementação em ciclo único, em que todasas instruções levam I ciclo de clock, com uma implementàção com pipeline. os tempos de operaçãopara as principais unidades funcionais neste exemplo são de 200ps para acesso à memória, 200pspara operação com ALU e l00ps para leitura o, 
"r"iitu d" registrad'ores. como dissemos no capítulo5' no modelo de ciclo único, cada instrução leva exatament"e l ciclo de clock, de modã que o cicloprecisa ser esticado para acomodar a instrução mais lenta.
28O Organização e projeto de Computadores ELSEVIIIR
A Figura 6.2 mosÍra o tempo exigido para cadauma das oito instruções. o projeto dc ciclo único prc-
cisa contemplar a instrução mais lenta 
- 
na Figura 6.2, elaé I w 
- 
de modo-quã o tcmpo exigido para
cada instrução é 800ps. Assim como na Figura 6.1, a Figura 6.3 compara a execução sem pipelinc e
com pipeline de três instruções load word. Desse modo, o tcmpo entre a primeira e a quarta instrução
no projeto sem pipeline é 3 x 800ns, ou 2.400ps.
Todos os estágios do pipeline utilizam um único ciclo de clock, de modo que o ciclo dc clock pre-
cisa scr grandc o suficiente para acomodar a operação mais lcnta. Assim corno o projeto de ciclo úni-
co de clock precisa levar o tempo do ciclo de clock no pior caso, de 800ps, c-bo.a algumas instru-
çõespossam ser tão rápidas quanto 500ps, o ciclo dc clock da execução côm pipeline pÃcisa ter o ci-
clo de clock no pior caso dc 200ps, embora alguns cstágios levcm apenas l00ps. O uso de pipeline
ainda oferece uma mclhoria de desempenho de quatro vezes: o tempo entre a primeira e a quarta ins-
truções é de 3 x 200ps, ou 600ps.
Agora, podemos converlcr a discussão sobre ganho de velocidade com a técnica de pipclining em
uma fórmula. Se os estágios forem perfcitamentc balanccados, então o tempo entre as instruções noprocessador com pipeline 
- 
assumindo condições ideais 
- 
ó igual a
Tempo entre instruçõescorn piperine
Tempo entre instruçõessem pipeline
Número de cstágios do pipe
Sob condições ideais e com uma grandc quantidade de instruções, o ganho de velocidade com a téc-
nica de pipelining é aproximadamente igual ao número dc estágios dó pipc; um pipclinc de cinco es-
tágios ó quase cinco vezes mais rápido.
A fórmula sugere que um pipelinc de cinco estágios deve oferecer uma melhoria de quase cinco
vczes sobre o tempo scm pipeline de 800ps, ou um ciclo de clock de l60ps. Entretanto, o exemplo
mostra que os estágios podem ser mal balanccados. Alóm disso, a técnica de pipelining envolve al-gum overhcad, cuja origem se tornará mais clara adiante. Assim, o tempo por instrução ro pro""..u-
dor com pipeline scrá superior ao mínimo possívcl, e o ganho de vclocidaáe será menor que o númc-
ro de estágios do pipcline.
Além do mais, até mesmo nossa afirmação de uma melhoria de quatro vezcs para nosso exem-plo não cstá reflctida no tempo de execução total para as três instruçõcs: saã t.+ogps yer,\Lts
2.400ps. Naturalmcnte, isso acontcce porque o número de instruções não ó grande. o quc aconte-
ccria se aumentásscmos o número de instruçõcs? Poderíamos cstendcr o. ,ãlor., antcriores para
1'000.003 instruções. Acrcscentaríamos 1.000.000 instruções no cxemplo com pipeline; cada ins-
trução acrescenta 200ps ao tempo dc execução total. O tempo dc execução total seria 1.000.000 x
200ps + 1.400ps, ou 200.001.400ps. No exemplo sem pipáhne, acrescentaríamos 1.000.000 ins-
truçõcs, cada uma exigindo 800ps, de modo que o tempo de execução total seria 1.000.000 x g00ps
+ 2'400ps, ou 800.002.400ps. Sob essas condiçõcs ideais, a razã.o entre os tcmpos de execução to-
tal para os programas reais nos processadores sem pipeline c com pipeline ó pióximo da razão d.e
tempos entre as instruções:
Load word(lw) 200ps 100ps 200ps 200ps 100ps 800ps
Store word (sw) 200ps 100ps 200ps 200ps 700ps
Formato R (add, sub, and, or, slt) 200ps 100ps 200ps 100ps 600ps
Branch (beq) 200ps 1000s 200ps 500ps
FIGURA 6.2 Tempo total para cada instrução ealcutada a paÉir do tempo para cada componente.
Essc cálculo considera que os multiplcxadores, unidade d.!- conrrLrli. acessos ao PC e unidade de cxtensão àe sinal não pos-
suem atraso.
ffi
EI§EVTER
Melhorando o Desempenho com pipelining 2g1
Ordem de
execução Tempo
oo programa
(em instruÇões)
1000 1200 1400 1600 t80O
Busca de
instruQóes Rêg ALU
Acesso
aos dados Reg
800 ps Busca de
instrucões Ret eLu | 4."".o IR"o
I aos dadosl
-
800 ps Busca de
nstruÇões
+...+
800 ps
1000 1200 1400
Itw 
sr, roolsoy
l'* 
*'' 
'oottol
llw 
$3, 300($0)
Ordem de
execução 1"rro
oo programa
(em instruções)
ltw 
sr, roolsoy
lrw 
$2,200($0)
lrw 
$3,300(g0)
200 ps 200 ps 200 ps 200 ps 200 pá
FlGURA6.3AGima'execuçãoemcicloúnico,sempipeline,yeIsí,§execuçãocompipeline.F
ffi:fi#|[:T""j,:':r,""'-':;1:::::-'j11Tjy11::,:'i:ir" #üd" ;;is,.,6 2 Neste caso, vemos um gaúo develocidade de 4 vezes no tempo médio entre as instruçáes, de 80ôps para 200pr. 4".;;:";)?l;ilj?.i.H?iffiff#:rff
consideramos que todos os estiígios eram iguais. se a secadora fosse mais l.rÁ, 
"nrao 
o 
"rtrígio daiecadora definiria o tempodo esüígio' os tempos de estágio do pipeline dos computadores são limitado, páo ,""u.ro 
-ais lento, seja a operação da ALUou o acesso à memória' consideramos que a escrita no banco de regishadores ocor.e na primeira metade do ciclo de clock e aleitura do banco de registradores oaorr. nu segunda metade. usamos essa suposição por todo este capítulo.
800.002.400ps 
. ^^ 800ns
,oooo{Joop. x +PU = 2oop.
A técnica de pipelining melhora o desempeú o aumentando a vazão de instruções, em vez de di-minuir o tempo de execução de uma instrução individual,mas avazãode instruções não é a medidaimportante, pois os programas reais executam bilhões de instruções.
Projetando coniuntos de instruções paÍa pipelining
Mesmo com essa explicação simples sobre pipelining, podemos entender melhor o projeto do con-junto de instruções MIPS, prqetâdo para execução com pipeline.
Primeiro, todas as instruções Mtps têm o mesmo tamaúo. Essa restrição torna muito mais fácilbuscar instruções no primeiro estigio do pipeline e decodificá-las no segundo estágio. Em um con-junto de instruções como orA-3 2,Áo quaias instruções variam a" t uyt" a 17 bytes, a técnica de pi-pelining é muito mais desafiadora. coÀo vimos no capítulo 5, todas as implementações recentes daarquitefura rA-32 na realidade traduzem instruções rA-32 emmicrooperações simples, que se pare-cem com instruções MIPS' conforme veremos na seção 6.10, na verdade, o pentiuL 4 usa um pipe-line de microoperações, no lugar das instruções lA_32nativas!
Em segundo lugar, o MIPS tem apenas uigrr* poucos formatos de instrução, com os campos deregistrador de origem localizados ,to 
-.r*ol.rgur.- .uou i".truião. Essa simetria signiÍica que osegundo estágio pode começar a ler o banco de registradores ao or"r-o tempo em que o hardwareestá determinando que tipo de instrução foi lida. Sús formatos de instmção do MIps não fossem si-
282 Organização e projeto de ComputadoÍes
ETSEVIER
hazard estrutural Uma
ocorrência em que uma
instrução planejada não
pode ser executada no
ciclo de clock coneto,
pois o hardware não
admite a combinação
de instruções definidas
para executar em
determinado ciclo de
clock.
tazüd dGdados
TamtÉrn chamado
hazard de dados do
pipeline. Uma
ocorência em que uma
instrução planejada não
pode ser executada no
ciclo de clock coreto
porque os dados
necesários para
executar a instrução
ainda nâo estão
disponíveis.
métricos' precisaríamos dividir o estágio 2, resultando em seis estágios de pipeline. Logo veremos adewantagem dos pipelines mais longãs.
Em terceiro lugar' os operandos em memória só aparecem em loads ou stores no MIps. F"sad
l1?i::l*toca que podemos usar o estágio o" 
"*""uçao pàru "ãr"rr* o endereço de memória e ô.pols acessar a memória no estágio seguinte. Se pudéssemo, op"ru. sobre os operandos na memória,como na arquitetura IA-32,os estágios 3 e 4 se expandiriarrrpul, 
"rtagio de endereço, estágio de me-mória e, em seguida, estágio de ex-ecução.
Em quarto lugar' conforme discutimos no capítulo 2, os operandos precisam estar alinhados namemória' Logo, não precisamos nos preocupar com uma única instrução de transferência de dadosexigindo dois acessos à memória de d'ados; às dados.solicitadls podem ser t urrr".iao. entre o pro-cessador e a memória em um único estágio do pipeline. - )
Pipeline hazards
Existem situações em pipelining em que a próxima instrução não pode ser executada no ciclo declock seguinte' Esses eventos são chamad oi hazards,e e*istemircs tipos diferentes.
Hazards estruturais
o primeiro hazardé chamado hazardestrutural. Ele significa que o hardware não pode admitir acombinação de instruções que queremos executarno mesmo ciclo de clock. um hazard,estrutural nalavanderia aconteceria se usássàmos uma combinação luuudoru-r".adora no lugar de lavadora e se-cadora separadas, ou se nosso colega estivesse ocupado com outra coisa e não pudesse guardar asroupas. No sso pipeline, cuidadosamente programado, fracassaria.
como dissemos, o conjunto de instruçõer [arri tJü;,rd*ara ser execurado em um piperine,tornando muito flícil para os projetistas e,vitarhazardr;d;;; [uanao projetaram o pipeline. con_tudo' suponha que tivéssemos uma única memória , emvezde duas. se o pipeline da Figura 6.3 tives-se uma quarta instrução, veríamos que, no mesmo ciclo de clock em que a primeira instrução estáacessando dados da memória, u quirtuinstrução está buscando uma instrução dessa mesma memó_ria' Sem duas memórias, nosso pipeline poderia ter um hazardestrutural.
Hazards de dados
os hazards de dados ocorrem guando o pipeline precisa ser interrompido porque uma etapa precisaesperar até que outra seja concluída. sufoúa qu" ,o.à á;;-;;"""trado umà meia na estação depassar para a qual não exista um par. uma estratàgia possível é correr até o seu quarto e procurar emsua gaveta para ver se consegue encontrar o par. obviamente, enquanto você está procurando, asroupas que ficaram secas e estãoprontas para serem passadas, e aqueras que acabaram de ser lavadase estão prontas para serem secadas deveião esperar.
Em um pipeline de computador, os hazards de dados surgem quando uma instrução depende deuma anterior que ainda está no pipeline (um relacioname"r"ãr" rá" existe realmente quando se lavaroupas)' Por exemplo, supoúa que tenhamos uma instruçãà add seguida imediatamente por umainstrução subtract que usa u ,o*u 1$.0;,
$s0,519,5,t
$t2,516, t,,
add
sub
sem intervenção' um hlzard.de dados poderia preju_dicar o piperine severamente. A instrução addnão escreve seu resultado até o quinto estrágio, signin"urao irã ,*ir*"s de acrescentar três bolhasao pipeline.
ffi
EI-SEVIER.
Melhorando o Desempenho com Pipelining 283
Embora pudéssemos contar com compiladores para remover todos esses hazards, os resultados
não seriam satisfatórios. Essas dependências acontecem com muita freqüência, e o atraso simples-
mente é muito longo para se esperar que o compilador nos tire desse dilema.
A solução principal é baseada na observação de que não precisamos esperar que a instrução termi-
ne antes de tentar resolver ohazardde dados. Para a seqüência de código anterior, assim que a ALU
cria a soma para o add, podemos fornecê-la como uma entrada para a subtração. O acréscimo de
hardware extra para ter o item que falta antes do previsto, diretamente dos recursos internos, é cha-
mado de forwarding ou bypassing.
FORWARDING COM DUAS INSTRUÇOES
Para as duas instruções anteriores, mostre quais estágios do pipeline estariam conectados pelo for-
warding. Use o desenho da Figura 6.4 pararepresentar o caminho de dados durante os cinco estagios
do pipeline. Alinhe a cópia do camiúo de dados para cada instrução, semelhante ao pipeline da la-
vanderia, na Figura 6.1.
A Figura 6.5 mostra a conexão para o forwarding do valor em $s0 após o estágio de execução da ins-
trução add como entrada para o estágio de execução da instrução sub.
200 400 1000
Tempo
add $s0, $t0, $t1
Ordem de
execução do
programa TemPo
(em instruções)
add §s*. $t0, $t1
sub §12, $s0, $t3
Íonvarding lambém
chamado bypassing. Um
método para resolver
um hazard de dados
utilizando o elemento de
dados que Íalta a partir
de buÍfers internos, em
vez de esperar que
chegue nos registradores
visíveis ao programador
ou na memória.
I
@
FtcURA 6.4 Representação EFáfiGa do pipeline de instruções, semelhante ao obietivo do pipeline da la
vanderia na Fisura 6.f. ,Lqui, usamos símbolos representando os recursos fisicos com as abreviações para os estágios
do pipeline usados no decorrer dà capítulo. Os símbolos para os cinco estagios são: lFpara o estágio de busca de instruções
llnstnrction Fetch), com a caixa representando a memória de instruções; ID para o estágio de decodificação de instru-
iões (Instruction Decode)/leitura do banco de registradores, com o desenho mostrando o banco de registradores sendo lido;
EX parao estâgio de execução, com o deseúo representand o a ALIJ; MEMpara o estágio de acesso à memória, com a cai
*u.epres"ntaldo a memória de dados; e WB para oesüígio de escrita do resultado (Write Back), com o desenho mostrando
o banco de registradores sendo escrito. O sombreado indica que o elemento é usado pela instrução. Logo, MEM possui um
fundo branco porque add não acessa a memória de dados. O sombreado na metade direita do banco de regiskadores ou na
memória significa que o elemento é lido nesse estágio, e o sombreado na metade esquerda significa que ele é escrito nesse
estágio. Loto, a meiade direita de ID é sombreada no segundo estágio porque o banco de registradores é lido, e a metade es-
quúa de úB é sombreada no quinto estágio porque o banco de registradores é escrito.
FTGURA 6.5 RepÍesedaçao gJráfica do fonvaldin§. A conexão mostra o caminho do forwarding desde a saída
do estágio EX dà add até a éntraãa do estágio EX para s u b, substituindo o valor do registrador $s0 lido no segundo es-
tágio de sub.
284 Organização e pÍojeto de ComputadoÍes
ELSEVIER
hazard de dados no uso
de load Uma forma
específica de hazard de
dados em que os dados
solicitados por uma
instruCão load ainda
não estão disponÍveis
quando requisitados.
pipeline stall Também
chamado bolha. Um
stall iniciado a Íim de
resolver um hazard.
Nessa representação gráfica dos eventos, os caminhos de forwarding só são válidos se o estágio dedestino estiver mais adiante no tempo do que o estágio de origem. poiexemplo, não pode haver um
camiúo de forwarding válido da saída do estiígio dé acesso imemória na primeira instrução para a
entrada do estágio de execução da instrução seguinte, pois isso significaria voltar no tempo.
O forwarding funciona muito bem e é descrito com detalhes na Seção 6.4. Entretanto, ele nãopode impedir todos os stalls do pipeline. Por exemplo, supoúa que a primeira instrução fosse umload de $s0 em vez de um add. Como podemos imaginar eiaminando a Figura 6.5, os dados deseja-
dos só estariam disponíveis depois do quarto estágio da primeira instrução na dependência, que é
muito tarde para a entrada do terceiro estiígio de sub. Logo, até mesmo com o forwarding, teríamos
de atrasar um estiígio para um hazard de dados no uso dúoad, como mostra a Figura 6.6. Essa figu-
ra mostra um conceito importante de pipeline, conhecido oficialmente como pipeline stall, mas nor-
malmente recebendo o apelido de botha. Veremos os stalls em outros lugarás ào pipeline. A Seção
6'5 mostra como podemos tratar de casos assim, usando a detecção de hardware 
" 
.tutt, ou software
que trata o atraso do load como um atraso de desvio.
Ordem de
execução do
programa TemPo 1 000 1200 1400
(em instruções)
lw $s0, 20($t1)
sub $t2,$s0, $t3
FIGURA 6'6 PÍêGisamos de um stall ató mosmo com forwarding quando uma instrução do formato R
aprôs um load tenta usar os dados. Sem o stall, o camiúo da saídaão estágio de acesso à memória para a entradado estiígio de execução estaria ao contrário no tempo, o que é impossível. Essa figura, na realidade, é uma simplificaçâo,pois não podemos saber, antes que a instrução de subtração seja lida e decodificada, se um stall será necessário. A Seção6.5 mostra os detalhes do que rearmente acontece no cnso de um hazard.
REORDENANDO O CÓOIEO PARA EVITAR PIPELINE STALIS
Considere o seguinte segmento de código em C:
A=
C=
Aqui está o código MIPS gerado para esse segmento, supondo que todas as variáveis estejam na me-
mória e sejam endereçáveis como offsets a partir de $t0:
lw $tt, o($to)tw $t2, 4($t0)
add $t:, $tt,$tZ
sw $t3, 12($t0)lw $t+, e($ot)
add $t5, $t1,$t4
sví $t5,16(gto)
Encontre os hazards no segmento de código a seguir e reordene as instruções para evitar quaisquer
pipeline stalls.
B+
B+
ffi
ELSEVIER
Melhorando o Desempenho com Pipelining 285
As duas instruções add possuem umhazaÍd,devido à respectiva dependência da instrução I w imedia-
tamente anterior. Observe que o bypassing elimina vários outros hazards em potencial, incluindo a
dependência do primeiro add no primeiro 1w e quaisquer hazards para instruções store. Subir a terceira
instruçãoI w elimina os dois hazards:
lw
lw
lw
add
SW
add
SW
Em um processador com pipeline com forwarding, a seqüência reordenada será completada em
dois ciclos a menos do que a versão original.
O forwarding leva a outro detalhe da arquitetura MIPS, além dos quatro mencionados nas páginas
281-282. Cada instrução MIPS escreve no máximo um resultado efazisso quase no final do pipeli-
ne. O forwarding é mais dificil se houver vários resultados para encaminharpor instrução, ou se pre-
cisarem escrever um resultado mais cedo na execução da instrução.
âetalhanruemt*: o nome "forwarding" vem da idéia de que o resultado é passado adiante a partir de uma ins-
truÇão anterior para uma instrução posterior. "Bypassing" vem de passar o resultado pelo banco de registrado
res à unidade desejada.
Hazards de controle
O terceiro tipo de hazard é chamado hazard de controle, vindo da necessidade de tomar uma deci-
são com base nos resultados de uma instrução enquanto outras estão sendo executadas.
Suponha que nosso pessoal da lavanderia receba a tarefa feliz de limpar os uniformes de um
time de futebol. Como a roupa é muito suja, temos de determinar se o detergente e a temperatura
da água que selecionamos são fortes o suficiente para limpar os uniformes, mas não tão forte
para desgastá-los antes do tempo. Em nosso pipeline de lavanderia, temos de esperar até o se-
gundo estágio para examinar o uniforme seco para ver se precisamos ou não mudar as opções da
la.vadara-. O que fazer?
Aqui está a primeira das duas soluções para controlar os hazards na lavanderia e seu equivalente
nos computadores.
Stall: Basta operar seqüencialmente até que o primeiro lote esteja seco e depois repetir até você
ter afórmula correta. Essa opção conservadora certamentefunciona, mas é lenta.
A tarefa de decisão equivalente em um computador é a instrução de desvio. Observe que temos de
começar a buscar a instrução após o desvio no próximo ciclo de clock. Contudo, o pipeline possivel-
mente não saberá qual deve ser a próxima instrução, pois ele só recebeu da memória a instrução de
desvio! Assim como na lavanderia, uma solução possível é ocasionar um stall no pipeline imediata-
mente após buscarmos um desvio, esperando até que o pipeline determine o resultado do desvio para
saber de que endereço apanhar a próxima instrução.
Vamos supor que colocamos hardware extra suflrciente de modo que possamos testar registrado-
res, calcular o endereço de desvio e atualizar o PC durante o segundo estágio do pipeline (ver Seção
6-6 para obter mais detalhes). Até mesmo com esse hardware extra, o pipeline envolvendo desvios
condicionais se pareceria com a Figura 6.7 . A instrução 1w, executada se o desvio não for tomado,
fica em stall durante um ciclo de clock extra de 200ps antes de iniciar.
hazad de controle
Também chamado
hazad de desvio. Um
acontecimento em que a
instrução apropriada
não pode ser executada
no seu devido ciclo de
clock porque a instrução
buscada não é aquela
necesária; ou seja, o
fluxo de endereços de
instrução não é o que o
pipeline esperava.
$t1,0($t0)
$tz, +($tt)
$t4,8($t1)
$t3, $t1,$t2
$t3, 12($t0)
$t5, $t1,$t4
$t5, i6 ($to)
286 OÍganização e Projeto de ComputadoÍês ELSEVIER
Ordem de
exêcuçao l
do programa
1000 1200 1400
(em instruções)
laoo 
$+, $s, $o
| 
t:er *t, s2, a0
I
louS7, $8, S§t
Busa de
instruçõês HeC ALU
Acesso
ros dados
Beg
200 ps
Busca dê
nstruçôês Rêg ALU
Acesso
ros dados
Reg
**ll
,{i a,
-g-çl;ry*.'1'* tld
**lEr*" d"l
40ü ps ltnstruçoesl
*§itrã(r
Rêg ALU Acesso
aos dados
Beg
I
lillsFlitr?il
FIGURA 6.7 Pipeline mostrando o stall êm cada desvio condicionat como solução paÍa controlar os h+
zalds. Existe um stall de um eslágio no pipeline, ou bolha, após o desvio. Na realidade, o processo de criação de um
stall é ligeiramente mais complicado, conforme veremos na Seção 6.6. No entanto, o efeito sobre o desempenho é o mesmo
que ocorreria se uma bolha fosse inserida.
DESEMPENHO DO ''STALL NO DESVIO''
Estime o impacto nos ciclos de clock por instrução (CPI) do stall nos desvios. Supoúa que todas as
outras instruções tenham um CPI de 1.
A Figura 3 .26, mostra que os desvios são 13o/o das instruções executadas no SPECint2000. Como
outras instruções possuem um CPI de I e os desvios tomaram um ciclo de clock extrapara o stall, en-
tão veríamos um CPI de 1,13 e, portanto, um stall de 1,13 em relação ao caso ideal. Observe que isso
inclui apenas branches e que os jumps também poderiam ocasionar um stall.
Se não pudermos resolver o desvio no segundo estágio, como norrnalmente acontece para pipeli-
nes maiores, então veríamos um atraso ainda maior se ocoÍresse um stall nos desvios. O custo dessa
opção é muito alto para a maioria dos computadores utilizar, e isso motiva uma segunda solução para
ohazard de controle:
Prever: se você estiver certo de que tem a formula correta paralavar os uniformes, então basta
prever que ela funcionará e lavar a segunda remessa enquanto espera que a primeira seque. Essa
opção não atrasa o pipeline quando você estiver correto. Entretanto, quando estiver errado, você
terá de refazer a remessa que foi lavada enquanto pensa na decisão.
Os computadores realmente utilizam a previsão para trataÍ dos desvios. Uma técnica simples é
sempre prever que os desvios não serão tomados. Quando você estiver certo, o pipeline prosseguirá
a toda velocidade. Somente quando os desvios são tomados é que o pipeline sofre um stall. A Figura
6.8 mostra um exemplo assim.
Uma versão mais sofisticada de previsão de desüo teria alguns desüos previstos como tomados e al-
guns como não tomados. Em nossa analogia, os uniformes escuros ou de casa poderiam usar uma fórmu-
la, enquanto os uniformes claros ou de sairpoderiam usar outra. Como um exemplo de computador, no
final dos loops existem desvios que voltam para o início do loop. Como provavelmente serão tomados e
desviam para trás, sempre poderíamos prever como tomados os desvios para ufn endereço anterior.
Essas técnicas rígidas para o desvio contam com o comportamento estereotipado e não são res-
ponsáveis pela individualidade de uma instrução de desvio específica. Previsores dehardware dinâ-
micos, ao contrario, fazem suas escolhas dependendo do comportamento de cada desvio, e podem
mudar as previsões para um desvio durante a vida de um programa. Seguindo nossa analogia, na pre-
visão dinâmica, uma pessoa veria como o uniforrne estava sujo e escolheria a fórmula, ajustando a
próxima escolha dependendo do sucesso das escolhas recentes. Uma técnica popular para a previsão
destil, úrtomado
Um que segue para a
instruÇão sucessiva. Um
desvio tomado é aquele
que causa a
transÍerência da
execuçâo para o destino
do desvio.
previsãodedesvio Um
mótodo de resolver um
hazard de desvio que
considera um
determinado resultado
para o desvio e
prossegue a partir dessa
suposiçã0, em vez de
esperar para veriÍicar o
resultado real.
ffi
EI-SEVIER Melhorando o Desempenho com pipelining 2g7
Ordem de
800 1O0o 12OO 14OO
Ordem de
execucão
do prograrnslemPo
(em instruções)
1000 1200 1400
laoo 
$+, $5, $6 I,,T;
l**o*, s2,-r 
=I 
- 
, ,2ol
I
I '*o's7.:s,sÉ
,-.,f i,1,tt -j,-.l rtlàn r.:l:,
1,ilütl tr;l$il
Busca dê
instruçõês Beg ALU Acesso
aos dado! Beg
200 ps
Busca de
nstruçÕês Reg ALU Acesso
aos dados Ber
a'' **t*|2
-Lrír-
.&--------_._..._
4ü0 p-<
FIGURA 6.8 prevendo que os desvios não serão tomados.olno *rudesenho superior mostra o pipeline quando 
" 
o"*ála" é tomado. o deseúo infitomado. Conforme observamos na Fipr*a 6 7 q i^.^_^x^ r^ __-- 
- 
r ,, _rror mostra o pipeline quando o desvio étomado' conforme observamos na-Figura 6.7, a inserção de uma borha n"..J;ffi:ffi,,ffi'j'r::Tffi:f.o":ffij:":pelo menos durante o primeiro ciclo ãe 
"1".k'i;;;à-ente após o desvio. A seção 6.6 escrarecerá os derarhes.\*'x',r r, j
Beg ALU Aceqgo
los dados Beg
dinâmica de desvios é manter um histórico de cada desvio como tomado ou não tomado, e depoisusar o comportamento passado recente para prever o futuro. como veremos mais adiante, a quanti-dade e o tipo de históricà mantido tom sJtornãdo extensos,..Jtuodo emprevisores de desvio dinâ-micos que podem prever os desvios corretamente, com umaprecisão superior a g0oÁ (verseção 6.6).Quando a escolha estiver errada, o 
"ont oL ao piperine ierãã" gu*nti, que as instruções após o des-vio errado não teúam efeito, devendo rerniciaio pú"fir" , p"ti" do endereço de desvio apropriado.
3âffi.,1iljf,-"':"Tj;#ffX- temos a" a"m,à" u""lt* nouu, remessas para poder reinic iar are-
como no caso de.todas as outras soluções para control ar hazards,pipelines mais longos aumen-tam o problema' neste caso, aumentando o 
"yt: d9 erro de p.wisao. As soluções para controlar oshazards são descritas com mais detalhes na Seção 6.6.
§etalhamentÔ: existe uma terceira técnica para o hazardde controre, chamada decisão adiada.Em nossaanalogia' sempre que você tiver de tomar uma decisão sobre a ruruno"riu, basta corocar uma remessa de rou-pas que nâo sejam de futebol na lavadora, enquanto espera que os uniformes de futebor sequem. Desde quevocê tenha roupas sujas suficientes, que não sejam afetadas pelo ,"",", u""u solução funcionará bem.chamado de detayed branch (desvio adiado) nos computadores, essa é a solução rearmente usada pera ar-quitetura MIPS' o delayed branch sempre 
",u"ú,u a.próxima instrução seqüenciar, com o desvio ocorrendo após.esse atraso de uma instrução' lsso fica escondido do programador assembly do Mrps, pois o montador pode ar_rumar as instruções automaticamente para conseguir o comportamento de desvio desejado pero programador.o software MIPS colocará uma instrução imeoiaàmente após a instrução de derayed branch, que não é afetadapelo desvio' e um desvio.tomado muda o endereço da instrução que vem após essa instrução segura. Em nossoexemplo' a instruÇão add antes do desvio na Figura 6.7 não afeta o desvio, e pode ser movida para depois dodesvio' para esconder totalmente o atraso no d-esvio. como os delayed branches são úteis quando os desviossão curtos' nenhum processador usa um delayeJ branch de mais oe r cicro. para atrasos em desvios maiores, aprevisão de desvio baseada em hardware normalmente é usada.
Busca dê
in§ruções
Acesso
aos dados
288 Orsanização e projeto de ComputadoÍes ELSEVIER
****xaw** &ffi
w*{%w**xewe
latência (pipeline) 0
número de estágios em
um pipeline ou o
número de estágios
entre duôs instruçoes
durante a execuçã0.
Resumo da visão geral de pipelining
Pipclining é uma técnica que cxplora o paralelisrno entre as instruções em um fluxos de instruções
seqüenciais. Ela tem a vantagem substancial de que, diferente de algumas técnicas para ganhar velo-
cidade (ver 0 capítulo 9), ela é fundamentalmcnte invisível ao programador.
Nas próximas seções destc capítulo, abordamos o conceito de pipelining usando o subconjunto de
instruções MIPS I w, sw, add, sub, and, or, s1t c beq (o mesmo do Óapítulo 5) e uma versão simplifica-
da do seu pipeline. Depois, examinamos os problemas quc a tócnica de pipelining introduz c o dc-
sempenho alcançável sob situações típicas.
Se você quiscr sabcr mais sobre o softwarc e as implicações dc descmpenho da tecnica dc pipeli-
ning, agora terá base suficiente para pular para a Seção 6.9. A Scção 6.9 introduz conceitos avança-
dos de pipelining, como o escalonamento supercscalar e dinâmico, e a Seção 6. l0 examina o pipcline
do microprocessador Pcntium 4.
Como altemativa, se vocô estiver interessado cm entendcr como a técnica de pipelining ó imple-
mentada e os dcsafios de lidar com hazards, poderá prosseguir para examinar o piojeto de um cami-
nho de dados com pipeline, cxplicado na Scção 6.2, e o controle básico, explicaáo na Seção 6.3. De-
pois, você poderá usar essc conhecimento para explorar a implementação do forwarding na Scção
6.4,eaimplernentaçãodestallsnaSeção6.5.Vocêpoderá,então,leraSeção 6.6paraaprendermais
sobre soluçõcs para hazards de dcsvio, e depois ver como as exccções são tratadàs, na-Seção 6.g.
A técnica de pipelining aumenta o número de instruções em exccução simultânea e a velocida-
de em que as instruções sâo iniciadas e concluídas. A lecnica de pipelining nào reduz o tempogftg para completar uma instrução individual, também chamado de latência. por exemplo, o
pipeline de cinco estágios ainda usa 5 ciclos dc clock para completar a instrução. Nos termos
usados no Capítulo 4, atócnicade pipelining melhora avazãcs de instruções, e não o tempo de
execução ou latência das instruções individualmente.
Os conjuntos de instruções podem simplificar ou dificultar a vida dos projetistas do pipeline,
que já precisam enfrentar hazards estruturais, de controle e de dados. A prwisão de desvio, o for-
warding e os strlls ajudam a tomarum computadorrápido enquanto aindà gcra as respostas certas.
Entendendo o desempenho dos programas
Fora do sistema de memória, a operação efi,caz do pipeline normalmente ó o fator mais importantc
para determinar o CPI do processador e, portanto, seu desempenho. Conformc veremos na Seção
6.9, compreender o desempcnho de um processador moderno com múltiplos problemas é algo com-
plexo e cxige a comprccnsão de mais do que apenas as questões que surgem cm um processador com
pipeline simplcs. Apesar disso, os hazards cstruturais, de dados e de controle continuam sendo im-
portantes cm pipelines simplcs e mais sofisticados.
Para pipelines modernos, os hazards estruturais costumam girar em torno da unidade de ponto flu-
tuante, que pode não ser totalmente implementada com pipeline, enquanto os hazards de controle
costumam ser um problema maior nos programas dc inteiros, que cosfurham tcr maiores freqüências
dc desvio, além de desvios menos previsíveis. os hazards de dados podem scr gargalos de dôsempe-
nho em programas de inteiros e de ponto flufuantc. Em geral, é mais flicit lidar com hazardsde dados
em programas de ponto flutuante porque a menor freqüência de desvios e os padrões de acesso mais
regulares permitem quc o compilador tente cscalonar instruçõcs para evitar os hazards. E mais dificil
realizat essas otimizações em programas de inteiros. quc possuem accsso mcnos regular e envolvem
um maior uso de ponteiros. Conforme veremos na Seção 6.9, existem técnicas dc compilação e de
hardware mais ambiciosas para reduzir as dependôncias de dados para o escalonamentó.
ffi
EISEVIER
Melhorando o Desempenho com Pipelining 289
Para cada seqüência de código a seguir, indique se ela deverá sofrer stall, pode evitar stalls usando Verifique
apenas forwarding, ou pode ser executada sem stall ou forwarding: você mesmo
lw $t0,0($t0)
add $t1,$t0,$t0
add
add i
addi
$t1,$r0,$t0
$t2, $to, #5
$t4, $t1, #5
addi $t1,$t0,#1
addi $12,$t0,#2
addi $t3,$t0,#2
addi $t3,$t0,#4
addi $t5,$t0,#5
Um caminho de dados usando pipeline
AFigura 6.9 mostrao caminho de dados de ciclo único do Capítulo 5. A diüsão deumainstrução emcin-
co estiigios significaumpipeline de cinco estiigios, que, por $urvez, significa que até cinco instruções es-
tarão em execução durante qualquer ciclo de clock. Assim, temos de separÍr o camiúo de dados em cin-
co partes, com cada parte possuindo um nome correspondente a um esüígio da execução da insfução:
1. IF (Instruction Fetch): Busca de instruções
2. ID (Instruction Decode): Decodificação de instruções e leitura do banco de registradores
3. EX: Execução ou cálculo de endereço
4. MEM: Acesso à memória de dados
5. WB (Write Back): Escrita do resultado
lF: Busca de instruções I
Há menos
nisso do que
chega aos olhos.
Tallulah Bankhead,
observação para
Alexander
Wollcott, 1922
lD: DecodiÍicação de IEX: Execução/cálculol
. 
instruções/leitura.do I de endereço Ibanco de registradoresj 
I
MEM: Acesso à
memória
WB: Escrita doresultado
Regifrdor &dc dâd€leibÉl bfthí
Rêgistadd
dê lêiúÉ 2
R.glrdG
Bêgistrador Dadcdâ
paÉ Mih leôe 2
Dado§
FIGURA 6.9 O caminho dê dados de ciclo único do GapÍtulo 5 (semelhante à Flggra 5.17). Cadaetapada
instução pode ser mapeada no camiúo de dados da esquerda para a direita. As únicas exceções são a atualização do PC e a eta-
pa de escrita do resultado, mostada em cores, que enüa o resultado da ALU ou os dados da memória para a esquerda, para se-
rern escritos no banco de registradores. §ormalmente, usamos liúas coloridas para contole, mas são liúas de dados.)
29O O4lanização e PÍoiêto de Computadores ELSEVIER
Na Figura 6.9, esses cinco componentes corespondem aproximadamente ao modo como o cami-
úo de dados é deseúado; as instruções e os dados em geral se movem da esquerda paÍaadireitape-
los cinco estágios enquanto completam a execução. Voltando ànossa analogia da lavanderia, as rou-
pas ficam mais limpas, mais secas e mais organizadas à medida que prosseguem na fila, e nunca se
movem para trás.
Entretanto, existem duas exceções para esse fluxo de informações da esquerda para a direita:
r O estágio de escrita do resultado, que coloca o resultado de volta no banco de registradores, no
meio do caminho de dados
I A seleção do próximo valor do PC, escolhendo entre o PC incrementado e o endereço de desvio
do estágio MEM
Os dados fluindo da direita para a esquerda não afetam a instrução atual; somente as instruções seguin-
tes no pipeline são influenciadas por esses movimentos de dados reversos. Observe que a primeira seta
da direita paÍaa esquerda pode levar ahazards de dados e a segunda ocasiona hazards de controle.
Uma maneira de mostrar o que acontece na execução com pipeline é fingir qu e cadainstrução tem
seu próprio caminho de dados, e depois colocar esses camiúos de dados em uma liúa de tempo
para mostrar seu relacionamento. A Figura 6. I 0 mostra a execução das instruções na Figura 6.3, exi-
bindo seus caminhos de dados privados em uma linha de tempo comum. Usamos uma versão estili-
zada do caminho de dados na Figura 6.9 para mostrar os relacionamentos na Figura 6. 10.
A Figura 6.10 parece sugerir que três instruções precisam de três caminhos de dados. No Capítulo
5, acrescentamos registradores para manter dados de modo que partes do camiúo de dados pudes-
sem ser compartilhadas durante a execução da instrução; usamos a mesma técnica aqui para compar-
tilhar os múltiplos caminhos de dados. Por exemplo, como mostra a Figura 6.10, a memória de ins-
Tempo (em ciclos de
clock)
Ordem de
execução do
programa
(em instruções)
lw $1 , 100($0)
lw $2, 200($0)
lw $3, 300($0)
FIGURA 6.10 Instruçôes executadas usando o caminho de dados de ciclo único na Fi§ura 6.9, assumin
do a execução com pipeline. Semelhante às Figuras de 6.4 a 6.6, esta figura finge que cada instrução possui seu pró-
prio caminho de dados e pinta cada parte de acordo com o uso. Ao contnírio daquelas figuqas, cada estilgio é rotulado pelo
recurso fisico usado nesse estágio, correspondendo às partes do caminho de dados na Figura 6.9. IM representa a memória
de instruções e o PC no esüígio de busca da instrução, Reg significa banco de registradores e extensor de sinal no estágio de
decodificação de instruções/leitura do banco 
.de registradores (ID), e assim por diante. Para manter a ordem de tempo corre-
ta, esse caminho de dados estilizado divide o banco de registradores em duas partes lógicas: leitura de registradores durante
abusca de registradores (ID) e registradores escritos durante a escrita do resultado (WB). Esse uso dual é represenüado pelo
desenho da metade esquerda não sombreada do banco de registradores, usando linhas tracejadas no estágio ID, quando ele
não estiver sendo escrito, e a metade direita não sombreada usando linhas hacejadas do estiígio WB, quando não estiver
sendo lido. Como antes, consideramos que o banco de registradores é escrito na primeira metade do ciclo de clock e o ban-
co de registradores é lido durante a segunda metade.
ffi
EI§EVIER
Melhorando o Desempenho com pipelining 291
truções é usada durante apenas um dos cinco estágios de uma instrução, permitindo que seja compar-
tilhada por outras instruções durante os outros quatro estágios.
Para reter o valor de uma instrução individual para seus outros quatro estágios, o valor lido da me-
mória de instruções precisa ser salvo em um registrador. Argumentos semelhantes se aplicam acada
estágio do pipeline, de modo que precisamos colocar registradores sempre que existam linhas divi-
sórias entre os estágios na Figura 6.9. Essa mudança é semelhante aos registradores acrescentados no
Capítulo 5, quando passamos de um ciclo único para um camiúo de dados de múltiplos ciclos. Re-
tornando à nossa analogia da lavanderia, poderíamos ter um cesto entre cada par de estágios para
conter as roupas paÍa a próxima etapa.
A Figura 6.1 I mostra o caminho de dados usando pipeline com os registradores do pipeline desta-
cados. Todas as instruções avançam durante cada ciclo de clock de um registrador ao prpetine para o
seguinte. Os registradores recebem os nomes dos dois estágios separados por esse rógistrador. por
exemplo, o registrador do pipeline entre os estágios IF e ID é chamado de IF/ID.
Observe que não existe um registrador de pipeline no final do estágio de escrita do resultado(WB). Todas as instruções precisam at:ualizar algum estado no processador- o banco de registrado-
res, memória ou o PC 
-, assim, um registrador de pipeline separado é redundante para o estado afua-
lizado. Por exemplo, uma instrução load colocará seu resultado em 1 dos 32 registradores, e qualquer
instrução posterior que precise desses dados simplesmente lerá o registrador apropriado.
Naturalmente, cada instrução atualizao PC, seja incrementando-o ou atribuindo a ele o endereço
de destino de um desvio. O PC pode ser considerado um registrador de pipeline: um que alimenta o
estágio IF do pipeline. Contudo, diferente dos registradores de pipeline sombreados nà Figura 6.11,
o PC faz parte do estado arquitetônico visível; seu conteúdo precisa ser salvo quando oco11e uma ex-
ceção, enquanto o conteúdo dos registradores de pipeline pode ser descartado. Na analogia da lavan-
deria, você poderia pensar no PC como coÍrespondendo ao cesto que mantém u ."*"r.u de roupas
sujas antes da etapa de lavagem!
Para mostrar como funciona a técnica de pipelining, no decorrer deste capítulo, apresentamos se-
qüências de figuras para demonstrar a operação com o tempo. Essas páginas extras parecem exigir
FIGURA 6.11 A versão com pipeline do caminho de dados na Figlura 6,9. os registradores do pipeline, em cinza, separam cada es-
tágio do pipeline. Eles são rotulados pelos nomes dos estágios que separam; por exemplo, o primeiro é rotulád o com IF/ID porque separa os está-
gios de busca de instruções e decodificação de instruções. Os registradores precisam ser grandes o suficiente para aÍÍnazenar todos os dados
correspondentes às linhas que passam por eles. Por exemplo, o registrador IF/ID precisa ter 64 bits de largura, pois precisa manter a instrução de
32 bits lida da memória e o endereço incrementado de 32 bits no PC. Vamos expandir esses registradores no decorrer deste capitulo, mas, por en-
quanto, os outros três registradores de pipeline contêm 128,97 e 64 bits, respectivamente.
292 Organização e projeto de Computadores
]ILSEVIEIT
muito mais tempo para você entender. Mas não tema; as seqüências levam muito menos tcmpo doqueparece, pois você pode compará-las para ver quc mudanças oco11em cm cada ciclo do clock. AsSeções 6'4 e 6'5 descrevem o que acontecc quando existem hazards de dados entre instruções em umpipelinc; ignorc-as por enquanto.
it^llq::: I :!2 
-o 
6 14,. nossa primc.ira seqüência, mostram as parre s arivas do caminho de dadosdcstacadas cnquanto uma instrução de load passa pelos cinco estági
rramos um roaà p.i."i-;;,;;:iffi1X1:::','jJ:ff;'.Tff'::'t:*;::T[X**T?I";Xfi.4 a 6.11.
do estágio do pipelinc que está ativo em cada figura. os cinco cstágios são os seguintcs:
llnr
i dêmdiíicaçào de rnsiruQoes I
FIGURA 6'12 !F e lD: primeiro e seglundo está§ios do pipe de uma instrução, com as paÉes ativas do ca-
illi:,ff.it::.:,t:"::í::^1 9:_t1:- aestaquã. .\ c.nr encào «ic destaquc é a mcsma utilizada na Figura 6.4. cornono capítulo 5' não há contusão quando sc lê e escr*.- nos rL-risrradorcs. pois o;ffi"do;H'r"Tj'llii,on. ao ctoctlEmbora o loacl só precise do registraclor dc cima no estágio l. . prtrc.-5sador não sabe que instrução cstá sen6o decodificada.de modo que estende o sinal da constante de l6 bits e lul os doir r.--r:istratlores para o registrador de pipelinc ID/EX. Não prc-cisamos de todos os três operandos, mas simprifica o COfltrtrrr. r,-rlnicr t.d.s os três.
ffi
ETSEVIER
Melhorando o Desempenho com pipelining 298
FIGURA 6'13 Ex: o terceiÍo esüɧio do pipe de uma instrução load, destacando as partes do caminho de dados da Figura6'11 usadas nesúe estágio do pipe. O registrador é acrescentado ao imediato com sinal esiendido, e a soma é colocada no registrador depipeline EX 4EM.
l ' Busca de instruções.' a parte superior da Figura 6.12 mostra a instrução sendo lida da memória
usando o endereço no PC e depois colocada no registrador de pipeline IF/ID. O registrador depipeline IF/ID é semelhante ao registrador de instrução na Figurá 5.26. oendereço do pC é in-
crementado em 4 e depois escrito de volta ao PC, para que fique pronto para o próximo ciclo de
clock. Esse endereço incrementado também é salvo no registrador de pipeline IFAD caso seja
necessário mais tarde para uma instrução, como beq. o cómputador raô tem como saber que
tipo de instrução está sendo buscada, de modo que piecisa se preparar para qualquer instrução,
passando informações potencialmente necessárias pelo pipeline.
2' Decodi/icação de instruções e leitura do banco de registradores: Aparte inferior da Figura
6'12 mostra aparte relativa à instrução do registradorãe pipeline IF/ID, fornecendo o 
"u-poimediato de l6 bits, que tem seu sinal estendido para32bits, e os números dos dois registrado-
res para leitura' Todos os três valores são armazenados no registrador de pipeline ID/EX, assim
como o endereço no PC incrementado. Novamente, transferimos tudo qu" porau ser necessáriopor qualquer instrução durante um ciclo de clock posterior.
3' Execução ou cálculo de endereço.'a Figura 6.13 mostra que a instrução load lê o conteúdo do
registrador I e o imediato com o sinal estendido do regislrador de pipeline ID/EX e os soma
usando a ALU. Essa soma é colocada no registrador de pipeline Bxtr,lBtrrt.
4' Acesso à memória: aparte superior da Figura 6.14 mostra a instrução load lendo a memória de
dados por meio do endereço vindo do registrador de pipeline EX/MEM 
" 
.urr"gurráo ;;;;ã;
no registrador de pipeline MEM/!VB.
5 ' Escrita do resultado.' a parte inferior da Figura 6.14 mostra a etapafinal: lendo os dados do re-gistrador de pipeline MEM/WB e escrevendo-os no banco de registradores, no meio da figura.
Essa revisão da instrução load mostra que qualquer informação necessária em um estágio poste-
rior do pipe precisa ser passada a esse estágio por meio de um iegistrador de pipeline. A revisão de
294 Organização e PÍojeto de Gomputadores ELSEVIER
tlwrH'§tu&
ssr,@
FIGURA 6.14 MEM e tYB: o quaÉo e quinto estágios do pipe de uma instrução load, destacando as par
tes do carninho de dados da FiÉura 6.11 usadas neases estáglos do pipe. A memória de dados é lida por
meio do endereço no registrador de pipeline EXMEM, e os dados são colocados no registrador de pipeline MEMIÇVB. Em
seguida, os dados são lidos do regiskador de pipeline MEI\íWB e escritos no banco de registradores, no meio do camiúo
de dados.
uma instrução store mostra a semelhança na execução da instrução, bem como a passagem da infor-
mação para os estágios posteriores. Aqui estão os cinco estágios do pipe da instrução store:
l. Busca de instruções: a instrução é lida da memória usando o endereço no PC e depois é coloca-
da no registrador de pipeline IF/ID. Esse estágio ocorre antes que a instrução sejã identificada,
de modo que a parte superior da Figura 6.12 funcionapaÍa store e também para load.
2. Decodfficação de instruções e leitura do banco de registradores.' a instrução no registrador
de pipeline IF/ID fornece os números de dois registradores para leitura e estende o sinal do
ffi
Et§EVIm Melhorando o Desempenho com pipelining 295
imediato de 16 bits' Esses três valores de 32 bits são armazenados no registrador de pipelineID/EX' A parte inferior da Figura 6.12 parainstruçoes làad também mostra as operações dosegundo estágio para stores. Esses dois p.i*"iror 
".iãÁi"r .a" executados por todas as ins-truções, pois é muito cedo para saber o tipo da instruçío.
3 ' Execução e cálculo de endereço: a Figura 6.15 mostra a terceira etapa; o endereço efetivo é co-locado no regisrrador de pipeiine pXTUfiU.
4' Acesso àmemória: aparÍesuperiordaFigura 6.16 mostraosda(qsse§(ses§,§\ss\t\§\N§\b..§\se§te que sregrs\raüor tÀntenüo os ôaôos a serem a.mur"rados foi lido .rn,r- estágio an-terior e armazenado no ID/EX. A única,lr*.Jlà;;i.pãliuilir* 
". 
d"d", à;ã*" o estágioMEM é colocar os dados no registrador de pipeline ÉLÃrivr no esrágio EX, assim como ar-mazenar o endereço efetivo em EXÀzIEM.
5 ' Escrita do resultado a parte inferior da Figura 6.16 mostra a última etapa dostore. para essainstrução' nada acontece no estágio de escita do resultadJ. como cada instrução por trás dostore já está em progresso, não temos como acelerar essas instruções. Logo, uma instrução pas-
::Jfi:T""#1?,:I::TJÍ::,T:.n"j" nada afazer, pois as instruçoe. poí",io,".1a 
"stáo 
p,o,_
A instrução store novamente ilusha que, para passar algo de um estágio anterior do pipe para umestágio posterior, a informação precisa .". áôto*au 
"-;;";;;rdor de pipeline; casà contrário, ainformação é perdida quando a próxima instrução entrar nessã estágio do pipeline. para a instruçãostore' precisamos passar um dos registradores lidos ,o ..6i;i;;ara o estágio MEM, onde é arma_zenado na memória' os dados foram colocados inilq#;;"êisÍador de pipeline ID/EX e de-pois passados para o registrador de pipeline DíMEM.
fll;ffinT:H.Iil*l?*,;i'#fí:j'".l,,'ilffff:h:1ffJ§,ffiH,:;HTÍ:1":1.:H::,",I:ã,;.Ti1T;:*f.rui
296 Organização e Projeto de ComputadoÍes ELSEVIER
t,l
FIGURA c.16 MEM e WB: o quarto e quinto estágios do pipe de uma instrução store. No quarto estágio,
os dados são escritos na memória de dados para o store. Observe que os dados vêm do registrador de pipeline E)íMEM e
que nada ó mudado no registrador de pipeline MEM/WB. Quando os dados são escritos na memória, não há nada mais para
a instrução store fazer, de modo quc nada acontece no estágio 5.
Load e store ilustram um segundo ponto importante: cada componente lógico do caminho de da-
dos 
- 
como memória de instruções, portas para leitua de registradores, ALU, memória dc dados c
porta para escrita de registradores 
- 
só pode scr usado dentro de um único esiágio do pipeline. Caso
contrário, teríamos um hazard estrutural (ver página 282). Logo, esses componentes e seu controle
podem ser associados a um único estágio do pipeline.
Agora, podemos dcscobrir um bug no projeto da instrução load. Você conseguiu ver? Qual rcgis-
trador é alterado no estágio final da leitura? Mais especificamcnte, qual instrução fornece o número
do registrador de escrita? A instrução no registrador de pipeline IFiID fomccc o número do registra-
dor de escrita, embora cssa instrução ocorra consideravelmente depois da instrução load!
Melhorando o Desempenho com pipelining
Logo' precisamos preseryar o número do registrador de destino da instrução load. Assim comostore passou o conteúdo do registrador do ID/ú para o*gir;;"d". de pipeline EX/MEM para usono estágio MEM' load precisa purru. o númerodo registrad"o.a"iozpx por EX/MEM para o regis-trador de pipeline MEM/!VB, pu'u o uso no estágio ú8. outru maneira de pensar sob.e u passagemdo número de registrad?t Í q*, para compartilhar o caminho de dados em pipeline, precisávamospreservar a instrução lida durantc o estágià IF, de 
-ooo qr" .JJu ..grrt.uaor de pipeline contenhauma parte da instrução necessária pu.u 
"ir" estágio . pu.u o. ".,,lgio, posteriores.A Figura 6. l7 mostra a versão óorreta 0"._",rr,"n? ae daaÀ plr.undo o númcro do registradorde escrita primeiro para o registrador ID/EX, depois para o registrador ExlMEM, e finalmente
FlGURA6.17oGaminhodedadosempipetinecorrigido*
trador de escrita agora vem do registrador de pip"rin" utenalwe Jira .";;.ilo:: 
.o 
número a"l.eir*à". e passado do estágio do pipe IDaté alcançar o registraclor de pipeúne uBurwri, u.,....ntunao mais 5 bits aos três últimor..girr.uaà."., àJpip.un". Esse novo caminho apare-ce em destaque.
FlGURA6.18ApaÉedocaminhodedadosnaFi§ura6.1?usada...*
298 Organização e Projeto de Computadores ELSEVIER
para o registrador MEM/WB. O número do registrador é usado durante o estágio WB para espe-
cificar o registrador a ser escrito. A Figura 6.18 é um único desenho do caminho de dados corre-
to, destacando o hardware utilizado em todos os cinco estágios da instrução load word nas Figu-
ras de 6.12 a 6.14. Ver na Seção 6.6 uma explicação de como fazer ainstrução branch funcionar
como esperado.
Representando pipelines gÍaficamente
Pipelining pode ser dificil de entender, pois muitas instruções estão executando simultaneamente em
um único caminho de dados em cada ciclo de clock. Para ajudar na compreensão, existem dois esti-
los básicos de figuras de pipeline: diagramas de pipeline com múltiplos ciclos de clock, comoa Figu-
ra 6. I 0, e diagramas de pipeline com único ciclo de clock,como as Figuras de 6.12 a 6.l6.Os diagra-
mas com múltiplos ciclos de clock são mais simples, mas não contêm todos os detalhes. Por exem-
plo, considere a seguinte seqüência de cinco instruções:
lw $10, 20($1)
sub $11, $2, $3
add $12, $3, $4lw $13, 24($1)
add $14, $5, $6
A Figura 6.19 mostra o diagrama de pipeline com múltiplos ciclos de clock para essas instruções.
O tempo avança da esquerda para a direita na horizontal, semelhante ao pipeline da lavanderia, na Fi-
gura 6.1. Uma representação dos estágios do pipeline é colocada em cada parte do eixo de instruções,
ocupando os ciclos de clock apropriados. Esses camiúos de dados estilizados representam os cinco
estágios do nosso pipeline, mas um retângulo indicando o nome de cada estágio do pipe também fun-
Tempo (em ciclos de clock)
cc1 cc2\ cc3
\
\
cc4 cc5 cc6 cc1 ccz cC3
Ordem de
execução
do programa
(em instruções)
lw $10,20($1)
sub $1 1, $2, $3
add $12, $3, $4
Iw $13, 24($1)
add $14, 95, g6
FTGURA 6.19 DiagFama de pipeline com múltiplos ciclos de ctocNr das dnco instruções. Esse esrilo de representação de pipeli-
ne mostra a execução completa das instruções em uma única figura. As instnrções são listadas por ordem de execuçâo, de cima para baixo, e os
ciclos de clock se movem da esquerda para a direita. Ao contnirio da Figura 6.4, aqui, mostramos os registradores de pipeline entre cada estiígio.
A Figura 6.20 mostra a maneira tradicional de desenhar esse diagrama.
ffi
EISEVIER,
Melhomndo o Desempenho com pipelining 29g
Tempo (em cíclos de clock)
cc 1 cc2 cc3 cc4 CC5 CC6 ccl ccz cc 3Ordem de
execução
do programa
(em instruções)
lw $10, 20(91)
sub g1 1, 92, g3
add $12, 93, g4
lw $13, 2a(gt)
add $14, $5. $6
Busca de
instru@s
Decodificação
dê instruções ExtruÉo Acêsso
aos dados
Escrih do
rêsultado
Eusca de
instruÉes
Dêcodilicaçao
de instruços Execlrçâo
Acesso
aos dados
EscIita do
resultado
Buma de
instruçóes
Decodificaçao
de instru@ês Execuçáo
Amss
aos dados
EsÍita do
resultado
Bus€ de
instÍuÉês
DecodiÍicaÉo
de instÍu@es Execuçào Aesm
aos dados
Escrila do
resuhado
Busca d€
instruçõ€s
DemdiÍiraçao
dê instruQoês Exeflçâo
Acesso
aos dados
Escrita do
resullado
ciona bem' A Figura 6'20 mostra a versão mais tradicional do diagrama de pipeline com múltiplos ci-clos de clock' observe que a Figura 6.19 mostra os recursos fisios utilizàdlos em cada estágio, en-quanto a Figura 6'20 usa o nome de cada estágio. usamos os diagramas com múltiplos ciclos declock para oferecer uma.idéia das situações de [ipelining.os diagramas de pipeline de ciclo único de .to"t 
-ori.am o estado do caminho de dados inteirodurante um único ciclo de clock, e normalmente todas as cinco instruções no pipeline são identifica-das por rótulos acima de seus respectivos estágios do pipeline- uru-o, esse tipo de figura para mos-trar os detalhes do que está acontecendo dentro ao pipeline durante cada ciclo de clock; normalmen-te' os desenhos aparecem em grupos, para mostrar a operação do pipeline durante urna'seqüência deciclos de clock' um diagrama ae cictà único de cloct\eprese;;;., fatia vertical de um conjunrodo diagrama com múltiplos ciclos de clock, ,no.rruJo(r*ao ãu-iot o de dados em cada uma dasinstruções do pipeline no ciclo de clock doig";;. p;r\ü;;a Figura 6.21 mostra o diagramacom ciclo único de clock correspondente ao ci-clo a. .ro.t àul iig*u. 6.19 e6.20. obviamente, osdiagramas com único ciclo de clock possu"- 
-"i. a"àirã ;;;r* muiro mais espaço pa.ra mos-trar o mesmo número de ciclos de clock. A Seção f "afr"n rá;;à" o aprendizado,, incluída no cDcontém os diagramas com ciclo único de clock .oo.rponoÀrrt., a essas duas instruções, além deexercícios pedindo que você crie tais diagramas para outra seqüência de código.
ii|ürl;1.ij3"ma de pipetine com múttiplos eiclos de crock rradieionar, corn r. 
"-n"oiffi
um grupo de alunos discutia sobre a eficiência de um pipeline de cinco estágios quando um delesapontou que nem todas as instruções estão ativas 
"._.uàu otagio do pipeline. Depois de decidir ig-norar os efeitos dos hazards, eles fizeram as cinco uti.-uç0".?r"g.rir. euais delas estão corretas?
1' Permitir que jumps, branches e instruções da ALU utilizem menos estágios do que os cinco ne_cessários pela instrução load aumentara o d"re-p"Joãá prp.r." sob todas as circunstâncias.
2' Tentarpermitir que algumas instruções utilizem menos ciclos não-ajuda, pois avazãoé deter-minada pelo ciclo do clock; o númeio de estágios a" pip" p", instruçâo afàta alatêrr.iu, e não a.
3' Permitir que jumps, branches e operações da ALU utilizem menos ciclos só ajuda quando nemloads nem stores estão no piperine, dá modo que os beneficios são pequenos.
4' você não pode fazer comque as instruções da ALU utilizem menos ciclos, devido à escrita do
[#Í,?#::'_'JâTj|:e jumps podem utitizar-"ro, "i"los, de modo lr" ã.i." arguma
Verifique
você mesmo
3OO Orsanização e Projeto de Gomputadores ELSEVIER
add $14, $5, $6 lw $13, 2a ($1) add $12, $3, $4, $11 sub $1 1, $2, $3 lw $1 0, 20($1)
Busca de instruções DecodiÍicaçáo de instruções Execução Escrita do
FIGURA 6.21 O diagfiama com ciclo único de clock Gorrospondente ao ciclo de clock 5 do pipeline das Ftglu]as 6,19 e 6.2O.
Como você pode ver, uma figura com ciclo único de clock é uma fatia vertical de um diagrama com múltiplos ciclos de clock.
\
5. Em vez de tentar fazercom que\s instruções utilizem menos ciclos de clock, devemos explo-
rar um meio de tornar o pipelinelmais longo, de modo que as instruções utilizem mais ciclos,
porém com ciclos mais curtos. Isso poderia melhorar o desempenho.
No computador
6600, talvez
ainda mais do
que em qualquer
computador
anteior, o
sistema de
controle é a
diferença.
James Thomton,
Design of a
Computer: The
Control Data 6600,
1970
Gontrole de um pipeline
Assim como acrescentamos controle ao caminho de dados simples na Seção 5.4, agora acrescenta-
mos controle ao caminho de dados de um pipeline. Começamos com um projeto simples, que vê o
problema por meio de óculos cor de rosa;nas Seções de 6.4 a 6.8, removemos os óculos para revelar
os hazards do mundo real.
O primeiro passo é rotular as linhas de controle no caminho de dados existente. AFigxa 6.22
mostra essas linhas. Pegamos o máximo possível emprestado do controle para o caminho de dados
simples da Figura 5.17. Emparticular, usamos a mesma lógica de controle daALU,lógica de desvio,
multiplexador do registrador destino e linhas de controle. Essas funções são definidas na Figura
5.l2,Figara 5.16 e Figura 5.18. Reproduzimos as principais informações nas Figuras 6.23 a 6.25
parafacilitaÍ o acompanhamento do restante do texto.
Quanto à implementação com ciclo único discutida no Capítulo 5, consideramos que o PC é
escrito a cada ciclo de clock, de modo que não existe um sinal de escrita separado para o PC. Pelo
mesmo argumento, não existem sinais de escrita para os registradores de pipeline (IF/ID, ID/EX,
EX/MEM e MEM/WB), pois os registradores de pipeline também são escritos durante cada ciclo
de clock.
resultado
ffi
EI.SEVIER
Melhorando o Desempenho com pipelining 301
cà ,\,.1:
'1-
,)'rÂi.i.;
FIGURA 8.22 O Gaminho de dados êm Pipeline da Flg!úra 6.17 com sinais de corÉrole identificados. Esse caminho de dadostoma emprestado a lógica de conkole para a origem do PC, o número do registrador destino e o controie da ALU, do Capítulo 5. observe que
agora precisamos do campo funct (código de função) de 6 bits da instrução no estígio EX como entrada para o controle da ALU, de modo que es-
ses bits também precisam ser incluídos no registrador de pipeline ID/EX. Lembre-se de que esses 6 bits também são os bits menos significativosdo campo imediato da instrução, de modo que o registrador de pipeline ID/EX pode fomecê-los a partir do campo imediato, já que a extensão do
sinal deixa esses bits inalterados.
LW 00 load woÍd xxxxxx add 0010
SW 00 store word xxxxxx add 0010
Branch equal 01 branch equal xxxxxx subtract 0110
Tipo R 10 add 100000 add 0010
Tipo R 10 subtract 100010 subtract 0110
Tipo R 10 AND 100100 and oooo
Tipo R 10 OR 100101 or 0001
Tipo R 10 set on less than 101010 set on less than ot77
FIGURA 6'23 uma Gópia da Figlrra 5'12. Essa figura mostra como os bits do controle da ALU são definidos dependendo dos bits de con-trole OpALU e dos diferentes códigos de função para instruções tipo R.
3O2 Organização e pÍojeto de ComputadoÍes
ELSE\1ER
RegDst O número do registrador destino para a entrada
Registrador para escrita vem do campo rt (bits 20:16).
O número do registrador destino para a entrada Registrador para
escrita vem do campo rd (bits 15:11)-
EscreveReg Nenhum. (J registrador na entrada Registrador para escrita é escrito com o
valor na entrada Dados para escrita.
OrigALU O segundo operando da ALU vem da segunda saída do
banco de registradores (Dados da leitura 2).
O segundo operando da ALU consiste nos 16 bits mais baixos da
instruÇão com sinal estendido.
OrigPC O PC é substituÍdo pela saída do somador que calcula
o valor de PC + 4.
O PC é substituído pela saÍda do somador que calcula o destino do
desvio.
LeMem Nenhum. O conteúdo da memória de dados designado pela entrada
Endereço é colocado na saída Dados da leitura.
EscreveMem Nenhum. O conteúdo da memória de dados designado pela entrada
Endereço é substituído pelo valor na entrada Dados para escrita.
MemparaReg O valor enviado para a entrada Dados para escrita do
banco de registradores vem da ALU.
O valor enviado para a entrada Dados para escrita do banco de
registradores vem da memória de dados.
FIGURA 6'24 uma Gópia da Fi§ura 5.16. A função de cada um dos sete sinais de controle é definida. As linhas de controle da ALU(opALU) são definidas na segunda coluna da Figura 6.23. Quando um controle de I bit para um multiplexador bidirecional é ativado, o multiple-
xador seleciona a entrada correspondente a l. Caso contrário, se o controle for desativado, o multiplexador seleciona a entrada 0. observe queOrigPC é conholado por uma porta lógica AND na Figu ra 6.22. Se o sinal Branch e o sinal Zero da ALU estiverem ativos, então OrigpC é I ; casocontrário, ele é 0' O controle define o sinal Branch somente durante uma instrução beq; caso conhário, o OrigpC é 0.
Formato R 7 L 0 0 0 r) 0 7 0
lw 0 0 U 7 0 7 0 7 I
sw X 0 0 7 0 0 7 0 x
beq x rl L 0 7 0 0 0 X
FIGURA 8'25 os Yalores das linhas de controle são igfirais aos da Figura 5.18, mas foram reorg]anizados em três grupos,corÍespondentes aos três últimos estágios do pipeline.
Para especificar o controle para o pipeline, só precisamos definir os valores de controle durante
cada estágio do pipeline' Como cada linha de controle está associada a um componente ativo em ape-
nas um estágio do pipeline, podemos dividir as liúas de controle em cinco grupos, de acordo com o
estágio do pipeline.
l' Busca de instruções.' os sinais de controle para ler a memória de instruções e escrever o pC
sempre são ativados, de modo que não existe nada de especial para controlar nesse estágio dopipeline.
2' DecodificaÇão de instruções/leitura do banco de resstradores.. como no estágio anterior, a
mesma coisa acontece em cada ciclo de clock, de modo que não existem linhas de controle op-
cionais para definir.
3. Execução/cálculo de endereço.'os sinais a serem definidos são RelDst, opALU e origALU(ver Figuras 6.23 e 6.24)- Os sinais selecionam o regisÍador destino, a operação da ALU e Da-
dos da leitura 2 ou um imediato com sinal estendido para a ALU.
4' Acesso à memória: as linhas de controle definidas nesse estágio são Branch, LeMem e Escre-
veMem. Esses sinais são definidos pelas instruções branch equal, load e store, respectivamen-
te. Lembre-se de que o OrigPC na Figura 6.24 seleciona o próximo endereço seqüencial, a
menos que o controle ative Branch e o resultado da ALU seja zero.
ffi
EI.SE/IER Melhorando o Desempenho com pipelining 303
5. Escrita do resultado..as duas linhas d
;;*ííf â:Ííüí;rffi ;HH:;JI :f #"y:I!?r*ri;*l:*,*Tffi l"."ilr.
como a uÍllização de um pipeline o caminho de dados deixa inalterado o significado das li-nhas de controle' podemos 
"ui o. *"r-o. valores de controle de antes. A Figura 6.25 tem os
âTfi:iJlores do capítulo 5, mas agora as nove linhas de controre estão agrupadas por esrágio
A implementação do controle significa definir as nove liúas de controle para esses varores em
;fg,";:t*T:?,?*""1ff;:;tn*,X1"*',-r['0"á'ÍJ.,..oe*,",áoã..ãeltradoresdo
como as liúas de controle começam * o e-sláqio EX, podemos criar a informação de controledurante a decodificaeio d1 instrução. ÀFrg* 6.2õ mostra;r;;;r", sinais de controle são usadosno respectivo estágio do pipeline à medida"que a instrução ," ,,,o* p"to piperine, assim como o nú-mero do registrador destino para loads se move pelo prpeline au rigrru 6.17. AFigura 6.27 mostra ocamiúo de dados completo, co- or r"girt uaoràs a" piperir" 
"ràroioos e com as linhas de controleconectadas ao estágio apropriado.
E Hazards r" /rrs e roÍwardins
os exemplos da seção anterior mostram o poder da execução em pipeline e como o hardware rcalizaatarefa' Agora é hora de retirarmos os ócuiÀ cor de rosa. 
"*u-iiur-os o que acontece com os pro-gramas reais' As instruções nas Figuras de 6.19 a 6.21 eramirã"p"ra"rtes; neúuma delas usava osresultados carculados por qualquei uma d.as outras. Mesmo ur.irr, na seção 6.1, vimos que os ha_zards de dados são obstácuios puruu.r".riao empipeline.
vejamos uma seqüência com muitas dependências, indicadas com rearce:
O que você quer
dizer, por que
isso precisa ser
criado? É uma
alternativa. Você
precisa criar
alternativas.
Douglas Adams,
Hitchhikers Guide
to the Galary,
1979
vvú:
i
-*--1*-*-.*-*----*
)
f-**-*.*.*-*--
M
t*-
r*-
:'**
FlGURA6.26AslinhasdecontrolePa]ao3trêsestág[osfinais.oo*ffi
trole são usadas na fase EX' com as tin"o rinrr* ãJcontrole restantes purruãu._uoiurte para o registrador de pipelineffiri*,'ffiTil,|:T.I#ç;*"o"r"toã"à-u,uau,duranre 
".,ãeJrriar,r, e as duas úrrimas sãopassadas para
MEM,,?V3
3O4 Organização e projeto dê Computadorêg
ELSEVIER
f*'_*-*___iie::.*ir
ID/EX
r-l
lv;ri
:^"-i
i
I5Xi
EtuM Dâd6
' pamEfon
kdâ
&dos
FlGURA6.27ocaminhodêdadosempipelinedaFtgu]a6.22,comossinaisdeconttole"on*ffi
ffi::Í#ffiffilr".llf,lllf;,.::1,:::*:Hfg+a:,,.,fg,ãii_li **rios são criados duranre o estágio de decodincação de ins_truções e depois colocados no registrador de pipeline ID/EX. As linhas de conrrole para cada esüígio 
" 
,,;;:tJ:ffi;:ffi[::H:;Y:i;restantes depois disso são passadas para o próximo estágio do pipeline.
sub $2, $1,$3
and $12,92,95
or $13,$6,$2
add $14,$2,$2
sw $15,i00(92)
# Registrador g2 escrito por sub# ls operando ($2) depende de sub# 2e operando (92) depende de sub# Le ($2) & z, ($z) dependem de sub# Base (92) depende de sub
As quatro últimas instruções são todas dependentes do resultado no registrador $2 da primeira instru-ção' se o registrador $2 tivesse o valor ld antes da instrução subtract e -20 depois dela, o programa-dor desejaria que 
-20 fosse usado nas instruções seguintés qrr" ," referem ao registrador g2.como essa seqüência funcionaria com rro..o pif"ünez Á Figura 6.2g ilustra a execução dessasinstruções usando uma representação de pipeline com múltiploí"i"lo, d" clock. para demonstrar aexecução dessa seqüência de instruções em nosso pipeline atual, o topo da Figura 6.2g mostra o valordo registrador $2, que muda durante o ciclo de clocki, q""rd;;';rtrução sub escreve seu resultado.umhazardem potencial pode ser resolvido peto p.opto ao rru.ã*ur" do banco de registradores: oque acontece quando um registrador é lido e escritó ró 
-..-o ciclo de clock? considãramos que aescrita está na primeira metade do ciclo de clock e a leitura está na segunda metade, de modo que a lei-tura fornece o que foi escrito' como acontece para muitas implementações dos bancos de registrado-res, não temos hazard, de dados nessa situação.
A Figura 6'28 mosha que os valores lidos para o registrado r $z nãoseriam o resultado da instru-ção sub' a menos que a leitura ocolTesse durante o ciclo de clock 5 ouposterior. Assim, as instruçõesque receberiam o valor correto de -20 são add e sr,; :rs instruções and e or receberiam o valor incorreto
ffi
ETSEVIER.
Melhorando o Desempenho com pipelining 305
Tempo (em ciclos de clock)
Valor do CC 1 CCz
registrador $2: 10 .10
CC4 CCs CC6
10 10t-20 
-20
CC8 CC9
-20 -20
CC3
10
cc7
-20
Ordem de
execução
do programa
(em instruções)
sub S2. $1, $3
and $12, S2, $5
or$13, $6, $â
add $14, §2, S2
sw $15, 100{S2i
FIGURA 6.28 Dependências em pipeline em uma sêqüência de cinco instruções usando caminhos de da.
dos simplificados para mosttar as dependências. Todas as ações dependentes são mostradas emciry1a,e,,CC f,
no alto da figura significa o ciclo de clock i. A primeira instrução escreve em $2, e todas as instruções seguintes lêem de $2.
Esse registrador é escrito no ciclo de clock 5, de modo que o valor correto esüi indisponível antes do cicú de clock 5. (Uma
leitura de um registrador durante um ciclo de clock retorna o valor escrito no final da primeira metade do ciclo, quando
ocorre tal escrita.) As linhas coloridas do caminho de dados do topo para os inferiores mostram as dependências. Aquelas
que precisam retomar no tempo são os hazards de dados do pipeline.
de l0! Usando esse estilo de desenho, esses problemas se tornam aparentes quando uma liúa de de-
pendência retorna no tempo.
Mas examine cuidadosamente aFigua6.2S.Quando éproduzido realmente os dados da instrução
sub? O resultado está disponível no final do estágio EX, ou ciclo de clock 3. euando os dados são
realmente necessários pelas instruções and e or? No início do estágio EX, ou nos ciclos de clock 4 e
5, respectivamente. Assim, podemos executar esse segmento sem stalls se simplesmente os dados
sofÍeremíorwarding assim que estiverem disponíveis para quaisquer unidades que precisam deles
antes de estarem disponíveis para leitura do banco de registradores.
Como funciona o forwarding? Parasimplificar o restante desta seção, consideramos apenas o de-
safio de forwarding para uma operação no estágio EX, que pode ser uma operação da ALU ou um
cálculo de endereço efetivo. lsso significa que, quando uma instrução tenta usarum registrador em
seu estágio EX, que uma instrução anterior pretende escrever em seu estágio WB, ,ru ,"ulidud" preci-
samos dos valores como entradas para a ALU.
Uma notação que nomeia os campos dos registradores de pipeline permite uma notação mais pre-
cisa das dependências. Por exemplo, "ID/EX.RegistradorRs" refere-se ao número de um registrádor
cujo valor se encontra no registrador de pipeline ID/EX; ou seja, aquele da primeira porta de leitura
do banco de registradores. A primeira parte do nome, à esquerda dó ponto, é o ,o-" do registrador
de pipeline; a segunda parte é o nome do campo nesse registrador. Uiando essa notação, os dois pa-
res de condições de hazard são
3OG Organização e projeto de ComputadoÍes
ELSEVIER
I a. EX/MEM.RegistradorRd : ID/EX.RegistradorRs
1 b. ExÀ{EM.RegistradorRd : ID/EX. RegistradorRt
2a. MEM/IVB.RegistradorRd : ID/EX.RegistradorRs
2b. MEM/lvB.RegistradorRd : ID/EX.RegistradorRt
o primeiro hazard na seqüênci a da página 304 está no registrador g2, entre o resultado de sub$2 
' 
$ 1' $3 e o primeiro operando de leitura áe and g 12, g2, $5. üsse hazard pode ser detectado quando
a instrução and está no estágio EX e a instrução anterior está no estágio MEM, de modo que este é ohazard la:.
Ex/MEM.RegistradorRd : ID/EX.RegistradorRs : g 2
DEIECçÃO DE DEPENDÊNCh
Classifique as dependências nesta seqüência dapâgina304:
sub $2, $1, $l # Registrador g2 escrito por suband $12, 52, gU # Ls operando ($z) depende de subor $tl, 96, 92 # 2! operando ($2) depende de subadd $14, 92, g2 # 1s ($2) & 20 (92) dependem de subsw $15, 100(92) # Index (g2) depende de sub
conforme já mencionamos, o sub-and é um hazard,tipo la. os outros hazards são
! O sub-or étrnhazardtipo2b:
MEI\OWB.RegistradorRd : ID/EX.RegistradorRt : g 2
I As duas dependências em sub-add não são hazards,pois o banco de registradores fornece osdados apropriados durante o estágio ID de add.
r Não existe hazard de dados entre sub e sw, porque sw lê $2 no ciclo de clock depoisque sub es-creve 92.
como algumas instruções não escrevem em registradores, essa política não é exata;às vezes, po-deria haver forwarding desnecessário. umasolução é simplesmente verificar se o sinal EscreveReg
estará ativo: examinando o campo de controle wB do registrador de pipeline durante os estágios EXe MEM, é possível determinar se EscreveReg estií ativo. Além disso, o MIpS exige que cada uso de$0 como operando deve gerar um valor de operando 0. se uma instrução no pipeline tiver g0 comoseu destino (por exemplo, s I I $0, $ 1 ,2), queremos evitar o forwarding ao ,à ,ao,. pàssivelmentediferente de zero. Não encaminhar os ,.rritudo, destinados a $0 libera o programador assembly e ocompilador de qualquer requisito para evitar o uso de g0 como destino. As cpndições anteriores, por-tanto, funcionam corretamente desde que acrescentemos Ex/NÍEM.RegistradorRd * 0 à primeiracondição de hazard, e MEI\{/WB.RegisúadorRd * 0 à segunda.
Agora que podemos detectar os hazards, metade do põblema está resolvido 
- 
mas ainda precisa-
mos fazer o forwarding dos dados corretos.
A Figura 6'29 mostra as dependências entre os registradores de pipeline e as entradas da ALUpara a mesma seqüência de código da Figura- 6.28. A mudança é que a dependência começa por umregistrador de pipeline, emvezde esperai pelo estágio we pà* 
"r"rever 
no banco de registradores.
ffi
ET-SEVIER
Assim, os dados exigidos existem a tempo para as instruções posteriores, com os registradores de 
pi-
peline mantendo os dados para forwarding'
se pudermos pegar as êntradas da ALU de qualquer registrador