Mengapa tidak ada instruksi `nand` di CPU modern?

52

Mengapa desainer x86 (atau arsitektur CPU lainnya juga) memutuskan untuk tidak memasukkannya? Ini adalah gerbang logika yang dapat digunakan untuk membangun gerbang logika lain, sehingga cepat sebagai instruksi tunggal. Daripada chaining notdan andinstruksi (keduanya dibuat dari nand), mengapa tidak ada nandinstruksi?

Amumu
sumber
20
Apa usecase yang Anda miliki untuk instruksi nand? Mungkin desainer x86 tidak pernah menemukan apa pun
PlasmaHH
16
ARM memiliki BICinstruksi, yaitu a & ~b. Arm Thumb-2 memiliki ORNinstruksi yaitu ~(a | b). ARM cukup modern. Pengkodean instruksi dalam set instruksi CPU memiliki biayanya. Jadi hanya yang paling "berguna" yang masuk ke ISA.
Eugene Sh.
24
@ Amumu Kita juga bisa mendapat ~(((a << 1) | (b >> 1)) | 0x55555555)instruksi. Tujuannya adalah agar ~(((a << 1) | (b >> 1)) | 0x55555555)dapat diterjemahkan ke dalam satu instruksi, bukan 6. Jadi, mengapa tidak?
user253751
11
@Amumu: Itu bukan usecase, dan juga ~ tidak! Usecase adalah alasan kuat mengapa instruksi itu berguna, dan di mana itu bisa diterapkan. Alasan Anda seperti mengatakan "Instruksi harus ada di sana sehingga dapat digunakan" tetapi pertanyaannya adalah "apa yang akan digunakan untuk itu sangat penting sehingga berguna untuk menghabiskan sumber daya".
PlasmaHH
4
Saya sudah pemrograman selama 45 tahun, menulis beberapa kompiler, dan menggunakan beberapa operator logis yang aneh ketika tersedia seperti IMP, tetapi saya tidak pernah menggunakan operator atau instruksi NAND.
user207421

Jawaban:

62

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

Tetapi umumnya CPU modern dibangun untuk mencocokkan pembuatan kode otomatis oleh kompiler, dan bitwise NAND sangat jarang diperlukan. Bitwise AND dan OR digunakan lebih sering untuk memanipulasi bitfield dalam struktur data. Faktanya, SSE memiliki AND-NOT tetapi tidak NAND.

Setiap instruksi memiliki biaya dalam logika decode dan mengkonsumsi opcode yang dapat digunakan untuk sesuatu yang lain. Khususnya dalam penyandian panjang variabel seperti x86, Anda dapat kehabisan opcode pendek dan harus menggunakan yang lebih lama, yang berpotensi memperlambat semua kode.

pjc50
sumber
5
@supercat AND-NOT biasanya digunakan untuk mematikan bit dalam variabel bit-set. misif(windowType & ~WINDOW_RESIZABLE) { ... do stuff for variable-sized windows ... }
adib
2
@adib: Yup. Fitur menarik dari "and-not" adalah bahwa tidak seperti operator "bitwise not" [~] ukuran hasil tidak masalah. Jika fooadalah uint64_t, pernyataan foo &= ~something;tersebut terkadang dapat menghapus lebih banyak bit daripada yang dimaksudkan, tetapi jika ada &~=operator masalah seperti itu dapat dihindari.
supercat
6
@adib jika WINDOW_RESIZABLEadalah konstanta, maka pengoptimal harus mengevaluasi ~WINDOW_RESIZABLEpada waktu kompilasi, jadi ini hanya DAN pada waktu berjalan.
alephzero
4
@MarkRansom: Tidak, sebab-akibat sepenuhnya benar dari sejarah komputasi. Fenomena ini merancang CPU yang dioptimalkan untuk kompiler bukan programmer perakitan manusia adalah bagian dari gerakan RISC (meskipun, gerakan RISC itu sendiri lebih luas dari sekedar aspek itu). CPU yang dirancang untuk kompiler termasuk ARM dan Atmel AVR. Pada akhir 90-an dan awal 00-an orang menyewa penulis kompiler dan pemrogram OS untuk merancang set instruksi CPU
slebetman
3
Hari-hari ini operasi register-to-register pada dasarnya gratis dibandingkan dengan akses RAM. Menerapkan instruksi yang berlebihan membutuhkan biaya silikon real-estate di CPU. Oleh karena itu biasanya hanya akan ada satu bentuk bitwise-OR dan bitwise-AND karena menambahkan operasi register-register bitwise melengkapi hampir tidak akan pernah memperlambat apa pun.
nigel222
31

Biaya fungsi ALU tersebut adalah

1) logika yang melakukan fungsi itu sendiri

2) pemilih yang memilih hasil fungsi ini, bukan yang lain dari semua fungsi ALU

3) biaya memiliki opsi ini dalam set instruksi (dan tidak memiliki beberapa fungsi bermanfaat lainnya)

Saya setuju dengan Anda bahwa biaya 1) sangat kecil. Namun biaya 2) dan 3) hampir tidak tergantung pada fungsinya. Saya pikir dalam hal ini 3) biaya (bit yang digunakan dalam instruksi) adalah alasan untuk tidak memiliki instruksi khusus ini. Bit dalam instruksi adalah sumber daya yang sangat langka untuk perancang CPU / arsitektur.

Wouter van Ooijen
sumber
29

Putar balik - pertama-tama lihat mengapa Nand populer dalam desain logika perangkat keras - ia memiliki beberapa properti yang berguna di sana. Kemudian tanyakan apakah properti itu masih berlaku dalam instruksi CPU ...

TL / DR - tidak, jadi tidak ada kerugian untuk menggunakan Dan, Atau atau Tidak sebagai gantinya.

Keuntungan terbesar untuk logika Nand yang ditanamkan adalah kecepatan, diperoleh dengan mengurangi jumlah level logika (tahap transistor) antara input dan output sirkuit. Dalam CPU, kecepatan clock ditentukan oleh kecepatan operasi yang jauh lebih kompleks seperti penambahan, jadi mempercepat operasi DAN tidak akan memungkinkan Anda untuk meningkatkan laju jam.

Dan berapa kali Anda perlu menggabungkan instruksi lain semakin kecil - cukup sehingga Nand benar-benar tidak mendapatkan ruang di set instruksi.

Brian Drummond
sumber
1
Dalam kasus di mana isolasi input tidak diperlukan, "dan tidak" akan tampak sangat murah di perangkat keras. Kembali pada tahun 1977 saya merancang pengontrol sinyal belok untuk trailer orangtua saya menggunakan dua transistor dan dua dioda per cahaya untuk melakukan fungsi "XOR" [lampu kiri == xor (sinyal kiri, rem); lampu kanan == xor (sinyal kanan, rem)], pada dasarnya menghubungkan dua atau tidak fungsi untuk setiap lampu. Saya belum melihat trik seperti itu digunakan dalam desain LSI, tetapi saya akan berpikir bahwa dalam TTL atau NMOS, dalam kasus di mana apa pun yang memberi makan input akan memiliki kemampuan drive yang memadai, trik tersebut dapat menghemat sirkuit.
supercat
12

Saya ingin setuju dengan Brian di sini, dan Wouter dan pjc50.

Saya juga ingin menambahkan bahwa untuk keperluan umum, terutama CISC, prosesor, instruksi tidak semua memiliki throughput yang sama - operasi yang rumit mungkin hanya membutuhkan lebih banyak siklus yang mudah.

Pertimbangkan X86: AND(yang merupakan operasi "dan") mungkin sangat cepat. Sama berlaku untuk NOT. Mari kita lihat sedikit pembongkaran:

Kode input:

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

Perintah untuk menghasilkan perakitan:

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

Majelis Output (disingkat):

    .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

Seperti yang Anda lihat, untuk tipe data berukuran sub-64, semuanya ditangani dengan mudah (karenanya dan l dan bukan l ), karena itulah "bandwidth" asli dari kompiler saya, seperti yang terlihat.

Fakta bahwa ada movdi antara hanya karena fakta bahwa eaxregister yang berisi nilai pengembalian fungsi. Biasanya, Anda hanya perlu menghitung di ediregister tujuan umum untuk menghitung dengan hasilnya.

Untuk 64 bit, itu sama - hanya dengan kata "quad" (karenanya, tertinggal q), dan rax/ rsibukannya eax/ edi.

Tampaknya untuk operan 128 bit dan lebih besar, Intel tidak peduli untuk mengimplementasikan operasi "tidak"; sebagai gantinya, kompiler menghasilkan 1register semua (perbandingan sendiri dari register dengan dirinya sendiri, hasil disimpan dalam register dengan vdcmpeqdinstruksi), dan xors itu.

Singkatnya: Dengan menerapkan operasi yang rumit dengan beberapa instruksi dasar, Anda tidak perlu memperlambat operasi - sama sekali tidak ada manfaatnya memiliki satu instruksi yang melakukan pekerjaan beberapa instruksi jika tidak lebih cepat.

Marcus Müller
sumber
10

Pertama jangan bingung operasi bitwise dan logis.

Operasi bitwise biasanya digunakan untuk mengatur / menghapus / beralih / memeriksa bit dalam bitfields. Tak satu pun dari operasi ini memerlukan nand ("dan ​​tidak", juga dikenal sebagai "bit clear" lebih berguna).

Operasi logis dalam sebagian besar bahasa pemrograman modern dievaluasi menggunakan logika hubung singkat. Jadi biasanya diperlukan pendekatan berbasis cabang untuk mengimplementasikannya. Bahkan ketika kompiler dapat menentukan bahwa hubungan pendek vs evaluasi lengkap tidak membuat perbedaan pada perilaku program, operan untuk operasi logis biasanya tidak dalam bentuk yang mudah untuk mengimplementasikan ekspresi menggunakan operasi asm bitwise.

Peter Green
sumber
10

NAND sering tidak diimplementasikan secara langsung karena memiliki instruksi AND secara implisit memberi Anda kemampuan untuk melompat pada kondisi NAND.

Melakukan operasi logis dalam CPU sering menetapkan bit dalam register bendera.

Sebagian besar register bendera memiliki bendera NOL. Bendera nol diatur jika hasil operasi logis adalah nol, dan dihapus jika tidak.

Kebanyakan CPU modern memiliki instruksi lompatan yang melompat jika flag nol diatur. Mereka juga memiliki istruction yang melompat jika bendera nol tidak diatur.

DAN dan NAND adalah pelengkap. Jika hasil dari operasi AND adalah nol maka hasil dari operasi NAND adalah 1, dan sebaliknya.

Jadi jika Anda ingin lompat atau NAND dari dua nilai benar maka cukup lakukan operasi DAN, dan lompat jika bendera nol diatur.

Jadi jika Anda ingin lompat atau jika NAND dari dua nilai salah maka lakukan saja operasi AND, dan lompat jika bendera nolnya jelas.

pengguna4574
sumber
Memang - pilihan instruksi lompat bersyarat memberi Anda pilihan logika pembalik dan non-pembalik untuk seluruh kelas operasi, tanpa harus mengimplementasikan pilihan itu untuk masing-masing individu.
Chris Stratton
Ini seharusnya menjadi jawaban terbaik. Operasi zero flag membuat NAND berlebihan untuk operasi logis karena AND + JNZ dan AND + JZ pada dasarnya masing-masing memiliki hubungan pendek / logis AND dan NAND, keduanya menggunakan jumlah opcode yang sama.
Lie Ryan
4

Hanya karena sesuatu itu murah tidak berarti itu hemat biaya .

Jika kami menggunakan argumentasi ad absurdum Anda, kami akan mencapai kesimpulan bahwa CPU sebagian besar terdiri dari ratusan rasa instruksi NOP - karena mereka adalah yang termurah untuk diterapkan.

Atau bandingkan dengan instrumen keuangan: apakah Anda akan membeli obligasi $ 1 dengan pengembalian 0,01% hanya karena Anda bisa? Tidak, Anda lebih suka menyimpan dolar itu sampai Anda memiliki cukup uang untuk membeli obligasi $ 10 dengan pengembalian yang lebih baik. Hal yang sama berlaku dengan anggaran silikon pada CPU: itu efektif untuk memotong banyak ops murah tapi tidak berguna seperti NAND, dan menempatkan transistor yang diselamatkan menjadi sesuatu yang jauh lebih mahal tetapi benar-benar berguna.

Tidak ada perlombaan untuk memiliki ops sebanyak mungkin. Seperti RISC vs CISC telah membuktikan apa yang Turing ketahui sejak awal: lebih sedikit lebih banyak. Sebenarnya lebih baik memiliki ops sesedikit mungkin.

Agent_L
sumber
noptidak dapat mengimplementasikan semua gerbang logika lainnya, tetapi nandatau nordapat, secara efektif membuat kembali setiap instruksi yang diimplementasikan dalam CPU dalam perangkat lunak. Jika kita mengambil pendekatan RISC, itu adalah ..
Amumu
@ Amumu saya pikir Anda sedang bingung gatedan instruction. Gates digunakan untuk mengimplementasikan instruksi, bukan sebaliknya. NOPadalah instruksi, bukan gerbang. Dan ya, CPU mengandung ribuan atau bahkan mungkin jutaan gerbang NAND untuk mengimplementasikan semua instruksi. Hanya saja bukan instruksi "NAND".
Agent_L
2
@Amumu Itu bukan pendekatan RISC :) Itu pendekatan "gunakan abstraksi terluas", yang tidak terlalu berguna di luar aplikasi yang sangat spesifik. Tentu, nandada satu gerbang yang bisa digunakan untuk mengimplementasikan gerbang lain; tetapi Anda sudah memiliki semua instruksi lainnya . Menerapkannya kembali menggunakan nandinstruksi akan lebih lambat . Dan mereka digunakan terlalu sering untuk mentolerir itu, tidak seperti contoh spesifik cherry-pick Anda di mana nandakan menghasilkan kode lebih pendek (bukan kode lebih cepat , hanya lebih pendek); tapi itu sangat jarang, dan manfaatnya tidak sebanding dengan biayanya.
Luaan
@Amumu Jika kami menggunakan pendekatan Anda, kami tidak akan memiliki nomor posisi. Apa gunanya Anda hanya bisa mengatakan ((((()))))bukannya 5, kan? Lima hanya satu nomor tertentu, itu terlalu membatasi - set jauh lebih umum: P
Luaan
@ Agg_L Ya, saya tahu gerbang menerapkan instruksi. nandmengimplementasikan semua gerbang, oleh karena itu secara implisit nanddapat mengimplementasikan semua instruksi lainnya. Kemudian, jika seorang programmer memiliki nandinstruksi yang tersedia, ia dapat menemukan instruksinya sendiri ketika berpikir di gerbang logika. Apa yang saya maksud dari awal adalah bahwa jika itu sangat mendasar, mengapa tidak diberikan instruksi sendiri (yaitu, opcode dalam logika decoder), sehingga seorang programmer dapat menggunakan instruksi tersebut. Tentu saja setelah saya dijawab, sekarang saya tahu itu tergantung pada penggunaan perangkat lunak.
Amumu
3

Pada tingkat perangkat keras, baik nand atau tidak adalah operasi logika dasar. Bergantung pada teknologinya (atau tergantung apa yang Anda panggil 1 dan apa yang Anda panggil 0), baik nand atau pun tidak dapat diimplementasikan dengan cara yang sangat sederhana dan sederhana.

Jika kita mengabaikan kasus "tidak", semua logika lain dibangun dari nand. Tetapi bukan karena ada beberapa bukti ilmu komputer bahwa semua operasi logika dapat dibangun dari dan - alasannya adalah bahwa tidak ada metode dasar untuk membangun xor, atau, dan lain-lain yang lebih baik daripada membangunnya dari nand's.

Untuk instruksi komputer, situasinya berbeda. Instruksi nand dapat diimplementasikan, dan itu akan menjadi sedikit lebih murah daripada mengimplementasikan xor, misalnya. Tetapi hanya sedikit, karena logika yang menghitung hasilnya kecil dibandingkan dengan logika yang menerjemahkan kode, memindahkan operan, memastikan bahwa satu operasi hanya dihitung, dan mengambil hasilnya dan mengirimkannya ke tempat yang tepat. Setiap instruksi membutuhkan satu siklus untuk dieksekusi, sama dengan penambahan yang sepuluh kali lebih rumit dalam hal logika. Penghematan nand vs xor akan diabaikan.

Yang penting kemudian adalah berapa banyak instruksi yang diperlukan untuk operasi yang sebenarnya dilakukan oleh kode biasa . Nand tidak ada di dekat bagian atas daftar operasi yang biasa diminta. Adalah jauh lebih umum bahwa dan, atau, tidak diminta. Perancang prosesor dan set instruksi akan memeriksa banyak kode yang ada dan menentukan bagaimana instruksi yang berbeda akan mempengaruhi kode itu. Mereka kemungkinan besar menemukan bahwa menambahkan instruksi nand akan menyebabkan pengurangan sangat sedikit dalam jumlah instruksi prosesor yang mengeksekusi untuk menjalankan kode khas, dan mengganti beberapa instruksi yang ada dengan nand akan meningkatkan jumlah instruksi yang dilakukan.

gnasher729
sumber
2

Hanya karena NAND (atau NOR) dapat mengimplementasikan semua gerbang dalam logika kombinasional, tidak menerjemahkan ke operator bitwise yang efisien dengan cara yang sama. Untuk menerapkan DAN hanya menggunakan operasi NAND, di mana c = a DAN b, Anda harus memiliki c = a NAND b, lalu b = -1, lalu c = c NAND b (untuk TIDAK). Operasi bitwise logika dasar adalah AND, OR, EOR, NOT, NAND, dan NEOR. Itu tidak banyak untuk dibahas, dan empat yang pertama biasanya dibangun. Dalam logika kombinasional, sirkuit logika dasar hanya dibatasi oleh jumlah gerbang yang tersedia, yang merupakan permainan bola yang sepenuhnya berbeda. Jumlah interkoneksi yang mungkin dalam array gerbang yang dapat diprogram, yang terdengar seperti apa yang benar-benar Anda cari, akan menjadi jumlah yang sangat besar. Beberapa prosesor memang memiliki larik gerbang bawaan.

Robin Hodson
sumber
0

Anda tidak menerapkan gerbang logika hanya karena memiliki kelengkapan fungsional, terutama jika gerbang logika lain tersedia secara native. Anda menerapkan apa yang cenderung paling sering digunakan oleh kompiler.

NAND, NOR dan XNOR sangat jarang dibutuhkan. Selain operator bitwise klasik AND, OR dan XOR, hanya ANDN ( ~a & b) - yang bukan NAND ( ~(a & b)) - yang memiliki utilitas praktis. Jika ada, CPU harus mengimplementasikannya (dan memang beberapa CPU memang mengimplementasikan ANDN).

Untuk menjelaskan utilitas praktis ANDN, bayangkan Anda memiliki bitmask yang menggunakan banyak bit, tetapi Anda hanya tertarik pada beberapa di antaranya, yaitu sebagai berikut:

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

Biasanya Anda ingin memeriksa tentang minat Anda pada bitmask apakah

  1. Mereka sudah siap
  2. Setidaknya satu diatur
  3. Setidaknya satu tidak disetel
  4. Tidak ada yang ditetapkan

Mari kita mulai dengan mengumpulkan sedikit minat Anda:

#define BITS_OF_INTEREST (IT_IS_FRIDAY | IT_IS_WARM | THE_SUN_SHINES)

1. Semua bit yang menarik ditetapkan: ANDN + bitwise TIDAK logis

Katakanlah Anda ingin tahu apakah minat Anda sudah ditentukan. Anda bisa melihatnya seperti (my_bitmask & IT_IS_FRIDAY) && (my_bitmask & IT_IS_WARM) && (my_bitmask & THE_SUN_SHINES). Namun biasanya Anda akan menciutkannya menjadi

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

2. Setidaknya satu bit minat ditetapkan: bitwise AND

Sekarang katakanlah Anda ingin tahu apakah setidaknya ada sedikit minat yang ditetapkan. Anda bisa melihatnya sebagai (my_bitmask & IT_IS_FRIDAY) || (my_bitmask & IT_IS_WARM) || (my_bitmask & THE_SUN_SHINES). Namun biasanya Anda akan menciutkannya menjadi

unsigned int life_is_not_bad = my_bitmask & BITS_OF_INTEREST;

3. Setidaknya satu bit minat tidak disetel: ANDN bitwise

Sekarang, katakanlah Anda ingin tahu apakah setidaknya ada sedikit minat yang tidak ditetapkan. Anda bisa melihatnya sebagai !(my_bitmask & IT_IS_FRIDAY) || !(my_bitmask & IT_IS_WARM) || !(my_bitmask & THE_SUN_SHINES). Namun biasanya Anda akan menciutkannya menjadi

unsigned int life_is_imperfect = ~my_bitmask & BITS_OF_INTEREST;

4. Tidak ada sedikit minat yang diatur: bitwise AND + logical NOT

Sekarang katakanlah Anda ingin tahu apakah semua bit yang menarik tidak ditetapkan. Anda bisa melihatnya sebagai !(my_bitmask & IT_IS_FRIDAY) && !(my_bitmask & IT_IS_WARM) && !(my_bitmask & THE_SUN_SHINES). Namun biasanya Anda akan menciutkannya menjadi

unsigned int life_is_horrible = !(my_bitmask & BITS_OF_INTEREST);

Ini adalah operasi umum yang dilakukan pada bitmask, ditambah bitwise klasik OR dan XOR. Saya pikir meskipun bahasa (yang bukan CPU ) harus mencakup operator NAND, NOR dan XNOR bitwise (yang simbolnya akan ~&, ~|dan ~^), meskipun jarang digunakan. Saya tidak akan menyertakan operator ANDN dalam bahasa, karena itu tidak komutatif ( a ANDN btidak sama dengan b ANDN a) - lebih baik untuk menulis ~a & bdaripada a ANDN b, mantan menunjukkan lebih jelas asimetri operasi.

madmurphy
sumber