Renomeação de registradores

Origem: Wikipédia, a enciclopédia livre.

Na arquitetura de computadores, Renomeação de Registradores refere-se a uma técnica utilizada para evitar a desnecessária serialização das operações de um programa, imposta pelo reuso dos registradores por essas operações.[1]

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

Em um computador programas são executados. Programas são compostos por inúmeras instruções (comandos). As instruções de um programa operam sobre valores alocados em registradores. Algumas instruções demoram mais tempos que outras para serem executadas. Ao acabarem de executar, liberam o processador para executarem outras instruções, que, por sua vez, acessaram novamente os registradores. Entretanto, como forma de melhorar o desempenho do computador, as instruções poderão ser executadas em qualquer ordem, observando as unidades de execução especializadas. O problema é que certas instruções têm dependência com outras instruções e isso pode gerar conflitos de dados. Vejamos a tabela 1.

# Instruction
1 R1 = M[1024]
2 R1 = R1 + 8
3 M[1032] = R1
4 R1 = M[2048]
5 R1 = R1 + 2
6 M[2056] = R1

Se todas as instruções executarem sobre um único registrador, ou seja, utilizando o mesmo registrador para recolher e salvar valores, uma instrução sempre precisará esperar a anterior terminar para poder utilizar o registrador, pois a instrução anterior o está utilizando. Mas, se as instruções 4, 5 e 6 utilizassem outro registrador, elas poderiam executar ao mesmo tempo que as instruções 1, 2 e 3, se houvesse processador disponível (tabela 2).[2]

# Instruction # Instruction
1 R1 = M[1024] 4 R2 = M[2048]
2 R1 = R1 + 8 5 R2 = R2 + 2
3 M[1032] = R1 6 M[2056] = R2

Os processadores atuais possuem inúmeros registradores para proporcionar a otimização ofertada pela técnica Register Renaming.

Perigos de Dados ou Conflitos de Dados - Problema principal a ser solucionado[editar | editar código-fonte]

Ocorre quando mais de uma instrução acessa o mesmo registrador, seja para leitura ou para escrita, mas precisa observar certa ordem de instruções, do contrário poderá haver o conflito de dados, que pode ser classificado de três formas:

RAW – Read After Write (Leitura após Escrita/Dependência Verdadeira)[editar | editar código-fonte]

Ocorre quando uma Leitura é feita após uma escrita na sequência de um programa, e portanto, espera recolher o valor colocado lá por essa última escrita em específico, e não uma outra escrita qualquer. O exemplo abaixo é um exemplo de RAW porque a instrução 2 deve recolher o valor 5 e não, por acaso, o valor 10.[1]

# Instruction
1 R1 = 5
2 MEM[100] = R1
3 R1 = 10
4 MEM[200] = R1 + 1

WAW – Write After Write (Escrita após Escrita/Dependência de Saída)[editar | editar código-fonte]

Ocorre quando existem várias instruções gravando valores no mesmo registrador numa determinada sequência. Nesse caso, o registrador deve permanecer com o valor setado pela última instrução da sequência. No exemplo abaixo o registrador R1 deverá ficar com o valor 20, portanto, a instrução 4 deve necessariamente ser a última a ser executada.[3]

# Instruction
1 R1 = 5
2 R1 = 200
3 R1 = 10
4 R1 = 20

WAR – Write After Read (Escrita após Leitura/Anti-dependência)[editar | editar código-fonte]

Ocorre quando um registrador deverá retornar um determinado valor, e após essa instrução, o registrador será alterado, e portanto, precisa-se assegurar que ele não seja alterado antes de retornar o valor para a primeira instrução. No exemplo abaixo, a instrução 3 não pode ser executada antes da instrução 2.[3]

# Instruction
1 R2 = 10
2 R1 = R2 + 5
3 R2 = 43

A dependência de saída e a antidependência são consideradas dependências falsas, visto que a serialização das instruções só é necessária por se utilizar o mesmo registrador nas duas instruções. Esta serialização não precisa ocorrer se houver a Renomeação de Registradores..[4]

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

Levando em consideração que as instruções não podem simplesmente serem executadas serialmente, pois isso seria custoso em termos de tempo,  utiliza-se a técnica da Renomeação de Registradores. Esta técnica consiste em renomear os registradores, aumentando o paralelismo disponível, ou seja, permitindo que duas instruções que antes deveriam ser executadas serialmente possam agora ser executadas concorrentemente pois estão utilizando registradores diferentes.

Equivale a traduzir:

#

Instruction

1

R1 = 5

2

MEM[100] = R1

3

R1 = 10

4

MEM[200] = R1

Para:

#

Instruction

1

R1 = 5

2

MEM[100] = R1

3

R9 = 10

4

MEM[200] = R9

Este método é baseado em uma técnica tradicional de tratamento de conflitos por recursos: a duplicação do recurso. Quando é possível, o compilador promove esta otimização dinamicamente, ou seja, o hardware do processador aloca os registradores dinamicamente. A cada registrador é associado um valor a cada instante de tempo, valor este requerido pelas instruções. Quando um novo valor deverá ser armazenado em um registrador que já está sendo utilizado, um novo registrador é criado para esse valor. O acesso ao valor que deveria estar neste registrador, seguirá um processo de renomeação de registradores: referências à registradores existentes nessas instruções são revisadas, passando a referir-se aos registradores que contêm os valores requeridos.[1]

Entretanto, o número de registradores de uso geral disponíveis para o compilador é limitado e por isso muitos registradores fazem esta renomeação em hardware. No entanto, ainda assim existem limitações:

  • É muito difícil para o compilador evitar a reutilização de registradores sem um grande aumento no tamanho do código. Em laços de repetição, por exemplo, iterações sucessivas teriam que usar diferentes registradores, o que requer a replicação do código.
  • Um grande número de registradores requer lotes de bits para especificação, novamente causando o aumento de tamanho do código.
  • Muitos conjuntos de instrução especificam um número baixo de registradores e isso não pode ser mudado.

Aumentos no tamanho do código são críticos porque quanto maior o tamanho do código mais custoso será o processamento em questões de tempo.[5]

Registradores Físicos vs. Registradores de Arquitetura[editar | editar código-fonte]

Programas de linguagem de máquina especificam leituras e escritas para um conjunto limitado de registradores especificado pela Arquitetura do Conjunto de Instruções (ISA – Instruction Set Architecture) – os registradores lógicos.  Por exemplo, o Alpha ISA especifica 32 registradores inteiros de 64 bits de largura e 32 registradores de ponto flutuante também de 64 bits de largura. Estes são registradores de arquitetura. Portanto, programas escritos para executarem sobre a arquitetura Alpha ISA usarão 64 registradores para leituras e escritas (32 para operações sobre inteiros e 32 para operações sobre ponto flutuante).

Em todos os esquemas de renomeação, a máquina converte os registradores da arquitetura referenciados na instrução em tags (etiquetas). O arquivo de mudança de nome deve ter uma porta de leitura para cada entrada de cada instrução renomeada a cada ciclo, e uma porta de escrita para cada saída de cada instrução renomeado a cada ciclo. Pelo fato de que o tamanho de um banco de registradores geralmente cresce em função do número de portas, ele se torna geralmente grande e consome uma potência significativa.[6]

Renomeação de Registradores Parcial e Renomeação de Registradores Total[editar | editar código-fonte]

Segundo Andaló[4] existe uma classificação da técnica de Renomeação de Registradores em Parcial ou Total para definir a extensão da utilização da técnica pelos processadores.

De acordo com essa diferenciação, a Renomeação de Registradores Parcial seria uma renomeação restrita a um ou pouco tipo de instruções, ou seja, ela seria executada apenas com poucas classes de instruções. Já a Renomeação de Registradores Total incluiria todas as instruções que possuem registrador de destino.

Conceitos Importantes[editar | editar código-fonte]

  • Banco de Registradores de Arquitetura: Conjunto de Registradores da Arquitetura.[1]
  • Arquivo Futuro (Future File): Algumas instruções são executadas mesmo sem saber se deveriam ser (na caso de desvios condicionais, por exemplo). Os resultados dessas instruções são guardadas no Future File e se as instruções forem realmente executadas, o conteúdo dos registradores deste arquivo é copiado para os registradores finais. Utilizado na previsão de acerto.[1]
  • Buffer de História (History Buffer): Comumente utilizado junto com o Future File, guarda os valores antigos dos registradores.[6]
  • Buffer de Reordem (Reorder Buffer - ROB): Buffer onde ficam os resultados das instruções executadas fora da ordem para que ao final sejam passadas para os registradores da arquitetura na ordem correta.[7]

Banco de Registradores Indexados por tags e Estação de Reserva[editar | editar código-fonte]

Existem duas formas de renomeação de registradores, o Arquivo de Registro Indexado ou Banco de Registradores Indexados por Etiquetas (tags) e a Estação de reserva.

No arquivo de registro de etiquetas indexadas, há um grande arquivo de registros que contém uma etiqueta (tag) para cada registro. Neste modelo, quando uma instrução é emitida para uma unidade de execução, as tags do banco de registradores são enviados para o arquivo de registradores físicos, onde os valores correspondentes a essas tags (etiquetas) são lidas e enviadas para a unidade de execução.

Na estação de reserva, existem pequenos arquivos de registradores associativos, geralmente um em cada entrada da unidade de execução. Cada operando de cada instrução em uma fila tem um lugar para um valor em um desses arquivos de registro. Neste estilo, há uma comparação entre as entradas dos arquivos de registro e as estradas das filas de problemas para que a instrução seja encaminhada para a unidade de execução.[7]

Banco de Registradores Indexados por tags[6][editar | editar código-fonte]

Este é o estilo de renomeação usado no MIPS R10000 , o Alpha 21264 , e na seção de ponto flutuante do AMD Athlon.[6]

Na fase de renomeação todos os registros referenciados da arquitetura, seja para escrita ou leitura, são procurados em um arquivo de mapeamento. O resultado desta procura é uma tag (etiqueta) e um bit de controle ligado. Se o bit de controle estiver desligado é porque existe alguma instrução que ainda não foi executada. Para operandos de leitura, esta tag toma o lugar do registro da arquitetura na instrução. Para todos os registros de escrita, uma nova tag é puxada de uma fila de tags livres, e um novo mapeamento é escrito no arquivo de mapeamento, assim as futuras leituras aos registradores da arquitetura vão se referir a essa nova etiqueta (tag). 

As instruções são então colocados em várias filas de emissão.

A cada instrução executada, resultados são gerados e as tags desses resultados são comparados com as tags da fila de operandos prontos para retirar (ou não), identificando as dependências. O arquivo de mapeamento também faz essa comparação de tags e então ele pode marcar o registrador físico correspondente como pronto. As instruções com estado de prontas são retirados da fila e enviados para as unidades de execução. Instruções não prontas permanecem na fila. Esta remoção desordenada de instruções das  filas é uma das questões que torna o Arquivo de Registro de Etiquetas (tags) Indexadas grande e com demanda energética alta.

Instruções lidas de um banco de registradores físicos indexados por tags são executadas. Os resultados da execução são escritos no banco de registradores físicos indexados e transmitidos para a rede de desvio antes de cada unidade funcional. O registrador arquitetural (registrador lógico) recebe a tag livre para que ele possa ser reutilizado.

Uma exceção ou erro de previsão acarreta com que o arquivo de mapeamento volte ao seu estado anterior, estado da última instrução válida pela combinação do estado instantâneo e cycling através das tags anteriores na fila de pré-graduação ordenada. Uma vez que este mecanismo é requerido, e uma vez que ele pode recuperar o estado de mapeamento (não apenas o estado antes da instrução atual ser graduada), o erro de previsão pode ser tratado antes da instrução alcançar a graduação, podendo esconder a latência do erro de previsão.

Estado de Reserva[6][editar | editar código-fonte]

Este é o estilo usado na seção de inteiro dos projetos AMD K7 e K8.

No estágio de renomeação todo registrador arquitetural (registrador lógico) referenciado por leituras é pesquisado no future file e no arquivo de  renomeação. A leitura do arquivo futuro dá o valor do registrador, e, se não existir nenhuma instrução de leitura remanescente, o valor será gravado no registrador. Quando a instrução é colocada em uma fila de issues, os valores lidos do future file são escritos nas entradas correspondentes das estações de reserva. Registradores escritos nas instruções originam uma nova tag de não pronto para ser escrito no  arquivo de renomeação. O numero da tag é usualmente alocado em ordem de instrução.

Assim como no esquema de tag indexada, as filas de issue esperam por operandos não prontos para haver a combinação de tags de transmissão. Diferente do esquema de tag indexada, tags de combinação fazem com que a transmissão dos valores correspondentes sejam escritos dentro da fila de issues no estado de reserva.

As instruções da fila de issues lêem seus argumentos do estado de reserva, ignoram operandos transmitidos e depois executam. Como mencionado antes, os arquivos de registradores do estado de reserva são geralmente pequenos, com talvez oito entradas.

Os resultados da execução são retiradas da estação de reserva e escritas no buffer de reordenamento (se a entrada da fila de issues tiver tags correspondentes), e no arquivo futuro se for a última instrução para o registrador arquitetural (que no caso será marcado como pronto).

São feitas cópias graduais dos valores do buffer de reordenamento no arquivo para os registradores arquiteturais. O uso exclusivo de um arquivo de registrador arquitetural serve para recuperar de exceções e erros de erros de previsão.

Exceções e erros de previsão reconhecidos na progressão gradual, fazem com que o banco arquitetural (banco de registradores lógicos) seja copiado no future file, e também todos os registradores marcados com pronto no arquivo de renomeação. Normalmente não existe um jeito de reconstruir o estado do future file para algumas instruções intermediárias entre decodificação e graduação, então normalmente não existe como se recuperar previamente das falhas de previsão nessa área.

Comparação entre os dois Esquemas[editar | editar código-fonte]

Em ambos os esquemas, as instruções são inseridas em ordem na fila, mas são removidas fora de ordem.[6] Se as filas não conflitarem com os slots vazios, então ambas terão algumas entradas não utilizadas, ou vão precisar de algum tipo de prioridade de variável codificada para quando múltiplas instruções que estão simultaneamente prontas irem. Filas que conflitam com os espaços vazios (slots vazios) tem uma codificação (implementação) de prioridade simples, mas requerem um simples porém extenso circuito para avançarem instruções através da fila.

Estações de reserva tem um tempo de latência melhor entre renomear e executar, porque acha os valores do registrador diretamente ao invés de achar o endereço físico do registrador, e depois usando isto para achar o valor. Essa latência se mostra como um componente de latência do erro de previsão.

Estações de reserva também tem uma latência melhor das instruções de issue para execução, porque cada arquivo de registrador local é menor do que o grande arquivo central do esquema de tag indexada. Geração de tags e processamento de exceções são também mais simples no esquema de estação de reserva, como discutido abaixo.

Os bancos de registradores físicos usados pelas estações de reserva normalmente conflitam com as entradas não utilizadas em paralelo com a fila de issue que eles servem (atendem), o que faz com que estes bancos de registradores possam ser escritos por qualquer barramento de resultado, então este banco de registradores da estação de reserva com fila de issues com 8 entradas por unidade funcional, vai ter tipicamente 9 vezes mais redes de by-pass (desvio) do que uma banco equivalente de tag indexada. Passando à frente os resultados e tomando muito mais poder (energia) em um design de tag indexada.

Além disso, os esquemas de estação de reserva tem 4 lugares (future file, estação de reserva, buffer de reordenação, arquivos arquiteturais) onde o valor resultante pode ser armazenado; já o esquema de tag indexada tem apenas um (o banco de registradores físicos). Pelo fato de que os resultados das unidades funcionais são transmitidas para todos os locais de armazenamento, precisam chegar a um número muito maior de locais na máquina do que no esquema de tag indexada, essa função consome muito mais energia, área e tempo. Ainda, em máquinas equipadas com esquema de previsão muito preciso, onde executar as latências é uma preocupação maior, estações de reserva podem funcionar muito bem.[5]

Banco de Registradores Físicos e Buffer de Reordenamento[editar | editar código-fonte]

Segundo Andaló[4] existem ainda duas formas de renomeação de registradores, sendo elas o Banco de Registradores Físicos e o Buffer de Reordenamento.

O Banco de Registradores Físicos trata-se de uma técnica em que os buffers de renomeação são implementados junto com o banco de registradores físicos, chamado de Banco Único de Renomeação e de Registradores da Arquitetura. Então, ambos os registradores serão alocados no mesmo banco de registradores físicos, dinamicamente, por meio da tabela de mapeamento. Esta tabela faz com que cada registrador de arquitetura (registradores lógicos - menor quantidade) seja mapeado a um registrador físico no estágio de decodificação.[4]

Utilizando-se o esquema de Buffer de Reordenação, as instruções serão mantidas nesse buffer até o seu término. O esquema funciona da seguinte forma:

  • Leitura dos operando de origem (disponíveis quando a instrução é decodificada do banco de registradores ou da entrada correspondente no buffer de reordenação);
  • Operandos não disponíveis saem das Unidades de Execução e vão para as filas de entradas correspondentes;
  • Quando uma instrução termina, seu resultado é copiado do buffer de reordenação para o banco de registradores.

Histórico[editar | editar código-fonte]

Processadores escalares mais antigos não faziam uso de renomeação. A técnica começou a ser implementada gradativamente, primeiro de maneira restrita (Renomeação Parcial), por volta de 1990. A Renomeação Total começou a ser explorada a partir de 1992. Depois disso, a Renomeação de Registradores passou a ser utilizada na maioria dos processadores superescalares.[4]

O sistema IBM 360 modelo 91 foi a primeira máquina que suportou execução de instruções fora de ordem. Ela utilizou o Algoritmo de Tomasulo, que utiliza Renomeação de Registradores. Trata-se de um supercomputador escalar pioneiro tanto em pipeline como em escalonamento dinâmico de instruções.[4]

O Power1 é o primeiro microprocessador que utilizou renomeação de registradores e execução de instruções fora de ordem em 1990.[6]

O projeto original do R10000 não teve nenhum conflito em filas nem variáveis de prioridade codificadas, mas teve problemas de Starvation com o resultado: as instruções envelheciam na fila porque, em alguns casos, não eram executadas nunca; até que a decodificação de instrução parou completamente com falta de renomeação de registradores. Revisões posteriores do projeto, iniciando com o R12000, codificaram variáveis de prioridade parciais, para minimizar este problema.[6]

No início, máquinas que utilizavam execução de instruções fora de ordem (Out-of-Ordem Execution - OoOE) não separavam a renomeação e o armazenamento ROB/PRF. Para isso alguns pioneiros alocavam todo armazenamento na mesma estrutura (como trata a secção Banco de Registradores Físicos). Além disso, usavam conteúdo endereçável de memória (um tipo de hardware que fornece a funcionalidade de uma matriz associativa ) na renomeação.[6]

A maioria das máquinas modernas fazem a renomeação pela tabela de mapeamento indexada em RAM. O Future File faz isso, e tem o armazenamento de dados na mesma estrutura.[6]

Em muitos aspectos a história mostra que métodos que geram ou usam arquivos grandes estão sendo eliminados. Pequenos arquivos são úteis, grandes arquivos  são impraticáveis.[6]

Referências

  1. a b c d e Stallings, W. (2012). "Paralelismo no nível de instruções e processadores superescalares". Arquitetura e Organização de Computadores. 5ª edição. ISBN 85-87918-53-2
  2. Smith, J. E.; Pleszkun, A. R. (June 1985). "Implementation of precise interrupts in pipelined processors". ACM SIGARCH Computer Architecture News 13 (3): 36–44. doi:10.1145/327070.327125.
  3. a b Stallings, W. (2012). "Paralelismo no nível de instruções e processadores superescalares". Arquitetura e Organização de Computadores. 8ª edição. ISBN 978-85-7605-564-8
  4. a b c d e f Andaló, F. A. "Register Renaming" - Unicamp. Disponível em: <http://www.ic.unicamp.br/~rodolfo/Cursos/mo401/2s2005/Trabalho/>
  5. a b Smith, J. E.; Pleszkun, A. R. (May 1988). "Implementing precise interrupts in pipelined processors". IEEE Trans. Comput. 37 (5): 562–573. doi:10.1109/12.4607.
  6. a b c d e f g h i j k «Register Renaming». Wikipédia 
  7. a b Smith, J. E.; Pleszkun, A. R. (1998). "Implementation of precise interrupts in pipelined processors". "25 years of the international symposia on Computer architecture (selected papers) - ISCA '98". pp. 291–299. doi:10.1145/285930.285988. ISBN 1581130589.