Kami mendapat kesempatan untuk melakukan latihan taktis kecil tapi sangat menarik
Dalam proses meneliti MK baru dari perusahaan terkenal berdasarkan arsitektur Cortex-M4 (saya pasti akan menulis tentang ini nanti), muncul pertanyaan tentang seberapa cepat operasi divisi integer dalam implementasi perangkat keras dapat bekerja. Eksperimen skala penuh memberikan hasil yang agak tak terduga: membagi angka 32-bit dengan angka 32-bit dilakukan selama 3 jam siklus frekuensi prosesor - yah, tidak peduli seberapa cepat itu. Ternyata ini hanya terjadi pada operan tertentu, tetapi studi lebih lanjut menunjukkan bahwa waktu yang diperlukan untuk menyelesaikan divisi tidak pernah melebihi 7 ukuran. Hasil yang diperoleh menyebabkan sedikit terburu-buru ("dan ini bukan kiasan tertentu, yang tidak tahu apa artinya, tetapi kata kerja yang sangat spesifik" - Divov, seperti biasa, tidak ada bandingannya).
Ya, Anda tidak bisa hanya mengambil dan dengan cepat membagi nomor yang panjang, itu aneh seperti itu, tetapi faktanya adalah hal yang keras kepala. Saya membayangkan gambar bahwa Presiden Federasi Rusia memanggil saya kepadanya besok dan menetapkan tugas membuat MK tidak lebih buruk dari pada ARM (saya setuju bahwa gambar itu delusi, tetapi itu tidak terjadi di dunia), tetapi saya melihatnya bingung dan mengerti bahwa Saya tidak akan dapat membuat pembagian nomor seperti itu dalam waktu seperti itu, dan saya tidak akan memenuhi harapan yang dikenakan pada saya (well, pada kenyataannya, saya selalu dapat dengan diam-diam membeli lisensi dari ARM, dan berpura-pura bahwa saya menciptakan semuanya sendiri, banyak yang melakukannya, tetapi GDP mengharapkan sesuatu yang sama sekali berbeda dari saya, dan kemudian - saya bisa menipu itu, tetapi saya tidak mungkin melakukannya).
Dan saya sedih bahwa orang-orang di ARM jauh lebih pintar daripada saya, dan saya pergi mencari di Internet untuk melihat bagaimana mereka melakukannya. Saya tidak menemukan informasi mengenai waktu eksekusi di situs web ARM, di salah satu materi tentang STM32 diindikasikan bahwa divisi ini mengambil dari 2 hingga 7 siklus clock, yang sesuai dengan pengamatan, tetapi tidak ada informasi tentang bagaimana ini dilakukan.
Secara umum, Internet yang mahakuasa tidak banyak membantu, ada trik dengan pembagian dengan konstan, saya menulis tentang mereka di salah satu posting, tetapi kami memiliki situasi yang berbeda, ada algoritma Newton dan versi akselerasinya, tetapi ini jelas bukan masalahnya, ada algoritma yang didasarkan pada Transformasi Fourier, tetapi ini untuk jumlah yang sangat besar dan tidak mungkin diselesaikan dalam 7 siklus clock bahkan pada arsitektur ARM. Saya harus memikirkannya sendiri dan solusinya ditemukan, dan begitu sederhana dan jelas sehingga menjadi agak memalukan dari kenyataan bahwa ini tidak dilakukan segera setelah tugas dirumuskan.
Sebelum melihat keputusan saya, saya sarankan Anda mencari sendiri, dan kemudian membandingkan dengan milik saya, dan jika mereka berbeda, saya menunggu Anda di komentar.
Jadi, bagaimana kita dengan cepat (tidak lebih dari 7 siklus) membagi dua angka 32-bit untuk mendapatkan hasil 32-bit.
Untuk memulainya, kita ingat bagaimana pembagian dalam aritmatika biner umumnya dilakukan di
bentuk klasik. Algoritma ini cukup sederhana dan mudah - kami mengurangi pembagi dari dividen. Jika hasilnya non-negatif (kami membagi angka-angka yang tidak ditandatangani), kemudian membuat digit berikutnya dari hasil sama dengan satu dan menganggap hasilnya sebagai dividen berikutnya, jika tidak, bit hasil berikutnya adalah 0. Sebelum pengukuran berikutnya, kami membagi dua pembagi (menggesernya ke kanan, atau menggeser dividen ke kiri) dan mengurangi berat bit sebanyak 2 kali (dengan pergeseran serupa). Jadi, kita mendapatkan sedikit hasil dalam satu siklus clock dan seluruh operasi akan berlangsung 32 siklus clock. Masih ada perubahan awal dalam proses ini, tetapi itu tidak mempengaruhi penilaian situasi secara keseluruhan. Kami akan mempercepat, tapi bagaimana caranya?
Kami mencatat bahwa algoritma yang dihasilkan sangat menyerupai operasi ADC dengan perkiraan sekuensial dan mengingat bahwa ada metode konversi lain, jauh lebih cepat - konversi paralel. Bagaimana jika ...
Kami akan mengurangi dari pembagi tidak hanya dividen, tetapi dividen * 2 dan dividen * 3 (pada saat yang sama, pada tiga adders), maka kita akan mendapatkan tiga bit (tanda hasil) dari informasi, yang mengambil 4 nilai berbeda, sehingga Anda dapat mengekstrak 2 bit dari mereka sekaligus hasil. Selanjutnya, kami memperkirakan pendekatan serupa untuk 3.4.5 bit hasilnya.
Untuk mendapatkan 5 bit informasi per siklus, kita memerlukan 31 adders, di mana masing-masing operasi Dividend-Divisor * n (1-31) akan dilakukan, tanda-tanda hasil dilewatkan melalui encoder dan kami akan segera menerima 5 bit dari hasilnya. Kemudian kita menggeser dividen dengan 5 digit ke kiri dan ulangi sampai siap. Maka kita membutuhkan 32/5 = 6.4 => 7 langkah untuk menyelesaikan operasi.
Untuk pekerjaan, kita memerlukan 31 + x adders, sepertinya banyak, tetapi kita sudah memilikinya, karena kita memiliki operasi multiplikasi 32 * 32 per siklus, dan untuk mengimplementasikannya kita tidak dapat melakukannya tanpa 32 adders (well, saya pikir begitu ... ), sehingga kita sudah memiliki peralatan yang diperlukan, satu-satunya pertanyaan adalah membangun sirkuit kontrol dan tumpukan multiplexer untuk mewujudkan pergeseran cepat, tetapi ini sepenuhnya bisa dipecahkan.
Jadi tugas membagi dalam 7 langkah diselesaikan, pertanyaannya tetap - bagaimana kali ini dapat dikurangi, karena dalam MK yang dipelajari kurang dari 7. Solusi yang jelas adalah menentukan jumlah digit paling signifikan dari dividen (H) dan pembagi (3) pada tahap persiapan algoritma. akan segera menjadi jelas berapa banyak bit tinggi hasil bagi yang sama dengan nol, sehingga kita dapat melewati fase pertama atau beberapa algoritma. Misalnya, jika C <3, maka hasilnya langsung nol dan kami menyelesaikan operasi, pasti Anda bisa mendapatkan rumus untuk jumlah langkah, tapi saya sudah bosan.
Menariknya, operasi udiv hanya memberikan hasil bagi, meskipun sisanya jelas tetap di suatu tempat di dalam. Pada prinsipnya, tidak sulit untuk mendapatkannya dalam dua langkah, yang dilakukan dalam fragmen yang dipelajari dari kode mesin dengan mengeksekusi pseudo-code Divisible-Private * Divider, tetapi ini untuk 2 langkah, mengapa tidak segera memberikannya pada pasangan register - Saya tidak tahu jawabannya sebuah pertanyaan.
Secara umum, temui GDP, katakan padanya bahwa kami pasti akan melakukan pembagian di MK jika masih menarik baginya.
PS: Ngomong-ngomong, ketika saya sedang mencari KDPV (seperti yang Anda perhatikan, saya tidak menemukannya), saya perhatikan satu dengan tulisan yang terus terang salah, "Anda tidak boleh membaginya dengan nol." Saya harus mengatakan dengan pasti bahwa adalah mungkin untuk membagi dengan nol, tidak dapat dibagi. Tapi serius, dalam arsitektur yang berbeda mereka membaginya dengan nol secara berbeda, di x86 kita mendapatkan pengecualian (ini adalah kesalahan yang tak terlupakan 200), dalam beberapa kita mendapat dividen atau nol, tetapi saya belum pernah melihat bilangan bulat maksimum. Dalam ARM n / 0 = 0/0 dan ternyata 0.