Algoritmo de Tomasulo

!

Algoritmo de Tomasulo!

!
Em 1967 o cientista Robert Tomasulo da IBM desenvolveu o Algoritmo de Tomasulo que permitiu a introdução do Pipeline e Paralelismo à nível de instrução de forma muito mais eficiente.!

!

!
O algoritmo utiliza o escalonamento dinâmico para realizar o pipeline, onde o hardware determina a ordem de execução das instruções, diferentemente do escalonamento estático, onde a ordem é determinada pelo compilador. Porém o
Escalonamento Dinâmico possui alguns problemas de conflito de dados, que afetam o processamento do programa e podem gerar resultados errados, tais conflitos podem ser do tipo: !
- RAW (Read-after-Write) funciona com o princípio que em um conjunto de 2 instruções, sendo A a primeira e B a segunda e possuindo ao menos um registrador em comum: a instrução B lê um registrador que também é utilizado na instrução A, então a instrução B pegará o dado antigo do registrador, gerando informação desatualizada, o correto seria gravar o valor do registrador da instrução A para somente depois realizar a instrução B.!
- WAW (Write-after-write) funciona de forma que: as instruções A e B possuem ao menos um registrador em comum e a instrução B é executada antes da instrução A, quebrando a ordem correta e gerando dado errado no registrador.!
- WAR (Write-after-Read) funciona de forma que a instrução B escreve em um registrador que é operando de A antes que A consiga lê-lo, então A lerá o valor incorreto que foi escrito por B, ocorre em instruções que gravam resultados muito cedo e outras que lêem muito tarde os operandos.!
!
Tendo em vista o desempenho da maquina, foi desenvolvido então o Algoritmo de
Tomasulo, que foi uma forma de gerenciamento eficiente dos conflitos, a chave do sucesso do algoritmo foi o conceito de renomeação de registradores em conjunto com vários buffers distribuídos pelas unidades funcionais ao invés de buffers centralizados, tais buffers são designados como estações de reserva, guardando os