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

52

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

Amumu
źródło
20
Jaki masz użytek z instrukcji nand? Prawdopodobnie projektanci x86 nigdy nie znaleźli
PlasmaHH
16
ARM ma BICinstrukcję, która jest a & ~b. Ramię Thumb-2 ma ORNinstrukcję, która jest ~(a | b). ARM jest dość nowoczesny. Kodowanie instrukcji w zestawie instrukcji CPU ma swoje koszty. Tak więc tylko najbardziej „przydatne” pojawiają się w ISA.
Eugene Sh.
24
@Amumu Też możemy mieć ~(((a << 1) | (b >> 1)) | 0x55555555)instrukcje. Celem byłoby, aby ~(((a << 1) | (b >> 1)) | 0x55555555)można było przetłumaczyć je na jedną instrukcję zamiast na 6. Więc dlaczego nie?
user253751
11
@Amumu: To nie jest przypadek użycia, a także jego ~ nie! Przypadek użycia jest istotnym powodem, dla którego instrukcja ta jest przydatna i gdzie można ją zastosować. Twoje rozumowanie przypomina powiedzenie „Instrukcja powinna tam być, aby można było z niej korzystać”, ale pytanie brzmi „w jaki sposób ją wykorzystać, ponieważ jest tak ważna, że ​​warto wydać zasoby”.
PlasmaHH
4
Programuję od 45 lat, napisałem kilka kompilatorów i używałem dziwnych operatorów logicznych, gdy są dostępne, takich jak IMP, ale nigdy nie miałem zastosowania dla operatora lub instrukcji NAND.
user207421,

Odpowiedzi:

62

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.

pjc50
źródło
5
@supercat AND-NOT jest powszechnie używany do wyłączania bitów w zmiennej o ustawionych bitach. np.if(windowType & ~WINDOW_RESIZABLE) { ... do stuff for variable-sized windows ... }
adib
2
@adib: Tak. Interesującą cechą „and-not” jest to, że w przeciwieństwie do operatora „bitwise not” [~] rozmiar wyniku nie będzie miał znaczenia. Jeśli foojest to uint64_t, instrukcja foo &= ~something;może czasami wyczyścić więcej bitów niż zamierzono, ale gdyby istniał &~=operator, problemów takich można by uniknąć.
supercat
6
@adib jeśli WINDOW_RESIZABLEjest stałą, to optymalizator powinien oceniać ~WINDOW_RESIZABLEw czasie kompilacji, więc jest to po prostu AND w czasie wykonywania.
alephzero
4
@MarkRansom: Nie, przyczyna i skutek są całkowicie poprawne z historii obliczeń. Zjawisko projektowania procesorów zoptymalizowanych pod kątem kompilatorów zamiast programistów zajmujących się montażem ludzi było częścią ruchu RISC (choć sam ruch RISC jest szerszy niż tylko ten aspekt). Procesory zaprojektowane dla kompilatorów obejmują ARM i Atmel AVR. W późnych latach 90. i wczesnych 00s ludzie zatrudniony pisarzy kompilator i programistów OS do projektowania zestawów instrukcji procesora
slebetman
3
Obecnie operacje rejestrowania w celu rejestracji są zasadniczo bezpłatne w porównaniu z dostępem do pamięci RAM. Wdrożenie zbędnych instrukcji kosztuje krzemową nieruchomość w CPU. Dlatego zwykle występuje tylko jedna forma bitowego-LUB i bitowego-AND, ponieważ dodanie operacji rejestru z uzupełnianiem bitowym prawie nigdy niczego nie spowolni.
nigel222
31

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.

Wouter van Ooijen
źródło
29

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.

Brian Drummond
źródło
1
W przypadkach, gdy izolacja wejściowa nie jest wymagana, „i nie” wydaje się bardzo tanie w sprzęcie. W 1977 roku zaprojektowałem kontroler kierunkowskazów dla przyczepy mojego rodzica, używając dwóch tranzystorów i dwóch diod na światło, aby wykonywać funkcję „XOR” [lewa lampa == xor (lewy sygnał, hamulec); prawa lampa == xor (prawy sygnał, hamulec)], zasadniczo łącząc dwie lub nie funkcje dla każdego światła. Nie widziałem takich sztuczek używanych w projektowaniu LSI, ale sądzę, że w TTL lub NMOS, w przypadkach, gdy cokolwiek zasilające wejście miałoby odpowiednie możliwości napędu, takie sztuczki mogłyby zaoszczędzić obwody.
supercat
12

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.

Marcus Müller
źródło
10

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.

Peter Green
źródło
10

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.

użytkownik4574
źródło
Rzeczywiście - wybór instrukcji skoku warunkowego daje wybór logiki odwracania i nieodwracania dla całej klasy operacji, bez konieczności implementowania tego wyboru dla każdego z osobna.
Chris Stratton
To powinna być najlepsza odpowiedź. Operacje z flagą zerową powodują, że NAND staje się zbędny dla operacji logicznych, ponieważ AND + JNZ i AND + JZ są w zasadzie odpowiednio zwarte / logiczne AND i NAND, oba przyjmują tę samą liczbę kodów operacyjnych.
Lie Ryan,
4

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.

Agent_L
źródło
nopnie może zaimplementować wszystkich innych bramek logicznych, ale nandlub normoże skutecznie odtworzyć dowolną instrukcję zaimplementowaną w procesorze w oprogramowaniu. Jeśli weźmiemy podejście RISC, to znaczy ...
Amumu
@Amumu Myślę, że mieszasz gatei instruction. Bramki służą do wdrażania instrukcji, a nie na odwrót. NOPjest instrukcją, a nie bramą. I tak, procesory zawierają tysiące, a może nawet miliony bramek NAND do implementacji wszystkich instrukcji. Po prostu nie instrukcja „NAND”.
Agent_L
2
@Amumu To nie jest podejście RISC :) To jest podejście „używaj najszerszych abstrakcji”, które nie jest zbyt przydatne poza bardzo specyficznymi aplikacjami. Jasne, nandto jedna brama, którą można wykorzystać do realizacji innych bram; ale masz już wszystkie pozostałe instrukcje . Wdrożenie ich za pomocą nandinstrukcji byłoby wolniejsze . I są one używane zbyt często, aby to tolerować, w przeciwieństwie do wybranego przez ciebie konkretnego przykładu, w którym nandprodukuje się krótszy kod (nie szybszy , tylko krótszy); ale to niezwykle rzadkie, a korzyść po prostu nie jest warta kosztów.
Luaan,
@Amumu Gdybyśmy zastosowali twoje podejście, nie mielibyśmy liczb pozycyjnych. Jaki jest sens, kiedy możesz po prostu powiedzieć ((((()))))zamiast 5, prawda? Pięć to tylko jedna konkretna liczba, co jest zbyt ograniczające - zestawy są znacznie bardziej ogólne: P
Luaan
@Agent_L Tak, wiem, że bramki wdrażają instrukcje. nandimplementuje wszystkie bramki, dlatego domyślnie nandmoże implementować wszystkie inne instrukcje. Następnie, jeśli programista ma nanddostępną instrukcję, może wymyślić własne instrukcje podczas myślenia w bramkach logicznych. Od samego początku miałem na myśli to, że jeśli jest tak fundamentalny, dlaczego nie otrzymał własnej instrukcji (czyli kodu operacyjnego w logice dekodera), więc programista może użyć takiej instrukcji. Oczywiście po otrzymaniu odpowiedzi wiem, że zależy to od użytkowania oprogramowania.
Amumu,
3

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.

gnasher729
źródło
2

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.

Robin Hodson
źródło
0

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.

madmurphy
źródło