Pourquoi n'y a-t-il pas d'instruction `nand` dans les CPU modernes?

52

Pourquoi les concepteurs x86 (ou d'autres architectures de CPU) ont-ils décidé de ne pas l'inclure? C'est une porte logique qui peut être utilisée pour construire d'autres portes logiques, elle est donc rapide comme une seule instruction. Plutôt que d'enchaîner notet d' andinstructions (les deux sont créés à partir de nand), pourquoi pas d' nandinstruction?.

Amumu
la source
20
Quel cas d'utilisation avez-vous pour l'instruction nand? Probablement les concepteurs x86 n'en ont jamais trouvé
PlasmaHH
16
ARM a l' BICinstruction, qui est a & ~b. Bras Thumb-2 a l' ORNinstruction qui est ~(a | b). ARM est assez moderne. Le codage d’une instruction dans le jeu d’instructions de la CPU a un coût. Ainsi, seuls les plus "utiles" se frayent un chemin vers ISA.
Eugene Sh.
24
@ Amumu Nous pourrions aussi avoir des ~(((a << 1) | (b >> 1)) | 0x55555555)instructions. Le but serait de ~(((a << 1) | (b >> 1)) | 0x55555555)pouvoir traduire en une seule instruction au lieu de 6. Alors, pourquoi pas?
user253751
11
@Amumu: Ce n'est pas un cas d'utilisation, et c'est aussi ~ pas! Une cas d'utilisation est une raison impérieuse pour laquelle cette instruction est utile et où elle peut être appliquée. Votre raisonnement revient à dire "L’instruction doit être là pour pouvoir être utilisée", mais la question est de savoir "quoi utiliser car elle est si importante qu’il est utile de dépenser des ressources".
PlasmaHH
4
Je programme depuis 45 ans, ai écrit quelques compilateurs et utilisé des opérateurs logiques étranges lorsqu'ils sont disponibles, tels que IMP, mais je n'ai jamais utilisé un opérateur ou une instruction NAND.
user207421

Réponses:

62

http://www.ibm.com/support/knowledgecenter/ssw_aix_61/com.ibm.aix.alangref/idalangref_nand_nd_instrs.htm : L’alimentation possède une NAND.

Mais les processeurs généralement modernes sont conçus pour correspondre à la génération de code automatisée par les compilateurs, et la NAND au niveau du bit est très rarement requise. Les bits AND et OR s'utilisent plus souvent pour manipuler des champs de bits dans des structures de données. En fait, SSE a AND-NOT mais pas NAND.

Chaque instruction a un coût dans la logique de décodage et consomme un code opération qui pourrait être utilisé pour autre chose. Surtout dans les codages de longueur variable tels que x86, vous pouvez manquer de codes d'opération courts et devoir en utiliser des plus longs, ce qui ralentit potentiellement tout le code.

pjc50
la source
5
@supercat AND-NOT est couramment utilisé pour désactiver les bits d'une variable de jeu de bits. par exempleif(windowType & ~WINDOW_RESIZABLE) { ... do stuff for variable-sized windows ... }
Adib
2
@adib: Yup. Une caractéristique intéressante de "and-not" est que, contrairement à l'opérateur "bitwise not" [~], la taille du résultat n'aura pas d'importance. Si fooest un uint64_t, l'instruction foo &= ~something;peut parfois effacer plus de bits que prévu, mais s'il y avait un &~=opérateur, de tels problèmes pourraient être évités.
Supercat
6
Si @adib WINDOW_RESIZABLEest une constante, un optimiseur doit évaluer ~WINDOW_RESIZABLEau moment de la compilation, il ne s'agit donc que d'un AND au moment de l'exécution.
alephzero
4
@MarkRansom: Non, la cause et l'effet sont entièrement corrects à partir de l'historique informatique. Ce phénomène de conception de processeurs optimisés pour les compilateurs plutôt que pour les programmeurs d'assemblages humains faisait partie du mouvement RISC (bien que le mouvement RISC lui-même soit plus large que cet aspect). Les processeurs conçus pour les compilateurs incluent ARM et Atmel AVR. À la fin des années 90 et au début des années 2000, des rédacteurs de compilateur et des programmeurs de système d'exploitation ont été embauchés pour concevoir des jeux d'instructions de CPU
slebetman
3
Ces opérations de registre à registre sont essentiellement gratuites par rapport à un accès RAM. L'implémentation d'instructions redondantes coûte de l'argent en silicium dans la CPU. Par conséquent, il n'y aura généralement qu'une seule forme de bit-OR et de bit-AND, car l'ajout d'une opération registre-complément à registre binaire ne ralentira presque jamais rien.
nigel222
31

Le coût d’une telle fonction ALU est de

1) la logique qui exécute la fonction elle-même

2) le sélecteur qui sélectionne ce résultat de fonction au lieu des autres parmi toutes les fonctions de l’ALU

3) le coût d’avoir cette option dans le jeu d’instructions (et de ne pas avoir d’autres fonctions utiles)

Je conviens avec vous que le 1) coût est très faible. Les coûts 2) et 3) sont toutefois presque indépendants de la fonction. Je pense que dans ce cas, le coût 3) (les bits occupés dans l'instruction) était la raison pour laquelle cette instruction spécifique n'était pas disponible. Les bits d'une instruction sont une ressource très rare pour un concepteur de CPU / architecture.

Wouter van Ooijen
la source
29

Retournez-le - voyez d'abord pourquoi Nand était populaire dans la conception de la logique matérielle - il possède plusieurs propriétés utiles. Puis demandez si ces propriétés s'appliquent toujours dans une instruction de la CPU ...

TL / DR - ce n’est pas le cas, il n’ya donc aucun inconvénient à utiliser And, Or or Not à la place.

Le principal avantage de la logique câblée Nand était la vitesse, obtenue en réduisant le nombre de niveaux logiques (étages de transistors) entre les entrées et les sorties d'un circuit. Dans une CPU, la vitesse d'horloge est déterminée par la vitesse d'opérations beaucoup plus complexes telles que l'addition. Par conséquent, accélérer une opération AND ne vous permettra pas d'augmenter la fréquence d'horloge.

Et le nombre de fois que vous avez besoin de combiner d'autres instructions est extrêmement réduit, ce qui est suffisant pour que Nand ne gagne vraiment pas sa place dans le jeu d'instructions.

Brian Drummond
la source
1
Dans les cas où l'isolation d'entrée n'est pas requise, "et non" semblerait très bon marché en matériel. En 1977, j’ai conçu pour la remorque de mon père un contrôleur de clignotant utilisant deux transistors et deux diodes par feu pour assurer une fonction "XOR" [feu gauche == xor (signal gauche, frein); voyant de droite == xor (signal de freinage, frein)], fonctionnant essentiellement par câble avec deux fonctions et non pour chaque lumière. Je n'ai pas vu de telles astuces utilisées dans la conception LSI, mais je penserais qu'en TTL ou NMOS, dans les cas où ce qui alimente une entrée aurait une capacité de commande adéquate, de telles astuces pourraient économiser les circuits.
Supercat
12

Je voudrais être d'accord avec Brian ici, et Wouter et pjc50.

J'aimerais également ajouter que, sur les processeurs à usage général, en particulier les programmes CISC, les instructions n'ont pas toutes les mêmes débits - une opération compliquée peut simplement prendre plus de cycles que de simples.

Considérez X86: AND(qui est une opération "and") est probablement très rapide. Même chose pour NOT. Regardons un peu de démontage:

Code d'entrée:

#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);}

Commande pour produire l'assemblage:

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

Ensemble de sortie (raccourci):

    .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

Comme vous pouvez le constater, pour les types de données de taille inférieure à 64, les choses sont simplement traitées comme des longs (d'où le et l et non l ), puisqu'il s'agit de la largeur de bit "native" de mon compilateur, semble-t-il.

Le fait qu'il y ait movs entre les deux n'est dû qu'au fait que eaxle registre contient la valeur de retour d'une fonction. Normalement, vous devez simplement calculer dans le ediregistre général pour calculer le résultat.

Pour 64 bits, c'est la même chose - juste avec des qmots "quad" (donc, finaux ) et rax/ rsiau lieu de eax/ edi.

Il semble que pour les opérandes de 128 bits et plus, Intel n’a pas voulu implémenter une opération "non"; au lieu de cela, le compilateur produit un 1registre complet (auto-comparaison du registre avec lui-même, résultat stocké dans le registre avec l' vdcmpeqdinstruction), et xorcela.

En bref: en implémentant une opération compliquée avec plusieurs instructions élémentaires, vous ne ralentissez pas nécessairement le fonctionnement. Il n’est tout simplement pas avantageux d’avoir une instruction qui exécute plusieurs instructions si elle n’est pas plus rapide.

Marcus Müller
la source
10

Tout d'abord, ne confondez pas les opérations au niveau du bit et logiques.

Les opérations au niveau des bits sont généralement utilisées pour définir / effacer / basculer / vérifier les bits dans les champs de bits. Aucune de ces opérations ne nécessite de nand ("et pas", aussi connu sous le nom de "bit clear" est plus utile).

Les opérations logiques dans la plupart des langages de programmation modernes sont évaluées à l'aide d'une logique de court-circuit. Il faut donc généralement une approche basée sur les branches pour les mettre en œuvre. Même lorsque le compilateur peut déterminer que l'évaluation par court-circuit par rapport à une évaluation complète ne change en rien le comportement du programme, les opérandes des opérations logiques ne sont généralement pas sous une forme commode pour implémenter l'expression à l'aide des opérations asm au niveau du bit.

Peter Green
la source
10

NAND n'est souvent pas implémenté directement parce que l'instruction AND vous donne implicitement la possibilité de sauter sur une condition NAND.

L'exécution d'une opération logique dans une CPU définit souvent des bits dans un registre d'indicateurs.

La plupart des registres de drapeaux ont un drapeau ZÉRO. L'indicateur zéro est défini si le résultat d'une opération logique est égal à zéro et est effacé dans le cas contraire.

La plupart des CPU modernes ont une instruction de saut qui saute si l'indicateur zéro est défini. Ils ont également une istruction qui saute si l'indicateur zéro n'est pas défini.

AND et NAND sont des compléments. Si le résultat d'une opération AND est égal à zéro, le résultat d'une opération NAND est égal à 1 et inversement.

Donc, si vous voulez sauter si le NAND de deux valeurs est vrai, exécutez simplement l'opération AND et sautez si l'indicateur zéro est défini.

Donc, si vous voulez sauter si la valeur NAND de deux valeurs est fausse, exécutez simplement l'opération AND et sautez si l'indicateur zéro est vide.

utilisateur4574
la source
En effet, le choix de l'instruction de saut conditionnel vous offre le choix d'une logique d'inversion et de non-inversion pour toute une classe d'opérations, sans avoir à implémenter ce choix individuellement.
Chris Stratton
Cela aurait dû être la meilleure réponse. Les opérations de drapeau zéro rendent NAND superflu pour les opérations logiques puisque AND + JNZ et AND + JZ sont essentiellement court-circuités / ET et NAND logiques respectivement, les deux prennent le même nombre d'opcode.
Lie Ryan
4

Ce n'est pas parce que quelque chose est bon marché que c'est rentable .

Si nous prenons votre argumentation comme absurdum, nous conclurions qu’un processeur devrait être composé principalement de centaines de types d’instructions NOP, car elles sont les moins chères à mettre en œuvre.

Ou comparez-le à des instruments financiers: achèteriez-vous une obligation de 1 $ avec un rendement de 0,01% simplement parce que vous le pouvez? Non, vous préférez économiser ces dollars jusqu'à ce que vous en ayez assez pour acheter une obligation de 10 $ avec un meilleur rendement. Il en va de même avec le budget en silicone sur un processeur: il est efficace de supprimer de nombreux ops bon marché mais inutiles comme NAND, et de placer les transistors sauvegardés dans une configuration beaucoup plus chère mais réellement utile.

Il n'y a pas de course pour avoir autant d'opérations que possible. Comme RISC contre CISC avaient prouvé ce que Turing savait depuis le début: moins c'est plus. En fait, il vaut mieux avoir le moins d'opérations possible.

Agent_L
la source
nopne peut pas implémenter toutes les autres portes logiques, mais peut nandou norpeut effectivement recréer toute instruction implémentée dans une CPU dans un logiciel. Si nous adoptons l'approche RISC, c'est ..
Amumu
@ Amumu Je pense que vous vous trompez gateet instruction. Les portes sont utilisées pour implémenter les instructions, pas l'inverse. NOPest une instruction, pas une porte. Et oui, les processeurs contiennent des milliers voire des millions de portes NAND pour mettre en œuvre toutes les instructions. Juste pas l'instruction "NAND".
Agent_L
2
@Amumu Ce n'est pas l'approche RISC :) C'est l'approche "utilisez les abstractions les plus larges", ce qui n'est pas très utile en dehors d'applications très spécifiques. Bien sûr, nandest une porte qui peut être utilisée pour mettre en œuvre d'autres portes; mais vous avez déjà toutes les autres instructions . Les réimplémenter en utilisant une nandinstruction serait plus lent . Et ils sont utilisés trop souvent pour tolérer cela, contrairement à votre exemple spécifique choisi par un cherry, nandqui produirait un code plus court (pas plus rapide , mais plus court); mais c'est extrêmement rare, et le bénéfice n'en vaut tout simplement pas le coût.
Luaan
@ Amumu Si nous utilisions votre approche, nous n'aurions pas de nombres de position. Quel est le point quand vous pouvez simplement dire ((((()))))au lieu de 5, non? Cinq n'est qu'un nombre, c'est trop limitatif - les ensembles sont beaucoup plus généraux: P
Luaan
@Agent_L Oui, je sais que les portes implémentent les instructions. nandimplémente toutes les portes, donc implicitement nandpeut implémenter toutes les autres instructions. Ensuite, si un programmeur a une nandinstruction disponible, il peut inventer ses propres instructions lorsqu'il pense à des portes logiques. Ce que je voulais dire dès le début, c’est que, si elle est aussi fondamentale, elle n’a pas reçu sa propre instruction (c’est-à-dire un opcode dans la logique du décodeur), afin qu’un programmeur puisse utiliser une telle instruction. Bien sûr, après avoir obtenu une réponse, je sais maintenant que cela dépend de l'utilisation du logiciel.
Amumu
3

Au niveau matériel, l'opération de logique élémentaire n'est ni ni ni. Selon la technologie (ou selon ce que vous appelez arbitrairement 1 et ce que vous appelez 0), ni nand ni ni ne peuvent être implémentés de manière très simple et élémentaire.

Si nous ignorons le cas "ni", toute autre logique est construite à partir de nand. Mais pas parce qu'il ya une preuve de l'informatique que toutes les opérations logiques peuvent être construits à partir de - la raison est qu'il ya juste ne importe quelle méthode élémentaire à construire XOR, ou, etc qui est mieux que le construire à partir nand de.

Pour les instructions informatiques, la situation est différente. Une instruction nand pourrait être implémentée, et cela coûterait un peu moins cher que de mettre en œuvre xor, par exemple. Mais seulement un tout petit peu, parce que la logique qui calcule le résultat est infime comparée à la logique qui décode l’instruction, déplace les opérandes, s’assure qu’une seule opération est calculée, récupère le résultat et le livre au bon endroit. Chaque instruction prend un cycle à exécuter, comme une addition qui est dix fois plus complexe en termes de logique. Les économies réalisées entre nand et xor seraient négligeables.

Ce qui compte alors, c'est le nombre d'instructions nécessaires pour les opérations réellement effectuées par du code typique . Nand est loin du haut de la liste des opérations couramment demandées. C'est beaucoup plus commun que et, ou, non sont demandés. Les concepteurs de processeurs et de jeux d'instructions examineront un grand nombre de codes existants et détermineront l'incidence des différentes instructions sur ce code. Ils ont très probablement constaté que l’ajout d’une instruction nand entraînerait une très faible réduction du nombre d’instructions de processeur exécutées pour exécuter un code typique, et que le remplacement d’une instruction existante par nand augmenterait le nombre d’instructions exécutées.

gnasher729
la source
2

Le fait que NAND (ou NOR) puisse implémenter toutes les portes en logique combinatoire ne se traduit pas de la même manière par un opérateur au niveau du bit efficace. Pour implémenter un AND en utilisant uniquement les opérations NAND, où c = a et b, vous devez avoir c = a NAND b, puis b = -1, puis c = c NAND b (pour un NON). Les opérations au niveau des bits de la logique de base sont AND, OR, EOR, NOT, NAND et NEOR. Ce n'est pas beaucoup à couvrir, et les quatre premiers sont généralement construits de toute façon. En logique combinatoire, les circuits logiques de base ne sont limités que par le nombre de portes disponibles, ce qui est un jeu de balle totalement différent. Le nombre d'interconnexions possibles dans un tableau de portes programmable, ce qui ressemble à ce que vous voulez vraiment, serait un très grand nombre. Certains processeurs ont effectivement des tableaux de portes intégrés.

Robin Hodson
la source
0

Vous n'implémentez pas une porte logique uniquement parce qu'elle a une fonctionnalité complète, en particulier si les autres portes logiques sont disponibles de manière native. Vous implémentez ce qui est le plus utilisé par les compilateurs.

NAND, NOR et XNOR sont très rarement nécessaires. Outre les opérateurs de bits classiques AND, OR et XOR, seul ANDN ( ~a & b) - qui n'est pas NAND ( ~(a & b)) - aurait une utilité pratique. Le cas échéant, un processeur doit implémenter cela (et certains processeurs implémentent également ANDN).

Pour expliquer l’utilité pratique d’ANDN, imaginez que vous disposiez d’un masque de masque utilisant de nombreux bits, mais que vous ne vous intéressiez qu’à certains d’entre eux, à savoir:

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

Normalement, vous voulez vérifier si le bitmask vous intéresse,

  1. Ils sont tous ensemble
  2. Au moins un est réglé
  3. Au moins un n'est pas défini
  4. Aucun n'est défini

Commençons par rassembler vos éléments d’intérêt:

#define BITS_OF_INTEREST (IT_IS_FRIDAY | IT_IS_WARM | THE_SUN_SHINES)

1. Tous les bits d’intérêt sont définis: AND au niveau du bit + NOT logique

Disons que vous voulez savoir si vos éléments d’intérêt sont tous définis. Vous pouvez le voir comme (my_bitmask & IT_IS_FRIDAY) && (my_bitmask & IT_IS_WARM) && (my_bitmask & THE_SUN_SHINES). Cependant, normalement, vous réduiriez cela en

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

2. Au moins un bit d’intérêt est défini: bitwise ET

Maintenant, disons que vous voulez savoir si au moins un élément d’intérêt est défini. Vous pouvez le voir comme (my_bitmask & IT_IS_FRIDAY) || (my_bitmask & IT_IS_WARM) || (my_bitmask & THE_SUN_SHINES). Cependant, normalement, vous réduiriez cela en

unsigned int life_is_not_bad = my_bitmask & BITS_OF_INTEREST;

3. Au moins un bit d’intérêt n’est pas défini: bitwise ANDN

Maintenant, disons que vous voulez savoir si au moins un élément d’intérêt n’est pas défini. Vous pouvez le voir comme !(my_bitmask & IT_IS_FRIDAY) || !(my_bitmask & IT_IS_WARM) || !(my_bitmask & THE_SUN_SHINES). Cependant, normalement, vous réduiriez cela en

unsigned int life_is_imperfect = ~my_bitmask & BITS_OF_INTEREST;

4. Aucun bit d’intérêt n’est défini: bitwise AND + logique NOT

Maintenant, disons que vous voulez savoir si tous les éléments d’intérêt ne sont pas définis. Vous pouvez le voir comme !(my_bitmask & IT_IS_FRIDAY) && !(my_bitmask & IT_IS_WARM) && !(my_bitmask & THE_SUN_SHINES). Cependant, normalement, vous réduiriez cela en

unsigned int life_is_horrible = !(my_bitmask & BITS_OF_INTEREST);

Ce sont les opérations courantes effectuées sur un masque de bits, plus les OR classiques au niveau des bits et XOR. Je pense cependant qu'un langage (qui n'est pas un processeur ) devrait inclure les opérateurs au niveau du bit NAND, NOR et XNOR (dont les symboles seraient ~&, ~|et ~^), bien qu'ils soient rarement utilisés. Cependant, je n'inclurais pas l'opérateur ANDN dans un langage, puisqu'il n'est pas commutatif (ce a ANDN bn'est pas la même chose que b ANDN a) - il est préférable d'écrire ~a & bau lieu de a ANDN b, l'ancien indique plus clairement l'asymétrie de l'opération.

madmurphy
la source