"Siapa pun dapat menyelesaikan paradoks Gray dengan lumba-lumba, dan Anda mencoba melakukannya tanpa lumba-lumba. "
Sebenarnya, saya berencana untuk menghabiskan akhir pekan dengan cara yang sedikit berbeda, untuk pergi ke Copter Huck (bukan bahwa saya adalah penggemar copters, hanya untuk melihat apa yang orang-orang muda ciptakan, untuk hang out seperti itu), tetapi kakak perempuan itu dengan tegas menentangnya. Tentu saja, saya bersikeras (yaitu, saya terkekeh beberapa kali dan berkata, "Yah, mungkin ... itu akan menyenangkan, toh"), tetapi dia keras kepala, dan ketika istri saya memihaknya, tidak ada kemungkinan perjalanan. Baiklah, oke, "Saya tidak benar-benar menginginkannya," tetapi saya duduk sedikit di atas teka-teki lucu dari bidang pemrograman, yang saya pikirkan sendiri, yang saya laporkan.
(Catatan yang diperlukan - akhir pekan sebelumnya dimaksudkan, selalu seperti ini - menulis program memerlukan beberapa jam, menulis laporan tentang hal itu dan lima hari perjalanan dengan transportasi umum tidak selesai.)
Dalam posting baru-baru ini, penulis mempertimbangkan masalah percepatan (antara lain) perhitungan kurva Bezier (KB) pada MK dengan parameter yang relatif lemah. Sebenarnya, parameter ini berada pada level mainframe rata-rata tahun 70-an, tetapi pada saat ini dianggap jelas tidak cukup. Sebagai hasil dari tindakan tertentu, penulis berhasil mempercepat perhitungan, menurut pendapat saya, jelas tidak cukup, jadi saya memutuskan untuk menulis bagaimana ini harus dilakukan sebagai perkiraan pertama. Saya benar-benar tahu resep universal untuk menyelesaikan masalah dengan kecepatan - untuk mengambil MK dengan frekuensi yang lebih tinggi atau beralih ke keluarga lain, tetapi saya datang dari saat kami belajar bertahan dengan apa yang kami miliki, hanya karena tidak ada yang lain, dari kata itu sama sekali. Saat ini, pendekatan itu sudah ketinggalan zaman, tetapi bagi saya tampaknya tidak akan menarik bagi pembaca Habr modern.
Kami nyatakan masalahnya - kami ingin menghitung koordinat titik pada kurva Bezier yang ditentukan oleh titik ekstrim A dan B dan fokus imajiner C. secepat mungkin. Rumus untuk menghitung titik P pada kurva diberikan oleh
di mana T bervariasi dari 0 hingga 1 inklusif. (Di Wiki mereka menulis bahwa formula ini rahasia pada suatu waktu, itu aneh seperti itu, tetapi semuanya mungkin). Jelas bahwa kami tidak akan mengambilnya dalam bentuk yang kompleks, sebaliknya kami akan secara terpisah mencari koordinat X dan Y. Kami akan memperkirakan kerumitan perhitungan menggunakan rumus ini, hanya dengan menghitung jumlah tanda operasi aritmatika dalam ekspresi ini - 7 perkalian dan 5 penambahan (=> 7 * 5 + ) Ada kemungkinan bahwa kompiler yang baik (dan sekarang semua kompiler bagus dan akan mengoptimalkan dengan sempurna jika Anda tidak melarangnya secara eksplisit) akan mengurangi biaya menjadi 7 * 3+, meskipun akan lebih baik untuk membantunya dengan menghitung (1-T) terlebih dahulu. Secara umum, kompiler yang baik umumnya dapat bekerja dengan baik jika semua nilai dalam rumus diwakili oleh konstanta, tetapi kami menganggap bahwa semua nilai secara statis tidak terdefinisi.
Bagian Satu, Matematika
Kami memulai proses pengoptimalan, di mana kami memperluas tanda kurung dan mengelompokkan istilah di T (mungkin suatu hari kompiler akan dapat melakukan ini untuk kami, tetapi sejauh ini bagian dari pekerjaan ini ditugaskan untuk kecerdasan alami), mendapatkan
=> 5 * 5 +, yang jelas lebih baik dari nilai awal 7 * 5 +, tetapi relatif ditingkatkan 7 * 3 + masih harus dipertimbangkan.
Jika kita meluangkan waktu untuk menyelesaikan operasi penjumlahan sebagai satu, maka waktu untuk menyelesaikan perkalian akan tepat tidak kurang dari satu, sebagai aturan, lebih lama, tetapi berapa banyak tergantung pada implementasi MK (pertama menulis - pada arsitektur, tetapi ini tidak sepenuhnya benar). Ketika tidak ada pengganda perangkat keras pada kristal, waktu eksekusi penggandaan akan puluhan (30+) kali lebih besar dari satu, dan ketika itu hadir, itu akan beberapa kali (1-6). Oleh karena itu, kami yakin dapat percaya bahwa mengganti perkalian dengan penambahan memberikan keuntungan (dan sering signifikan) dalam waktu pelaksanaan hampir selalu. Baiklah, kami akan segera melihat bahwa transisi dari angka titik tetap ke titik mengambang (kami mengesampingkan bukti dari fakta ini) mengarah ke peningkatan waktu eksekusi sebesar 20+ kali untuk penambahan (penyelarasan sangat berpengaruh di sini), tetapi hanya sedikit peningkatan untuk penggandaan . Oleh karena itu, untuk angka floating-point, penambahan dan waktu multiplikasi sedikit berbeda, terutama dalam hal relatif (kita dapat mengharapkan maksimum 2 kali), tetapi mereka masih berbeda dan tidak mendukung multiplikasi, sehingga ada keuntungan di sini.
Kembali ke paragraf sebelumnya, kami menemukan bahwa untuk PT peringkat 5 * 5 + seharusnya tidak memiliki keunggulan signifikan di atas 7 * 3 +, tetapi kami masih memiliki cadangan. Perhatikan fakta bahwa kita harus menghitung sekumpulan nilai poin pada kurva Bezier ketika parameter T berubah, dan semua parameter kurva lainnya diperbaiki (tapi tidak konstan, tetapi sayang), maka sisa rumus dapat dihitung di muka dan dapatkan
=> 3 * 2 +, di mana
dan
sudah bagus, tetapi jika Anda mengingat skema Horner dan menulis
=> 2 * 2 +, maka dibandingkan dengan keputusan "di dahi" kita harus menang lebih dari 2 kali, hampir 3, dan optimasi ini sangat jelas.
Mari kita periksa teorinya dengan praktik (walaupun ini sepenuhnya berlebihan, kami yakin dengan perkiraan kami, tetapi tiba-tiba saya meremehkan kompiler), yang untuk itu kami perlu mengukur waktu nyata pelaksanaan berbagai opsi pada perangkat keras nyata. Nah, kebetulan di rumah saya punya banyak jenis papan debug untuk MK dari berbagai perusahaan (termasuk barang langka seperti debug dari Luminary Micro atau Intel Edisson, coba beli sekarang), tetapi tidak ada satu pun papan Arduino ("Yaah kami tidak punya nanas "). Tampaknya jalan buntu, tetapi ada opsi - situs tinkercad.com yang sangat menarik datang ke bantuan kami, di mana Anda dapat membangun sirkuit Anda di papan tempat memotong roti menggunakan modul Arduino, menulis sketsa dan segera menjalankannya. Pada saat yang sama, Anda dapat mengatur breakpoints, menjalankan program langkah demi langkah dan bahkan (hal yang belum pernah terjadi sebelumnya untuk Arduino nyata) melihat nilai-nilai variabel pada saat kerusakan.
Kami membuka situs ini dan mulai mengukur. Untuk mulai dengan, kami memeriksa asumsi kami tentang waktu pelaksanaan operasi dan, setelah membersihkan dari keadaan, kami memperoleh data berikut untuk bilangan bulat:
8 + 8 => 8 - 1 ketukan, 16 + 16 => 16 - 2,
8 * 8 => 16 - 2, 16 * 16 => 16 - 14 (satu-satunya hal yang ternyata tidak terduga, saya pikir mendapatkan 4 * 2 + 4 * 2 = 16, ada optimasi yang menarik),
8/8 => 8 - 230, 16/16 => 16 - 230.
Perhatikan dua digit terakhir, jelas dari mereka bahwa operasi divisi dilarang jika kita benar-benar ingin menghitung dengan cepat. Sekarang (akhirnya) kami mengukur waktu yang diperlukan untuk melakukan operasi pada jumlah PT dengan mantissa 24-bit
a + b - 126 (dan sangat bergantung pada operan), a * b - 140, a / b - 482.
Data yang diperoleh berkorelasi baik dengan asumsi teoritis kami, jelas bahwa ada implementasi perangkat keras di papan MK ini: untuk perkalian, untuk divisi, bukan untuk operasi, PT.
Sekarang kita mulai mengukur waktu perhitungan penuh. Kami menetapkan nilai A = 140, B = 120, C = 70 dan membangun 170 titik yang didistribusikan secara merata di biro desain. Mengapa tepatnya nilai-nilai ini - mereka diberikan dalam pos yang ditentukan saat mengevaluasi kinerja. Di bawah ini adalah algoritma dan waktu pelaksanaan pengujian yang sesuai.
Formula (1) => 20 ms atau 1.900 siklus per sampel
Formula (1) => 18ms atau 1660 clock cycle per sampel (pertimbangkan secara terpisah 1-T)
Formula (2) => 16ms atau 1540 clock cycle per sampel
Formula (3) => 10ms atau 923 clock cycle per sampel
Formula (4) => 8ms atau 762 tindakan per hitungan
Dapat dilihat bahwa pengurangan waktu eksekusi yang dihasilkan (dari 20 ms menjadi 8 ms) berkorelasi dengan baik dengan yang diharapkan dan kami dapat mempercepat perhitungan lebih dari 2 kali. Perhatikan bahwa selain pertimbangan dan matematika yang sangat jelas, tidak melampaui sekolah menengah, kami tidak perlu.
Dan sekarang mari kita bicara tentang apa yang harus dilakukan jika hasilnya tidak cukup, dan kita sudah memeras semuanya dari rumus perhitungan. Mereka menulis kepada saya di sini (dalam komentar ke posting lain) bahwa secara umum masalah apa pun dapat direduksi menjadi komputasi dengan FT dan, terlepas dari kontroversi yang jelas dari asumsi tersebut (coba lakukan ini untuk solusi numerik dari persamaan Navier-Stokes), dalam kasus khusus rekomendasi ini berlaku Meskipun, seperti biasa, ada nuansa.
Bagian Dua, Komputasi
Setelah modifikasi algoritma habis, hanya struktur data yang tersisa dan kita memasuki tanah angka-angka tetap. Di sini kita akan menemukan banyak jebakan yang tidak kita pikirkan untuk rentang dan akurasi PT (secara umum, untuk PT kita harus memikirkan masalah ini, tetapi di sini semuanya lebih sederhana, banyak yang telah dilakukan untuk kita). Penting untuk melakukan studi kecil tentang masalah untuk menentukan representasi FT yang diperlukan (dipilih dalam pos 9.7 yang disebutkan di atas, menilai dari hasilnya, jelas tidak cukup), tetapi saya mengusulkan untuk mengambil jalan yang sedikit berbeda. By the way, jika kita tidak mengambil 170 langkah pada interval, tetapi 128 (saya melihat tidak ada alasan yang melarang kita dari langkah ini), maka ide ini akan cocok untuk kita dengan sempurna. Jika kita memperhitungkan fakta bahwa konstanta yang mendefinisikan KB diberikan oleh bilangan bulat, dan satu-satunya parameter T dapat diwakili oleh sebagian kecil dari formulir dan / dan kami akan menggunakan hasilnya untuk merender di layar, yaitu, menerjemahkan ke dalam koordinat bilangan bulat, maka kita dapat lakukan saja semuanya dalam bilangan bulat, yang prosesnya jauh lebih cepat.
Kami hanya menggunakan rumus terakhir dan menulis ulang di notasi baru
(=> 2 * 2 + 2 /), di mana A1 dan B1 dihitung dengan cara yang sama seperti untuk PT. Jelas, semua angka adalah bilangan bulat dan operasi yang sesuai harus dilakukan jauh lebih cepat. Agar tidak kehilangan keakuratan selama operasi pembagian bilangan bulat (2/3 = 1! = 1.5) dan untuk melakukan pembagian pada saat-saat terakhir, kami sedikit mengubah rumus ke bentuk
(=> 4 * 2 + 2 /). Semua nomor FT, jadi kami menerapkan algoritme ini dan mendapatkan ... inilah Anda, nenek, dan hari Yuryev ... 1869 siklus, tetapi ini jauh lebih buruk daripada FT, kami mulai dari ini, semacam sampah, karena bilangan bulat jauh lebih cepat.
Kami memulai tanya jawab dan ternyata hanya mengubah jenis variabel saja tidak cukup. Pertama, kita harus menggunakan angka bukan 8 atau bahkan 16, tetapi 32 bit, jika tidak akan terjadi overflow, dan angka panjang, meskipun lebih cepat dari PT, tetapi tidak begitu banyak untuk mengkompensasi kekurangan dalam algoritma. kami lagi memiliki konstanta yang dihitung pada setiap ukuran - kami menghapusnya dengan perhitungan awal B2 = B1 * I, A2 = A * I * I. Lalu kita dapatkan
(=> 2 * 2 + 2 /) dengan hasil 1684 lebih baik dari yang sebelumnya, tetapi kami masih belum bisa menghindarinya.
Kami mengecualikan perhitungan satu lagi konstanta And2 = Dan * Dan kami dapatkan
(=> 2 * 2 + 1 /), dengan waktu pelaksanaan 956 siklus - tetapi ini menarik, pengecualian satu operasi menyebabkan peningkatan produktivitas yang signifikan.
Itulah yang memperlambat kami - divisi, karena ini adalah operasi yang sangat memakan waktu, tetapi kami memiliki trik yang menarik untuk menghadapinya. Untuk menghitung ekspresi 1 / Dan kita dapat melakukan transformasi elementer 1 / = 1 / * ( / ) = 1 * ( / ) / . Jika kita memilih derajat dua sebagai H, maka pembagian dengan H dapat digantikan oleh shift, dan jika eksponen adalah kelipatan dari 8, maka bahkan shift tidak akan diperlukan. Dan nilai N / A harus dihitung dengan jujur, tetapi hanya sekali, setelah itu hanya perkalian yang tersisa dalam siklus perhitungan.
Perhatikan fakta bahwa kami melakukan konversi yang tidak benar dan mengganti N / A dengan nilai bulat K untuk beralih ke operasi secara eksklusif dengan bilangan bulat. Kekeliruan tersebut disebabkan oleh hilangnya keakuratan dan penelitian tambahan harus dilakukan untuk membuktikan penerapan pendekatan ini pada kasus kami. Kita menulis H / I dalam bentuk (K * I + d) / I = K + (d / I), di mana q kurang dari I. Kemudian kesalahan absolut untuk pergi ke H / I ke K akan menjadi d / I, dan kesalahan relatif akan menjadi d / I I / (K + d / I)> = d / I / (K + 1) ~ d / I / K, asalkan K >> 1 (ini bukan pergeseran). Maka nilai H harus dipilih sebesar mungkin, karena kesalahan perhitungan absolut sama dengan A * d / I / K> = A * 1 / N / I. Jika kita ingin kesalahan tidak lebih dari satu, kita harus tahan dengan kondisi A / K <= 1, maka K> = A, kita mengonversi K * I> = A * I, yang berarti H> = A * I, maka kita tidak kehilangan akurasi. Dalam kasus kami, A <= 256 dan I <= 256, kami mendapatkan H> = 2 ** 16, yang cukup dapat diterima. Jelas, dalam formula di atas, modul angka asli harus digunakan.
Catat untuk masa depan bahwa jika kita membulatkan bukan ke bawah, tetapi menuju bilangan bulat terdekat, maka persyaratannya agak berkurang dan H harus cukup menjadi setengahnya, meskipun ada nuansa.
Bagaimanapun, kami dapat memberikan akurasi yang diperlukan dan mendapatkan algoritma berikut: H = 2 ** 16; K = [N / A] (I <256); 0 <= dan <= DAN;
(=> 4 * 2 + 2 >> 16) di mana semua operasi dilakukan pada bilangan bulat panjang. Kami menerapkan algoritma ini dan mendapatkan 583 siklus clock ... tapi ini sudah mendekati ideal, tetapi belum ideal.
Selanjutnya datang pengaturan kecil untuk MK tertentu - bekerja dengan variabel global lebih cepat. dibandingkan dengan yang lokal, tetapi lebih cepat lagi dengan mendaftar yang lokal, yang mengarah pada pengurangan waktu menjadi 506 siklus clock.
Lebih lanjut, kami mencatat bahwa perkalian terakhir sebelum shift dapat dilakukan dengan angka 16 bit, yang akan memberikan 504 - sedikit, tapi bagus.
Secara total, kami mempercepat perhitungan dibandingkan dengan implementasi "dahi" pada 1900/504 - lebih dari 3 kali, dan kami tidak kehilangan kata sama sekali. Ini adalah hasil yang saya sebut optimasi waktu, dan tidak 20% diterima di pos asli.
Apakah mungkin untuk mencapai indikator yang lebih baik - itu mungkin, tetapi ini adalah topik dari posting selanjutnya.