Por que a adição é tão rápida quanto as operações bit a bit nos processadores modernos?

73

Eu sei que as operações bit a bit são tão rápidas nos processadores modernos, porque elas podem operar em 32 ou 64 bits em paralelo; portanto, as operações bit a bit levam apenas um ciclo de clock. No entanto, a adição é uma operação complexa que consiste em pelo menos uma e possivelmente até uma dúzia de operações bit a bit, então naturalmente pensei que seria 3-4 vezes mais lenta. Fiquei surpreso ao ver, após um simples benchmark, que a adição é exatamente tão rápida quanto qualquer uma das operações bit a bit (XOR, OR, AND etc.). Alguém pode esclarecer isto?

SoloNasus
fonte
11
Sim, a multiplicação também foi muito rápida nos meus testes. Foi apenas cerca de duas vezes mais lenta que a adição, enquanto a divisão foi cerca de 30x (!) Vezes mais lenta.
SoloNasus 27/05
Visão geral compacta dos adicionadores de árvores de prefixo paralelo de última geração: Uma taxonomia de redes de prefixos paralelos por David Harris: pages.hmc.edu/harris/research/taxonomy.pdf
Franki
Mais elaborado: tese de doutorado de PhD de Jun Chen "Estruturas de prefixo paralelo para aditivos binários e de módulos {2n − 1, 2n, 2n + 1}" digital.library.okstate.edu/etd/Chen_okstate_0664D_10070.pdf
Franki

Respostas:

104

A adição é rápida porque os projetistas de CPU instalaram o circuito necessário para torná-lo mais rápido. São necessários muito mais portões do que operações bit a bit, mas é frequente o suficiente para que os projetistas de CPU considerem que vale a pena. Consulte https://en.wikipedia.org/wiki/Adder_(electronics) .

Ambos podem ser feitos com rapidez suficiente para serem executados em um único ciclo da CPU. Eles não são igualmente rápidos - a adição requer mais portas e mais latência do que uma operação bit a bit - mas é rápido o suficiente para que um processador possa fazer isso em um ciclo de clock. Há uma sobrecarga de latência por instrução para a lógica de decodificação e controle de instruções, e a latência é significativamente maior que a latência para executar uma operação bit a bit, de modo que a diferença entre os dois é inundada por essa sobrecarga. A resposta do AProgrammer e a resposta de Paul92 explicam bem esses efeitos.

DW
fonte
Comentários não são para discussão prolongada; esta conversa foi movida para o bate-papo .
DW
38

Existem vários aspectos.

  • O custo relativo de uma operação bit a bit e uma adição. Um somador ingênuo terá uma profundidade de porta que depende linearmente da largura da palavra. Existem abordagens alternativas, mais caras em termos de portões, que reduzem a profundidade (IIRC a profundidade então depende logaritmicamente da largura da palavra). Outros já deram referências para essas técnicas, apenas ressaltarei que a diferença também é menos importante do que parece, considerando apenas o custo da operação, devido à necessidade de lógica de controle que adicione atrasos.

  • Além disso, existe o fato de que os processadores geralmente têm clock de clock (estou ciente de algumas pesquisas ou projetos com clock de uso especial, mas não tenho certeza de que alguns estejam disponíveis comercialmente). Isso significa que, qualquer que seja a velocidade de uma operação, será necessário um múltiplo inteiro do ciclo do relógio.

  • Finalmente, há as considerações micro-arquitetônicas: você tem certeza de que mede o que deseja? Atualmente, os processadores tendem a ser pipelines, multi-escalares, com execução fora de ordem e qualquer outra coisa. Isso significa que eles são capazes de executar várias instruções ao mesmo tempo, em vários estágios de conclusão. Se você deseja mostrar por medições que uma operação leva mais tempo que outra, é necessário levar em consideração esses aspectos, pois o objetivo deles é ocultar essas diferenças. Você pode muito bem ter a mesma taxa de transferência para operações de adição e bit a bit ao usar dados independentes, mas uma medida da latência ou introdução de dependências entre as operações pode mostrar o contrário. E você também deve ter certeza de que o gargalo da sua medida está na execução e não, por exemplo, nos acessos à memória.

AProgrammer
fonte
6
+1. Sim, a maioria dos processadores tem clock de clock, mas algumas CPUs sem clock estão disponíveis comercialmente.
David Cary
2
Outra possibilidade é que um processador possa armazenar um registro de 64 bits como uma peça de 16 bits e três peças de 17 bits, onde os bits extras de cada peça que contém um adiado são transportados por baixo. Uma adição que é seguida por uma operação bit a bit ou um armazenamento pode exigir 1-2 ciclos extras para propagar o transporte, mas uma adição que é seguida por outra adição não exigiria. Além disso, no caso "armazenamento", o tempo extra de propagação pode atrasar o desempenho do armazenamento, mas não haveria necessidade de código "esperar" por ele.
Supercat 24/05
3
@supercat O Pentium 4 fez algo parecido com isto, com uma ALU de velocidade dupla (em relação ao restante do processador) que teria os 16 ou 32 bits baixos prontos para uma operação subseqüente meio ciclo antes dos bits da metade superior.
Jeffrey Bosboom
2
tem certeza de que mede o que deseja? Nesse caso, a conclusão do OP das medições está correta para a grande maioria das CPUs. A adição é tão comum que as CPUs superescalares adicionam unidades em todas as portas de execução, e os booleanos são tão baratos de implementar (na contagem de transistores) que também estão presentes em todas as portas. Portanto, add e booleanos quase sempre têm a mesma taxa de transferência (por exemplo, 4 por clock no Intel Haswell).
Peter Cordes
2
A adição de número inteiro SIMD geralmente é uma taxa de transferência mais baixa que o booleano SIMD, embora eles geralmente tenham a mesma latência. As CPUs da Intel, do PentiumII a Broadwell, podem executar apenas adições vector-int (por exemplo paddw) a 2 por relógio, mas booleanos (como pand) a 3 por relógio. (Skylake coloca uma víbora vetor em todas as portas de execução de três vetores.)
Peter Cordes
24

CPUs operam em ciclos. A cada ciclo, algo acontece. Normalmente, uma instrução leva mais ciclos para executar, mas várias instruções são executadas ao mesmo tempo, em diferentes estados.

Por exemplo, um processador simples pode ter 3 etapas para cada instrução: buscar, executar e armazenar. A qualquer momento, três instruções estão sendo processadas: uma está sendo buscada, uma está sendo executada e uma armazena seus resultados. Isso é chamado de pipeline e possui neste exemplo três estágios. Os processadores modernos possuem dutos com mais de 15 estágios. No entanto, além disso, assim como a maioria das operações aritméticas, geralmente são executadas em um estágio (estou falando sobre a operação de adicionar 2 números pela ALU, não sobre a própria instrução - dependendo da arquitetura do processador, a instrução pode exigir mais ciclos para buscar argumentos da memória, executar condicionais, armazenar resultados na memória).

A duração de um ciclo é determinada pelo caminho crítico mais longo. Basicamente, é o tempo mais longo necessário para que algum estágio do pipline seja concluído. Se você deseja acelerar a CPU, precisa otimizar o caminho crítico. Se a redução do caminho crítico em si não for possível, ele poderá ser dividido em 2 estágios do pipeline, e agora você poderá sincronizar sua CPU com quase o dobro da frequência (supondo que não exista outro caminho crítico que o impeça de fazer isso). ) Mas isso vem com uma sobrecarga: você precisa inserir um registro entre os estágios do pipeline. O que significa que você não ganha velocidade 2x (o registro precisa de tempo para armazenar os dados) e complicou todo o design.

Já existem métodos bastante eficientes para executar a adição (por exemplo, carregadores com adição de olhais) e a adição não é um caminho crítico para a velocidade do processador; portanto, não faz sentido dividi-lo em vários ciclos.

Além disso, observe que, embora possa parecer complicado para você, no hardware as coisas podem ser feitas em paralelo muito rapidamente.

Paul92
fonte
3
A grande sobrecarga de oleodutos mais longos é de mais ciclos para se recuperar de uma previsão incorreta de uma filial! Passar transistores para armazenar dados em buffer entre estágios é menor hoje em dia. Até mesmo uma CPU simples em pipeline precisa buscar / decodificar antes das instruções que estão em execução. Se a CPU descobrir que o front-end estava trabalhando no código errado, porque uma ramificação seguiu um caminho diferente do previsto (ou alguma outra especulação incorreta), ela deve descartar esse trabalho e começar com as instruções corretas. As coisas só pioram com CPUs superescalares fora de ordem que podem ter muitos insns em vôo.
Peter Cordes
12

Os processadores têm clock de clock, portanto, mesmo que algumas instruções possam ser claramente feitas mais rapidamente que outras, elas podem levar o mesmo número de ciclos.

Você provavelmente descobrirá que o circuito necessário para transportar dados entre registradores e unidades de execução é significativamente mais complicado que os somadores.

Observe que a instrução MOV simples (registrar para registrar) faz ainda menos cálculos que a lógica bit a bit, mas ambos, MOV e ADD, geralmente levam um ciclo. Se o MOV pudesse ser feito duas vezes mais rápido, as CPUs teriam um clock duas vezes mais rápido e os ADDs teriam dois ciclos.

James Hollis
fonte
Comentários não são para discussão prolongada; esta conversa foi movida para o bate-papo .
Gilles 'SO- stop be evil'
11
Resumo da discussão: algumas CPUs com problemas lidam com MOV especialmente com renomeação de registro, com latência efetivamente zero. Veja O MOV do x86 pode realmente ser "gratuito"? Por que não consigo reproduzir isso? para obter todos os detalhes sobre o que o MOV realmente custa.
Peter Cordes
12

A adição é importante o suficiente para não esperar um bit de transporte percorrer um acumulador de 64 bits: o termo é um somador de carry-lookahead e eles são basicamente parte de CPUs de 8 bits (e suas ALUs) e superiores. De fato, os processadores modernos tendem a não precisar de muito mais tempo de execução para uma multiplicação completa: carry-lookahead é realmente uma ferramenta muito antiga (e comparativamente acessível) na caixa de ferramentas de um designer de processador.

user72735
fonte
A multiplicação de números inteiros é definitivamente mais alta latência e menor taxa de transferência do que ADD em x86. Mas é incrivelmente rápido, considerando quantos somadores são necessários para criar um multiplicador rápido: por exemplo, na Intel desde Nehalem e AMD desde Ryzen, a multiplicação escalar de 8/16 / 32/64 bits é uma latência de 3 ciclos, com uma taxa de transferência por 1 c (uma unidade de execução totalmente em pipeline). Isso é péssimo em comparação com a taxa de transferência de ADD de 3 ou 4 por relógio, mas é incrível em comparação com a latência IMUL de 9 ciclos no Intel Pentium P5. As coisas são semelhantes para o SIMD: a multiplicação vector-int é uma latência mais alta e uma taxa de transferência menor do que a adição, mas ainda é rápida.
Peter Cordes
Então, sim, multiplicar costumava ser muito mais caro em relação a outras instruções do que é agora. Evitá-lo a um custo de mais de 2 instruções geralmente não vale a pena, e às vezes nem mesmo um substituto de 2 instruções vale a pena (por exemplo, com uma leainstrução shift + add ).
Peter Cordes
9

Eu acho que seria difícil encontrar um processador que tivesse uma adição adicional de mais ciclos do que uma operação bit a bit. Em parte porque a maioria dos processadores deve realizar pelo menos uma adição por ciclo de instruções simplesmente para aumentar o contador do programa. Meras operações bit a bit não são tão úteis.

(Ciclo de instruções, não ciclo de clock - por exemplo, o 6502 realiza no mínimo dois ciclos de clock por instrução devido a não ter pipelines e a não ter um cache de instruções)

O conceito real que você pode estar perdendo é o do caminho crítico : dentro de um chip, a operação mais longa que pode ser executada em um ciclo determina, no nível do hardware, a rapidez com que o chip pode ter clock.

A exceção é a lógica assíncrona (raramente usada e pouco comercializada), que realmente é executada em velocidades diferentes, dependendo do tempo de propagação da lógica, da temperatura do dispositivo etc.

pjc50
fonte
Não são operações bit a bit controláveis ​​pelo usuário, mas algumas instruções no 8086 (por exemplo, limpando o sinalizador de interrupção ) levaram menos ciclos do que uma adição de número inteiro. Mais abstratamente, um sistema RISC em que todas as instruções têm uma palavra em tamanho pode usar um contador binário simples para o PC, o que seria um circuito muito mais rápido que um somador de uso geral.
Mark
A adição sobre o contador de programa tende a ser muito simples em comparação com uma instrução aritmética disso, porque um dos operandos é pequena (um tamanho de instruções, ou um salto de deslocamento relativo, que também é de tamanho limitado)
Ben Voigt
O 6502 foi canalizado - leu o primeiro byte da próxima instrução durante o último ciclo do anterior. Caso contrário, buscar / decodificar / executar teria sido pelo menos três ciclos.
gnasher729
8

No nível do portão, você está certo de que é preciso mais trabalho para fazer acréscimos e, portanto, leva mais tempo. No entanto, esse custo é trivial o suficiente e não importa.

Processadores modernos são cronometrados. Você não pode executar instruções com nada além de múltiplos dessa taxa de clock. Se as taxas de clock fossem aumentadas, para maximizar a velocidade das operações bit a bit, você teria que gastar pelo menos 2 ciclos além disso. Muito desse tempo seria gasto esperando, porque você realmente não precisava dos 2 ciclos completos. Você só precisava de 1.1 (ou algum número assim). Agora, seu chip é mais lento que todos os outros no mercado.

Pior, o simples ato de adicionar ou executar operações bit a bit é apenas uma pequena parte do que está acontecendo durante um ciclo. Você precisa buscar / decodificar instruções dentro de um ciclo. Você deve poder executar operações de cache dentro de um ciclo. Muitas outras coisas acontecem na mesma escala de tempo da operação simples de adição ou de bits.

A solução, é claro, é desenvolver um pipeline extremamente profundo, dividindo essas tarefas em pequenas partes que se encaixam no pequeno tempo de ciclo definido por uma operação bit a bit. O Pentium 4 mostrou famosos os limites do pensamento nesses termos profundos do pipeline. Todos os tipos de problemas surgem. Em particular, a ramificação se torna notoriamente difícil porque você precisa liberar o pipeline depois de ter os dados para descobrir qual ramificação deve ser executada.

Cort Ammon
fonte
7

Os processadores modernos têm clock de clock: cada operação requer um número integral de ciclos de clock. Os projetistas do processador determinam a duração de um ciclo de clock. Existem duas considerações: Uma, a velocidade do hardware, por exemplo, medida como o atraso de um único gate NAND. Isso depende da tecnologia usada e de compensações como velocidade versus uso de energia. É independente do design do processador. Segundo, os projetistas decidem que a duração de um ciclo de clock é igual a n atrasos de um único gate NAND, onde n pode ser 10 ou 30 ou qualquer outro valor.

Essa opção n limita a complexidade das operações que podem ser processadas em um ciclo. Haverá operações que podem ser feitas em 16, mas não em 15 atrasos NAND. Portanto, escolher n = 16 significa que essa operação pode ser realizada em um ciclo, escolhendo n = 15 significa que não pode ser realizada.

Os projetistas escolherão n para que muitas operações importantes possam ser realizadas em um ou em dois ou três ciclos. n será escolhido localmente ideal: se você substituísse n por n-1, a maioria das operações seria um pouco mais rápida, mas algumas (aquelas que realmente precisam de todos os atrasos n na NAND) seriam mais lentas. Se poucas operações desacelerassem, para que a execução geral do programa fosse mais rápida, em média, você escolheria n-1. Você também pode ter escolhido n + 1. Isso torna a maioria das operações um pouco mais lentas, mas se você tiver muitas operações que não podem ser realizadas com n atrasos, mas que podem ser realizadas com n + 1 atrasos, isso tornaria o processador mais rápido.

Agora sua pergunta: adicionar e subtrair são operações tão comuns que você deseja poder executá-las em um único ciclo. Como resultado, não importa que AND, OR etc. possam executar mais rapidamente: eles ainda precisam desse ciclo. É claro que a unidade "calculando" AND, OR etc tem muito tempo para mexer os polegares, mas isso não pode ser ajudado.

Observe que não é apenas se uma operação pode ser realizada com n atrasos NAND ou não: uma adição, por exemplo, pode ser feita mais rapidamente sendo um pouco inteligente, ainda mais rápida por ser muito inteligente, ainda mais rápida, investindo quantidades extraordinárias de hardware e, finalmente, um processador pode ter uma mistura de circuitos muito rápidos, muito caros e um pouco mais lentos e mais baratos; portanto, há a possibilidade de fazer uma operação com rapidez suficiente, gastando mais dinheiro com isso.

Agora você pode tornar a velocidade do relógio tão alta / o ciclo tão curto que apenas as operações simples de bits são executadas em um ciclo e todo o resto em dois ou mais. Isso provavelmente atrasaria o processador. Para operações que levam dois ciclos, geralmente há sobrecarga para mover uma instrução incompleta de um ciclo para o próximo, portanto, dois ciclos não significa que você tem o dobro do tempo para execução. Então, para fazer a adição em dois ciclos, você não pode dobrar a velocidade do relógio.

gnasher729
fonte
6

Deixe-me corrigir algumas coisas que não foram mencionadas explicitamente em suas respostas existentes:

Eu sei que as operações bit a bit são tão rápidas nos processadores modernos, porque podem operar em 32 ou 64 bits em paralelo,

Isso é verdade. Rotular uma CPU como bit "XX" geralmente (nem sempre) significa que a maioria de suas estruturas comuns (larguras de registro, RAM endereçável etc.) tem tamanho de XX bits (geralmente "+/- 1" ou algo assim). Mas em relação à sua pergunta, você pode assumir com segurança que uma CPU com 32 bits ou 64 bits fará qualquer operação básica de bits em 32 ou 64 bits em tempo constante.

portanto, as operações bit a bit levam apenas um ciclo de clock.

Esta conclusão não é necessariamente o caso. Especialmente CPUs com conjuntos de instruções avançados (google CISC vs. RISC) podem facilmente levar mais de um ciclo para comandos simples. Com a intercalação, mesmo comandos simples podem ser divididos em fetch-exec-store com 3 relógios (como exemplo).

No entanto addtion é uma operação complexa

Não, a adição de números inteiros é uma operação simples; subtração também. É muito fácil implementar adicionadores em hardware completo, e eles fazem suas coisas instantaneamente como operações básicas de bits.

que consiste em pelo menos uma e possivelmente até uma dúzia de operações bit a bit, então naturalmente pensei que seria 3-4 vezes mais lento.

Serão necessários 3-4 vezes mais transistores, mas em comparação com o quadro geral que é negligenciável.

Fiquei surpreso ao ver, após um simples benchmark, que a adição é exatamente tão rápida quanto qualquer uma das operações bit a bit (XOR, OR, AND etc.). Alguém pode esclarecer isto?

Sim: a adição de números inteiros é uma operação bit a bit (com mais alguns bits que os outros, mas ainda assim). Não há necessidade de fazer nada em etapas, não há necessidade de algoritmos complicados, relógios ou qualquer outra coisa.

Se você deseja adicionar mais bits do que a arquitetura da CPU, você será penalizado por fazê-lo em etapas. Mas isso está em outro nível de complexidade (nível da linguagem de programação, não nível de montagem / código de máquina). Esse era um problema comum no passado (ou hoje em pequenas CPUs incorporadas). Para PCs etc., seus 32 ou 64 bits são suficientes para que os tipos de dados mais comuns comecem a se tornar um ponto discutível.

AnoE
fonte
É interessante notar que reduzir o custo do tempo de adição de O (N) para O (sqrt (N)) não aumenta significativamente o número necessário de transistores ou a complexidade de roteamento (cada estágio precisa apenas permitir que um fio se esgueire de baixo para baixo , e é preciso haver estágios extras de fusão do sqrt (N) .O custo do tempo pode ser reduzido para O (lgN) a um custo de transistores O (lgN), mas em muitos casos pode ser útil processar algo como um 64- além pouco como por exemplo oito bits 8 acrescenta (usando sqrtN encaminhamento) juntou-se com três camadas de fusão lógica, em vez de como um 64 bits acrescenta com seis camadas de fusão.
supercat
Sim, adicionadores são bastante simples. O que é realmente impressionante são as CPUs x86 modernas com um multiplicador inteiro de 64 bits de latência e ciclo de 3 ciclos . (por exemplo, imul rax, rcxpossui latência 3c e taxa de transferência de 1 por 1c na família Intel Sandybridge e AMD Ryzen). Mesmo a multiplicação completa de 64 bits (produzindo o resultado de 128 bits em rdx: rax) tem a mesma latência e taxa de transferência, mas é implementada como 2 uops (que são executados em paralelo em portas diferentes). (Consulte agner.org/optimize para obter tabelas de instruções e um excelente guia de microarquitetura).
Peter Cordes
[add-with-carry] está em outro nível de complexidade (nível de linguagem de programação, não de montagem / código de máquina . Depende do idioma. O compilador AC direcionado a uma CPU de 16 bits deve emitir add / adc para você quando compilar adição de dois uint32_tvalores. Isso ainda é relevante hoje para int64_t em destinos de 32 bits. O AVR é ​​um microcontrolador RISC de 8 bits, portanto, números inteiros de 32 bits exigem 4 instruções: godbolt.org/g/wre0fM
Peter Cordes
Sim, @ PeterCordes, foi isso que eu quis dizer, esclarei um pouco minha frase.
AnoE