Por que não há instrução `nand` nas CPUs modernas?

52

Por que os designers do x86 (ou outras arquiteturas de CPU também) decidiram não incluí-lo? É uma porta lógica que pode ser usada para construir outras portas lógicas, portanto, é rápida como uma única instrução. Em vez de encadeamento note andinstruções (ambas são criadas a partir de nand), por que nenhuma nandinstrução ?.

Amumu
fonte
20
Qual é o seu caso para a instrução nand? Provavelmente, os designers do x86 nunca encontraram nenhum.
PlasmaHH 17/01
16
ARM tem a BICinstrução, que é a & ~b. Braço Thumb-2 tem a ORNinstrução que é ~(a | b). O BRAÇO é bem moderno. A codificação de uma instrução no conjunto de instruções da CPU tem seus custos. Portanto, apenas os mais "úteis" estão entrando no ISA.
Eugene Sh.
24
@ Amumu Poderíamos ter ~(((a << 1) | (b >> 1)) | 0x55555555)instruções também. O objetivo seria que ~(((a << 1) | (b >> 1)) | 0x55555555)pudesse ser traduzido em uma única instrução em vez de 6. Então, por que não?
precisa saber é o seguinte
11
@ Amumu: Isso não é um caso de uso, e também não ~. Um caso de usuário é um motivo convincente pelo qual essa instrução é útil e onde pode ser aplicada. Seu raciocínio é como dizer "A instrução deve estar lá para que possa ser usada", mas a questão é "para que usá-la é tão importante que é útil gastar recursos".
precisa saber é o seguinte
4
Faço programação há 45 anos, escrevi alguns compiladores e usei alguns operadores lógicos estranhos quando disponíveis, como o IMP, mas nunca usei um operador ou instrução NAND.
precisa saber é o seguinte

Respostas:

62

http://www.ibm.com/support/knowledgecenter/ssw_aix_61/com.ibm.aix.alangref/idalangref_nand_nd_instrs.htm : POWER possui NAND.

Mas geralmente as CPUs modernas são construídas para corresponder à geração automatizada de código pelos compiladores, e o NAND bit a bit é muito raramente solicitado. Bitwise AND e OR são usados ​​com mais frequência para manipular campos de bits em estruturas de dados. De fato, o SSE possui AND-NOT, mas não NAND.

Toda instrução tem um custo na lógica de decodificação e consome um código de operação que pode ser usado para outra coisa. Especialmente em codificações de tamanho variável, como x86, você pode ficar sem códigos de operação curtos e precisar usar códigos mais longos, o que potencialmente diminui todo o código.

pjc50
fonte
5
@supercat AND-NOT é comumente usado para desativar bits em uma variável definida por bits. por exemploif(windowType & ~WINDOW_RESIZABLE) { ... do stuff for variable-sized windows ... }
adib 17/01
2
@adib: Sim. Uma característica interessante do "e-não" é que, diferentemente do operador "bit a bit", o tamanho do resultado não importa. Se foofor um uint64_t, a instrução foo &= ~something;às vezes pode limpar mais bits do que o pretendido, mas se houvesse um &~=operador, esses problemas poderiam ser evitados.
Supercat
6
@adib se WINDOW_RESIZABLEfor uma constante, um otimizador deve avaliar ~WINDOW_RESIZABLEem tempo de compilação, portanto, esse é apenas um AND em tempo de execução.
alephzero
4
@ MarkRansom: Não, a causa e o efeito estão totalmente corretos no histórico da computação. Esse fenômeno de projetar CPUs otimizadas para compiladores em vez de programadores de montagem humana fazia parte do movimento RISC (no entanto, o próprio movimento RISC é mais amplo do que apenas esse aspecto). As CPUs projetadas para compiladores incluem o ARM e o Atmel AVR. No final dos anos 90 e início dos anos 00, as pessoas contratavam escritores de compiladores e programadores de sistemas operacionais para projetar conjuntos de instruções de CPU
slebetman
3
Atualmente, as operações de registro para registro são essencialmente gratuitas em comparação com o acesso à RAM. A implementação de instruções redundantes custa imobiliário de silício na CPU. Portanto, geralmente haverá apenas uma forma de bit a bit-OR e bit a bit-AND, porque adicionar uma operação de registro de complemento bit a bit dificilmente reduzirá a velocidade de qualquer coisa.
precisa saber é o seguinte
31

O custo de tais funções ALU é

1) a lógica que executa a própria função

2) o seletor que seleciona esse resultado da função em vez dos outros de todas as funções da ALU

3) o custo de ter essa opção no conjunto de instruções (e de não ter outra função útil)

Concordo com você que o 1) custo é muito pequeno. O custo 2) e 3), no entanto, é quase independente da função. Penso que, neste caso, o 3) custo (os bits ocupados na instrução) foram a razão de não ter essa instrução específica. Os bits em uma instrução são um recurso muito escasso para um designer de CPU / arquitetura.

Wouter van Ooijen
fonte
29

Inverta - primeiro veja por que o Nand era popular no design da lógica de hardware - ele tem várias propriedades úteis lá. Em seguida, pergunte se essas propriedades ainda se aplicam em uma instrução de CPU ...

TL / DR - eles não têm, portanto não há desvantagem em usar And, Or ou Not.

A maior vantagem da lógica Nand com fio foi a velocidade, obtida pela redução do número de níveis lógicos (estágios do transistor) entre as entradas e saídas de um circuito. Em uma CPU, a velocidade do clock é determinada pela velocidade de operações muito mais complexas, como a adição, portanto, acelerar uma operação AND não permitirá aumentar a taxa de clock.

E o número de vezes que você precisa combinar outras instruções é muito pequeno - o suficiente para que o Nand realmente não ganhe espaço no conjunto de instruções.

Brian Drummond
fonte
11
Nos casos em que o isolamento de entrada não é necessário ", e não" pareceria muito barato em hardware. Em 1977, projetei um controlador de sinal de mudança de direção para o trailer de meus pais usando dois transistores e dois diodos por luz para executar uma função "XOR" [lâmpada esquerda == xor (sinal esquerdo, freio); lâmpada direita == xor (sinal direito, freio)], essencialmente conectando duas ou mais funções para cada luz. Eu não vi esses truques usados ​​no projeto LSI, mas acho que em TTL ou NMOS, nos casos em que qualquer coisa que esteja alimentando uma entrada teria capacidade de unidade adequada, esses truques poderiam economizar circuitos.
Supercat
12

Eu gostaria de concordar com Brian aqui, Wouter e pjc50.

Eu também gostaria de acrescentar que, de propósito geral, especialmente os processadores CISC, as instruções nem todas têm as mesmas taxas de transferência - uma operação complicada pode simplesmente levar mais ciclos do que a fácil.

Considere o X86: AND(que é uma operação "e") é provavelmente muito rápido. O mesmo vale para NOT. Vejamos um pouco de desmontagem:

Código de entrada:

#include <immintrin.h>
#include <stdint.h>

__m512i nand512(__m512i a, __m512i b){return ~(a&b);}
__m256i nand256(__m256i a, __m256i b){return ~(a&b);}
__m128i nand128(__m128i a, __m128i b){return ~(a&b);}
uint64_t nand64(uint64_t a, uint64_t b){return ~(a&b);}
uint32_t nand32(uint32_t a, uint32_t b){return ~(a&b);}
uint16_t nand16(uint16_t a, uint16_t b){return ~(a&b);}
uint8_t nand8(uint8_t a, uint8_t b){return ~(a&b);}

Comando para produzir montagem:

gcc -O3 -c -S  -mavx512f test.c

Conjunto de saída (reduzido):

    .file   "test.c"
nand512:
.LFB4591:
    .cfi_startproc
    vpandq  %zmm1, %zmm0, %zmm0
    vpternlogd  $0xFF, %zmm1, %zmm1, %zmm1
    vpxorq  %zmm1, %zmm0, %zmm0
    ret
    .cfi_endproc
nand256:
.LFB4592:
    .cfi_startproc
    vpand   %ymm1, %ymm0, %ymm0
    vpcmpeqd    %ymm1, %ymm1, %ymm1
    vpxor   %ymm1, %ymm0, %ymm0
    ret
    .cfi_endproc
nand128:
.LFB4593:
    .cfi_startproc
    vpand   %xmm1, %xmm0, %xmm0
    vpcmpeqd    %xmm1, %xmm1, %xmm1
    vpxor   %xmm1, %xmm0, %xmm0
    ret
    .cfi_endproc
nand64:
.LFB4594:
    .cfi_startproc
    movq    %rdi, %rax
    andq    %rsi, %rax
    notq    %rax
    ret
    .cfi_endproc
nand32:
.LFB4595:
    .cfi_startproc
    movl    %edi, %eax
    andl    %esi, %eax
    notl    %eax
    ret
    .cfi_endproc
nand16:
.LFB4596:
    .cfi_startproc
    andl    %esi, %edi
    movl    %edi, %eax
    notl    %eax
    ret
    .cfi_endproc
nand8:
.LFB4597:
    .cfi_startproc
    andl    %esi, %edi
    movl    %edi, %eax
    notl    %eax
    ret
    .cfi_endproc

Como você pode ver, para os tipos de dados com tamanho abaixo de 64, tudo é tratado como comprido (daí eu e não l ), já que essa é a largura de bits "nativa" do meu compilador, ao que parece.

O fato de existirem movs entre isso se deve apenas ao fato de eaxser o registrador que contém o valor de retorno de uma função. Normalmente, você apenas calcula o ediregistro de uso geral para calcular o resultado.

Para 64 bits, é o mesmo - apenas com as qpalavras "quad" (portanto, à direita ) e rax/ em rsivez de eax/ edi.

Parece que, para operandos de 128 bits e maiores, a Intel não se importou em implementar uma operação "não"; em vez disso, o compilador produz um 1registro completo (auto-comparação do registro consigo mesmo, resultado armazenado no registro com a vdcmpeqdinstrução) e xoré isso.

Resumindo: ao implementar uma operação complicada com várias instruções elementares, você não necessariamente desacelera a operação - simplesmente não há vantagem em ter uma instrução que executa várias tarefas se não for mais rápida.

Marcus Müller
fonte
10

Primeiro, não confunda operações lógicas e bit a bit.

As operações bit a bit são geralmente usadas para definir / limpar / alternar / verificar bits nos campos de bits. Nenhuma dessas operações requer nand ("e não", também conhecido como "pouco claro" é mais útil).

As operações lógicas nas linguagens de programação mais modernas são avaliadas usando lógica de curto-circuito. Geralmente, é necessária uma abordagem baseada em ramificações para implementá-las. Mesmo quando o compilador pode determinar que a avaliação de curto-circuito versus avaliação completa não faz diferença para o comportamento do programa, os operandos para as operações lógicas geralmente não estão em uma forma conveniente para implementar a expressão usando as operações bit asm.

Peter Green
fonte
10

Muitas vezes, o NAND não é implementado diretamente, porque ter a instrução AND implicitamente permite que você salte em uma condição NAND.

A realização de uma operação lógica em uma CPU geralmente define bits em um registro de sinalizador.

A maioria dos registradores de bandeiras tem uma bandeira ZERO. O sinalizador zero é definido se o resultado de uma operação lógica for zero e limpo de outra forma.

As CPUs mais modernas têm uma instrução de salto que salta se o sinalizador zero estiver definido. Eles também têm uma instrução que salta se o sinalizador zero não estiver definido.

AND e NAND são complementos. Se o resultado de uma operação AND for zero, o resultado de uma operação NAND será 1 e vice-versa.

Portanto, se você quiser pular se o NAND de dois valores for verdadeiro, basta executar a operação AND e pular se o sinalizador zero estiver definido.

Portanto, se você quiser pular se o NAND de dois valores for falso, basta executar a operação AND e pular se o sinalizador zero estiver limpo.

user4574
fonte
De fato - a escolha da instrução de salto condicional oferece uma opção de lógica inversa e não inversora para toda uma classe de operações, sem a necessidade de implementar essa escolha para cada uma individualmente.
Chris Stratton
Esta deveria ter sido a melhor resposta. As operações de sinalizador zero tornam NAND supérfluo para operações lógicas, pois AND + JNZ e AND + JZ são essencialmente em curto-circuito / lógicos AND e NAND, respectivamente, ambos recebem o mesmo número de código de operação.
Lie Ryan
4

Só porque algo é barato , não significa que é econômico .

Se considerarmos sua argumentação ad absurdum, chegaremos à conclusão de que uma CPU deve ser composta principalmente de centenas de tipos de instruções NOP - porque elas são as mais baratas de implementar.

Ou compará-lo com instrumentos financeiros: você compraria um título de US $ 1 com retorno de 0,01% só porque pode? Não, você prefere economizar esses dólares até ter o suficiente para comprar um título de US $ 10 com melhor retorno. O mesmo vale para o orçamento de silicone em uma CPU: é eficaz encontrar muitas operações baratas, mas inúteis, como a NAND, e colocar os transistores salvos em algo muito mais caro, mas realmente útil.

Não há corrida para ter o maior número possível de operações. Como o RISC vs o CISC provou o que Turing sabia desde o início: menos é mais. Na verdade, é melhor ter o mínimo de operações possível.

Agent_L
fonte
nopnão pode implementar todas as outras portas lógicas, mas nandou norpodem, efetivamente recriar qualquer instrução que é implementado em uma CPU em software. Se tomarmos a abordagem RISC, que é ..
Amumu
@ Amumu Eu acho que você está se misturando gatee instruction. Gates são usados ​​para implementar instruções, e não o contrário. NOPé uma instrução, não um portão. E sim, as CPUs contêm milhares ou talvez milhões de portas NAND para implementar todas as instruções. Apenas não a instrução "NAND".
Agent_L 19/01/19
2
@ Amumu Essa não é a abordagem RISC :) Essa é a abordagem "usar as abstrações mais amplas", que não é muito útil fora de aplicativos muito específicos. Claro, nandé um portão que pode ser usado para implementar outros portões; mas você já tem todas as outras instruções . Reimplementá-los usando uma nandinstrução seria mais lento . E eles são usados ​​com muita frequência para tolerar isso, ao contrário do exemplo específico escolhido por cereja, onde nandproduziria código mais curto (não mais rápido , apenas mais curto); mas isso é extremamente raro, e o benefício simplesmente não vale o custo.
Luaan 19/01/19
@ Amumu Se usássemos sua abordagem, não teríamos números posicionais. Qual é o ponto em que você pode simplesmente dizer em ((((()))))vez de 5, certo? Cinco é apenas um número específico, isso é muito limitador - os conjuntos são muito mais gerais: P
Luaan
@Agent_L Sim, eu sei que os portões implementam instruções. nandimplementa todos os portões, portanto, implicitamente, nandpode implementar todas as outras instruções. Então, se um programador tiver uma nandinstrução disponível, ele poderá inventar suas próprias instruções ao pensar em portas lógicas. O que eu quis dizer desde o início é que, se é tão fundamental, por que não recebeu sua própria instrução (ou seja, um código de operação na lógica do decodificador), para que um programador possa usar essa instrução. É claro que depois que recebi a resposta, agora sei que depende do uso do software.
Amumu
3

Em um nível de hardware, nand ou nor é a operação lógica elementar. Dependendo da tecnologia (ou dependendo do que você chama arbitrariamente 1 e do que você chama 0), nem e nem pode ser implementado de uma maneira muito simples e elementar.

Se ignorarmos o caso "nem", toda a outra lógica será construída a partir de nand. Mas não porque haja alguma prova de ciência da computação de que todas as operações lógicas possam ser construídas e - a razão é que simplesmente não existe um método elementar para construir xor, ou, e etc., que seja melhor do que construí-lo a partir de nand.

Para instruções do computador, a situação é diferente. Uma instrução nand poderia ser implementada e seria um pouco mais barata que a implementação do xor, por exemplo. Mas apenas um pouquinho, porque a lógica que calcula o resultado é pequena comparada com a lógica que decodifica a instrução, move operandos, garante que apenas uma operação seja computada e apanha o resultado e o entrega no lugar certo. Cada instrução leva um ciclo para executar, o mesmo que uma adição que é dez vezes mais complicada em termos de lógica. As economias de nand vs. xor seriam insignificantes.

O que conta, então, é quantas instruções são necessárias para operações que são realmente executadas por código típico . Nand não está nem perto do topo da lista de operações comumente solicitadas. É muito mais comum que e ou não seja solicitado. Os designers do processador e do conjunto de instruções examinarão muitos códigos existentes e determinarão como as instruções diferentes afetariam esse código. Eles provavelmente descobriram que a adição de uma instrução nand levaria a uma redução muito pequena no número de instruções do processador executadas para executar código típico, e a substituição de algumas instruções existentes por nand aumentaria o número de instruções executadas.

gnasher729
fonte
2

Só porque o NAND (ou NOR) pode implementar todos os portões na lógica combinacional, não se traduz em um operador bit a bit eficiente da mesma maneira. Para implementar um AND usando apenas operações NAND, em que c = a AND b, você teria que ter c = a NAND b, depois b = -1 e c = c NAND b (para um NOT). As operações lógicas bit a bit básicas são AND, OR, EOR, NOT, NAND e NEOR. Isso não é muito para cobrir, e os quatro primeiros geralmente são construídos de qualquer maneira. Na lógica combinacional, os circuitos lógicos básicos são limitados apenas pelo número de portas disponíveis, que é um jogo de bola completamente diferente. O número de interconexões possíveis em uma matriz de portas programável, que soa como o que você realmente procura, seria realmente um número muito grande. Alguns processadores realmente têm matrizes de gate incorporadas.

Robin Hodson
fonte
0

Você não implementa um portão lógico apenas porque ele possui integridade funcional, especialmente se os outros portões lógicos estiverem disponíveis nativamente. Você implementa o que tende a ser mais usado pelos compiladores.

NAND, NOR e XNOR são muito raramente necessários. Além dos operadores bit a bit clássicos AND, OR e XOR, apenas ANDN ( ~a & b) - que não é NAND ( ~(a & b)) - teria uma utilidade prática. Se houver, uma CPU deve implementar isso (e de fato algumas CPUs implementam ANDN).

Para explicar a utilidade prática do ANDN, imagine que você tenha uma máscara de bits que usa muitos bits, mas está interessado apenas em algumas delas, que são as seguintes:

enum my_flags {
    IT_IS_FRIDAY = 1,
    ...
    IT_IS_WARM = 8,
    ...
    THE_SUN_SHINES = 64,
    ...
};

Normalmente, você deseja verificar seus bits de interesse na máscara de bit se

  1. Eles estão todos prontos
  2. Pelo menos um está definido
  3. Pelo menos um não está definido
  4. Nenhum está definido

Vamos começar reunindo seus bits de interesse:

#define BITS_OF_INTEREST (IT_IS_FRIDAY | IT_IS_WARM | THE_SUN_SHINES)

1. Todos os bits de interesse são definidos: ANDN bit a bit + NOT lógica

Digamos que você queira saber se seus bits de interesse estão prontos. Você pode vê-lo como (my_bitmask & IT_IS_FRIDAY) && (my_bitmask & IT_IS_WARM) && (my_bitmask & THE_SUN_SHINES). No entanto, normalmente você colapsaria isso em

unsigned int life_is_beautiful = !(~my_bitmask & BITS_OF_INTEREST);

2. Pelo menos um bit de interesse está definido: AND bit a bit

Agora, digamos que você queira saber se pelo menos um pouco de interesse está definido. Você pode vê-lo como (my_bitmask & IT_IS_FRIDAY) || (my_bitmask & IT_IS_WARM) || (my_bitmask & THE_SUN_SHINES). No entanto, normalmente você colapsaria isso em

unsigned int life_is_not_bad = my_bitmask & BITS_OF_INTEREST;

3. Pelo menos um bit de interesse não está definido: ANDN bit a bit

Agora, digamos que você queira saber se pelo menos um pouco de interesse não está definido. Você pode vê-lo como !(my_bitmask & IT_IS_FRIDAY) || !(my_bitmask & IT_IS_WARM) || !(my_bitmask & THE_SUN_SHINES). No entanto, normalmente você colapsaria isso em

unsigned int life_is_imperfect = ~my_bitmask & BITS_OF_INTEREST;

4. Nenhum bit de interesse está definido: bit a bit AND + lógico NOT

Agora, digamos que você queira saber se todos os bits de interesse não estão definidos. Você pode vê-lo como !(my_bitmask & IT_IS_FRIDAY) && !(my_bitmask & IT_IS_WARM) && !(my_bitmask & THE_SUN_SHINES). No entanto, normalmente você colapsaria isso em

unsigned int life_is_horrible = !(my_bitmask & BITS_OF_INTEREST);

Essas são as operações comuns executadas em uma máscara de bits, além do OR ou XOR clássico, bit a bit. Penso no entanto que uma língua (que não é um CPU ) deve incluir o NAND bit a bit, NOR e operadores XNOR (cujos símbolos seria ~&, ~|e ~^), apesar de raramente usado. Porém, eu não incluiria o operador ANDN em um idioma, já que não é comutativo ( a ANDN bnão é o mesmo que b ANDN a) - é melhor escrever em ~a & bvez de a ANDN b, o primeiro mostra mais claramente a assimetria da operação.

madmurphy
fonte