Apa sajakah strategi yang baik untuk meningkatkan kinerja serial kode saya?

Saya bekerja dalam ilmu komputasi, dan sebagai hasilnya, saya menghabiskan banyak waktu untuk mencoba meningkatkan throughput ilmiah banyak kode, serta memahami efisiensi kode-kode ini.

Mari kita asumsikan saya telah mengevaluasi kinerja vs keterbacaan / penggunaan kembali / pemeliharaan tradeoff dari perangkat lunak yang saya kerjakan, dan saya telah memutuskan bahwa sudah waktunya untuk mencari kinerja. Mari kita juga berasumsi bahwa saya tahu saya tidak memiliki algoritma yang lebih baik untuk masalah saya (dalam hal gagal / s dan bandwidth memori). Anda juga dapat mengasumsikan basis kode saya dalam bahasa tingkat rendah seperti C, C ++, atau Fortran. Akhirnya, mari kita asumsikan bahwa tidak ada paralelisme yang bisa didapat dalam kode, atau bahwa kita hanya tertarik pada kinerja pada satu inti.

Apa hal terpenting yang harus dicoba terlebih dahulu? Bagaimana saya tahu berapa banyak kinerja yang bisa saya dapatkan?

Pertama-tama, seperti yang ditunjukkan oleh pakar dan Dan , pembuatan profil itu penting. Saya pribadi menggunakan Intel VTune Amplifier di Linux karena memberi saya gambaran yang sangat bagus tentang di mana waktu dihabiskan untuk melakukan apa.

Jika Anda tidak akan mengubah algoritma (yaitu jika tidak akan ada perubahan besar yang akan mengubah semua optimasi Anda menjadi usang), maka saya sarankan mencari beberapa detail implementasi umum yang dapat membuat perbedaan besar:

• Memori lokalitas : apakah data yang dibaca / digunakan bersama juga disimpan bersama, atau apakah Anda mengambil potongan-potongan di sana-sini?

• Memory alignment : apakah ganda Anda benar-benar sejajar dengan 4 byte? Bagaimana Anda mengepak barang Anda structs? Untuk menjadi bertele-tele, gunakan posix_memalignsaja malloc.

• Efisiensi cache : Lokalitas menangani sebagian besar masalah efisiensi cache, tetapi jika Anda memiliki beberapa struktur data kecil yang sering Anda baca / tulis, ini membantu jika mereka adalah multiple integer atau fraksi dari garis cache (biasanya 64 byte). Ini juga membantu jika data Anda sejajar dengan ukuran garis cache. Ini secara drastis dapat mengurangi jumlah bacaan yang diperlukan untuk memuat sepotong data.

• Vektorisasi : Tidak, jangan pergi mental dengan assembler kode tangan. gccmenawarkan tipe vektor yang bisa diterjemahkan ke SSE / AltiVec / instruksi apa pun secara otomatis.

• Parallelism Instruksi-Level : Bajingan vektorisasi. Jika beberapa perhitungan yang sering diulang tidak menghasilkan vektor dengan baik, Anda dapat mencoba mengakumulasi nilai input dan menghitung beberapa nilai sekaligus. Ini seperti loop terbuka. Apa yang Anda eksploitasi di sini adalah bahwa CPU Anda biasanya akan memiliki lebih dari satu unit floating-point per inti.

• Aritmatika presisi : Apakah Anda benar-benar membutuhkan aritmatika presisi ganda dalam semua yang Anda lakukan? Misalnya, jika Anda menghitung koreksi dalam iterasi Newton, Anda biasanya tidak memerlukan semua digit yang Anda hitung. Untuk diskusi yang lebih mendalam, lihat makalah ini .

Beberapa trik ini digunakan di utas daxpy_cvec ini . Karena itu, jika Anda menggunakan Fortran (bukan bahasa tingkat rendah dalam buku saya), Anda akan memiliki sedikit kontrol atas sebagian besar "trik" ini.

Jika Anda menjalankan beberapa perangkat keras khusus, mis. Sebuah cluster yang Anda gunakan untuk semua proses produksi Anda, Anda mungkin juga ingin membaca spesifik CPU yang digunakan. Bukannya Anda harus menulis hal-hal di assembler langsung untuk arsitektur itu, tetapi mungkin menginspirasi Anda untuk menemukan beberapa optimasi lain yang mungkin Anda lewatkan. Mengetahui fitur adalah langkah awal yang penting untuk menulis kode yang dapat mengeksploitasinya.

Memperbarui

Sudah lama sejak saya menulis ini dan saya tidak memperhatikan bahwa itu telah menjadi jawaban yang populer. Untuk alasan ini, saya ingin menambahkan satu poin penting:

• Bicaralah dengan Ilmuwan Komputer lokal Anda : Bukankah lebih keren jika ada disiplin ilmu yang khusus membahas membuat algoritma dan / atau perhitungan lebih efisien / elegan / paralel, dan kita semua bisa meminta saran dari mereka? Nah, kabar baik, disiplin itu ada: Ilmu Komputer. Kemungkinannya, institusi Anda bahkan memiliki seluruh departemen yang didedikasikan untuknya. Bicaralah pada mereka.

Saya yakin dengan sejumlah Ilmuwan non-Komputer ini akan membawa kembali ingatan akan diskusi yang membuat frustrasi dengan disiplin yang tidak menghasilkan apa-apa, atau ingatan tentang anekdot orang lain. Jangan berkecil hati. Kolaborasi antardisiplin adalah hal yang rumit, dan itu membutuhkan sedikit usaha, tetapi hasilnya bisa sangat besar.

Dalam pengalaman saya, sebagai Ilmuwan Komputer (CS), triknya adalah mendapatkan harapan dan komunikasi dengan benar.

Harapannya , CS hanya akan membantu Anda jika dia menganggap masalah Anda menarik. Ini cukup banyak mengecualikan mencoba mengoptimalkan / membuat vektor / memparalelkan sepotong kode yang telah Anda tulis, tetapi tidak benar-benar berkomentar, untuk masalah yang tidak mereka mengerti. CSs biasanya lebih tertarik pada masalah yang mendasarinya, misalnya algoritma yang digunakan untuk menyelesaikannya. Jangan berikan mereka solusi Anda , beri mereka masalah Anda .

Juga, bersiaplah untuk CS untuk mengatakan " masalah ini telah dipecahkan ", dan hanya memberi Anda referensi ke makalah. Sebuah saran: Baca makalah itu dan, jika benar-benar berlaku untuk masalah Anda, terapkan algoritma apa pun yang disarankan. Ini bukan CS yang puas diri, ini CS yang hanya membantu Anda. Jangan tersinggung, ingat: Jika masalahnya tidak menarik secara komputasi, yaitu masalah itu sudah dipecahkan dan solusi terbukti optimal, mereka tidak akan bekerja di atasnya, apalagi kode itu untuk Anda.

Komunikasi -bijaksana, mengingat bahwa sebagian besar CSS tidak ahli dalam bidang Anda, dan menjelaskan masalah dalam hal apa yang Anda lakukan, sebagai lawan bagaimana dan mengapa . Kami biasanya benar-benar tidak peduli tentang alasannya , dan bagaimana , yah, yang terbaik yang kami lakukan.

Misalnya, saya saat ini bekerja dengan sekelompok Ahli Kosmologi Komputasi dalam menulis versi yang lebih baik dari kode simulasi mereka, berdasarkan SPH dan Multipoles . Butuh sekitar tiga pertemuan untuk berhenti berbicara dalam hal materi gelap dan galaksi (huh?) Dan untuk menelusuri inti perhitungan, yaitu bahwa mereka perlu menemukan semua tetangga dalam radius tertentu dari setiap partikel, menghitung beberapa kuantitas atas mereka, dan kemudian menabrak semua tetangga kata lagi dan menerapkan kuantitas itu dalam beberapa perhitungan lain. Kemudian pindahkan partikel-partikelnya, atau setidaknya beberapa di antaranya, dan lakukan semuanya lagi. Anda tahu, sementara yang pertama mungkin sangat menarik (itu!), Yang terakhir adalah apa yang perlu saya pahami untuk mulai berpikir tentang algoritma.

Tapi saya menyimpang dari poin utama: Jika Anda benar-benar tertarik untuk membuat perhitungan dengan cepat, dan Anda sendiri bukan seorang Ilmuwan Komputer, bicaralah dengan salah satunya.

Perangkat lunak ilmiah tidak jauh berbeda dari perangkat lunak lain, sejauh cara mengetahui apa yang perlu dicari.

Metode yang saya gunakan adalah jeda acak . Berikut adalah beberapa speedup yang telah saya temukan:

Jika sebagian besar waktu dihabiskan dalam fungsi seperti logdan exp, saya bisa melihat apa argumen untuk fungsi-fungsi itu, sebagai fungsi dari titik mereka dipanggil. Seringkali mereka dipanggil berulang kali dengan argumen yang sama. Jika demikian, memoisasi menghasilkan faktor percepatan besar-besaran.

Jika saya menggunakan fungsi BLAS atau LAPACK, saya mungkin menemukan bahwa sebagian besar waktu dihabiskan dalam rutinitas untuk menyalin array, mengalikan matriks, mengubah choleski, dll.

• Rutin untuk menyalin array tidak ada untuk kecepatan, itu ada untuk kenyamanan. Anda mungkin menemukan ada cara yang kurang nyaman, tetapi lebih cepat, untuk melakukannya.

• Rutinitas untuk menggandakan atau membalikkan matriks, atau mengambil transformasi choleski, cenderung memiliki argumen karakter yang menentukan opsi, seperti 'U' atau 'L' untuk segitiga atas atau bawah. Sekali lagi, itu ada untuk kenyamanan. Apa yang saya temukan adalah, karena matriks saya tidak terlalu besar, rutinitas menghabiskan lebih dari setengah waktu mereka memanggil subrutin untuk membandingkan karakter hanya untuk menguraikan pilihan. Menulis versi tujuan khusus dari rutinitas matematika yang paling mahal menghasilkan percepatan besar-besaran.

Jika saya dapat memperluas yang terakhir: matrix-multiply, DGEMM rutin memanggil LSAME untuk memecahkan kode argumen karakternya. Melihat persen waktu inklusif (satu-satunya statistik yang layak dilihat) yang dianggap profiler "baik" dapat menunjukkan DGEMM menggunakan beberapa persen dari total waktu, seperti 80%, dan LSAME menggunakan beberapa persen dari total waktu, seperti 50%. Melihat yang pertama, Anda akan tergoda untuk mengatakan "baik itu harus sangat dioptimalkan, jadi tidak banyak yang bisa saya lakukan tentang itu". Melihat yang terakhir, Anda akan tergoda untuk mengatakan "Hah? Tentang apa semua itu? Itu hanya sedikit rutinitas kecil. Profiler ini pasti salah!"

Itu tidak salah, itu hanya tidak memberi tahu Anda apa yang perlu Anda ketahui. Apa jeda acak menunjukkan kepada Anda adalah bahwa DGEMM ada di 80% dari sampel tumpukan, dan LSAME pada 50%. (Anda tidak perlu banyak sampel untuk mendeteksi itu. 10 biasanya banyak.) Terlebih lagi, pada banyak sampel tersebut, DGEMM sedang dalam proses memanggil LSAME dari beberapa baris kode yang berbeda.

Jadi sekarang Anda tahu mengapa kedua rutinitas menghabiskan banyak waktu inklusif. Anda juga tahu di mana dalam kode Anda mereka dipanggil dari untuk menghabiskan waktu ini. Itu sebabnya saya menggunakan jeda acak dan mengambil tampilan profiler yang kuning, tidak peduli seberapa bagus mereka. Mereka lebih tertarik mendapatkan pengukuran daripada memberi tahu Anda apa yang terjadi.

Sangat mudah untuk mengasumsikan rutin perpustakaan matematika telah dioptimalkan ke tingkat ke-n, tetapi pada kenyataannya mereka telah dioptimalkan untuk dapat digunakan untuk berbagai keperluan. Anda perlu melihat apa yang sebenarnya terjadi, bukan apa yang mudah diasumsikan.

TAMBAH: Jadi untuk menjawab dua pertanyaan terakhir Anda:

Apa hal terpenting yang harus dicoba terlebih dahulu?

Ambil 10-20 tumpukan sampel, dan jangan hanya meringkasnya, pahami apa yang diceritakan masing-masing. Lakukan ini dulu, terakhir, dan di antara keduanya. (Tidak ada "coba", Skywalker muda.)

Bagaimana saya tahu berapa banyak kinerja yang bisa saya dapatkan?

Sampel tumpukan akan memberi Anda perkiraan yang sangat kasar berapa fraksi waktu yang akan disimpan. (Ini mengikuti distribusi , di mana adalah jumlah sampel yang menampilkan apa yang akan Anda perbaiki, dan adalah jumlah total sampel. Itu tidak menghitung biaya kode yang Anda gunakan untuk menggantinya, yang diharapkan akan menjadi kecil.) Kemudian rasio speedup adalah yang bisa jadi besar. Perhatikan bagaimana ini berlaku secara matematis. Jika , dan , rata-rata dan mode adalah 0,5, untuk rasio percepatan 2. Berikut adalah distribusinya: Jika Anda menghindari risiko, ya, ada kemungkinan kecil (0,03%) bahwa$x$$\beta(s+1,(n-s)+1)$$s$$n$$1/(1-x)$$n=10$$s=5$$x$

$x$ kurang dari 0,1, untuk speedup kurang dari 11%. Tetapi menyeimbangkan itu adalah probabilitas yang sama bahwa lebih besar dari 0,9, untuk rasio percepatan lebih dari 10! Jika Anda mendapatkan uang sebanding dengan kecepatan program, itu bukan peluang buruk.$x$

Seperti yang telah saya tunjukkan kepada Anda sebelumnya, Anda dapat mengulangi seluruh prosedur sampai Anda tidak bisa lagi, dan rasio percepatan yang diperparah bisa sangat besar.

TAMBAH: Dalam menanggapi kekhawatiran Pedro tentang positif palsu, izinkan saya mencoba membuat contoh di mana hal itu mungkin terjadi. Kami tidak pernah menindaklanjuti masalah yang potensial kecuali jika kami melihatnya dua kali atau lebih, jadi kami berharap kesalahan positif terjadi ketika kami melihat masalah pada waktu sesedikit mungkin, terutama ketika jumlah total sampel besar. Misalkan kita mengambil 20 sampel dan melihatnya dua kali. Yang memperkirakan biayanya adalah 10% dari total waktu eksekusi, mode distribusinya. (Rata-rata distribusi lebih tinggi - itu adalah .) Kurva yang lebih rendah pada grafik berikut adalah distribusinya:$(s+1)/(n+2)=3/22=13.6\%$

Pertimbangkan jika kami mengambil sebanyak 40 sampel (lebih dari yang pernah saya miliki pada satu waktu) dan hanya melihat masalah pada dua dari mereka. Perkiraan biaya (mode) dari masalah itu adalah 5%, seperti yang ditunjukkan pada kurva yang lebih tinggi.

Apa itu "false positive"? Ini adalah bahwa jika Anda memperbaiki masalah Anda menyadari keuntungan yang lebih kecil dari yang diharapkan, bahwa Anda menyesal telah memperbaikinya. Kurva menunjukkan (jika masalahnya "kecil") itu, sementara gain bisa kurang dari fraksi sampel yang menunjukkan itu, rata-rata akan lebih besar.

Ada risiko yang jauh lebih serius - "negatif palsu". Saat itulah ada masalah, tetapi tidak ditemukan. (Menyumbang pada hal ini adalah "bias konfirmasi", di mana ketiadaan bukti cenderung diperlakukan sebagai bukti ketidakhadiran.)

Apa yang Anda dapatkan dengan profiler (yang baik) adalah Anda mendapatkan pengukuran yang jauh lebih tepat (kesempatan sehingga kurang positif palsu), dengan mengorbankan banyak informasi yang kurang tepat tentang apa masalah sebenarnya adalah (sehingga kurang kesempatan untuk menemukan itu dan mendapatkan keuntungan apapun ). Itu membatasi speedup keseluruhan yang bisa dicapai.

Saya akan mendorong pengguna profiler untuk melaporkan faktor percepatan yang sebenarnya mereka dapatkan dalam praktik.

Ada hal lain yang harus dibuat kembali. Pertanyaan Pedro tentang positif palsu.

Dia menyebutkan mungkin ada kesulitan ketika turun ke masalah kecil dalam kode yang sangat optimal. (Bagi saya, masalah kecil adalah yang menyumbang 5% atau kurang dari total waktu.)

Karena sepenuhnya mungkin untuk membangun program yang sepenuhnya optimal kecuali 5%, poin ini hanya dapat diatasi secara empiris, seperti dalam jawaban ini . Untuk menggeneralisasi dari pengalaman empiris, seperti ini:

Suatu program, seperti tertulis, biasanya mengandung beberapa peluang untuk optimisasi. (Kita dapat menyebutnya "masalah" tetapi mereka sering merupakan kode yang sangat baik, hanya mampu melakukan perbaikan yang cukup besar.) Diagram ini menggambarkan program buatan yang memakan waktu lama (100-an, katakanlah), dan berisi masalah A, B, C, ... itu, ketika ditemukan dan diperbaiki, hemat 30%, 21%, dll dari 100-an asli.

Perhatikan bahwa masalah F berharga 5% dari waktu semula, sehingga "kecil", dan sulit ditemukan tanpa 40 atau lebih sampel.

Namun, 10 sampel pertama dengan mudah menemukan masalah A. ** Ketika itu diperbaiki, program hanya membutuhkan 70-an, untuk percepatan 100/70 = 1,43x. Itu tidak hanya membuat program lebih cepat, ia memperbesar, dengan rasio itu, persentase diambil oleh masalah yang tersisa. Misalnya, masalah B awalnya mengambil 21 yang merupakan 21% dari total, tetapi setelah menghapus A, B mengambil 21 dari 70-an, atau 30%, sehingga lebih mudah untuk menemukan ketika seluruh proses diulang.

Setelah proses diulang lima kali, sekarang waktu eksekusi adalah 16,8 detik, dari yang masalah F adalah 30%, bukan 5%, sehingga 10 sampel merasa mudah.

Jadi itu intinya. Secara empiris, program mengandung serangkaian masalah yang memiliki distribusi ukuran, dan setiap masalah yang ditemukan dan diperbaiki membuatnya lebih mudah untuk menemukan yang tersisa. Untuk mencapai hal ini, tidak ada masalah yang dapat dilewati karena, jika memang ada, mereka duduk di sana mengambil waktu, membatasi total speedup, dan gagal memperbesar masalah yang tersisa. Itu sebabnya sangat penting untuk menemukan masalah yang bersembunyi .

Jika masalah A sampai F ditemukan dan diperbaiki, kecepatannya adalah 100 / 11.8 = 8.5x. Jika salah satu dari mereka terlewat, misalnya D, maka percepatannya hanya 100 / (11,8 + 10.3) = 4.5x. Itulah harga yang dibayarkan untuk negatif palsu.

Jadi, ketika profiler mengatakan "sepertinya tidak ada masalah yang signifikan di sini" (yaitu pengkode yang baik, ini adalah kode yang secara praktis optimal), mungkin itu benar, dan mungkin tidak. (A false negative .) Anda tidak tahu pasti apakah ada lebih banyak masalah untuk diperbaiki, untuk percepatan yang lebih tinggi, kecuali jika Anda mencoba metode profil lain dan menemukan bahwa ada. Dalam pengalaman saya, metode pembuatan profil tidak memerlukan sejumlah besar sampel, diringkas, tetapi sejumlah kecil sampel, di mana setiap sampel dipahami cukup menyeluruh untuk mengenali setiap peluang untuk optimasi.

** Diperlukan minimal 2 klik pada masalah untuk menemukannya, kecuali seseorang memiliki pengetahuan sebelumnya bahwa ada (dekat) loop tak terbatas. (Tanda centang merah mewakili 10 sampel acak); Jumlah rata-rata sampel yang diperlukan untuk mendapatkan 2 hit atau lebih, ketika masalahnya adalah 30%, adalah ( distribusi binomial negatif ). 10 sampel menemukannya dengan probabilitas 85%, 20 sampel - 99,2% ( distribusi binomial ). Untuk mendapatkan probabilitas untuk menemukan masalah, di R, mengevaluasi , misalnya: .$2/0.3=6.67$1 - pbinom(1, numberOfSamples, sizeOfProblem)1 - pbinom(1, 20, 0.3) = 0.9923627

TAMBAH: Fraksi waktu yang dihemat, , mengikuti distribusi Beta , di mana adalah jumlah sampel, dan adalah jumlah yang menampilkan masalah. Namun, rasio percepatan sama dengan (dengan asumsi semua disimpan), dan akan menarik untuk memahami distribusi . Ternyata mengikuti distribusi BetaPrime . Saya mensimulasikannya dengan 2 juta sampel, sampai pada perilaku ini:β ( s + 1 , ( n - s ) + 1 ) n s y 1 / ( 1 - x ) x y y - $x$$\beta(s+1,(n-s)+1)$$n$$s$$y$$1/(1-x)$$x$$y$$y-1$

         distribution of speedup
               ratio y

 s, n    5%-ile  95%-ile  mean
 2, 2    1.58    59.30   32.36
 2, 3    1.33    10.25    4.00
 2, 4    1.23     5.28    2.50
 2, 5    1.18     3.69    2.00
 2,10    1.09     1.89    1.37
 2,20    1.04     1.37    1.17
 2,40    1.02     1.17    1.08

 3, 3    1.90    78.34   42.94
 3, 4    1.52    13.10    5.00
 3, 5    1.37     6.53    3.00
 3,10    1.16     2.29    1.57
 3,20    1.07     1.49    1.24
 3,40    1.04     1.22    1.11

 4, 4    2.22    98.02   52.36
 4, 5    1.72    15.95    6.00
 4,10    1.25     2.86    1.83
 4,20    1.11     1.62    1.31
 4,40    1.05     1.26    1.14

 5, 5    2.54   117.27   64.29
 5,10    1.37     3.69    2.20
 5,20    1.15     1.78    1.40
 5,40    1.07     1.31    1.17

Dua kolom pertama memberikan interval kepercayaan 90% untuk rasio percepatan. Rasio kecepatan rata-rata sama dengan kecuali untuk kasus di mana . Dalam hal itu tidak terdefinisi dan, memang, ketika saya meningkatkan jumlah nilai simulasi , rata-rata empiris meningkat.s = n $(n+1)/(n-s)$$s=n$$y$

Ini adalah plot distribusi faktor percepatan, dan artinya, untuk 2 hit dari 5, 4, 3, dan 2 sampel. Misalnya, jika 3 sampel diambil, dan 2 di antaranya merupakan hit pada suatu masalah, dan masalah itu dapat dihilangkan, faktor percepatan rata-rata adalah 4x. Jika 2 hit terlihat hanya dalam 2 sampel, speedup rata-rata tidak terdefinisi - secara konseptual karena program dengan loop tak terbatas ada dengan probabilitas tidak nol!

Anda tidak hanya harus memiliki pengetahuan yang mendalam tentang kompiler Anda, Anda juga memiliki pengetahuan yang mendalam tentang arsitektur target dan sistem operasi Anda .

Apa yang dapat memengaruhi kinerja?

Jika Anda ingin memeras setiap ons kinerja terakhir, maka setiap kali Anda mengubah arsitektur target Anda, Anda harus mengubah dan mengoptimalkan ulang kode Anda. Sesuatu yang merupakan optimasi dengan satu CPU dapat menjadi kurang optimal dalam revisi berikutnya dari CPU yang sama.

Contoh yang sangat baik dari ini adalah cache CPU. Pindahkan program Anda dari CPU dengan cache cepat kecil ke cache dengan cache sedikit lebih lambat, sedikit lebih besar dan profil Anda dapat berubah secara signifikan.

Bahkan jika arsitektur target tidak berubah, perubahan level rendah ke sistem operasi juga dapat mempengaruhi kinerja. Patch mitigasi Spectre dan Meltdown memiliki dampak besar pada beberapa beban kerja, jadi ini mungkin memaksa evaluasi ulang optimisasi Anda.

Bagaimana saya bisa menjaga kode saya dioptimalkan?

Ketika mengembangkan kode yang sangat dioptimalkan, Anda harus tetap modular dan membuatnya mudah untuk menukar versi berbeda dari algoritma yang sama masuk dan keluar, bahkan mungkin memilih versi spesifik yang digunakan pada saat run time, tergantung pada sumber daya yang tersedia dan ukuran / kompleksitas dari data yang akan diproses.

Modularitas juga berarti dapat menggunakan test suite yang sama pada semua versi Anda yang dioptimalkan dan tidak dioptimalkan, memungkinkan Anda untuk memverifikasi bahwa mereka semua berperilaku yang sama dan profil masing-masing dengan cepat dalam perbandingan suka-untuk-suka . Saya masuk ke sedikit lebih detail dalam jawaban saya untuk Bagaimana mendokumentasikan dan mengajar orang lain "dioptimalkan di luar pengakuan" kode komputasi intensif? .

Bacaan lebih lanjut

Selain itu, saya akan sangat menyarankan mengambil melihat kertas Ulrich Drepper ini sangat baik Apa Setiap Programmer Harus Anda Ketahui Tentang Memory , yang judulnya adalah penghormatan kepada David Goldberg sama fantastis Apa Setiap Komputer Scientist Harus Anda Ketahui Tentang Floating-Point Arithmetic .

Ingat setiap optimasi memiliki potensi untuk menjadi anti-optimisasi di masa depan , jadi harus dianggap sebagai kemungkinan bau kode, untuk dijaga agar tetap minimum. Jawaban saya untuk Apakah optimasi mikro penting ketika coding? memberikan contoh nyata dari pengalaman pribadi ini.

Saya pikir Anda mengucapkan pertanyaan itu terlalu sempit. Dalam pandangan saya, sikap yang berguna adalah hidup dengan asumsi bahwa hanya perubahan pada struktur data dan algoritma yang dapat menghasilkan keuntungan kinerja yang signifikan pada kode yang lebih dari 100 baris, dan saya percaya bahwa saya belum menemukan contoh tandingan untuk klaim ini.

Hal pertama yang harus Anda lakukan adalah membuat profil kode Anda. Anda ingin mengetahui bagian mana dari program Anda yang memperlambat Anda sebelum Anda mulai mengoptimalkan, jika tidak, Anda akhirnya dapat mengoptimalkan bagian dari kode Anda yang tidak memakan banyak waktu eksekusi.

Linux

gprof cukup bagus, tetapi hanya memberi tahu Anda berapa banyak waktu yang diambil oleh masing-masing fungsi daripada setiap baris.

Apple OS X

Anda mungkin ingin mencoba Shark . Ini tersedia di situs Pengembang Apple di bawah Unduhan> Alat Pengembang> CHUD 4.6.2, versi yang lebih lama di sini . CHUD juga berisi alat profil lain seperti BigTop frontend, alat pencarian Indeks PMC, profiler fungsi level Saturnus dan banyak perintah lainnya. Shark akan datang dengan versi commandline.

Adapun berapa banyak kinerja yang bisa Anda peroleh, ambil hasil dari profiling kode Anda dan katakanlah Anda mengidentifikasi bagian yang membutuhkan sebagian kecil waktu. Jika Anda ingin meningkatkan kinerja karya itu hanya dengan faktor "s", speedup keseluruhan Anda akan menjadi 1 / ((1-p) + p / s). Karena itu Anda dapat secara maksimal meningkatkan kecepatan Anda dengan faktor 1 / (1-p). Semoga Anda memiliki area p tinggi! Ini setara dengan Hukum Amdahl untuk optimasi serial.

Mengoptimalkan kode Anda harus dilakukan dengan hati-hati. Mari kita asumsikan Anda sudah mendebug kode tersebut. Anda dapat menghemat banyak waktu jika mengikuti prioritas tertentu, yaitu:

1. Gunakan perpustakaan yang sangat dioptimalkan (atau dioptimalkan secara profesional) jika memungkinkan. Beberapa contoh mungkin termasuk FFTW, OpenBlas, Intel MKL, perpustakaan NAG, dll. Kecuali Anda sangat berbakat (seperti pengembang GotoBLAS), Anda mungkin tidak bisa mengalahkan para profesional.

2. Gunakan profiler (beberapa di daftar berikut telah diberi nama di utas ini - Intel Tune, valgrind, gprof, gcov, dll.) Untuk mengetahui bagian mana dari kode Anda yang paling memakan waktu. Tidak ada gunanya membuang waktu mengoptimalkan bagian-bagian kode yang jarang dipanggil.

3. Dari hasil profiler, lihat bagian dari kode Anda yang paling lama. Tentukan apa sifat algoritme Anda - apakah terikat CPU atau terikat memori? Masing-masing membutuhkan serangkaian teknik optimisasi yang berbeda. Jika Anda mendapatkan banyak cache yang hilang, memori mungkin menjadi penghambat - CPU membuang-buang siklus menunggu memori tersedia. Pikirkan apakah loop cocok dengan cache L1 / L2 / L3 dari sistem Anda. Jika Anda memiliki pernyataan "jika" di loop Anda, periksa apakah profiler mengatakan sesuatu tentang salah prediksi cabang? Apa hukuman salah duga cabang dari sistem Anda? Omong-omong, Anda bisa mendapatkan data salah prediksi cabang dari Manual Referensi Pengoptimalan Intel [1]. Perhatikan bahwa penalti misprediksi cabang adalah khusus untuk prosesor, seperti yang akan Anda lihat dalam manual Intel.

4. Terakhir, atasi masalah yang diidentifikasi oleh profiler. Sejumlah teknik telah dibahas di sini. Sejumlah sumber daya yang baik, andal, dan komprehensif tentang pengoptimalan juga tersedia. Untuk menyebutkan hanya dua, ada Manual Referensi Optimasi Intel [1], dan lima manual optimasi oleh Agner Fog [2]. Perhatikan bahwa ada beberapa hal yang mungkin tidak perlu Anda lakukan, jika kompiler sudah melakukannya - misalnya, loop membuka gulungan, menyelaraskan memori, dll. Baca dokumentasi kompiler Anda dengan cermat.

Referensi:

[1] Manual Referensi Optimasi Arsitektur Intel 64 dan IA-32: http://www.intel.sg/content/dam/doc/manual/64-ia-32-architectures-optimization-manual.pdf

[2] Agner Fog, "Sumber Daya Optimalisasi Perangkat Lunak": http://www.agner.org/optimize/

• "Mengoptimalkan perangkat lunak dalam C ++: Panduan pengoptimalan untuk platform Windows, Linux dan Mac"
• "Mengoptimalkan subrutin dalam bahasa assembly: Panduan pengoptimalan untuk platform x86"
• "Mikroarsitektur Intel, AMD dan VIA CPU: Panduan pengoptimalan untuk programmer perakitan dan pembuat kompiler"
• "Tabel instruksi: Daftar latensi instruksi, throughput, dan gangguan operasi mikro untuk CPU Intel, AMD, dan VIA"
• "Konvensi panggilan untuk berbagai kompiler C ++ dan sistem operasi"

Saya bukan ilmuwan komputasi seperti banyak orang lain di sini (jadi saya bisa salah :)) tetapi hari ini ada sedikit gunanya menghabiskan terlalu banyak waktu pada kinerja serial selama kita menggunakan lib standar. Mungkin lebih bermanfaat untuk menghabiskan waktu / upaya tambahan untuk membuat kode lebih terukur.

Bagaimanapun, berikut adalah dua contoh (jika Anda belum membacanya) tentang bagaimana kinerja ditingkatkan (untuk masalah FE yang tidak terstruktur).

Serial : Lihat paruh kedua teks abstrak dan terkait.

Paralel : Khususnya fase inisialisasi, dalam bagian 4.2.

Ini mungkin lebih merupakan jawaban meta daripada jawaban ...

Anda harus mengembangkan keakraban akrab dengan kompiler Anda. Anda dapat memperoleh ini dengan paling efisien dengan membaca manual dan bereksperimen dengan berbagai opsi.

Banyak saran bagus yang dikeluarkan @Pedro dapat diimplementasikan dengan menyesuaikan kompilasi daripada program.

Cara mudah dari profil program (di Linux) adalah dengan menggunakan perfdi statmodus. Cara paling sederhana adalah menjalankannya seperti

perf stat ./my_program args ...

dan itu akan memberi Anda banyak statistik kinerja yang berguna:

Performance counter stats for './simd_test1':

     3884.559489 task-clock                #    1.000 CPUs utilized
              18 context-switches          #    0.005 K/sec
               0 cpu-migrations            #    0.000 K/sec
             383 page-faults               #    0.099 K/sec
  10,911,904,779 cycles                    #    2.809 GHz
 <not supported> stalled-cycles-frontend
 <not supported> stalled-cycles-backend
  14,346,983,161 instructions              #    1.31  insns per cycle
   2,143,017,630 branches                  #  551.676 M/sec
          28,892 branch-misses             #    0.00% of all branches

     3.885986246 seconds time elapsed

Terkadang ia juga akan membuat daftar D-cache memuat dan ketinggalan. Jika Anda melihat banyak cache yang hilang, maka program Anda intensif memori dan tidak memperlakukan cache dengan baik. Saat ini, CPU semakin cepat dari bandwidth memori, dan biasanya masalahnya selalu mengakses memori.

Anda juga dapat mencoba perf record ./my_program; perf reportyang merupakan cara mudah untuk profil. Baca halaman manual untuk mempelajari lebih lanjut.