Predicação (arquitetura de computadores)

Na arquitetura de computadores, a predicação é um recurso que oferece uma alternativa à transferência condicional de controle, conforme implementada por instruções de máquina de desvio condicional. A predicação funciona associando instruções condicionais (predicadas) não-desvio a um predicado, um valor booleano usado pela instrução para controlar se a instrução tem permissão para modificar o estado arquitetural ou não. Se o predicado especificado na instrução for verdadeiro, a instrução modifica o estado arquitetural; caso contrário, o estado arquitetural permanece inalterado. Por exemplo, uma instrução de movimentação predicada (uma movimentação condicional) só modificará o destino se o predicado for verdadeiro. Assim, em vez de usar um desvio condicional para selecionar uma instrução ou uma sequência de instruções a executar com base no predicado que controla se o desvio ocorre, as instruções a serem executadas são associadas a esse predicado, de modo que serão executadas, ou não, com base em o predicado ser verdadeiro ou falso.^[1]

Processadores vetoriais, algumas ISAs SIMD (como AVX2 e AVX-512) e GPUs em geral fazem uso intenso de predicação, aplicando um bit de um vetor de máscara condicional aos elementos correspondentes nos registradores vetoriais sendo processados, enquanto a predicação escalar em conjuntos de instruções escalares só precisa do único bit de predicado. Onde as máscaras de predicado se tornam particularmente poderosas no processamento vetorial é quando um array de códigos de condição, um por elemento vetorial, pode realimentar máscaras de predicado que são então aplicadas a instruções vetoriais subsequentes.

Visão geral

A maioria dos programas de computador contém código condicional, que será executado apenas sob condições específicas dependendo de fatores que não podem ser determinados antecipadamente, por exemplo, dependendo da entrada do usuário. Como a maioria dos processadores simplesmente executa a próxima instrução em sequência, a solução tradicional é inserir instruções de desvio que permitem a um programa desviar condicionalmente para uma seção diferente do código, alterando assim o próximo passo na sequência. Isso foi suficiente até que os projetistas começaram a melhorar o desempenho implementando o pipeline de instruções, um método que é desacelerado pelos desvios. Para uma descrição mais completa dos problemas que surgiram e uma solução popular, ver preditor de desvio.

Felizmente, um dos padrões de código mais comuns que normalmente depende de desvio tem uma solução mais elegante. Considere o seguinte pseudocódigo:^[1]

if condição
    {faça_algo}
else
    {faça_outra_coisa}

Em um sistema que usa desvio condicional, isso poderia se traduzir em instruções de máquina semelhantes a:^[1]

    desvie_se_condição_para rótulo1
    faça_outra_coisa
    desvie_sempre_para rótulo2
rótulo1:
    faça_algo
rótulo2:
    ...

Com predicação, todos os caminhos de desvio possíveis são codificados em linha, mas algumas instruções são executadas enquanto outras não. A ideia básica é que cada instrução é associada a um predicado (a palavra aqui usada de forma semelhante ao seu uso na lógica de predicados) e que a instrução só será executada se o predicado for verdadeiro. O código de máquina para o exemplo acima usando predicação poderia ser algo assim:^[1]

(condição)     faça_algo
(não condição) faça_outra_coisa

Além de eliminar desvios, menos código é necessário no total, desde que a arquitetura forneça instruções predicadas. Embora isso não garanta execução mais rápida em geral, garantirá se os blocos de código faça_algo e faça_outra_coisa forem suficientemente curtos.

A forma mais simples de predicação é a predicação parcial, onde a arquitetura tem instruções de movimentação condicional ou seleção condicional. Instruções de movimentação condicional escrevem o conteúdo de um registrador sobre outro apenas se o valor do predicado for verdadeiro, enquanto instruções de seleção condicional escolhem qual de dois registradores tem seu conteúdo escrito em um terceiro com base no valor do predicado. Uma forma mais generalizada e capaz é a predicação total. A predicação total tem um conjunto de registradores de predicado para armazenar predicados (o que permite que múltiplos desvios aninhados ou sequenciais sejam eliminados simultaneamente) e a maioria das instruções na arquitetura tem um campo especificador de registrador (opcional) para especificar qual registrador de predicado fornece o predicado.^[2]

Vantagens

O principal propósito da predicação é evitar saltos sobre seções muito pequenas de código de programa, aumentando a eficácia da execução pipelineada e evitando problemas com a cache. Ela também tem uma série de benefícios mais sutis:

Funções que são tradicionalmente computadas usando aritmética simples e operações bit a bit podem ser mais rápidas de computar usando instruções predicadas.
Instruções predicadas com predicados diferentes podem ser misturadas entre si e com código incondicional, permitindo melhor escalonamento de instruções e, portanto, desempenho ainda melhor.
Eliminação de instruções de desvio desnecessárias pode tornar a execução de desvios necessários, como os que compõem loops, mais rápida ao diminuir a carga sobre os mecanismos de predição de desvio.
Eliminação do custo de uma predição incorreta de desvio, que pode ser alto em arquiteturas com pipeline profundo.
Conjuntos de instruções que têm Códigos de Condição abrangentes gerados por instruções podem reduzir ainda mais o tamanho do código usando diretamente os Registradores de Condição na predicação ou como predicação.

Desvantagens

A principal desvantagem da predicação está no aumento do espaço de codificação. Em implementações típicas, cada instrução reserva um campo de bits para o predicado, especificando sob quais condições essa instrução deve ter efeito. Quando a memória disponível é limitada, como em dispositivos embarcados, esse custo de espaço pode ser proibitivo. No entanto, algumas arquiteturas como Thumb-2 conseguem evitar esse problema (ver abaixo). Outros detrimentos são os seguintes:^[3]

A predicação complica o hardware ao adicionar níveis de lógica aos caminhos críticos e potencialmente degrada a velocidade do clock.
Um bloco predicado inclui ciclos para todas as operações, então caminhos mais curtos podem levar mais tempo e ser penalizados.
Uma leitura extra de registrador é necessária. Um ADD não predicado leria dois registradores de um banco de registradores, enquanto um ADD Predicado precisaria também ler o banco de registradores de predicado. Isso aumenta os Hazards na execução fora de ordem.
A predicação geralmente não é especulada e causa uma cadeia de dependência mais longa. Para dados ordenados, isso se traduz em uma perda de desempenho comparada a um desvio previsível.^[4]

A predicação é mais eficaz quando os caminhos são balanceados ou quando o caminho mais longo é o mais frequentemente executado,^[3] mas determinar tal caminho é muito difícil em tempo de compilação, mesmo na presença de informação de perfil.

História

Instruções predicadas eram populares em projetos de computadores europeus da década de 1950, incluindo o Mailüfterl (1955), o Zuse Z22 (1955), o ZEBRA (1958) e o Electrologica X1 (1958). O projeto IBM ACS-1 de 1967 alocou um bit "skip" em seus formatos de instrução, e o CDC Flexible Processor em 1976 alocou três bits de execução condicional em seus formatos de microinstrução.

A arquitetura PA-RISC da Hewlett-Packard (1986) tinha um recurso chamado nullification, que permitia que a maioria das instruções fosse predicada pela instrução anterior. A arquitetura POWER da IBM (1990) apresentava instruções de movimentação condicional. A sucessora da POWER, PowerPC (1993), abandonou essas instruções. A arquitetura Alpha da Digital Equipment Corporation (1992) também apresentava instruções de movimentação condicional. O MIPS ganhou instruções de movimentação condicional em 1994 com a versão MIPS IV; e o SPARC foi estendido na Versão 9 (1994) com instruções de movimentação condicional tanto para registradores inteiros quanto de ponto flutuante. O RISC-V inicialmente não tinha predicação, mas na versão 2.0 da ISA não privilegiada adquiriu-a através de uma extensão (Zicond) contendo instruções de zeragem condicional com as quais aritmética condicional e seleção podem ser sintetizadas.

Na arquitetura IA-64 da Hewlett-Packard/Intel, a maioria das instruções é predicada. Os predicados são armazenados em 64 registradores de predicado de propósito especial; e um dos registradores de predicado é sempre verdadeiro, de modo que instruções não predicadas são simplesmente instruções predicadas com o valor verdadeiro. O uso da predicação é essencial na implementação do software pipelining do IA-64 porque evita a necessidade de escrever código separado para prólogos e epílogos.^{[necessário esclarecer]}

Na arquitetura x86, uma família de instruções de movimentação condicional (CMOV e FCMOV) foi adicionada à arquitetura pelo processador Intel Pentium Pro (1995). As instruções CMOV copiavam o conteúdo do registrador de origem para o registrador de destino dependendo de um predicado fornecido pelo valor do registrador de flags.

Na arquitetura ARM, o conjunto de instruções original de 32 bits fornece um recurso chamado execução condicional que permite que a maioria das instruções seja predicada por um dos 13 predicados que são baseados em alguma combinação dos quatro códigos de condição definidos pela instrução anterior. O conjunto de instruções Thumb da ARM (1994) abandonou a execução condicional para reduzir o tamanho das instruções para que coubessem em 16 bits, mas seu sucessor, Thumb-2 (2003), superou esse problema usando uma instrução especial que não tem efeito além de fornecer predicados para as quatro instruções seguintes. O conjunto de instruções de 64 bits introduzido no ARMv8-A (2011) substituiu a execução condicional por instruções de seleção condicional.

Predicação SIMD, SIMT e vetorial

Alguns conjuntos de instruções SIMD within a register (SWAR), como AVX2, têm a capacidade de usar uma máscara lógica para carregar/armazenar valores condicionalmente na memória, em uma forma paralela da movimentação condicional. Eles também podem aplicar bits de máscara individuais a unidades aritméticas individuais executando uma operação paralela. Um bit de máscara de predicado está disponível para cada subpalavra do registrador SWAR ou cada valor de carga/armazenamento. Essa forma de predicação multibit também é usada em processadores vetoriais no nível de elemento (sinônimo de subpalavras SWAR):

para cada (subpalavra i) do registrador SWAR (ou Vetorial)
    (bit de máscara de condição i)     faça_algo(subpalavra i)
    (não bit de máscara de condição i) faça_outra_coisa(subpalavra i)

O mascaramento é parte integrante dos Processadores de Array como o ILLIAC IV. Processadores de Array são conhecidos hoje como single instruction, multiple threads (SIMT), e um bit de predicado por PE usado para ativar ou desativar cada Elemento de Processamento. Quando o PE não tem instruções SIMD within a register, cada PE pode ser individualmente Predicado:

para cada (PE j) // de array síncrono-concorrente não-SWAR
    (bit de máscara ativo j)     transmite_instrução_escalar_para(PE j)

GPUs SIMT modernas usam (ou usavam, mas a documentação do ILLIAC IV chamava de "branching") predicação para habilitar/desabilitar Elementos de Processamento individuais e, separadamente e além disso, para também mascarar subpalavras dentro de qualquer ALU SWAR de um dado PE.

para cada (PE j) do array síncrono-concorrente SIMT
  (bit de máscara ativo j) { // transmite apenas para PEs SWAR ativos
    para cada (subpalavra i) do registrador SWAR em (PE j)
      (bit de máscara de condição i)     faça_algo(subpalavra i)
      (não bit de máscara de condição i) faça_outra_coisa(subpalavra i)
  }

Todas as técnicas, vantagens e desvantagens da predicação escalar única aplicam-se igualmente ao caso de processamento paralelo, onde as questões associadas ao desvio se tornam muito mais complexas.^[5]

Ver também

Referências

1 2 3 4 Rick Vinyard (26 de abril de 2000). «Predication». cs.nmsu.edu. Consultado em 22 de abril de 2014. Cópia arquivada em 20 de abril de 2015
↑ Mahlke, Scott A.; Hank, Richard E.; McCormick, James E.; August, David I.; Hwn, Wen-mei W. (1995). A Comparison of Full and Partial Predicated Execution Support for ILP Processors. The 22nd International Symposium on Computer Architecture, 22–24 de junho de 1995. ISBN 0-89791-698-0. doi:10.1145/223982.225965
1 2 Fisher, Joseph A.; Faraboschi, Paolo; Young, Cliff (2004). «4.5.2 Predication § Predication in the Embedded Domain». Embedded Computing — A VLIW Approach to Architecture, Compilers, and Tools. https://books.google.com/books?id=DbOa0p1wRD4C&pg=PA172. [S.l.]: Elsevier. p. 172. ISBN 978-0-08-047754-1
↑ Cordes, Peter. «assembly - How does Out of Order execution work with conditional instructions, Ex: CMOVcc in Intel or ADDNE (Add not equal) in ARM». Stack Overflow. Unlike with control dependencies (branches), they don't predict or speculate what the flags will be, so a cmovcc instead of a jcc can create a loop-carried dependency chain and end up being worse than a predictable branch. gcc optimization flag -O3 makes code slower than -O2 is an example of that.
↑ https://gpgpuarch.org/en/basic/simt/

Leitura adicional

Clements, Alan (2013). «8.3.7 Predication». Computer Organization & Architecture: Themes and Variations. https://books.google.com/books?id=ySILAAAAQBAJ&pg=PA532. [S.l.]: Cengage Learning. pp. 532–9. ISBN 978-1-285-41542-0

[rvinyard-1] 1 2 3 4 Rick Vinyard (26 de abril de 2000). «Predication». cs.nmsu.edu. Consultado em 22 de abril de 2014. Cópia arquivada em 20 de abril de 2015

[2] Mahlke, Scott A.; Hank, Richard E.; McCormick, James E.; August, David I.; Hwn, Wen-mei W. (1995). A Comparison of Full and Partial Predicated Execution Support for ILP Processors. The 22nd International Symposium on Computer Architecture, 22–24 de junho de 1995. ISBN 0-89791-698-0. doi:10.1145/223982.225965

[Fisher04-3] 1 2 Fisher, Joseph A.; Faraboschi, Paolo; Young, Cliff (2004). «4.5.2 Predication § Predication in the Embedded Domain». Embedded Computing — A VLIW Approach to Architecture, Compilers, and Tools. https://books.google.com/books?id=DbOa0p1wRD4C&pg=PA172. [S.l.]: Elsevier. p. 172. ISBN 978-0-08-047754-1

[4] Cordes, Peter. «assembly - How does Out of Order execution work with conditional instructions, Ex: CMOVcc in Intel or ADDNE (Add not equal) in ARM». Stack Overflow. Unlike with control dependencies (branches), they don't predict or speculate what the flags will be, so a cmovcc instead of a jcc can create a loop-carried dependency chain and end up being worse than a predictable branch. gcc optimization flag -O3 makes code slower than -O2 is an example of that.

[5] ttps://gpgpuarch.org/en/basic/simt/

[1]

[2]

[3]

[4]

[5]