Pekerjaan rumah aritmatika

Lyoshenka, Lyoshenka, bantu aku!
Belajar, Alyoshenka, tabel perkalian!
Agnia Barto


Tugas pertama untuk siswa kelas satu. Beberapa angka positif diberikan. Anda perlu mengalikannya dengan nomor lain, tidak diketahui sebelumnya. Pertanyaannya adalah, bagaimana para bangsawan don menyarankan untuk melakukan ini ??? Pengembang yang berpengalaman pasti akan mengatakan, kata mereka manusia, letakkan pengganda dan jangan khawatirkan otak saya. Dan mungkin itu salah secara fundamental! Karena selain monster dari Alterra dan Xilinx, ada juga keluarga yang luar biasa seperti iCE-40 dari Lattice . Mengkonsumsi sangat mikro. Sangat murah Ya, masalahnya adalah, mereka sangat kecil, dan sayangnya, tidak ada pengganda di sana. Saya menemukan ini sekitar 4 tahun yang lalu ketika saya porting codec ADPCM tertentu dari assembler adsp-2185 ke kristal seperti itu.

Tidak, tanpa pengganda tujuan umum (untuk dua variabel) tentu saja tidak bisa dilakukan. Saya harus membuatnya dengan pena dan dia mengambil setengah kristal. Masalahnya adalah dia mengirik dalam setiap langkah saya, yaitu tidak ada jendela sama sekali. Dan selain penggandaan variabel dalam algoritma ada koefisien tetap, yang juga harus dikalikan. Dan tidak ada cara untuk menggunakan pengganda untuk ini, tidak ada jendela yang tersisa. Dan karena perjuangan dalam proyek melewati setiap sel, tentu saja saya sangat tertarik dengan cara menghindar, dan menggunakan properti dari koefisien ini membuat skema optimal untuk mengalikannya (bukan pengali tujuan umum, tetapi alat pengali dengan nomor tertentu!). Yah, seperti mimpi yang lengkap menjadi kenyataan - sehingga skema perkalian dengan koefisien yang berbeda memanfaatkan sebagian besar sumber daya kristal yang sama.

Jadi, dari tugas untuk siswa kelas satu, kami dengan lancar beralih ke tugas untuk insinyur dan ahli matematika. Bagaimana cara membangun skema penggandaan yang optimal untuk nomor tertentu?

Mari kita ingat sedikit bagaimana kita secara umum mengalikan angka A dengan B.

1. Untuk mulai dengan, atur hasilnya ke nol.
2. Mari kita bahas bit A.
3. Jika dalam debit 0, kami tidak melakukan apa pun.
4. Jika dalam bit 1, kami menggeser B dengan jumlah bit yang sesuai dan menambah hasilnya.

Total, semakin sedikit unit A dalam digit, semakin mudah untuk mengalikannya. Mengalikan dengan 2, 4 atau 8 itu mudah. Hanya dibutuhkan pergeseran. Agak sulit untuk mengalikannya dengan 3, 5 atau 10. Dibutuhkan satu tambahan. Semakin sulit untuk dikalikan dengan 11. Semakin banyak unit, semakin sulit.

Nah, bagaimana dengan mengalikannya dengan 255? Sebanyak 8 unit, tugas mimpi buruk, kan? Dan inilah patung-patungnya! Mari kita membuat tipuan yang sulit dengan telinga kita. Lipat gandakan B kita dengan 256 (mis., Geser dengan 8 digit) dan kurangi dari hasilnya. Ternyata meskipun terlihat tangguh, mengalikan dengan 255 semudah mengalikan dengan 10. Mudah untuk mengalikan dengan 254, dan dengan 240, dan dengan 224 (jika Anda mau, periksa!).

Secara total, pengurangan membantu perkalian. Ingat pemikiran berharga ini. Sementara itu, kami menyebut kesulitan angka sebagai jumlah minimum operasi penambahan (atau pengurangan) yang diperlukan untuk dikalikan dengannya. Pergeseran tidak diperhitungkan. Karena dalam konteks masalah (kami memiliki sirkuit, bukan pemrograman!) Mereka diperoleh secara gratis. Mari kita merumuskan satu pernyataan yang jelas namun bermanfaat:

Kesulitan angka kurang dari atau sama dengan jumlah unit dalam notasi binernya.
Bahkan, jika kita dengan jujur ​​mengalikan tanpa trik pengurangan, seperti yang kita ajarkan di sekolah, jumlah penambahan akan sama dengan jumlah unit dalam biner A. Dan jika kita mulai menipu dan selain itu, kita beruntung, maka kita akan mengurangi jumlah operasi.

Konsekuensi yang menarik dari pernyataan ini:
Kesulitan dari setiap nomor n-bit selalu benar-benar kurang dari n .
Setelah semua, jumlah unit terbesar dalam angka n- digit adalah n , untuk angka seperti 255. Di sisi lain, jelas bahwa fokus, seperti mengalikan dengan 255, kita dapat mengulangi untuk jumlah kapasitas apa pun. Ini membuka prospek untuk mengoptimalkan pengganda tujuan umum.

Mari kita berikan alasan kita tampilan yang lebih teratur. Untuk memulainya, mari kita sudah memiliki semacam skema multiplikasi oleh A. Kami mengambil sebagai unit. Kemudian semua istilah bergerak, tambahkan dan kurangi sedemikian rupa sehingga hasilnya adalah A. yang sama Secara total, skema perkalian kami dengan A tidak lebih dari representasi dari angka A dalam bentuk jumlah kekuatan dua di mana istilahnya dapat berupa tanda + dan dengan tanda - . Dan Anda dapat mengelompokkan istilah positif dan negatif, dan mengatakan bahwa skema tersebut dijelaskan oleh perbedaan beberapa angka A + dan A- , sama dengan A. Ini buruk ... Anggota perbedaannya bisa sangat besar. Mari kita pikirkan apakah ada pertimbangan untuk membatasi mereka?
Pertama-tama, kami perhatikan bahwa masing-masing kekuatan dua dapat memasuki sirkuit hanya sekali. Bahkan, jika dia masuk dua kali dengan tanda yang sama, ini bisa digantikan oleh kekuatan dua oleh unit yang lebih besar. Jika dia masuk dua kali dengan tanda yang berbeda, mereka akan saling dikurangkan. Secara total, skema ini sangat mirip dengan representasi biner A. Satu-satunya perbedaan adalah bahwa "bit" -nya (selanjutnya kita akan menyebutnya trit ) dapat mengambil bukan dua, tetapi tiga nilai: 1, 0 dan -1.

Total Jika A adalah bilangan biner n- bit, skema penggandaannya dijelaskan dengan jumlah:

$$

$$A = {t_m} 2 ^ m + {t_ {m-1}} 2 ^ {m-1} + .... + {t_1} 2 + {t_0}$$

dimana $$${t_i}$- trit, mengambil nilai 1, 0 dan -1, dan m adalah angka yang tidak diketahui.

Dalam apa yang berikut, kita akan menyebut ungkapan semacam itu skema terner atau sekadar skema atau skema multiplikasi untuk nomor A.

Ayo coba cari m . Seperti dapat dilihat dari contoh dengan perkalian dengan 255, m sama sekali tidak kurang dari n . Mari kita lihat apakah itu bisa sama dengan n +1 .
Biarkan A, seperti sebelumnya, menjadi angka positif n- digit. Kemudian skema multiplikasi didefinisikan sebagai:

$$

$$A = {t_ {n + 1}} 2 ^ {n + 1} + {t_ {n}} 2 ^ {n} + {t_ {n-1}} 2 ^ {n-1} .... + {t_1} 2 + {t_0}$$

Ingat itu $$$2 ^ k + 2 ^ {k-1} + .... + 2 + 1 = 2 ^ {k + 1} -1$
Oleh karena itu, trit teratas tidak boleh sama dengan -1. Memang, bahkan jika yang lainnya adalah 1, jumlahnya masih tetap -1. Dan dengan kondisi A positif. Sekarang biarlah trit teratas menjadi 1. Tetapi dalam kasus ini, trit berikutnya harus -1. Kalau tidak, jumlahnya akan terlalu besar. Bahkan, jika trit berikutnya adalah 0, jumlahnya akan tidak kurang dari $$$2 ^ {n + 1} - (2 ^ {n-1} + ... + 1) = 2 ^ {n + 1} - (2 ^ n - 1) = 2 ^ n + 1$
Sementara n- bit A tidak lebih $$$2 ^ n - 1$. Tetapi jika trit teratas adalah 1, dan -1 berikutnya, maka jumlah dari dua anggota teratas adalah $$$2 ^ {n + 1} -2 ^ n = 2 ^ n$. Jadi trit teratas adalah 0.

Dengan demikian, pernyataan penting terbukti: m = n .

Dengan kata lain, untuk mewakili skema perkalian dengan n- bit A , n + 1 dari dua sudah cukup - dari 0 hingga n (satu lebih dari representasi biner), yang segera menyelamatkan kita dari ketakberhinggaan.

Sekarang Anda dapat mencoba menghitung kesulitan (lihat di atas) dari angka tertentu. Hal paling sederhana adalah melakukan apa yang kita lakukan dengan menulis angka biner secara berurutan. Hanya pertama, kami tidak memiliki bit di sini tetapi basi (tiga nilai yang mungkin), kedua, beberapa kombinasi baki memberikan angka negatif dan mereka harus dibuang, ketiga, beberapa kombinasi dapat memberikan angka bertepatan. Ini berarti bahwa untuk nomor tersebut ada beberapa skema.

Kami akan menulis dengan python. Bukan karena aku penggemar dia, tapi karena sangat nyaman bekerja dengannya di notebook jupyter. Sebagai permulaan, kita menulis kelas TriScheme yang berfungsi dengan skema ternary yang diperkenalkan di atas, fungsi allSchemes, yang menghitung semua skema untuk jumlah ukuran bit tertentu dengan penghitungan sederhana, dan fungsi printSchemes yang mencetak hasilnya:


Kami menghitung skema untuk semua angka 4-bit:

0 0 1 [00000]
1 1 5 [0000+, 000 + -, 00 + -, 0 + ---, + ----]
2 1 4 [000 + 0, 00 + -0, 0 + - 0, + --- 0]
3 2 7 [000 ++, 00 + - +, 00 + 0-, 0 + - +, 0 + -0-, + --- +, + - 0-]
4 1 3 [00 + 00, 0 + -00, + - 00]
5 2 8 [00 + 0 +, 00 ++ -, 0 + -0 +, 0 + - + -, 0 + 0--, + - 0+, + - + -, + -0--]
6 2 5 [00 ++ 0, 0 + - + 0, 0 + 0-0, + - + 0, + -0-0]
7 2 7 [00 +++, 0 + - ++, 0 + 0- +, 0 + 00-, + - ++, + -0- +, + -00-]
8 1 2 [0 + 000, + -000]
9 2 7 [0 + 00 +, 0 + 0 + -, 0 ++ -, + -00 +, + -0 + -, + - + -, +0 ---]
10 2 5 [0 + 0 + 0, 0 ++ - 0, + -0 + 0, + - + - 0, + 0-0]
11 3 8 [0 + 0 ++, 0 ++ - +, 0 ++ 0-, + -0 ++, + - + - +, + - + 0-, +0 - +, + 0-0 -]
12 2 3 [0 ++ 00, + - + 00, + 0-00]
13 3 7 [0 ++ 0 +, 0 +++ -, + - + 0+, + - ++ -, + 0-0 +, +0 - + -, + 00--]
14 2 4 [0 +++ 0, + - ++ 0, + 0- + 0, + 00-0]
15 2 5 [0 ++++, + - +++, +0 - ++, + 00- +, + 000-]

Di sini, di awal baris adalah angka, diikuti oleh kesulitannya (jumlah minimum elemen bukan nol dalam skema), kemudian jumlah skema, dan akhirnya daftar skema.

Dalam skema, + adalah singkatan dari 1, 0 - 0, dan - - -1. Trit tertua di sebelah kiri (seperti dalam ejaan angka biasa).

Tabel menunjukkan, pertama, bahwa hanya angka 13 dan 11 yang memiliki kesulitan 3 (maksimum untuk angka 4-bit, seperti yang dibuktikan di atas). Dan kedua, bahwa jumlah skema yang berbeda untuk setiap angka cukup besar. Ini menunjukkan, pertama, bahwa perkalian adalah yang paling sering operasinya jauh lebih sederhana daripada yang diajarkan di sekolah. Dan kedua, bahwa untuk implementasi perangkat untuk dikalikan oleh beberapa konstanta menggunakan sumber daya kristal umum, pilihan sirkuit cukup besar. Yang lebih menarik adalah data angka yang lebih panjang. Jadi untuk angka 14-bit, kesulitan maksimum adalah 8. Dan jumlah maksimum sirkuit adalah 937.

Semuanya akan baik-baik saja, tetapi algoritma di atas terlalu mahal. Kompleksitasnya tumbuh sebagai $$$3 ^ n$tergantung pada panjang angka n . Untuk 8 digit dihitung secara instan. Selama 14 - menit. Selama 16 jam. Jika Anda perlu membaca sirkuit UNTUK SEMUA angka n, bit, tidak ada yang bisa dilakukan selain menulis ulang ke C dan mengambil komputer yang lebih kuat. Namun, algoritma ini diparalelkan dengan sempurna dan tentunya dapat dijalankan pada GPU atau pada cluster.

Untuk merancang kelenjar tertentu, daftar skema untuk angka tertentu biasanya diperlukan. Dan SEMUA diinginkan, dan bukan hanya optimal. Untuk yang memilih tergantung pada keadaan (misalnya, perangkat untuk mengalikan dengan beberapa konstanta). Dan di sini Anda dapat menawarkan algoritma yang lebih manusiawi. Sekali lagi, kita mengingat kesetaraan yang luar biasa: $$$2 ^ k + 2 ^ {k-1} + .... + 2 + 1 = 2 ^ {k + 1} -1$.

Dalam konteks tugas, ini berarti yang berikut. Misalkan beberapa skema trit senior diketahui. Semua trit minor mulai dari posisi k tidak diketahui dan sebelumnya dianggap sama dengan nol. Kemudian mengubah trit yang tidak dikenal dengan cara apa pun, kami akan mengubah nilai sirkuit dengan tidak lebih dari plus / minus $$$2 ^ {k + 1} -1$. Terlebih lagi, dengan kemajuan ke trits yang lebih rendah, nilai ketidakpastian ini berkurang. Ini memungkinkan Anda untuk mencari skema dengan perkiraan berturut-turut, trit demi trit.

Biarkan angka positif A diberikan. Kita perlu menemukan semua skema untuk itu di antara nomor n- bit. Nilai absolut dari perbedaan antara A dan nilai sirkuit tertentu disebut kesalahan sirkuit. Untuk memulainya, kita mengambil skema n + 1- bit yang menggambarkan angka n- bit, yang semuanya tidak diketahui dan pada awalnya diset sama dengan nol. Dan mari kita mulai mendefinisikan trit, satu per satu, dimulai dengan yang lama. Dalam posisi k- th, sirkuit dapat menghasilkan tiga pola baru - dengan nilai-nilai trit 1, 0 dan -1. Kami meninggalkan dalam daftar skema untuk kelanjutan hanya mereka yang kesalahannya tidak melebihi $$$2 ^ k-1$. Dengan daftar sirkuit yang dihasilkan, mari beralih ke langkah di posisi k-1 . Dengan demikian, dalam daftar yang dihasilkan (pada posisi 0) akan ada SEMUA skema yang mungkin yang nilainya A. Mari kita menulis fungsi calcSchemes.


Dan akhirnya, penjualan mimpi yang dijanjikan.

Dalam proyek itu, ada dua koefisien yang perlu dikalikan: 16351 dan 16318. Menggunakan calcSchemes, kami menemukan skema untuk koefisien ini:


Kita beruntung! Kedua faktor mengalami kesulitan 3. Kami memilih skema optimal untuk keduanya:
Untuk 16318 + 0000000-0000-0 dan untuk 16351 - + 00000000-0000- . Kami beruntung lagi! Perhatikan bagian ujung skema. Mereka untuk 16318 dan 16351 hanya berbeda dengan pergeseran kiri dengan satu posisi. Jadi perangkat mengalikan oleh 16318 dan 16351, hanya mencakup satu multiplexer tambahan, mengganti operan yang bergeser dan tidak bergeser pada input dari penambah.

Mari kita lihat hasilnya. Kami menulis di Veril tiga opsi untuk perangkat perkalian oleh 16318 dan 16351:

1. Opsi "Sekolah" (hanya tambahan dan shift)
2. Sirkuit optimal
3. Skema optimal menggunakan sumber daya bersama

Untuk ketiga opsi, kami melakukan sintesis, dan melihat berapa banyak sumber daya kristal akan dihabiskan untuk masing-masing.


Ketiga opsi bekerja dengan benar, mengalikan pada 0 pada input dengan 16318, dan pada 1 pada 16351. Pada saat yang sama, yosys memberikan 488 sel untuk versi sekolah, 206 untuk versi optimal, dan 202 untuk varian dengan sumber daya bersama. itu mengoptimalkan, meskipun masih ada perbedaan dalam 4 sel. Seperti yang Anda lihat, perbedaan dengan opsi sekolah sangat layak.

Ya akhirnya. Mungkin, tampaknya tidak perlu bagi seseorang untuk memagari taman semacam itu, hanya untuk sekadar menyadari bahwa 16318 = 16384-64-2, dan 16351 = 16384-32-1. Namun, pertama-tama, jumlahnya bisa lebih rumit. Kedua, jika perangkat harus mengalikan beberapa angka, jauh dari jelas bahwa skema optimal harus diambil. Saya hanya beruntung dalam proyek itu. Secara umum, program pencarian rangkaian dapat banyak membantu. Semoga artikel ini bermanfaat bagi seseorang. Dan orang yang membacanya, saya harap tidak akan panik jika Anda perlu mengalikan, tetapi tidak ada pengali.