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

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 ?.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.