¿Por qué no hay instrucciones 'nand' en las CPU modernas?

52

¿Por qué los diseñadores x86 (u otras arquitecturas de CPU también) decidieron no incluirlo? Es una puerta lógica que se puede usar para construir otras puertas lógicas, por lo tanto, es rápida como una sola instrucción. En lugar de encadenar note andinstrucciones (ambas se crean a partir de nand), ¿por qué no hay nandinstrucciones?

Amumu
fuente
20
¿Qué caso de uso tiene para la instrucción nand? Probablemente los diseñadores de x86 nunca encontraron ninguno
PlasmaHH
16
ARM tiene la BICinstrucción, que es a & ~b. Arm Thumb-2 tiene la ORNinstrucción que es ~(a | b). ARM es bastante moderno. Codificar una instrucción en el conjunto de instrucciones de la CPU tiene sus costos. Así que solo los más "útiles" están llegando a ISA.
Eugene Sh.
24
@Amumu Podríamos tener ~(((a << 1) | (b >> 1)) | 0x55555555)instrucciones también. El propósito sería que ~(((a << 1) | (b >> 1)) | 0x55555555)pueda traducirse en una sola instrucción en lugar de 6. Entonces, ¿por qué no?
user253751
11
@Amumu: ¡Eso no es un caso de uso, y también es ~ no! Un caso de uso es una razón convincente por la que esa instrucción es útil y dónde se puede aplicar. Su razonamiento es como decir "La instrucción debe estar ahí para que pueda usarse" pero la pregunta es "para qué usarla, eso es tan importante que es útil para gastar recursos".
PlasmaHH
44
He estado programando durante 45 años, escribí algunos compiladores y usé algunos operadores lógicos extraños cuando están disponibles, como IMP, pero nunca he tenido un uso para un operador o instrucción NAND.
user207421

Respuestas:

62

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

Pero, en general, las CPU modernas se crean para que coincidan con la generación automática de código por parte de los compiladores, y rara vez se requiere NAND bit a bit. Bitwise AND y OR se utilizan con mayor frecuencia para manipular campos de bits en estructuras de datos. De hecho, SSE tiene AND-NOT pero no NAND.

Cada instrucción tiene un costo en la lógica de decodificación y consume un código de operación que podría usarse para otra cosa. Especialmente en codificaciones de longitud variable como x86, puede quedarse sin códigos de operación cortos y tener que usar códigos más largos, lo que potencialmente ralentiza todo el código.

pjc50
fuente
55
@supercat AND-NOT se usa comúnmente para desactivar bits en una variable de conjunto de bits. por ejemploif(windowType & ~WINDOW_RESIZABLE) { ... do stuff for variable-sized windows ... }
adib el
2
@adib: Sí. Una característica interesante de "and-not" es que, a diferencia del operador "bitwise not" [~], el tamaño del resultado no importará. Si fooes un uint64_t, la instrucción a foo &= ~something;veces puede borrar más bits de los previstos, pero si hubiera un &~=operador, estos problemas podrían evitarse.
supercat
66
@adib si WINDOW_RESIZABLEes una constante, entonces un optimizador debe evaluar ~WINDOW_RESIZABLEen tiempo de compilación, por lo que esto es solo un AND en tiempo de ejecución.
alephzero
44
@MarkRansom: No, la causa y el efecto son completamente correctos del historial informático. Este fenómeno de diseñar CPU que están optimizadas para compiladores en lugar de programadores de ensamblaje humano fue parte del movimiento RISC (aunque, el movimiento RISC en sí mismo es más amplio que solo ese aspecto). Las CPU diseñadas para compiladores incluyen ARM y Atmel AVR. A finales de los años 90 y principios de los 00s personas contratadas escritores y programadores del sistema operativo a los conjuntos de instrucciones de diseño de CPU compilador
slebetman
3
Actualmente, las operaciones de registro a registro son esencialmente gratuitas en comparación con el acceso a RAM. La implementación de instrucciones redundantes cuesta espacio de silicio en la CPU. Por lo tanto, generalmente solo habrá una forma de OR-bit a bit y de AND-bit a bit porque agregar una operación de registro-registro de complemento a nivel de bit casi nunca ralentizará nada.
nigel222
31

El costo de tales funciones ALU es

1) la lógica que realiza la función en sí

2) el selector que selecciona el resultado de esta función en lugar de los demás de todas las funciones ALU

3) el costo de tener esta opción en el conjunto de instrucciones (y no tener alguna otra función útil)

Estoy de acuerdo con usted en que el 1) costo es muy pequeño. Sin embargo, el costo 2) y 3) es casi independiente de la función. Creo que en este caso el 3) costo (los bits ocupados en la instrucción) fueron la razón para no tener esta instrucción específica. Los bits en una instrucción son un recurso muy escaso para un diseñador de CPU / arquitectura.

Wouter van Ooijen
fuente
29

Déle la vuelta, primero vea por qué Nand era popular en el diseño de lógica de hardware , tiene varias propiedades útiles allí. Luego pregunte si esas propiedades aún se aplican en una instrucción de CPU ...

TL / DR: no lo hacen, por lo que no hay inconveniente en usar And, Or or Not en su lugar.

La mayor ventaja de la lógica Nand cableada era la velocidad, obtenida al reducir el número de niveles lógicos (etapas del transistor) entre las entradas y salidas de un circuito. En una CPU, la velocidad del reloj está determinada por la velocidad de operaciones mucho más complejas como la suma, por lo que acelerar una operación AND no le permitirá aumentar la velocidad del reloj.

Y la cantidad de veces que necesita combinar otras instrucciones es muy pequeña, lo suficiente para que Nand realmente no gane su espacio en el conjunto de instrucciones.

Brian Drummond
fuente
1
En casos donde no se requiere aislamiento de entrada, "y no" parecería muy barato en hardware. En 1977 diseñé un controlador de señal de giro para el remolque de mis padres usando dos transistores y dos diodos por luz para realizar una función "XOR" [lámpara izquierda == xor (señal izquierda, freno); lámpara derecha == xor (señal derecha, freno)], esencialmente cablear o dos funciones y no para cada luz. No he visto tales trucos utilizados en el diseño de LSI, pero creo que en TTL o NMOS, en los casos en que cualquier cosa que alimente una entrada tenga una capacidad de conducción adecuada, tales trucos podrían ahorrar circuitos.
supercat
12

Me gustaría estar de acuerdo con Brian aquí, y con Wouter y pjc50.

También me gustaría agregar que para propósitos generales, especialmente CISC, procesadores, las instrucciones no tienen el mismo rendimiento: una operación complicada podría tomar más ciclos que una fácil.

Considere X86: AND(que es una operación "y") es probablemente muy rápido. Lo mismo vale para NOT. Veamos un poco de desmontaje:

Codigo 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 producir ensamblaje:

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

Conjunto de salida (acortado):

    .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 puede ver, para los tipos de datos de tamaño inferior a 64, las cosas simplemente se manejan como largas (de ahí el yl y no l ), ya que ese es el ancho de bits "nativo" de mi compilador, como parece.

El hecho de que haya movs en el medio solo se debe al hecho de que eaxes el registro que contiene el valor de retorno de una función. Normalmente, solo calcularía en el ediregistro de propósito general para calcular con el resultado.

Para 64 bits, es lo mismo, solo con qpalabras "quad" (por lo tanto, finales ) y rax/ en rsilugar de eax/ edi.

Parece que para operandos de 128 bits y mayores, a Intel no le importó implementar una operación "no"; en su lugar, el compilador produce un 1registro completo (autocomparación del registro consigo mismo, el resultado almacenado en el registro con la vdcmpeqdinstrucción), y xoreso.

En resumen: al implementar una operación complicada con múltiples instrucciones elementales, no necesariamente se ralentiza la operación; simplemente no hay ventaja en tener una instrucción que haga el trabajo de múltiples instrucciones si no es más rápida.

Marcus Müller
fuente
10

En primer lugar, no confunda las operaciones bit a bit y lógicas.

Las operaciones bit a bit se usan generalmente para establecer / borrar / alternar / verificar bits en campos de bits. Ninguna de estas operaciones requiere nand ("y no", también conocido como "bit clear" es más útil).

Las operaciones lógicas en la mayoría de los lenguajes de programación modernos se evalúan mediante lógica de cortocircuito. Por lo general, se necesita un enfoque basado en sucursales para implementarlos. Incluso cuando el compilador puede determinar que la evaluación de cortocircuito versus completa no hace ninguna diferencia en el comportamiento del programa, los operandos para las operaciones lógicas generalmente no están en una forma conveniente para implementar la expresión usando las operaciones asm bit a bit.

Peter Green
fuente
10

NAND a menudo no se implementa directamente porque tener la instrucción AND implícitamente te da la capacidad de saltar en una condición NAND.

Realizar una operación lógica en una CPU a menudo establece bits en un registro de bandera.

La mayoría de los registros de banderas tienen una bandera CERO. El indicador de cero se establece si el resultado de una operación lógica es cero, y se borra de lo contrario.

La mayoría de las CPU modernas tienen una instrucción de salto que salta si se establece el indicador de cero. También tienen una instrucción que salta si no se establece la bandera de cero.

AND y NAND son complementos. Si el resultado de una operación AND es cero, entonces el resultado de una operación NAND es 1, y viceversa.

Entonces, si desea saltar si la NAND de dos valores es verdadera, simplemente realice la operación AND, y salte si se establece la bandera de cero.

Entonces, si desea saltar si la NAND de dos valores es falsa, simplemente realice la operación AND y salte si la bandera de cero está limpia.

usuario4574
fuente
De hecho, la elección de la instrucción de salto condicional le ofrece una opción de lógica invertida y no inversora para toda una clase de operaciones, sin tener que implementar esa opción para cada uno individualmente.
Chris Stratton
Esta debería haber sido la mejor respuesta. Las operaciones de bandera cero hacen que NAND sea superfluo para operaciones lógicas ya que AND + JNZ y AND + JZ son esencialmente cortocircuito / lógico AND y NAND respectivamente, ambos toman el mismo número de código de operación.
Lie Ryan
4

El hecho de que algo sea barato no significa que sea rentable .

Si tomamos su argumentación de manera absurda, llegaremos a la conclusión de que una CPU debe estar compuesta principalmente por cientos de sabores de instrucción NOP, porque son los más baratos de implementar.

O compárelo con instrumentos financieros: ¿compraría un bono de $ 1 con un retorno de 0.01% solo porque puede? No, preferiría ahorrar esos dólares hasta que tenga suficiente para comprar un bono de $ 10 con un mejor rendimiento. Lo mismo ocurre con el presupuesto de silicona en una CPU: es efectivo para eliminar muchas operaciones baratas pero inútiles como NAND, y colocar los transistores guardados en algo mucho más costoso pero realmente útil.

No hay carrera para tener tantas operaciones como sea posible. Como RISC vs CISC había demostrado lo que Turing sabía desde el principio: menos es más. En realidad, es mejor tener la menor cantidad de operaciones posible.

Agent_L
fuente
nopno puede implementar todas las demás puertas lógicas, pero puede nando norpuede recrear efectivamente cualquier instrucción que se implemente en una CPU en el software. Si
adoptamos
@ Amumu Creo que te estás confundiendo gatey instruction. Las puertas se utilizan para implementar instrucciones, no al revés. NOPEs una instrucción, no una puerta. Y sí, las CPU contienen miles o incluso millones de puertas NAND para implementar todas las instrucciones. Simplemente no es la instrucción "NAND".
Agent_L
2
@Amumu Ese no es el enfoque RISC :) Ese es el enfoque de "usar las abstracciones más amplias", que no es demasiado útil fuera de aplicaciones muy específicas. Claro, nandes una puerta que se puede utilizar para implementar otras puertas; pero ya tienes todas las otras instrucciones . Reimplementarlos usando una nandinstrucción sería más lento . Y se usan con demasiada frecuencia para tolerar eso, a diferencia de su ejemplo específico seleccionado donde nandproduciría un código más corto (no un código más rápido , solo más corto); pero eso es extremadamente raro, y el beneficio simplemente no vale el costo.
Luaan
@Amumu Si usáramos su enfoque, no tendríamos números posicionales. ¿Cuál es el punto cuando puedes decir simplemente en ((((()))))lugar de 5, verdad? Cinco es solo un número específico, eso es demasiado limitante: los conjuntos son mucho más generales: P
Luaan
@Agent_L Sí, sé que las puertas implementan instrucciones. nandimplementa todas las puertas, por lo tanto, implícitamente nandpuede implementar todas las demás instrucciones. Luego, si un programador tiene una nandinstrucción disponible, puede inventar sus propias instrucciones cuando piensa en puertas lógicas. Lo que quise decir desde el principio es que si es tan fundamental, por qué no se le dio su propia instrucción (es decir, un código de operación en la lógica del decodificador), por lo que un programador puede usar dicha instrucción. Por supuesto, después de recibir una respuesta, ahora sé que depende del uso del software.
Amumu
3

A nivel de hardware, nand o nor es la operación lógica elemental. Dependiendo de la tecnología (o de lo que llames arbitrariamente 1 y de lo que llames 0), nand o nor pueden implementarse de una manera muy simple y elemental.

Si ignoramos el caso "nor", toda otra lógica se construye a partir de nand. Pero no porque haya alguna prueba informática de que todas las operaciones lógicas puedan construirse a partir de, y la razón es que simplemente no hay ningún método elemental para construir xor, o, y etc. que sea mejor que construirlo desde Nand's.

Para las instrucciones de la computadora, la situación es diferente. Se podría implementar una instrucción nand, y sería un poco más barato que implementar xor, por ejemplo. Pero solo un poco, porque la lógica que calcula el resultado es pequeña en comparación con la lógica que decodifica la instrucción, mueve los operandos, se asegura de que solo se calcule una operación, y recoge el resultado y lo entrega en el lugar correcto. Cada instrucción tarda un ciclo en ejecutarse, igual que una adición que es diez veces más complicada en términos de lógica. Los ahorros de nand vs.xor serían insignificantes.

Entonces, lo que cuenta es cuántas instrucciones se necesitan para las operaciones que realmente realiza un código típico . Nand no está cerca de la parte superior de la lista de operaciones comúnmente solicitadas. Es mucho más común que y, o, no se soliciten. Los diseñadores de conjuntos de procesadores e instrucciones examinarán gran cantidad de código existente y determinarán cómo las diferentes instrucciones afectarían ese código. Lo más probable es que descubrieran que agregar una instrucción nand conduciría a una reducción muy pequeña en la cantidad de instrucciones del procesador que se ejecutan para ejecutar el código típico, y reemplazar algunas instrucciones existentes con nand aumentaría la cantidad de instrucciones realizadas.

gnasher729
fuente
2

El hecho de que NAND (o NOR) pueda implementar todas las puertas en lógica combinatoria, no se traduce en un operador eficiente a nivel de bits de la misma manera. Para implementar un AND usando solo operaciones NAND, donde c = a AND b, tendrías que tener c = a NAND b, luego b = -1, luego c = c NAND b (para un NOT). Las operaciones lógicas básicas a nivel de bits son AND, OR, EOR, NOT, NAND y NEOR. Eso no es mucho para cubrir, y los primeros cuatro generalmente están integrados de todos modos. En la lógica combinacional, los circuitos lógicos básicos solo están limitados por el número de puertas disponibles, que es un juego de pelota completamente diferente. El número de posibles interconexiones en una matriz de compuerta programable, que suena como lo que realmente buscas, sería un número muy grande. Algunos procesadores tienen matrices de compuerta incorporadas.

Robin Hodson
fuente
0

No implementa una puerta lógica solo porque tiene integridad funcional, especialmente si las otras puertas lógicas están disponibles de forma nativa. Implementas lo que los compiladores suelen usar más.

NAND, NOR y XNOR son muy raramente necesarios. Además de los operadores bit a bit clásicos AND, OR y XOR, solo ANDN ( ~a & b), que no es NAND ( ~(a & b)), tendría una utilidad práctica. Si hay alguno, una CPU debería implementar eso (y de hecho algunas CPU implementan ANDN).

Para explicar la utilidad práctica de ANDN, imagine que tiene una máscara de bits que utiliza muchos bits, pero solo le interesan algunos de ellos, que son los siguientes:

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

Normalmente, desea verificar acerca de sus partes de interés en la máscara de bits si

  1. Todos estan listos
  2. Al menos uno está configurado
  3. Al menos uno no está configurado
  4. Ninguno está configurado

Comencemos reuniendo sus partes de interés:

#define BITS_OF_INTEREST (IT_IS_FRIDAY | IT_IS_WARM | THE_SUN_SHINES)

1. Todos los bits de interés están configurados: bit a bit ANDN + lógico NO

Digamos que quieres saber si tus intereses están listos. Puedes verlo como (my_bitmask & IT_IS_FRIDAY) && (my_bitmask & IT_IS_WARM) && (my_bitmask & THE_SUN_SHINES). Sin embargo, normalmente colapsarías eso en

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

2. Se establece al menos un bit de interés: bit a bit Y

Ahora supongamos que desea saber si se establece al menos un poco de interés. Puedes verlo como (my_bitmask & IT_IS_FRIDAY) || (my_bitmask & IT_IS_WARM) || (my_bitmask & THE_SUN_SHINES). Sin embargo, normalmente colapsarías eso en

unsigned int life_is_not_bad = my_bitmask & BITS_OF_INTEREST;

3. Por lo menos un poco de interés es no establece: bit a bit ANDN

Ahora digamos que usted quiere saber si al menos un bit de interés es no establece. Puedes verlo como !(my_bitmask & IT_IS_FRIDAY) || !(my_bitmask & IT_IS_WARM) || !(my_bitmask & THE_SUN_SHINES). Sin embargo, normalmente colapsarías eso en

unsigned int life_is_imperfect = ~my_bitmask & BITS_OF_INTEREST;

4. No se establece ningún bit de interés: bit a bit Y + lógico NO

Ahora supongamos que desea saber si no se han establecido todos los bits de interés . Puedes verlo como !(my_bitmask & IT_IS_FRIDAY) && !(my_bitmask & IT_IS_WARM) && !(my_bitmask & THE_SUN_SHINES). Sin embargo, normalmente colapsarías eso en

unsigned int life_is_horrible = !(my_bitmask & BITS_OF_INTEREST);

Estas son las operaciones comunes realizadas en una máscara de bits, más los clásicos OR y XOR a nivel de bits. Sin embargo, creo que un lenguaje (que no es una CPU ) debería incluir los operadores NAND, NOR y XNOR a nivel de bits (cuyos símbolos serían ~&, ~|y ~^), a pesar de que rara vez se usan. Sin embargo, no incluiría el operador ANDN en un lenguaje, ya que no es conmutativo ( a ANDN bno es lo mismo que b ANDN a): es mejor escribir en ~a & blugar de a ANDN b, el primero muestra más claramente la asimétrica de la operación.

madmurphy
fuente