# Algoritmo de Tomasulo

Estações de reserva, etiquetas de operandos, CDB e evolução por ciclo.

Página: https://resumos.rgo.pt/cadeiras/ac/tomasulo/

Uma soma independente pode ter operandos prontos enquanto uma multiplicação anterior espera. Tomasulo mantém a emissão pela ordem do programa, mas deixa executar as operações prontas nas suas estações. A renomeação distingue resultados de escritas diferentes do mesmo registo. Cada estação guarda uma instrução; a espera distribui-se pelas estações, sem uma fila única atrás da execução.

## O estado de uma estação

Uma estação de reserva guarda uma instrução emitida e os seus operandos. Uma etiqueta identifica quem produzirá cada valor pendente. O CDB, barramento comum de dados, comunica um resultado a todos os consumidores dessa etiqueta.

![Emissão coloca operações nas estações de reserva; unidades calculam quando operandos estão prontos; CDB difunde etiqueta e valor a registos e estações à espera.](https://resumos.rgo.pt/cadeiras/ac/tomasulo/figura-1.svg)

| Campo | Significado |
| --- | --- |
| Busy | A estação está ocupada |
| Op | Operação a executar |
| Vj, Vk | Valores dos operandos que já estão disponíveis |
| Qj, Qk | Etiquetas das estações que ainda produzirão operandos; zero significa disponível |
| Qi, no registo | Etiqueta da última operação emitida que deverá atualizar esse registo; zero se nenhuma pendente |

V e Q descrevem alternativas para cada operando: se Qj não é zero, Vj ainda não contém o operando correto. O valor antigo visível no registo não deve ser usado.

## Emitir, executar e difundir

Ordem de eventos usada nesta página. Emissão escolhe estação livre e captura origens antes de renomear o destino. Execução começa no ciclo seguinte à emissão ou à receção do último operando. Um resultado difunde no ciclo seguinte ao fim da execução. Um CDB serve uma etiqueta por ciclo, com prioridade à instrução mais antiga.

A convenção temporal faz parte do problema. Na prática associada, multiplicação e soma duram ambas dois ciclos, pelo que os resultados não competem pelo CDB e a última difusão ocorre no ciclo 8. Aqui a multiplicação dura três ciclos e cria um conflito de CDB, levando a conclusão ao ciclo 9. Antes de comparar tabelas, confere durações, início de execução e difusão.

1.  **Emitir:** escolher uma estação livre da classe certa. Capturar cada origem: valor se Qi=0, etiqueta se Qi≠0. Só depois atribuir a etiqueta da estação ao Qi do destino.
2.  **Executar:** iniciar quando ambos os Q são zero e a unidade admite uma nova operação. A duração e o intervalo de início seguem o enunciado.
3.  **CDB:** difundir `(etiqueta,valor)`. Estações que esperam essa etiqueta capturam o valor e zeram Q. Um registo só recebe o resultado se o seu Qi ainda for essa etiqueta. Libertar a estação após a difusão.

Se a instrução lê e escreve o mesmo registo, captura a origem **antes** de renomear o destino, porque senão esperaria pelo seu próprio resultado.

## Um exemplo completo

Estado inicial: `f2=2`, `f4=3`, `f6=4`, `f8=5`.

```
I1: f0 = f2 * f4
I2: f2 = f6 + f8
I3: f0 = f0 - f2
```

Uma estação M1 para multiplicação, duas A1/A2 para adição/subtração. Unidades sem pipeline: multiplicação 3 ciclos, adição/subtração 2. Uma emissão por ciclo; execução começa no ciclo seguinte à emissão ou à receção do último operando. Um CDB, com prioridade à instrução mais antiga; difusão no ciclo seguinte ao fim da execução.

| Ciclo | Emissão | Execução | CDB e alterações |
| --- | --- | --- | --- |
| 1 | I1 em M1; Qi(f0)=M1 | Sem ação | Sem ação |
| 2 | I2 em A1; Qi(f2)=A1 | I1:1/3 | I1 já capturou f2=2 |
| 3 | I3 em A2; Qj=M1, Qk=A1; Qi(f0)=A2 | I1:2/3; I2:1/2 | Sem ação |
| 4 | Sem ação | I1:3/3; I2:2/2 | Dois resultados ficam prontos |
| 5 | Sem ação | Sem ação | M1→6; A2 recebe Vj=6, Qj=0; f0 não é atualizado |
| 6 | Sem ação | Sem ação | A1→9; f2=9, Qi=0; A2 recebe Vk=9, Qk=0 |
| 7 | Sem ação | I3:1/2 | Sem ação |
| 8 | Sem ação | I3:2/2 | Sem ação |
| 9 | Sem ação | Sem ação | A2→−3; f0=−3, Qi=0 |

Ideia-chave

A primeira multiplicação não sobrescreve f0 no ciclo 5 porque Qi(f0)=A2, a escrita mais recente. O seu resultado não se perde: a estação A2 recebe-o.

I1 também conserva o f2 inicial, apesar de I2 produzir f2=9; a WAR não força I1 a esperar pela nova escrita.

## Tabela de operandos após emitir I3

| ER | Busy | Op | Qj | Qk | Vj | Vk |
| --- | --- | --- | --- | --- | --- | --- |
| M1 | 1 | mul | 0 | 0 | 2 | 3 |
| A1 | 1 | add | 0 | 0 | 4 | 5 |
| A2 | 1 | sub | M1 | A1 | Por obter | Por obter |

E no banco: Qi(f0)=A2, Qi(f2)=A1. A estação identifica a versão de um valor; não é um número de registo arquitetural.

## Bloqueios e arbitragem

A mesma operação pode esperar por motivos diferentes:

| Situação | Onde espera? | O que permite avançar? |
| --- | --- | --- |
| Nenhuma estação da classe livre | Na fila de emissão, bloqueando as seguintes | Libertar uma estação após difusão |
| Estação ocupada com Qj ou Qk pendente | Na estação, sem ocupar a unidade de cálculo | Receber o operando no CDB |
| Operandos prontos, unidade sem pipeline ocupada | Na estação | A unidade admitir outra operação |
| Resultado pronto, CDB usado pela mais antiga | Na estação, após execução | A próxima oportunidade no CDB |

No ciclo 4 do exemplo, M1 e A1 terminam. M1 difunde no 5, mas A1 conserva o resultado e só difunde no 6. A2 ainda não pode começar no 6: recebe aí o segundo operando e executa a partir de 7. O atraso do CDB chega assim ao consumidor.

Uma estação à espera de operandos continua ocupada, mesmo com a unidade livre. Define também se uma estação libertada pode receber nova emissão no mesmo ciclo ou apenas no seguinte; aplica a mesma ordem de eventos em todo o traço.

O CPI efetivo de um fragmento é ciclos totais/instruções, incluindo o início e a conclusão final. Neste exemplo é 9/3=3, apesar de haver trabalho sobreposto.

## Limites do algoritmo básico

Renomeação resolve WAR/WAW de registos, mas RAW continua a esperar pelo valor. Acessos à memória exigem ordenar endereços e stores relevantes. O CDB é um recurso partilhado.

A versão básica não inclui, por si só, confirmação em ordem nem recuperação de especulação. Para essas propriedades acrescenta-se um reorder buffer. Um resultado pronto pode então esperar pelo commit, e um resultado especulativo não deve tornar-se uma alteração irreversível de memória antes da confirmação.

## Exercícios

Capturar e renomear na ordem certa

Qi(f0)=M1. Emite f0=f0−f2 em A2, com f2 pronto. Indica Qj, Qk e Qi(f0) logo depois.

Pista

O f0 lido é uma versão anterior ao f0 escrito.

Solução

Qj=M1, Qk=0, Vk=valor atual de f2; Qi(f0)=A2. Se retagássemos antes de capturar, A2 esperaria pelo próprio resultado.

Confere a tua resposta:

*   Capturei a etiqueta da origem antes de alterar Qi.
*   A nova estação espera a etiqueta antiga.
*   Atribuí Qi do destino à nova estação.

Erros frequentes

Manter Qi(f0)=M1 até o primeiro resultado sair ou fazer A2 esperar A2.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/ac/tomasulo/#emitir-executar-e-difundir)

Esperar pelos dois operandos

I1: f0=f2×f4; I2: f2=f6+f8; I3: f0=f0−f2. Todos os registos estão inicialmente prontos. Há uma unidade de multiplicação e outra de adição/subtração, ambas sem pipeline, com 2 ciclos de execução. Há uma estação M1 e duas A1/A2. Emite uma instrução por ciclo a partir do ciclo 1; começa a executar no ciclo seguinte à emissão ou à receção do último operando. Difunde no ciclo seguinte ao fim da execução, num CDB que dá prioridade à mais antiga. Em que ciclo se difunde I3?

Pista

I3 espera pelos resultados de I1 e I2, não pelos valores iniciais de f0/f2.

Solução

I1 difunde no ciclo 4 e I2 no 5, sem competir pelo CDB. I3 recebe o último operando no ciclo 5, executa nos ciclos 6 e 7 e difunde no 8. Qi(f0)=A2 impede I1 de sobrescrever o destino, mas A2 recebe o seu valor.

Erros frequentes

Difundir dois resultados no mesmo CDB ou começar EX antes de receber o operando.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/ac/tomasulo/#um-exemplo-completo)

Seguir uma difusão para dois consumidores

Antes do CDB, f0 tem valor antigo 20 e Qi(f0)=A2. A2 tem Qj=M1 e Qk=0, Vk=9. M1 difunde 6. Indica Vj/Qj de A2, valor e Qi de f0, e a origem que uma instrução emitida no ciclo seguinte captura ao ler f0.

Solução

A2 recebe Vj=6 e Qj=0 e passa a ter os dois operandos 6 e 9. f0 mantém valor 20 e Qi=A2, porque M1 não é a etiqueta atual do destino. A instrução nova captura a etiqueta A2, não 20 nem 6. Quando A2 difundir −3, f0 aceita-o se Qi continuar A2.

Confere a tua resposta:

*   Atualizei Vj e Qj de A2.
*   Conservei Qi(f0)=A2 e o valor arquitetural antigo.
*   Dei a uma instrução nova a etiqueta A2 para ler f0.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/ac/tomasulo/#tabela-de-operandos-ap%C3%B3s-emitir-i3)

Uma estação cheia pode bloquear uma instrução independente

Tomasulo com emissão em ordem, uma estação M1 de multiplicação e uma A1 de adição. I1 é mul e ocupa M1 até difundir; I2 é outra mul; I3 é add independente e A1 está livre. Antes de I1 libertar M1, o que acontece a I3?

Pista

Distingue esperar pela emissão de esperar em uma estação.

Solução

I3 não é emitida enquanto I2 bloqueia a fila por falta de estação. Se I2 já tivesse sido emitida para outra estação, I3 poderia executar antes dela quando tivesse operandos e unidade.

*   **I3 espera porque I2 ainda não pode ser emitida..** Neste modelo a emissão segue a ordem do programa, mesmo quando unidades diferentes estão livres.
*   **I3 é emitida logo para A1 porque é independente..** Execução fora de ordem não permite ultrapassar uma instrução ainda na fila de emissão.
*   **I2 ocupa A1 temporariamente..** Uma estação de adição não aceita a multiplicação neste contrato.

Erros frequentes

Confundir emissão em ordem com execução em ordem ou atribuir uma operação a uma estação de classe errada.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/ac/tomasulo/#bloqueios-e-arbitragem)