Mengapa pembagian perangkat keras membutuhkan waktu lebih lama daripada perkalian?

Mengapa pembagian perangkat keras memakan waktu lebih lama daripada multiplikasi pada mikrokontroler? Misalnya, pada dsPIC, sebuah divisi membutuhkan 19 siklus, sedangkan multiplikasi hanya membutuhkan satu siklus clock.

Saya telah melalui beberapa tutorial, termasuk algoritma Division dan algoritma Multiplication di Wikipedia. Ini alasan saya.

Algoritma pembagian, seperti metode pembagian lambat dengan memulihkan di Wikipedia, adalah algoritma rekursif. Ini berarti bahwa (perantara) hasil dari langkah kdigunakan sebagai input ke langkah k+1, yang berarti bahwa algoritma ini tidak dapat diparalelkan. Oleh karena itu, dibutuhkan setidaknya nsiklus untuk menyelesaikan pembagian, sedangkan nsejumlah bit dalam dividen. Untuk dividen 16-bit, ini sama dengan setidaknya 16 siklus.

Algoritma multiplikasi tidak perlu bersifat rekursif, yang artinya dimungkinkan untuk memparalelkannya. Namun, ada banyak algoritma multiplikasi yang berbeda, dan saya tidak memiliki petunjuk yang mana yang dapat digunakan oleh mikrokontroler. Bagaimana cara kerja multiplikasi pada perangkat keras / mikrokontroler?

Saya telah menemukan algoritma pengali Dadda , yang seharusnya hanya membutuhkan satu siklus clock untuk menyelesaikannya. Namun, yang tidak saya dapatkan di sini adalah bahwa algoritma Dadda menghasilkan dalam tiga langkah, sedangkan hasil dari langkah 1 digunakan pada langkah 2, dll. Menurut ini, ini akan memakan waktu setidaknya tiga siklus jam untuk menyelesaikannya.

Sebuah pembagi memetakan jauh lebih tidak elegan ke perangkat keras biasa. Ambil Lattice ICE40 FPGAs sebagai contoh.

Mari kita bandingkan dua kasing: pengganda 8x8 bit hingga 16 bit ini:

module multiply (clk, a, b, result);
   input clk;
   input [7:0]a;
   input [7:0]b;
   output [15:0]result;
   always @(posedge clk)
     result = a * b;
endmodule // multiply

dan pembagi ini yang mengurangi operan 8 dan 8 bit menjadi 8 bit:

module divide(clk, a, b, result);
   input clk;
   input [7:0] a;
   input [7:0] b;
   output [7:0] result;
   always @(posedge clk)
     result = a / b;
endmodule // divide

(Ya, saya tahu, jamnya tidak melakukan apa - apa)

Gambaran umum dari skema yang dihasilkan saat memetakan pengali ke ICE40 FPGA dapat ditemukan di sini dan pembagi di sini .

Statistik sintesis dari Yosys adalah:

berkembang biak

• Jumlah kabel: 155
• Jumlah bit kawat: 214
• Jumlah kabel publik: 4
• Jumlah bit kawat publik: 33
• Jumlah kenangan: 0
• Jumlah bit memori: 0
• Jumlah proses: 0
• Jumlah sel: 191
  • SB_CARRY 10
  • SB_DFF 16
  • SB_LUT4 165

membagi

• Jumlah kabel: 145
• Jumlah bit kawat: 320
• Jumlah kabel publik: 4
• Jumlah bit kawat publik: 25
• Jumlah kenangan: 0
• Jumlah bit memori: 0
• Jumlah proses: 0
• Jumlah sel: 219
  • SB_CARRY 85
  • SB_DFF 8
  • SB_LUT4 126

Perlu dicatat bahwa ukuran Verilog yang dihasilkan untuk pengali lebar penuh dan pembagi pembagi maksimal tidak terlalu ekstrem. Namun, jika Anda melihat gambar-gambar di bawah ini, Anda akan melihat bahwa pengali mungkin memiliki kedalaman 15, sedangkan pembagi lebih mirip 50 atau lebih; jalur kritis (yaitu jalur terpanjang yang dapat terjadi selama operasi) adalah apa yang menentukan kecepatan!

Anda tidak akan bisa membaca ini, untuk mendapatkan kesan visual. Saya pikir perbedaan dalam kompleksitas mungkin dikenali. Ini adalah pengali / pembagi siklus tunggal!

Berkembang biak

Lipat gandakan pada ICE40 (peringatan: ~ gambar 100 Mpixel)

Membagi

( Bagilah pada ICE40 ) (peringatan: ~ gambar 100 Mpixel)

Pembagian lambat secara inheren berulang sehingga cenderung memakan waktu lebih lama. Ada algoritma pembagian lambat agak lebih cepat daripada yang sederhana, menggunakan tabel pencarian. Algoritma SRT menghasilkan dua bit per siklus. Kesalahan dalam tabel seperti itu adalah penyebab bug PentIV FDIV yang terkenal (sekitar 1994). Lalu ada yang disebut algoritma pembagian cepat.

Tentu saja, pada prinsipnya, Anda cukup menggunakan tabel pencarian besar untuk menghitung produk atau hasil bagi dari dua angka, dan dengan demikian mendapatkan hasil dalam satu siklus tunggal, tetapi itu cenderung dengan cepat menjadi tidak praktis karena jumlah bit per angka meningkat.

Kita dapat memiliki beberapa lapisan logika per siklus clock tetapi ada batasnya, persis berapa banyak layer logika yang dapat kita miliki, seberapa kompleks lapisan tersebut dapat bergantung pada kecepatan clock dan proses semikonduktor kami.

Namun, ada banyak algoritma multiplikasi yang berbeda, dan saya tidak memiliki petunjuk yang mana yang dapat digunakan oleh mikrokontroler

Afaict sebagian besar perkalian di komputer menggunakan varian perkalian panjang biner. Penggandaan panjang biner melibatkan

• Mengubah satu operan dengan berbagai jumlah yang berbeda
• Menyembunyikan angka yang digeser berdasarkan operan kedua
• Menambahkan hasil masking bersama.

Jadi mari kita lihat mengimplementasikan ini dalam perangkat keras.

• Menggeser hanyalah masalah bagaimana kita menghubungkan semuanya, jadi itu gratis.
• Masking membutuhkan gerbang AND. Itu berarti satu lapisan logika, jadi dari sudut pandang waktu itu murah.
• Tambahannya relatif mahal karena kebutuhan untuk membawa rantai. Untungnya ada trik yang bisa kita gunakan. Untuk sebagian besar tahap penambahan daripada menambahkan dua angka untuk menghasilkan satu, kita dapat menambahkan tiga angka untuk menghasilkan dua.

Jadi mari kita masukkan berapa banyak tahapan logika yang kita butuhkan untuk pengganda 8x8 dengan hasil 16 bit. Untuk kesederhanaan mari kita asumsikan kita tidak mencoba dan mengoptimalkan karena fakta bahwa tidak semua hasil antara memiliki bit di semua posisi.

Mari kita asumsikan bahwa penambah penuh diimplementasikan dalam dua "tahap gerbang".

• 1 untuk masking untuk menghasilkan 8 hasil antara.
• 2 untuk menambah grup dari tiga angka untuk mengurangi 8 hasil antara menjadi 6
• 2 untuk menambah grup dari tiga angka untuk mengurangi 6 hasil antara menjadi 4
• 2 untuk menambahkan kelompok tiga angka untuk mengurangi 4 hasil antara menjadi 3
• 2 untuk menambahkan kelompok tiga angka untuk mengurangi 3 hasil antara menjadi 2
• 32 untuk menjumlahkan dua hasil akhir.

Jadi sekitar 46 tahapan logika total. Sebagian besar dari yang dihabiskan menambahkan hingga dua hasil menengah terakhir.

Ini dapat ditingkatkan lebih lanjut dengan mengeksploitasi fakta bahwa tidak semua hasil antara memiliki semua bit yang hadir (yang pada dasarnya adalah apa yang dilakukan pengganda dada), dengan menggunakan carry lookahead adder untuk langkah terakhir. Dengan menambahkan 7 angka untuk menghasilkan 3 bukannya tiga untuk menghasilkan dua (mengurangi jumlah tahap dengan harga lebih banyak gerbang dan gerbang yang lebih luas) dll.

Itu semua detail kecil, poin penting adalah bahwa jumlah tahapan yang diperlukan untuk mengalikan dua bilangan n bit dan menghasilkan hasil 2n bit kira-kira sebanding dengan n.

Di sisi lain jika kita melihat algoritma pembagian kita menemukan mereka semua memiliki proses berulang di mana.

1. Apa yang dilakukan pada satu iterasi tergantung pada hasil iterasi sebelumnya.
2. jumlah tahapan logika yang diperlukan untuk mengimplementasikan iterasi kira-kira sebanding dengan n (pengurangan dan perbandingan sangat mirip dalam kerumitan dengan penambahan)
3. jumlah iterasi juga kira-kira sebanding dengan n.

Jadi jumlah tahapan logika yang diperlukan untuk mengimplementasikan divisi kira-kira sebanding dengan n kuadrat.

Algoritma pembagian (sebenarnya algoritma apa pun) dapat dibuat dalam satu siklus clock. Jika Anda bersedia membayar untuk transistor tambahan dan tarif clock yang diizinkan lebih rendah.

Misalkan Anda memiliki satu set gerbang yang mengimplementasikan satu siklus clock dari algoritma pembagian multi-siklus yang ada. Untuk membuat algoritma siklus tunggal, gunakan beberapa tahap perangkat keras (mirip dengan yang digunakan dalam satu tahap algoritma multi-siklus), dengan output dari satu tahap memberi makan tahap berikutnya.

Tentu saja alasan untuk tidak melakukannya dengan cara itu adalah karena menggunakan banyak transistor. Misalnya untuk divisi 16 bit mungkin menggunakan hampir 16 X lebih banyak transistor. Juga memiliki lebih banyak tahap gerbang menurunkan frekuensi clock maksimum yang diizinkan (karena ada lebih banyak tahap penundaan propagasi).

Algoritma pembagian praktis semua didasarkan pada suite numerik yang menyatu dengan hasil bagi.

• Ada metode aditif, seperti non-restore atau SRT yang bekerja dengan menambahkan atau menghapus 2 ^ N ke hasil bagi dan secara bersamaan menambah atau menghapus 2 ^ N * Pembagi ke sisa parsial sampai telah terkonvergensi ke nol.

• Ada metode multiplikasi, seperti Newton-Raphson atau Goldshmidth, yang merupakan metode pencarian root di mana divisi dihitung sebagai kebalikan dari perkalian.

Metode aditif memberikan satu atau beberapa bit per siklus. Metode multiplikasi menggandakan jumlah bit untuk setiap siklus tetapi membutuhkan beberapa perkiraan awal, sering diperoleh dengan tabel konstan.

Denominasi "lambat" dan "cepat" menyesatkan, karena kecepatan sebenarnya tergantung pada jumlah bit, berapa banyak perangkat keras yang dikhususkan untuk fungsi (dan pengganda cepat sangat besar) ...

Divisi lebih lambat daripada perkalian karena tidak ada metode paralel langsung untuk menghitungnya: Entah ada iterasi, atau perangkat keras disalin untuk mengimplementasikan iterasi sebagai blok bertingkat (atau pipeline).

Mengapa pembagian perangkat keras memakan waktu lebih lama daripada multiplikasi pada mikrokontroler?

Ini bukan pertanyaan elektronik. Paling-paling itu adalah pertanyaan komputer, lebih baik ditujukan ke Stack Overflow.

Lihat, misalnya, di sini: Apakah multiplikasi lebih cepat daripada pembagian float?

Pada kenyataannya, ini adalah pertanyaan di Kehidupan Nyata: Mengapa pembagian membutuhkan waktu lebih lama daripada multiplikasi?

Mana yang ingin Anda hitung di atas kertas?

51 * 82

atau

4182 / 51

Pembagian membutuhkan waktu lebih lama daripada perkalian karena lebih sulit dilakukan .