Apakah analisis algoritmik dengan penghitungan gagal sudah usang?

Dalam kursus analisis numerik saya, saya belajar untuk menganalisis efisiensi algoritma dengan menghitung jumlah operasi floating-point (jepit) yang mereka butuhkan, relatif terhadap ukuran masalah. Misalnya, dalam teks Trefethen & Bau pada Numerical Linear Algebra, bahkan ada gambar 3D yang tampak dari jumlah kegagalan.

Sekarang modis untuk mengatakan bahwa "jepit gratis" karena latensi memori untuk mengambil apa pun yang tidak ada dalam cache jauh lebih besar daripada biaya kegagalan. Tapi kami masih mengajar siswa untuk menghitung jepit, setidaknya dalam kursus analisis numerik. Haruskah kita mengajar mereka untuk menghitung akses memori? Apakah kita perlu menulis buku pelajaran baru? Atau apakah akses memori terlalu spesifik mesin untuk menghabiskan waktu? Apa tren jangka panjang yang akan terjadi dalam hal apakah kegagalan atau akses memori adalah hambatannya?

Catatan: beberapa jawaban di bawah ini sepertinya menjawab pertanyaan yang berbeda seperti "Haruskah saya menulis ulang implementasi saya secara obsesif untuk menghemat beberapa kegagalan atau meningkatkan kinerja cache?" Tetapi apa yang saya tanyakan lebih pada baris " Apakah lebih berguna untuk memperkirakan kompleksitas algoritmik dalam hal operasi aritmatika atau akses memori ?"

Saya pikir (urutan pertama) yang benar untuk dilakukan adalah melihat rasio jepit ke byte yang diperlukan dalam algoritma, yang saya sebut . Biarkan menjadi flop rate maksimum prosesor, dan bandwidth maksimum. Jika , maka algoritma akan dibatasi bandwidth. Jika , algoritma ini terbatas.F m a x B m a x F m a $\beta$$F_{\mathrm{max}}$$B_{\mathrm{max}}$Bmaxβ>Fma$\frac{F_{\mathrm{max}}}{\beta} > B_{\mathrm{max}}$$B_{\mathrm{max}}\beta > F_{\mathrm{max}}$

Saya pikir menghitung akses memori adalah wajib, tetapi kita juga harus memikirkan:

• Berapa banyak memori lokal diperlukan

• Berapa banyak kemungkinan konkurensi yang kita miliki

Kemudian Anda dapat mulai menganalisis algoritma untuk perangkat keras modern.

Saya tidak mengerti mengapa seseorang harus menjadi "pemenang"; ini bukan permainan zero-sum, di mana gagal dan akses memori harus menenggelamkan yang lain. Anda dapat mengajar mereka berdua, dan saya pikir mereka berdua memiliki kegunaannya. Bagaimanapun, sulit untuk mengatakan bahwa algoritma dengan akses memori tentu akan lebih cepat daripada algoritma dengan akses . Itu semua tergantung pada biaya relatif dari bagian-bagian yang berbeda (prefactor sial yang selalu kita abaikan dalam analisis ini!).O ( N ) O ( N log N ) O ( N 2$O(N^4)$$O(N)$$O(N \log N)$$O(N^2)$

Dari perspektif yang lebih luas, saya berpikir bahwa analisis kinerja algoritmik harus "menyeluruh". Jika kita mengajar orang untuk menjadi pengembang dan pengguna HPC yang sebenarnya, maka mereka perlu memahami berapa biaya pemrograman di dunia nyata. Model analisis abstrak yang kami miliki tidak memperhitungkan waktu programmer. Kita harus berpikir dalam hal "total waktu untuk solusi," daripada hanya menghitung kegagalan dan efisiensi algoritmik. Masuk akal untuk menghabiskan tiga atau empat hari programmer untuk menulis ulang rutin yang akan menghemat satu detik waktu komputer per pekerjaan kecuali Anda berencana menjalankan beberapa juta perhitungan. Demikian pula, investasi beberapa hari untuk menghemat satu atau dua jam waktu perhitungan dengan cepat terbayar. Algoritma novel itu mungkin luar biasa,

Seperti yang telah ditunjukkan oleh orang lain, jawabannya tentu saja tergantung pada apakah hambatannya adalah CPU atau bandwidth memori. Untuk banyak algoritme yang bekerja pada beberapa dataset berukuran acak, bottleneck biasanya adalah bandwidth memori karena dataset tidak cocok dengan cache CPU.

Selain itu, Knuth menyebutkan bahwa analisis akses memori lebih mungkin untuk bertahan dalam ujian waktu, mungkin karena itu relatif sederhana (bahkan ketika memperhitungkan cache-friendly) dibandingkan dengan kompleksitas pipeline CPU modern dan prediksi cabang.

Knuth menggunakan istilah gigamem dalam Volume 4A dari TAOCP, ketika menganalisis BDD. Saya tidak yakin apakah dia menggunakannya dalam volume sebelumnya. Dia membuat komentar di atas tentang bertahan dalam ujian waktu dalam Kuliah Pohon Natal tahunannya pada tahun 2010.

Menariknya, You're Doing It Wrong menunjukkan bahwa bahkan menganalisis kinerja berdasarkan operasi memori tidak selalu mudah karena ada unsur-unsur seperti tekanan VM yang ikut berperan jika data tidak masuk ke dalam RAM fisik sekaligus.

Bagaimana Anda menentukan biaya suatu algoritma tergantung pada "level" komputasi ilmiah mana Anda bekerja, dan kelas masalah (sempit atau luas) mana yang Anda pertimbangkan.

Jika Anda berpikir tentang optimasi cache, ini jelas lebih relevan untuk, misalnya, implementasi paket aljabar linier numerik seperti BLAS dan perpustakaan serupa. Jadi ini milik optimasi tingkat rendah, dan tidak apa-apa jika Anda memiliki algoritme tetap untuk masalah tertentu dan dengan kendala yang cukup pada input. Misalnya, optimasi Cache mungkin relevan untuk memiliki implementasi cepat dari iterasi gradien konjugasi jika matriks dijanjikan cukup jarang.

Di sisi lain, semakin luas kelas masalah, semakin sedikit Anda dapat memprediksi pada komputasi yang sebenarnya (seperti, katakanlah, Anda tidak tahu seberapa jarang matriks input implementasi CG Anda akan benar-benar). Semakin luas kelas mesin yang harus dijalankan oleh program Anda, semakin sedikit Anda dapat memprediksi arsitektur Cache.

Selain itu, pada tingkat komputasi ilmiah yang lebih tinggi, mungkin lebih relevan untuk mengubah struktur masalah. Misalnya, jika Anda menghabiskan waktu mencari prekondisi yang bagus untuk sistem persamaan linear, optimasi semacam ini biasanya mengalahkan optimasi tingkat rendah, karena jumlah iterasi berkurang secara drastis.

Dalam kesimpulan, optimisasi cache hanya berguna jika tidak ada yang tersisa untuk dioptimalkan oleh paralelisme dan pengurangan jumlah FLOP yang asimptotik.

Saya pikir itu bijaksana untuk mengadaptasi sikap ilmu komputer teoritis: Pada akhirnya, meningkatkan kompleksitas asimptotik dari suatu algoritma memiliki lebih banyak pengembalian daripada optimasi mikro dari beberapa baris kode yang ada. Oleh karena itu, penghitungan FLOP masih lebih disukai.

Saya selalu menolak untuk berpikir tentang menghitung jepit, akses memori, atau apa pun yang Anda miliki. Itu konsep dari tahun 1960-an ketika apa yang Anda lakukan cukup banyak diberikan dan hanya bagaimana Anda melakukannya terserah optimasi algoritmik. Pikirkan memecahkan masalah elemen hingga pada mesh xyz yang seragam menggunakan eliminasi Gaussian dari iterasi Jacobi.

Sekarang, Anda dapat mengoptimalkan ini ke neraka dan menghemat beberapa jepit, mendapatkan 10% dari waktu berjalan. Atau Anda dapat berpikir tentang menerapkan metode multigrid dan blok preconditioner yang optimal, mendapatkan faktor 10 dalam waktu berjalan. Inilah yang harus kita latih untuk dilakukan oleh siswa kita - pikirkan tentang apa, algoritma luar yang kompleks dapat membuat Anda lebih dari mencoba menemukan algoritma dalam yang lebih baik. Atasan Anda (Keyes) memiliki slide-slide ini tentang kemajuan dalam perhitungan MHD yang membuat poin ini sangat jelas.

Ya usang. Analisis algoritmik dengan jepit, atau metode lain apa pun, hanya berguna seperti model abstrak mesin saat mempertimbangkan ukuran masalah yang dihadapi. Kinerja aktual tergantung baik pada implementasi dan perangkat keras, dan penerapan model abstrak apa pun untuk yang terakhir terhadap kenyataan semakin menurun dari waktu ke waktu. Sebagai contoh, ketika Anda lebih lanjut memparalelkan penerapan algoritma yang kompleks, seperti dinamika molekuler, aspek yang berbeda menjadi batasan kecepatan pada perangkat keras yang berbeda, dan analisis algoritmik tidak ada hubungannya dengan pengamatan. Di satu sisi, satu-satunya hal yang penting adalah mengukur kinerja implementasi algoritma pada tipe perangkat keras yang bersangkutan.

Apakah abstraksi semacam itu bermanfaat sebagai alat pembelajaran? Ya, seperti banyak model yang digunakan untuk mengajar, mereka berguna selama mereka ditempatkan di samping pemahaman tentang keterbatasan model. Mekanika klasik baik-baik saja selama Anda menghargai bahwa itu tidak akan bekerja pada skala jarak kecil atau besar ...

Tidak benar-benar menjawab pertanyaan Anda, tetapi lebih menambahkan variabel lain untuk dipertimbangkan: sesuatu yang harus diperhitungkan adalah fitur dari bahasa pemrograman. Misalnya, Python sortmenggunakan algoritma Timsort , yang dirancang (di antara properti bagus lainnya) untuk meminimalkan jumlah perbandingan, yang bisa berpotensi lambat untuk objek Python. Di sisi lain, membandingkan dua float di C ++ sangat cepat, tetapi menukar mereka lebih mahal, sehingga mereka menggunakan algoritma lain .

Contoh lain adalah alokasi memori dinamis (sepele dalam daftar Python, cepat dalam waktu runtime dan waktu pengembang, adil .append()), vs FORTRAN atau C, di mana, meskipun mungkin dan lebih cepat bila diterapkan dengan benar, dibutuhkan waktu dan otak pemrograman yang jauh lebih besar. Lihat Python lebih cepat dari FORTRAN.