O Pentium tinha um circuito dedicado e complexo para multiplicar por 3

 (righto.com)
3 pontos por GN⁺ 2025-03-04 | 1 comentários | Compartilhar no WhatsApp
  • Em 1993, o Pentium da Intel incluía um circuito dedicado de ×3 para gerar valores triplicados rapidamente no processamento de multiplicação em ponto flutuante, e só esse pequeno circuito usava milhares de transistores
  • O Pentium usa multiplicação radix-8 para reduzir os termos a somar de 64 para 22 em uma multiplicação de 64 bits, mas esse método exige gerar rapidamente múltiplos de ×3
  • O cálculo de ×3 em si é a soma x + 2x, mas como o restante das etapas da multiplicação precisa esperar esse resultado, são necessárias técnicas de somadores rápidos como carry lookahead e Kogge-Stone
  • O circuito tem uma estrutura hierárquica que combina 8 blocos de 8 bits com lookahead superior, e a saída real se expande para 69 bits por causa de overflow e arredondamento
  • O fato de cerca de 9000 transistores serem usados em um único circuito de ×3 mostra o nível de otimização complexa de hardware empregado na geração Pentium em busca de desempenho

Por que o Pentium tinha um circuito separado de ×3

  • O multiplicador de ponto flutuante do Pentium multiplica dois números de 64 bits usando o método radix-8
    • Na multiplicação binária comum, soma-se 0 ou o multiplicando para cada bit, então uma multiplicação de 64 bits exige 64 termos
    • No método radix-8, o multiplicador é agrupado em blocos de 3 bits para multiplicar por um valor entre 0 e 7, reduzindo os termos a somar para 22
  • Alguns dos múltiplos entre 0 e 7 podem ser gerados com relativa simplicidade no hardware
    • ×2 é feito com um deslocamento de 1 bit para a esquerda
    • ×4 é feito com um deslocamento de 2 bits para a esquerda
    • ×6 e ×7 podem ser tratados com o algoritmo de multiplicação de Booth, combinando +1 da próxima posição radix-8 com a subtração da posição atual
    • ×5 pode ser obtido subtraindo ×3 de ×8
  • No fim, o múltiplo realmente problemático é o ×3, e o Pentium resolve isso com um circuito dedicado dentro do multiplicador de ponto flutuante

Onde uma soma simples vira gargalo

  • O valor triplicado pode ser gerado somando o valor de entrada com ele mesmo deslocado 1 bit para a esquerda
    • Em termos estruturais, é a soma x + 2x
  • O gargalo aparece na propagação de carry durante a soma
    • Em um somador ripple-carry, o carry gerado nos bits inferiores precisa se propagar em sequência até os bits superiores
    • Como o restante do processo de multiplicação não pode começar antes que o resultado de ×3 esteja pronto, é preciso reduzir esse atraso
  • O Pentium usa um carry-lookahead adder para calcular os carries em paralelo, em vez de propagá-los sequencialmente
    • Em cada bit, ele gera sinais de carry generate e carry propagate
    • generate indica que aquela posição gera um carry
    • propagate indica que um carry de entrada será repassado adiante
    • Quando os carries são calculados em paralelo, os bits da soma também podem ser calculados em paralelo

Kogge-Stone e carry lookahead em 2 níveis

  • Se o carry lookahead for implementado de forma direta, a carga de circuito e de interconexão cresce conforme aumenta o número de bits
    • A lógica fica mais complexa nas posições de bits mais altas
    • Portas com muitas entradas ficam mais lentas por razões elétricas
  • O Pentium usa um somador prefixado paralelo Kogge-Stone em blocos de 8 bits
    • O Kogge-Stone calcula os carries em paralelo combinando sinais propagate/generate por intervalos
    • Ele reutiliza resultados intermediários para controlar atraso e área de circuito
  • Em vez de tratar todos os 64 bits com um único Kogge-Stone, o Pentium divide o problema em uma estrutura hierárquica de 2 níveis
    • O nível inferior usa 8 circuitos Kogge-Stone de 8 bits para calcular os carries dentro de cada bloco
    • O nível superior trata cada bloco de 8 bits como uma unidade e calcula os carries entre blocos
    • A combinação dos dois níveis fornece rapidamente os carries necessários para a soma de 64 bits
  • Embora o circuito possa ser visto como sendo de 64 bits, na prática ele produz uma saída de 69 bits, incluindo bits extras para evitar overflow e para arredondamento

carry-select para reduzir o tempo de espera

  • Cada bloco de 8 bits inclui um carry-select adder
    • Ele calcula antecipadamente as duas somas possíveis: uma para carry-in igual a 0 e outra para carry-in igual a 1
    • Quando o circuito superior de lookahead informa o carry-in real, um multiplexador escolhe o resultado correto
  • Essa abordagem economiza tempo em troca de mais hardware
    • São necessários dois adders e um multiplexador para selecionar o resultado
    • O cálculo da soma e o cálculo do carry passam a ocorrer em sobreposição, reduzindo o atraso total
  • O bloco de 8 bits mais baixo não tem carry-in, então não precisa de circuito carry-select
    • Os bits de saída desse bloco são calculados com portas XNOR

O que acontece dentro de um bloco de 8 bits

  • Cada bloco de 8 bits do circuito de ×3 divide as linhas de entrada entre o adder à esquerda e o caminho à direita
    • Essa estrutura de ramificação implementa o ×3 ao somar o valor de entrada com ele mesmo deslocado 1 bit para a esquerda
  • A parte superior do bloco é formada pelo circuito que gera os sinais propagate/generate
    • Esses sinais entram no circuito lookahead Kogge-Stone de 8 bits
    • A parte Kogge-Stone tem complexidade diferente em cada posição de bit, então sua aparência é irregular, e não a de um bloco repetido
  • A parte inferior do bloco é a área do carry-select adder
    • As duas somas são calculadas antecipadamente, e o multiplexador escolhe conforme o carry-in
    • Os blocos do carry-select adder são colocados de forma mais estreita que o circuito ao redor, abrindo espaço para parte do circuito Kogge-Stone superior
  • Cada bloco amplifica seus bits de saída com um circuito driver antes de enviá-los ao circuito multiplicador seguinte

Portas XNOR e implementação no nível de transistores

  • As portas XNOR na região dos bits mais baixos são implementadas no Pentium como multiplexadores
    • O Intel 386 implementava XOR com portas AND-NOR, e o Z-80 usava transistores de passagem, mas a abordagem do Pentium é diferente
  • Esse circuito XNOR é composto por quatro inversores e um multiplexador com transistores de passagem
    • A entrada B escolhe, entre as duas entradas do multiplexador, a entrada A ou A invertido
    • O resultado é a função XNOR
  • Na análise das fotos do chip, as duas camadas metálicas superiores foram removidas para observar a camada metálica inferior M1 e as regiões de silício dopado
    • Os pontos em que linhas de polisilício cruzam o silício dopado formam as portas dos transistores
    • O circuito CMOS é composto por transistores NMOS na parte superior e PMOS na parte inferior

Driver de saída BiCMOS

  • A saída do circuito de ×3 exige corrente alta
    • Cada sinal de ×3 pode acionar até 22 termos dentro do multiplicador de ponto flutuante
    • O circuito de destino pode estar fisicamente distante do circuito de ×3
    • Fios longos e muitas portas de transistores aumentam a capacitância, e mudar o sinal rapidamente exige corrente elevada
  • O Pentium usa um processo BiCMOS que combina transistores bipolares e CMOS no mesmo chip
    • O Pentium usava circuitos BiCMOS de forma ampla para reduzir o atraso de sinal em até 35%
    • A Intel também usou BiCMOS no Pentium Pro, Pentium II, Pentium III e Xeon
    • Conforme a tensão dos chips caiu, a vantagem dos transistores bipolares diminuiu, e o BiCMOS acabou deixando de ser usado
  • O driver do circuito de ×3 tem uma estrutura em que um driver BiCMOS aciona um segundo driver BiCMOS
    • As portas dos transistores do inversor de alta corrente são grandes, então é necessário um estágio intermediário para acioná-las
    • Amplificar um sinal pequeno em vários estágios pode reduzir o atraso total
  • O transistor NPN do driver BiCMOS aparece como uma grande estrutura em forma de caixa, diferente de um transistor MOS comum
    • O inversor usa a estrutura CMOS padrão, elevando a saída com PMOS e reduzindo-a com NMOS
    • Alguns inversores são projetados com características de corrente assimétricas para fornecer um nível alto forte ou um nível baixo forte

O aumento de complexidade mostrado pelo hardware de multiplicação

  • A história do hardware de multiplicação em computadores remonta aos anos 1950
  • Os primeiros microprocessadores tinham suporte limitado a multiplicação em hardware
    • Processadores como o 6502 não tinham hardware de multiplicação, então o usuário precisava implementar isso em software com deslocamentos e somas
    • O Intel 8086 executava um loop lento de shift-and-add em microcódigo
    • O 386 incluía uma multiply unit, mas a instrução de multiplicação podia levar até 41 ciclos de clock
  • Na época do Pentium, já era possível integrar milhões de transistores, o que abriu espaço para otimizações de desempenho muito mais complexas
    • A multiplicação em ponto flutuante do Pentium leva 3 ciclos de clock, e o circuito multiplicador é usado durante 2 desses ciclos
    • A multiplicação inteira MUL é bem mais lenta, com 11 ciclos
    • A microarquitetura Nehalem, em 2008, reduziu a multiplicação em ponto flutuante para 1 ciclo
  • O multiplicador ×3 do Pentium contém cerca de 9000 transistores
    • Isso é um pouco mais do que o microprocessador Z80 inteiro, lançado em 1976
    • O circuito de ×3 é apenas uma pequena parte do multiplicador de ponto flutuante dentro da unidade de ponto flutuante do Pentium

Leituras relacionadas

1 comentários

 
GN⁺ 2025-03-04
Opiniões no Hacker News

  • É uma tangente bem lateral, mas, muito tempo atrás, enquanto eu trabalhava em emulação de computadores ternários, usei um truque bonitinho para encontrar uma transformação em forma fechada que convertia a divisão por potências de 3 em uma série de shifts de bits e somas
    Primeiro, basta notar que 1/3 - 1/2 = 2/6 - 3/6, ou seja, 1/3 = 1/2 - 1/2 (1/3)
    Substituindo essa expressão infinitamente no lado direito, aparece uma forma 1/3 = -(-1/2)^N, com N no intervalo 1..inf
    Dá para fazer algo parecido não só com pares de potências de 2 e 3, mas também em outras bases
    O significado é que, para valores próximos de potências de 2, é bastante fácil criar um circuito de divisão constante em tempo fixo usando apenas somadores e subtratores

    • Impressionante. Imagino que um computador ternário se baseasse em lógica de três estados; será que é correto entender que isso era menos confiável do que transistores, ou até válvulas, codificando estados binários?

  • O processador dos jogos de arcade da Cinematronics tem dois acumuladores de 12 bits
    A instrução de multiplicação desloca os dois para a direita como se fossem um único valor de 24 bits e, se sair 1 no bit menos significativo, soma o conteúdo da memória
    Então você zerava a metade superior, carregava um valor na metade inferior e — já esqueci como era configurado o endereço de memória do outro operando — executava várias multiplicações de 1 bit em sequência
    Assim era possível obter um produto de 24 bits, mas a maior parte do código que vi encadeava 8 multiplicações, e o uso mais comum era multiplicação de matriz 2x2 para rotacionar coordenadas de objetos do jogo
    Era feito com peças prontas da série 7400 em meados dos anos 1970, e o throughput máximo era de 5 MIPS

    • Acho que uma multiplicação não levava exatamente um ciclo. Nesse caso, os 5 MIPS seriam consumidos rapidamente
      Nas últimas duas décadas, houve algumas vezes em que precisei fazer aritmética de ponto fixo, e meu respeito pelos programadores das gerações anteriores aumentou

  • Complementando a parte em que talvez você já tenha ouvido falar de técnicas como carry lookahead e Kogge-Stone addition: aqui, Kogge é Peter Kogge
    Ele fez o doutorado em Stanford, trabalhou em coisas relacionadas ao ônibus espacial, é IBM Fellow e foi quem inventou a primeira CPU multicore

    • Embora seja claro que ele tenha muitas realizações, a formulação de que inventou a primeira CPU multicore poderia ser omitida sem prejudicar os fatos, e acho que o mundo ficaria melhor sem esse tipo de frase
      “CPU multicore”, em si, rigorosamente falando, é mais uma ideia do que uma invenção. Em certo ponto da história dos semicondutores, também é uma ideia bastante óbvia e trivial
      Fazer uma CPU multicore funcionar de fato não é trivial, mas isso também não é uma única invenção; nessa época as equipes de desenvolvimento já eram tão grandes que dizer que uma pessoa resolveu todos os problemas sozinha chega a ser ofensivo
      Kogge pode ter liderado o desenvolvimento da primeira CPU multicore, e talvez tenha sido um pioneiro que insistiu nisso antes que outros vissem como possível, mas, em qualquer caso, ele não a inventou sozinho
    • Eu achava que a equipe da primeira CPU multicore tinha sido liderada por Kunle Olukotun
    • Mais uma coisa: Peter Kogge escreveu um dos primeiros livros-texto sobre microarquitetura em pipeline, que vale a leitura para quem quer aprender como os primeiros processadores vetoriais de supercomputadores eram projetados: The Architecture of Pipelined Computers (1981)
    • Peter já prestou consultoria e colaborou com nosso laboratório. Ele defendia a abordagem de levar a computação de sensoriamento remoto para mais perto dos sensores — no vocabulário atual, edge computing
      Essa abordagem é intelectualmente bem defensável. Se há latência ou custo para mover os dados até a computação central, ela faz sentido; no nosso caso, por serem sensores baseados no espaço, era possível montar esse argumento
      Porém, até onde sei, esse tipo de processamento nunca foi adotado de forma sistemática em sistemas de processamento baseados no espaço, embora muitos sistemas, como radares, façam reduções provisórias de dados em hardware próximo ao sensor
      Obrigado por apontar essa conexão

  • Sou o autor. Se tiverem perguntas, respondo

    • Fiquei curioso sobre o que aconteceu com o multiplicador dedicado por 3 nas máquinas posteriores. Ele continuou existindo de alguma forma, ou a estratégia mudou e ele deixou de ser útil?
    • Ken, já não está na hora de publicar um livro?
    • Talvez seja uma pergunta básica, mas isso é para multiplicação em ponto flutuante? Como o expoente também precisa ser somado, a parte que é realmente multiplicada não é menor que 64 bits?
    • Minha compreensão está meio nebulosa, então ignore se for uma pergunta muito boba, mas, se “quando dá para calcular ×3, você pode subtrair de ×8 para obter ×5”, por que não daria para subtrair x4 de x7 para obter x3?

  • Acho que algo ficou faltando
    Se ×2 é fácil de calcular a ponto de permitir usar 6x = 8x - 2x, e ×4 também é fácil como 4x = 4x, não entendo por que calcular 3x como a soma 2x + 1x ou a diferença 4x - 1x seria mais difícil do que isso
    Também fico curioso: se ×6 pode ser calculado facilmente de algum modo, por que não deslocar esse valor para a direita para obter ×3? Seria uma etapa extra, mas essa etapa é um shift

    • Em uma multiplicação de 64 bits, você soma 22 termos, um para cada dígito em octal. Pense na multiplicação do ensino fundamental
      Cada termo precisa ser trivial de calcular; para obter um termo, você pode fazer shift ou inverter o sinal, mas não pode fazer outra soma
      O ponto central é que, se você pré-calcula ×3 uma vez, depois pode simplesmente usá-lo em qualquer um dos 22 termos necessários
      Não dá para colocar ×2 e ×1 dentro de um termo para formar ×3. Para isso, você precisaria de outro somador para cada termo
      Em outras palavras, o que se quer é um único circuito que calcule ×3, não 22 circuitos
      Quanto à pergunta sobre ×6, esse valor é calculado colocando um ×2 negativo no termo e, conceitualmente, somando 1 ao dígito seguinte para obter ×8. Esse valor ×8 faz parte de um termo completamente diferente, então não dá para deslocá-lo para a direita
      Há muitos números e somas indo e vindo, então é complicado, mas visto assim deve fazer sentido

  • Multiplicação por 3 é, na prática, uma operação comum, especialmente em cálculo de endereços, em que muitas vezes se multiplica um índice por 3 usando shift e soma
    Se implementado de forma ingênua, a latência aumenta bastante. Mas, usando esse circuito, a instrução LEA (Load Effective Address) pode ser processada em um ciclo, então gastar esse orçamento de transistores nisso era uma escolha plenamente boa

    • Esse circuito é mesmo usado ali? Pelo que entendi do texto, esse circuito faz parte da multiplicação de ponto flutuante
    • Não entendo o que você quer dizer
      LEA é apenas uma instrução que coloca o endereço calculado pelo modo de endereçamento no operando de saída, em vez de transferir dados daquele endereço, e todos os cálculos de endereço que a LEA consegue fazer a instrução MOV também consegue
      No x86, o modo de endereçamento indexado usado por MOV ou LEA não suporta fator de escala 3, apenas potências de 2 como 1, 2, 4 e 8. Portanto, na geração de endereços não há onde usar multiplicação por 3
      O texto deixa claro que o multiplicador por 3 faz parte do multiplicador de ponto flutuante

  • “Este multiplicador ×3 contém aproximadamente 9000 transistores, um pouco mais que todo o microprocessador Z80 (1976). Lembre-se de que o multiplicador ×3 é apenas uma pequena parte do multiplicador de ponto flutuante dentro da unidade de ponto flutuante do Pentium. Ou seja, um pequeno pedaço de uma função é mais complexo que um microprocessador inteiro de 17 anos antes, o que mostra o quanto a complexidade dos processadores aumentou enormemente.”
    Esse ritmo de crescimento de desempenho foi o que gerou o inchaço de software atual. Porque o ganho de desempenho do ano seguinte conseguia encobrir a maior parte da culpa por não pensar criticamente em algoritmos e em contexto/localidade do fluxo de dados
    Hoje, pelo que li, chegamos ao limite prático do que é razoavelmente possível com a tecnologia de semicondutores de silício e a compreensão atual da física. Agora o pêndulo precisa se mover no sentido oposto, e os computadores devem trabalhar de forma mais inteligente, não mais à força

    • O “limite prático do que é possível com a compreensão atual da física” já tinha sido alcançado décadas atrás
    • O fenômeno em que o inchaço de software acompanha o ritmo das melhorias de hardware é conhecido como Lei de Wirth: https://en.wikipedia.org/wiki/Wirth%27s_law
      Só que acho que o inchaço de software está crescendo mais rápido
    • Por outro lado, o multiplicador tem uma estrutura muito mais regular que o Z80. O caminho de dados do Pentium também é várias vezes mais largo
    • A história das chamadas de função: movimentação de instruções com goto/jmp → consulta à vtable → hash e busca em um dicionário → execução de grandes modelos de linguagem
    • Felizmente, ainda há bastante espaço para melhoria na maioria das aplicações

  • “Em vez de multiplicar por 7, soma-se 8 vezes o número e subtrai-se o número para obter 7 vezes. Pode parecer que isso exige duas etapas, mas, com o truque de multiplicar por mais 1 na posição à esquerda, obtém-se o coeficiente 8 vezes sem uma etapa adicional.”
    Isso quer dizer que há um somador que adiciona 1 à “próxima posição” antes de inserir o número na parte principal do multiplicador? Isso, por si só, também parece algo parecido com um circuito de previsão de carry
    Também me faz pensar em quando isso é necessário: 7 = 8-1, 6 = 8-2, 5 = 8-3, 4 = 8-4
    No último caso, o texto não diz que isso é feito, mas parece que daria para economizar algumas portas se o bit mais significativo do valor de 3 bits fosse usado para decidir se é preciso somar 1 à próxima posição

  • É interessante a escolha de um multiplicador Booth de base 8 que precisa de um circuito ×3. Parece uma troca área/desempenho para elevar a frequência máxima, e como o mesmo poderia ter sido feito com mais pipelining, provavelmente havia uma restrição de ciclos de latência

    • Sim, é uma troca. Na época, muitas outras unidades de ponto flutuante usavam base 4, porque assim podiam evitar o circuito ×3 adicional
      O pipelining é complicado, porque não há uma boa posição para dividir o array de multiplicação em dois

  • https://github.com/EI2030/Low-power-E-Paper-OS/blob/master/P...
    8086: 29.000
    386: 275.000
    486: 1,2 milhão
    Pentium: 3,1 milhões
    Pelo que me lembro, a NSA entrou nesse jogo em algum momento depois de 2000