Algoritmo de Tomasulo

Em arquitetura de computadores, o Algoritmo de Tomasulo é um algoritmo de hardware para distribuição dinâmica de tarefas, permitindo a execução simultânea de instruções com o uso de unidades de execução múltiplas. O algoritmo permite que a execução de uma instrução comece antes que a execução da instrução anterior seja concluída, o que é conhecido como execução fora-de-ordem(out-of-order execution).

Foi desenvolvido por Robert Tomasulo na IBM em 1967 e foi implementado pela primeira vez em uma unidades de ponto flutuante de um mainframe IBM System/360 modelo 91.

O Algoritmo de Tomasulo permitiu inúmeras inovações, como a renomeação de registradores em hardware, estações de reserva para todas as unidades de execução, e um barramento de dados comum (common data bus ou CBD) no qual os valores computados são enviados para todas as estações que podem precisar deles. Esses avanços permitiram um grande aumento de performance na execução paralela de instruções, que antes só seria possível por meio de um algoritmo de marcador(scoreboarding) ou outros algoritmos ultrapassados. É considerado um dos grandes avanços da engenharia e ciência da computação.

Por ter desenvolvido o algoritmo, Robert Tomasulo recebeu, em 1997, o Prêmio Eckert–Mauchly.^[1]

Implementação[editar | editar código-fonte]

Os conceitos necessários para a implementação do algoritimo de Tomasulo são:

Barramento Comum de Dados(Common Data Bus)[editar | editar código-fonte]

O Barramento Comum de Dados (CDB) conecta as estações de reserva diretamente às unidades funcionais. Nas palavras de Tomasulo, "preserva a precedência enquanto estimula a concorrência".^[2]^:33 Isso tem dois efeitos importantes:

As unidades funcionais podem acessar o resultado de qualquer operação sem um registrador de pontos flutuantes, permitindo que múltiplas unidades de execução possam prosseguir com suas tarefas individuais sem precisarem esperar a resolução da contenção de recursos.
A detecção de riscos e o controle de execução são distribuídos, de forma que as estações de reserva controlam quando uma instrução é executada, ao invés de uma única unidade de risco dedicada.

Ordem de instruções[editar | editar código-fonte]

As instruções são atríbuidas sequencialmente, permitindo que os efeitos da sequência de instruções ocorram na mesma ordem que ocorreriam em um processador in-order, apesar das instruções serem executadas fora-de-ordem(out-of-order).

Renomeação de registradores[editar | editar código-fonte]

O Algoritimo de Tomasulo utiliza renomeação de registradores para realizar corretamente a execução fora de ordem(out-of-order). Cada unidade funcional tem apenas uma estação de reserva, que armazena a informação necessária para executar uma única instrução, incluindo a operação em si e os operandos. Os registradores armazenam um valor real ou um valor provisório(placeholder). Esse valor provisório é usado se o valor real estiver indisponível, e indica qual estação de reserva vai produzir o valor real. Quando a unidade é concluída, o valor provisório é imediatamente substituído pelo valor real. A unidade funcional inicia o processamento assim que todos os valores dos operandos para uma instrução forem reais.

Exceções[editar | editar código-fonte]

Durante a execução do programa, podem ocorrer exceções que não fornecem informações suficientes sobre o seu estado. Nesse caso, o processador levanta uma exceção especial chamada exceção imprecisa, ou seja, a origem da exceção não pode ser determinada. Nesse caso, o programa não pode ser re-executado a partir do ponto aonde parou, pois o sistema não consegue determinar qual instrução gerou a exceção.

Aplicações e legado[editar | editar código-fonte]

Por décadas, o Algoritmo de Tomasulo foi pouquíssimo usado fora dos mainframes da IBM. No entanto, seu uso aumentou de forma repentina na década de 1990. Acredita-se que esse aumento foi devido principalmente a 3 razões:

Com a proliferação do cache, a capacidade do Algoritmo de Tomasulo de manter concorrência (mesmo com tempos de carregamento imprevisíveis) se tornou uma vantagem valiosa para processadores.
A distribuição dinâmica de tarefas possibilitou uma melhora muito significativa na performance, ajudando os processadores a lidar com cada vez mais instruções.
A popularização de softwares comerciais fez com que os desenvolvedores não quisessem mais desenvolver e compilar seus programas apenas para um tipo de sistema, e sim para o maior público possível. O O Algoritmo de Tomasulo funciona em qualquer estrutura de pipeline, e assim são necessárias menos modificações para arquiteturas específicas.^[3]

Muitos processadores modernos implementam métodos de distribuição dinâmica de tarefas que são derivados do algoritmo original de Tomasulo, incluindo os processadores Intel e AMD x86-64.^[4]