Dlaczego we współczesnych procesorach nie ma instrukcji `nand`?

Dlaczego projektanci x86 (lub inne architektury procesorów) zdecydowali się go nie uwzględniać? Jest to bramka logiczna, której można użyć do budowy innych bram logicznych, dlatego jest szybka jak pojedyncza instrukcja. Zamiast tworzenia łańcuchów noti andinstrukcji (oba są tworzone nand), dlaczego nie ma nandinstrukcji ?.

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

Ale generalnie nowoczesne procesory są zbudowane tak, aby pasowały do ​​automatycznego generowania kodu przez kompilatory, a bitowa NAND jest bardzo rzadko wymagana. Bitowe AND i OR częściej wykorzystywane są do manipulowania polami bitowymi w strukturach danych. W rzeczywistości SSE ma AND-NOT, ale nie NAND.

Każda instrukcja ma swój koszt w logice dekodowania i zużywa kod operacji, którego można użyć do czegoś innego. Zwłaszcza w kodowaniu o zmiennej długości, takim jak x86, możesz skończyć z krótkimi kodami i użyć dłuższych, co może spowolnić cały kod.

Koszt takich funkcji ALU wynosi

1) logika, która wykonuje samą funkcję

2) selektor, który wybiera tę funkcję zamiast innych spośród wszystkich funkcji ALU

3) koszt posiadania tej opcji w zestawie instrukcji (i braku innych przydatnych funkcji)

Zgadzam się z tobą, że 1) koszt jest bardzo mały. Koszt 2) i 3) jest jednak prawie niezależny od funkcji. Myślę, że w tym przypadku 3) koszt (bity zajmowane w instrukcji) były powodem braku takiej konkretnej instrukcji. Bity w instrukcji są bardzo rzadkim zasobem dla projektanta procesora / architektury.

Odwróć to - najpierw sprawdź, dlaczego Nand był popularny w projektowaniu logiki sprzętowej - ma tam kilka przydatnych właściwości. Następnie zapytaj, czy te właściwości nadal mają zastosowanie w instrukcji procesora ...

TL / DR - nie robią tego, więc nie ma wady używania And, Or or Not zamiast tego.

Największą zaletą przewodowej logiki Nand była szybkość, uzyskana dzięki zmniejszeniu liczby poziomów logicznych (stopni tranzystorowych) między wejściami i wyjściami obwodu. W CPU szybkość zegara zależy od prędkości znacznie bardziej złożonych operacji, takich jak dodawanie, więc przyspieszenie operacji AND nie pozwoli na zwiększenie częstotliwości taktowania.

Liczba przypadków, w których musisz łączyć inne instrukcje, jest znikomo mała - wystarczająca, aby Nand naprawdę nie zajmował miejsca w zestawie instrukcji.

Chciałbym się tutaj zgodzić z Brianem, Wouterem i pjc50.

Chciałbym również dodać, że w przypadku procesorów ogólnego przeznaczenia, zwłaszcza procesorów CISC, instrukcje nie wszystkie mają taką samą przepustowość - skomplikowana operacja może po prostu zająć więcej cykli niż łatwa.

Rozważ X86: AND(która jest operacją „i”) jest prawdopodobnie bardzo szybka. To samo dotyczy NOT. Spójrzmy na trochę demontażu:

Kod wejściowy:

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

Polecenie wykonania złożenia:

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

Zespół wyjściowy (skrócony):

    .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

Jak widać, dla typów danych mniejszych niż 64, wszystkie rzeczy są po prostu obsługiwane jako długie (stąd i l, a nie l ), ponieważ, jak się wydaje, jest to „natywna” przepustowość mojego kompilatora.

Fakt, że jest movmiędzy nimi wynika tylko z faktu, że eaxjest to rejestr zawierający wartość zwracaną przez funkcję. Zwykle wystarczy obliczyć w edirejestrze ogólnego przeznaczenia, aby obliczyć wynik.

W przypadku 64 bitów jest tak samo - tylko z „quad” (stąd końcowymi q) słowami i rax/ rsizamiast eax/ edi.

Wygląda na to, że dla 128-bitowych operandów i większych Intel nie dbał o wdrożenie operacji „nie”; zamiast tego kompilator tworzy 1rejestr ogólny (samo porównanie rejestru z samym sobą, wynik zapisany w rejestrze z vdcmpeqdinstrukcją) i tak xorjest.

W skrócie: Implementując skomplikowaną operację z wieloma instrukcjami elementarnymi, niekoniecznie spowalniasz operację - po prostu nie ma korzyści z posiadania jednej instrukcji, która wykonuje wiele instrukcji, jeśli nie jest szybsza.

Po pierwsze, nie myl bitowych i logicznych operacji.

Operacje bitowe są zwykle używane do ustawiania / usuwania / przełączania / sprawdzania bitów w polach bitowych. Żadna z tych operacji nie wymaga nand (bardziej przydatne jest „i nie”, znane również jako „bit clear”).

Operacje logiczne w większości współczesnych języków programowania są oceniane przy użyciu logiki zwarciowej. Dlatego zazwyczaj potrzebne jest podejście oparte na oddziałach. Nawet jeśli kompilator może stwierdzić, że zwarcie w porównaniu z całkowitą oceną nie ma znaczenia dla zachowania programu, operandy operacji logicznych zwykle nie są w wygodnej formie do implementacji wyrażenia za pomocą bitowych operacji asm.

NAND często nie jest implementowany bezpośrednio, ponieważ posiadanie instrukcji AND daje ci możliwość przeskoczenia na warunek NAND.

Wykonywanie operacji logicznej w CPU często ustawia bity w rejestrze flag.

Większość rejestrów flag ma flagę ZERO. Flaga zerowa jest ustawiana, jeśli wynikiem operacji logicznej jest zero, i w przeciwnym razie jest kasowana.

Większość współczesnych procesorów ma instrukcję skoku, która skacze, jeśli ustawiona jest flaga zerowa. Mają także instrukcję, która przeskakuje, jeśli flaga zerowa nie jest ustawiona.

AND i NAND są uzupełnieniami. Jeżeli wynik operacji AND wynosi zero, to wynikiem operacji NAND jest 1 i odwrotnie.

Więc jeśli chcesz przeskoczyć, jeśli NAND dwóch wartości jest prawdziwy, po prostu wykonaj operację AND i przeskocz, jeśli ustawiona jest flaga zero.

Więc jeśli chcesz przeskoczyć, jeśli NAND dwóch wartości jest fałszywy, po prostu wykonaj operację AND i przeskocz, jeśli flaga zerowa jest czysta.

To, że coś jest tanie , nie oznacza, że ​​jest opłacalne .

Jeśli weźmiemy twoją argumentację ad absurdum, dojdziemy do wniosku, że procesor powinien składać się głównie z setek odmian instrukcji NOP - ponieważ są one najtańsze do wdrożenia.

Lub porównaj to z instrumentami finansowymi: czy kupiłbyś obligację 1 $ z zyskiem 0,01% tylko dlatego, że możesz? Nie, wolisz oszczędzać te dolary, dopóki nie będziesz mieć dość, aby kupić 10 USD obligacji z lepszym zwrotem. To samo dotyczy silikonu budżetowego na procesor: efektywnie wypiera wiele tanich, ale bezużytecznych operacji, takich jak NAND, i zapisuje zapisane tranzystory w coś znacznie droższego, ale naprawdę przydatnego.

Nie ma rasy, która miałaby jak najwięcej operacji. Jak RISC kontra CISC udowodniły, co Turing wiedział od samego początku: mniej znaczy więcej. Tak naprawdę lepiej mieć jak najmniej operacji.

Na poziomie sprzętowym nand lub nor jest podstawową operacją logiczną. W zależności od technologii (lub w zależności od tego, co arbitralnie nazywasz 1 i co nazywasz 0), zarówno nand, jak i n, można zaimplementować w bardzo prosty, podstawowy sposób.

Jeśli zignorujemy przypadek „ani”, cała logika zostanie skonstruowana z nand. Ale nie dlatego, że istnieje jakiś informatyczny dowód na to, że wszystkie operacje logiczne mogą być konstruowane z - i dlatego, że po prostu nie ma żadnej elementarnej metody budowania xor, itp., Która byłaby lepsza niż konstruowanie z nandów.

W przypadku instrukcji komputerowych sytuacja jest inna. Instrukcja nand mogłaby zostać zaimplementowana i byłaby nieco tańsza niż na przykład implementacja xor. Ale tylko niewielka część, ponieważ logika, która oblicza wynik, jest niewielka w porównaniu z logiką, która dekoduje instrukcję, przesuwa operandy, upewnia się, że tylko jedna operacja jest obliczona, i zbiera wynik i dostarcza go we właściwe miejsce. Każda instrukcja wykonuje jeden cykl, tak samo jak dodawanie, które jest dziesięć razy bardziej skomplikowane logicznie. Oszczędności nand vs. xor byłyby znikome.

Liczy się wtedy, ile instrukcji jest potrzebnych do operacji faktycznie wykonywanych przez typowy kod . Nand nie jest nigdzie na górze listy najczęściej żądanych operacji. Jest o wiele bardziej powszechne, że i, lub, nie są wymagane. Projektanci procesorów i zestawów instrukcji zbadają wiele istniejących kodów i ustalą, w jaki sposób różne instrukcje wpłyną na ten kod. Najprawdopodobniej stwierdzili, że dodanie instrukcji nand doprowadziłoby do bardzo niewielkiego zmniejszenia liczby instrukcji procesora wykonujących typowy kod, a zastąpienie niektórych istniejących instrukcji nand zwiększyłoby liczbę wykonywanych instrukcji.

Tylko dlatego, że NAND (lub NOR) może implementować wszystkie bramki w logice kombinacyjnej, nie przekłada się to na wydajnego operatora bitowego w ten sam sposób. Aby zaimplementować operację AND za pomocą operacji NAND, gdzie c = a AND b, musisz mieć c = a NAND b, następnie b = -1, a następnie c = c NAND b (dla NOT). Podstawowymi logicznymi operacjami bitowymi są AND, OR, EOR, NOT, NAND i NEOR. To nie jest wiele do omówienia, a pierwsze cztery są generalnie wbudowane. W logice kombinacyjnej podstawowe obwody logiczne są ograniczone tylko liczbą dostępnych bramek, co jest zupełnie inną grą w piłkę. Liczba możliwych połączeń w programowalnej tablicy bramek, która brzmi jak to, czego naprawdę szukasz, byłaby naprawdę bardzo duża. Niektóre procesory rzeczywiście mają wbudowane tablice bramek.

Nie wdrażasz bramki logicznej tylko dlatego, że ma ona funkcjonalną kompletność, zwłaszcza jeśli inne bramki logiczne są dostępne natywnie. Wdrażasz to, co jest najczęściej używane przez kompilatory.

NAND, NOR i XNOR są bardzo rzadko potrzebne. Oprócz klasycznych operatorów bitowych AND, OR i XOR, tylko ANDN ( ~a & b) - który nie jest NAND ( ~(a & b)) - miałby praktyczną użyteczność. Jeśli tak, procesor powinien to zaimplementować (i rzeczywiście niektóre procesory implementują ANDN).

Aby wyjaśnić praktyczną użyteczność ANDN, wyobraź sobie, że masz maskę bitową, która używa wielu bitów, ale interesują Cię tylko niektóre z nich, które są następujące:

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

Zwykle chcesz sprawdzić, czy interesuje Cię maska ​​bitowa

1. Wszystkie są ustawione
2. Ustawiono przynajmniej jeden
3. Co najmniej jeden nie jest ustawiony
4. Żadne nie jest ustawione

Zacznijmy od zebrania swoich interesujących elementów:

#define BITS_OF_INTEREST (IT_IS_FRIDAY | IT_IS_WARM | THE_SUN_SHINES)

1. Wszystkie bity zainteresowania są ustawione: bitowe ANDN + logiczne NIE

Powiedzmy, że chcesz wiedzieć, czy wszystkie interesujące Cię elementy są ustawione. Możesz to zobaczyć jak (my_bitmask & IT_IS_FRIDAY) && (my_bitmask & IT_IS_WARM) && (my_bitmask & THE_SUN_SHINES). Jednak normalnie byś to zwinął

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

2. Ustawiony jest co najmniej jeden bit zainteresowania: bitowe ORAZ

Powiedzmy teraz, że chcesz wiedzieć, czy ustawiony jest przynajmniej jeden interesujący element. Możesz to zobaczyć jako (my_bitmask & IT_IS_FRIDAY) || (my_bitmask & IT_IS_WARM) || (my_bitmask & THE_SUN_SHINES). Jednak normalnie byś to zwinął

unsigned int life_is_not_bad = my_bitmask & BITS_OF_INTEREST;

3. Co najmniej jeden bit zainteresowania nie jest ustawiony: bitowe ANDN

Powiedzmy teraz, że chcesz wiedzieć, czy nie ustawiono co najmniej jednego zainteresowania . Możesz to zobaczyć jako !(my_bitmask & IT_IS_FRIDAY) || !(my_bitmask & IT_IS_WARM) || !(my_bitmask & THE_SUN_SHINES). Jednak normalnie byś to zwinął

unsigned int life_is_imperfect = ~my_bitmask & BITS_OF_INTEREST;

4. Nie ustawiono żadnego zainteresowania: bitowe ORAZ + logiczne NIE

Powiedzmy teraz, że chcesz wiedzieć, czy wszystkie interesujące elementy nie są ustawione. Możesz to zobaczyć jako !(my_bitmask & IT_IS_FRIDAY) && !(my_bitmask & IT_IS_WARM) && !(my_bitmask & THE_SUN_SHINES). Jednak normalnie byś to zwinął

unsigned int life_is_horrible = !(my_bitmask & BITS_OF_INTEREST);

Są to typowe operacje wykonywane na masce bitowej oraz klasyczne bitowe OR i XOR. Sądzę jednak, że język (co nie jest CPU ) powinien zawierać bitowe NAND, NOR i operatorzy XNOR (których symbole byłoby ~&, ~|i ~^), mimo rzadko stosowane. Nie dołączałbym jednak operatora ANDN w języku, ponieważ nie jest on przemienny ( a ANDN bto nie to samo, co b ANDN a) - lepiej pisać ~a & bzamiast a ANDN b, ten pierwszy pokazuje jaśniej asymetrię operacji.