Mengapa penambahan secepat operasi bit-bijaksana dalam prosesor modern?

Saya tahu bahwa operasi bit-wise sangat cepat pada prosesor modern, karena mereka dapat beroperasi pada 32 atau 64 bit secara paralel, sehingga operasi bit-wise hanya memerlukan satu siklus clock. Namun penambahan adalah operasi kompleks yang terdiri dari setidaknya satu dan mungkin hingga selusin operasi yang bijaksana, jadi saya secara alami berpikir itu akan 3-4 kali lebih lambat. Saya terkejut melihat setelah tolok ukur sederhana bahwa penambahan persis sama cepatnya dengan operasi bit-wise (XOR, OR, DAN dll). Adakah yang bisa menjelaskan ini?

Penambahan cepat karena desainer CPU telah memasukkan sirkuit yang diperlukan untuk membuatnya cepat. Memang dibutuhkan gerbang lebih banyak daripada operasi bitwise, tetapi cukup sering bahwa desainer CPU menilai itu layak dilakukan. Lihat https://en.wikipedia.org/wiki/Adder_(electronics) .

Keduanya dapat dibuat cukup cepat untuk dieksekusi dalam satu siklus CPU. Mereka tidak sama cepatnya - penambahan membutuhkan lebih banyak gerbang dan lebih banyak latensi daripada operasi bitwise - tetapi cukup cepat sehingga prosesor dapat melakukannya dalam satu siklus clock. Ada overhead latensi per-instruksi untuk decoding instruksi dan logika kontrol, dan latensi untuk itu secara signifikan lebih besar daripada latensi untuk melakukan operasi bitwise, sehingga perbedaan antara keduanya akan dibanjiri oleh overhead itu. Jawaban programmer dan jawaban Paul92 menjelaskan efek itu dengan baik.

Ada beberapa aspek.

• Biaya relatif dari operasi bitwise dan tambahan. Seorang penambah naif akan memiliki kedalaman gerbang yang tergantung secara linear dari lebar kata. Ada pendekatan alternatif, lebih mahal dalam hal gerbang, yang mengurangi kedalaman (IIRC kedalaman kemudian bergantung secara logis dari lebar kata). Orang lain telah memberikan referensi untuk teknik tersebut, saya hanya akan menunjukkan bahwa perbedaan juga kurang penting daripada apa yang tampaknya hanya mempertimbangkan biaya operasi karena perlunya logika kontrol yang menambah penundaan.

• Lalu ada fakta bahwa prosesor biasanya clocked (Saya mengetahui beberapa penelitian atau tujuan khusus desain non clocked, tapi saya bahkan tidak yakin bahwa beberapa tersedia secara komersial). Itu berarti bahwa berapapun kecepatan operasi, ia akan mengambil kelipatan integer dari clock cycle.

• Akhirnya ada pertimbangan mikro-arsitektur: apakah Anda yakin bahwa Anda mengukur apa yang Anda inginkan? Saat ini, prosesor cenderung pipelined, multi-skalar, dengan eksekusi out-of-order dan apa pun. Itu berarti bahwa mereka dapat menjalankan beberapa instruksi pada saat yang sama, pada berbagai tahap penyelesaian. Jika Anda ingin menunjukkan dengan ukuran bahwa suatu operasi membutuhkan lebih banyak waktu daripada yang lain, Anda harus mempertimbangkan aspek tersebut karena tujuannya adalah untuk menyembunyikan perbedaan itu. Anda mungkin memiliki throughput yang sama untuk operasi penambahan dan bitwise ketika menggunakan data independen tetapi ukuran latensi atau memperkenalkan dependensi antara operasi dapat menunjukkan sebaliknya. Dan Anda juga harus memastikan bahwa hambatan ukuran Anda dalam eksekusi, dan tidak misalnya dalam memori mengakses.

CPU beroperasi dalam siklus. Pada setiap siklus, sesuatu terjadi. Biasanya, suatu instruksi membutuhkan lebih banyak siklus untuk dieksekusi, tetapi beberapa instruksi dieksekusi pada waktu yang sama, di berbagai negara.

Misalnya, prosesor sederhana mungkin memiliki 3 langkah untuk setiap instruksi: ambil, jalankan dan simpan. Kapan saja, 3 instruksi sedang diproses: satu sedang diambil, satu sedang dieksekusi dan satu menyimpan hasilnya. Ini disebut pipeline dan memiliki dalam contoh ini 3 tahap. Prosesor modern memiliki saluran pipa dengan lebih dari 15 tahap. Namun, penambahan, serta sebagian besar operasi aritmatika, biasanya dieksekusi dalam satu tahap (saya berbicara tentang operasi penambahan 2 angka oleh ALU, bukan tentang instruksi itu sendiri - tergantung pada arsitektur prosesor, instruksi mungkin memerlukan lebih banyak siklus untuk mengambil argumen dari memori, melakukan pengkondisian, menyimpan hasil ke memori).

Durasi siklus ditentukan oleh jalur kritis terpanjang. Pada dasarnya, ini adalah jumlah waktu terlama yang diperlukan untuk menyelesaikan beberapa tahap pipeline. Jika Anda ingin membuat CPU lebih cepat, Anda perlu mengoptimalkan jalur kritis. Jika mengurangi jalur kritis per se tidak mungkin, itu dapat dibagi menjadi 2 tahap dari pipa, dan Anda sekarang dapat clock CPU Anda pada frekuensi hampir dua kali lipat (dengan asumsi tidak ada jalur kritis lain yang mencegah Anda melakukan ini ). Tapi ini disertai dengan overhead: Anda perlu memasukkan register di antara tahapan-tahapan pipa. Yang berarti Anda tidak benar-benar mendapatkan kecepatan 2x (register perlu waktu untuk menyimpan data), dan Anda telah memperumit seluruh desain.

Sudah ada metode yang cukup efisien untuk melakukan penambahan (mis. Bawa lookahead adders) dan penambahan bukanlah jalur penting untuk kecepatan prosesor, sehingga tidak masuk akal membaginya menjadi beberapa siklus.

Juga, perhatikan bahwa walaupun mungkin terlihat rumit bagi Anda, dalam hal-hal perangkat keras dapat dilakukan secara paralel dengan sangat cepat.

Prosesor di-clock, sehingga meskipun beberapa instruksi jelas dapat dilakukan lebih cepat daripada yang lain, mereka mungkin mengambil jumlah siklus yang sama.

Anda mungkin akan menemukan bahwa sirkuit yang diperlukan untuk mengangkut data antara register dan unit eksekusi secara signifikan lebih rumit daripada para adders.

Perhatikan bahwa instruksi MOV (register to register) sederhana bahkan lebih sedikit perhitungannya daripada logika bitwise, namun MOV dan ADD biasanya mengambil satu siklus. Jika MOV dapat dibuat dua kali lebih cepat, CPU akan clock dua kali lebih cepat dan ADD akan menjadi dua siklus.

Penambahan cukup penting untuk tidak membiarkannya menunggu carry bit untuk beriak melalui akumulator 64-bit: istilah untuk itu adalah adder carry-lookahead dan mereka pada dasarnya adalah bagian dari CPU 8-bit (dan ALU mereka) dan ke atas. Memang, prosesor modern cenderung tidak memerlukan banyak waktu eksekusi untuk multiplikasi penuh, baik: carry-lookahead sebenarnya adalah alat yang sangat lama (dan relatif terjangkau) dalam kotak peralatan perancang prosesor.

Saya pikir Anda akan sulit sekali menemukan prosesor yang memiliki tambahan mengambil lebih banyak siklus daripada operasi bitwise. Sebagian karena sebagian besar prosesor harus melakukan setidaknya satu tambahan per siklus instruksi hanya untuk menambah penghitung program. Hanya operasi bitwise tidak terlalu berguna.

(Siklus instruksi, bukan siklus clock - misalnya 6502 membutuhkan minimal dua siklus clock per instruksi karena non-pipelined dan tidak memiliki cache instruksi)

Konsep nyata Anda mungkin hilang adalah bahwa dari jalur kritis : dalam sebuah chip, operasi terpanjang yang dapat dilakukan dalam satu siklus menentukan, pada tingkat perangkat keras, seberapa cepat chip dapat clock.

Pengecualian untuk hal ini adalah logika asinkron (jarang digunakan dan sulit dikomersialkan), yang benar-benar mengeksekusi pada kecepatan yang berbeda tergantung pada waktu propagasi logika, suhu perangkat dll.

Di tingkat gerbang, Anda benar bahwa dibutuhkan lebih banyak pekerjaan untuk melakukan penambahan, dan karenanya membutuhkan waktu lebih lama. Namun, biaya itu cukup sepele yang tidak masalah.

Prosesor modern diberi waktu. Anda tidak dapat melakukan instruksi apa pun kecuali kelipatan dari laju jam ini. Jika laju jam didorong lebih tinggi, untuk memaksimalkan kecepatan operasi bitwise, Anda harus menghabiskan setidaknya 2 siklus untuk penambahan. Sebagian besar waktu ini akan dihabiskan menunggu karena Anda tidak benar-benar membutuhkan waktu 2 siklus penuh. Anda hanya membutuhkan 1.1 (atau nomor seperti itu). Sekarang chip Anda menambahkan lebih lambat daripada orang lain di pasar.

Lebih buruk lagi, tindakan hanya menambah atau melakukan operasi bitwise hanya satu bagian kecil dari apa yang terjadi selama siklus. Anda harus dapat mengambil / mendekode instruksi dalam satu siklus. Anda harus dapat melakukan operasi cache dalam satu siklus. Banyak hal lain yang terjadi pada skala waktu yang sama dengan penambahan sederhana atau operasi bitwise.

Solusinya, tentu saja, adalah mengembangkan pipa yang sangat dalam, memecah tugas-tugas ini menjadi bagian-bagian kecil yang sesuai dengan waktu siklus kecil yang ditentukan oleh operasi bitwise. Pentium 4 terkenal menunjukkan batas pemikiran dalam istilah pipa yang dalam ini. Segala macam masalah muncul. Khususnya percabangan menjadi sangat sulit karena Anda harus menyiram pipa begitu Anda memiliki data untuk menentukan cabang mana yang akan diambil.

Prosesor modern diberi clock: Setiap operasi membutuhkan sejumlah siklus clock yang tidak terpisahkan. Perancang prosesor menentukan panjang siklus jam. Ada dua pertimbangan di sana: Satu, kecepatan perangkat keras, misalnya diukur sebagai penundaan satu gerbang NAND. Ini tergantung pada teknologi yang digunakan, dan pada pengorbanan seperti kecepatan vs penggunaan daya. Tidak tergantung pada desain prosesor. Dua, perancang memutuskan bahwa panjang siklus clock sama dengan n penundaan satu gerbang NAND, di mana n mungkin 10, atau 30, atau nilai lainnya.

Pilihan ini dan membatasi seberapa rumit operasi yang dapat diproses dalam satu siklus. Akan ada operasi yang dapat dilakukan dalam 16 tetapi tidak dalam 15 penundaan NAND. Jadi memilih n = 16 berarti operasi seperti itu dapat dilakukan dalam satu siklus, memilih n = 15 berarti itu tidak dapat dilakukan.

Para desainer akan memilih dan sehingga banyak operasi penting dapat dilakukan dalam satu, atau mungkin dua atau tiga siklus. n akan dipilih secara lokal optimal: Jika Anda mengganti n dengan n-1, maka sebagian besar operasi akan sedikit lebih cepat, tetapi beberapa (yang benar-benar membutuhkan penundaan penuh n NAND) akan lebih lambat. Jika beberapa operasi akan melambat, sehingga pelaksanaan program secara keseluruhan rata-rata lebih cepat, maka Anda akan memilih n-1. Anda juga bisa memilih n +1. Itu membuat sebagian besar operasi sedikit lebih lambat, tetapi jika Anda memiliki banyak operasi yang tidak dapat dilakukan dalam n penundaan tetapi dapat dilakukan dalam penundaan n + 1 maka itu akan membuat prosesor secara keseluruhan lebih cepat.

Sekarang pertanyaan Anda: Tambah dan kurangi adalah operasi yang sangat umum sehingga Anda ingin dapat menjalankannya dalam satu siklus. Akibatnya, tidak masalah bahwa AND, ATAU dll. Dapat mengeksekusi lebih cepat: Mereka masih membutuhkan satu siklus itu. Tentu saja unit "menghitung" DAN, ATAU dll memiliki banyak waktu untuk mengutak-atik ibu jarinya, tetapi itu tidak dapat membantu.

Perhatikan bahwa ini bukan hanya apakah operasi dapat dilakukan dalam n NAND-keterlambatan atau tidak: Tambahan misalnya dapat dibuat lebih cepat dengan menjadi sedikit pintar, masih lebih cepat dengan menjadi sangat pintar, masih sedikit lebih cepat dengan menginvestasikan jumlah perangkat keras yang luar biasa , dan akhirnya sebuah prosesor dapat memiliki campuran sirkuit yang sangat cepat sangat mahal dan sedikit lebih lambat dan lebih murah, sehingga ada kemungkinan untuk membuat satu operasi cukup cepat dengan menghabiskan lebih banyak uang untuk itu.

Sekarang Anda dapat membuat kecepatan clock sangat tinggi / siklus sangat singkat sehingga hanya operasi bit sederhana yang dijalankan dalam satu siklus dan yang lainnya dalam dua atau lebih. Itu kemungkinan besar akan memperlambat prosesor. Untuk operasi yang membutuhkan dua siklus, biasanya ada overhead untuk memindahkan instruksi yang tidak lengkap dari satu siklus ke siklus berikutnya, jadi dua siklus tidak berarti Anda memiliki waktu dua kali lebih banyak untuk dieksekusi. Jadi untuk melakukan penambahan dalam dua siklus, Anda tidak bisa menggandakan kecepatan jam.

Izinkan saya memperbaiki beberapa hal yang tidak disebutkan dengan jelas dalam jawaban Anda yang ada:

Saya tahu bahwa operasi bitwise sangat cepat pada prosesor modern, karena mereka dapat beroperasi pada 32 atau 64 bit secara paralel,

Ini benar. Memberi label CPU sebagai bit "XX" biasanya (tidak selalu) berarti bahwa sebagian besar struktur umumnya (lebar register, RAM yang dapat dialamatkan dll.) Berukuran XX bit (sering "+/- 1" atau semacamnya). Tetapi sehubungan dengan pertanyaan Anda, Anda dapat dengan aman berasumsi bahwa CPU dengan 32 bit atau 64 bit akan melakukan operasi bit dasar pada 32 atau 64 bit dalam waktu konstan.

jadi operasi bitwise hanya membutuhkan satu siklus clock.

Kesimpulan ini belum tentu demikian. Terutama CPU dengan set instruksi yang kaya (google CISC vs RISC) dapat dengan mudah mengambil lebih dari satu siklus bahkan untuk perintah sederhana. Dengan interleaving, bahkan perintah simples mungkin terurai menjadi fetch-exec-store dengan 3 jam (sebagai contoh).

Namun penambahan adalah operasi yang kompleks

Tidak, penambahan bilangan bulat adalah operasi sederhana; pengurangan juga. Sangat mudah untuk mengimplementasikan adders dalam perangkat keras penuh, dan mereka melakukan pekerjaan mereka dengan seketika seperti operasi bit dasar.

yang terdiri dari setidaknya satu dan mungkin hingga selusin operasi bitwise, jadi saya pikir itu akan 3-4 kali lebih lambat.

Ini akan memakan 3-4 kali lebih banyak transistor, tetapi dibandingkan dengan gambaran besar yang dapat diabaikan.

Saya terkejut melihat setelah tolok ukur sederhana bahwa penambahan persis sama cepatnya dengan operasi bitwise mana pun (XOR, OR, DAN dll). Adakah yang bisa menjelaskan ini?

Ya: penambahan integer adalah operasi bitwise (dengan beberapa bit lebih banyak dari yang lain, tetapi masih). Tidak perlu melakukan apa pun secara bertahap, tidak perlu algoritma rumit, jam atau apa pun.

Jika Anda ingin menambahkan lebih banyak bit daripada arsitektur CPU Anda, Anda akan dikenakan penalti karena harus melakukannya secara bertahap. Tapi ini pada tingkat kompleksitas yang lain (level bahasa pemrograman, bukan level assembly / kode mesin). Ini adalah masalah umum di masa lalu (atau hari ini pada CPU tertanam kecil). Untuk PC, dll., 32 atau 64 bitnya cukup untuk tipe data yang paling umum agar mulai menjadi titik diperdebatkan.