Berapa banyak perangkat lunak ilmiah harus dioptimalkan?

13

Untuk aplikasi yang membutuhkan sumber daya komputasi yang signifikan, kinerja tinggi dapat menjadi faktor penting ketika datang untuk memberikan hasil ilmiah atau mencapai "terobosan" dalam waktu yang wajar.

Berapa banyak waktu dan upaya yang harus diinvestasikan pengembang perangkat lunak dalam mengoptimalkan aplikasi? Apa kriteria utama yang digunakan?

Allan P. Engsig-Karup
sumber
Program yang ditulis para ilmuwan sering kali dijalankan untuk waktu yang sangat lama (misalnya simulasi). Waktu programer dan waktu pengoperasian komputer mungkin sebanding. Ini sangat berbeda dari pekerjaan programmer "biasa" hari ini. Seperti pada hari-hari awal komputasi, seringkali perlu investasi beberapa upaya (dan waktu programmer) untuk membuat simulasi lebih cepat dan menyelesaikan lebih cepat, dan menyelesaikan pekerjaan lebih cepat.
Szabolcs

Jawaban:

15

Dalam sebagian besar kasus, peningkatan dalam algoritma membuat perbedaan yang lebih besar daripada peningkatan dalam optimasi. Algoritma juga lebih portabel daripada optimasi tingkat rendah. Saran saya adalah untuk mengikuti praktik terbaik umum sehubungan dengan tata letak memori untuk penggunaan kembali cache, menghindari salinan atau komunikasi yang berlebihan, memperlakukan sistem file dengan cara yang waras, dan membuat kernel floating point memiliki granularity yang cukup untuk vektorisasi. Kadang-kadang ini cukup untuk mencapai fraksi "puncak" yang cukup tinggi (untuk operasi ini).

Buat sketsa model kinerja untuk operasi yang menurut Anda penting (atau yang menurut Anda penting dengan membuat profil). Kemudian Anda dapat menggunakan model kinerja untuk memperkirakan apa yang bisa dilakukan oleh implementasi yang sangat disetel. Jika Anda memutuskan bahwa speedup sepadan (relatif terhadap hal-hal lain yang bisa Anda lakukan), maka lakukan optimasi.

Mungkin tantangan terberat adalah merancang antarmuka tingkat tinggi, penting (dalam arti bahwa banyak kode akan tergantung pada pilihan ini) dan struktur data sehingga Anda dapat mengoptimalkan nanti tanpa perlu mengubah API. Berbeda dengan optimisasi spesifik dan pedoman umum, saya tidak tahu bagaimana mengajar ini kecuali melalui pengalaman. Bekerja dengan perangkat lunak sumber terbuka yang peka terhadap kinerja membantu. Seperti halnya keputusan API, penting untuk memahami ruang masalah.

Jed Brown
sumber
1
Baru-baru ini saya mendapat faktor 10.000 (untuk acara terbesar kami) peningkatan dalam jangka waktu langkah membatasi analisis kami hanya akan mengganti algoritma yang O (n ^ 2) dalam waktu dan ruang dengan satu O (n log n ) di keduanya. Pikiran Anda itu berarti ketergantungan lain dan beberapa kompleksitas tambahan, tetapi kadang-kadang itu layak ...
dmckee --- ex-moderator kitten
1
Faktor-faktor percepatan (yang relatif terhadap sesuatu) tidak terlalu berharga dengan referensi yang jelas tentang apa yang telah Anda bandingkan. Jika Anda membandingkan dengan implementasi yang buruk berdasarkan pada algoritma yang tidak tepat dan kemudian berubah maka jelas tidak masuk akal untuk mengharapkan keuntungan relatif besar.
Allan P. Engsig-Karup
1
@ Allan: Jika ada faktor 10.000 untuk mendapatkan dari satu perubahan maka jelas itu adalah implementasi yang dipilih dengan buruk. Kode sebelumnya terluka oleh ruang yang tidak perlu dan kompleksitas waktu: kinerja caching buruk. Tapi itu intinya bukan?
dmckee --- ex-moderator kitten
8

Bagaimana Anda mendefinisikan "mengoptimalkan"? Ada seluruh spektrum dari pengembangan algoritma yang lebih baik atau model komputasi hingga menggunakan assembler yang disetel dengan tangan.

Menurut pendapat dan pengalaman saya, buah yang menggantung rendah adalah di suatu tempat di tengah, misalnya memilih algoritma yang paling cocok untuk arsitektur komputer yang mendasarinya. Algoritme tidak harus novel dan pemahaman Anda tentang arsitektur yang mendasarinya tidak harus sangat spesifik, misalnya

  • Jika Anda tahu bahwa arsitektur Anda mendukung SIMD, susun ulang perhitungan sehingga operasi Anda dapat ditulis dalam vektor pendek,
  • Jika Anda tahu arsitektur adalah komputer multi-inti, cobalah untuk menguraikan tugas komputasi Anda menjadi sub-tugas individual yang tidak saling mengganggu dan menjalankannya secara paralel (pikirkan DAG sub-tugas Anda) ,
  • Jika arsitektur dasar Anda memiliki GPU, pikirkan cara-cara Anda dapat merumuskan kembali perhitungan Anda sebagai sekelompok utas yang berbaris melalui data dalam langkah-kunci,
  • dll ...

Semua fitur di atas, misalnya SIMD, paralelisme dan GPU, dapat diakses tanpa banyak pengetahuan tingkat rendah, tetapi hanya benar-benar menawarkan keuntungan dalam algoritma yang dapat dengan mudah mengeksploitasi mereka.

Pedro
sumber
4

Saya setuju dengan semua jawaban yang sudah diajukan sejauh ini ... Saya hanya ingin membahas satu aspek lagi dari optimasi kode: harapan kualitas.

Masalah optimasi kode biasanya muncul ketika pengguna mencoba untuk memecahkan masalah yang lebih besar dan lebih besar dan kode tidak cukup untuk memenuhi kebutuhan / harapan pengguna. Jumlah waktu yang harus diinvestasikan dalam optimalisasi kode tergantung pada permintaan untuk memenuhi harapan ini. Tentu bernilai investasi waktu yang signifikan jika ada kebutuhan kritis untuk keunggulan kompetitif (misalnya menyelesaikan & menerbitkan penelitian Anda tentang topik hangat sebelum yang lain).

Tentu saja, berapa banyak waktu yang harus diinvestasikan tergantung pada seberapa cepat Anda membutuhkannya, dan seberapa portabel kode yang Anda inginkan. Seringkali, kedua kebutuhan ini bertentangan satu sama lain, dan Anda harus memutuskan mana yang lebih penting sebelum Anda memulai optimasi. Semakin portabel Anda menginginkannya, semakin Anda harus bergantung pada perubahan desain tingkat tinggi ke kode (algoritma / struktur data). Semakin cepat Anda ingin menjalankan kode, harus disetel dengan optimasi tingkat rendah khusus untuk mesin tertentu (mis. Optimasi kode / kompiler / runtime).

Paul
sumber
4

Anda harus membuat analisis (biaya) untuk menghabiskan begitu banyak bulan kerja (dan itu selalu mitos :-)) untuk mendapatkan kecepatan eksekusi. Anda harus mengetahui berapa kali perangkat lunak ini akan digunakan dan berapa banyak orang sehingga Anda dapat memperkirakan perolehannya.

Aturan praktisnya, seperti biasa, adalah aturan 80/20 yang terkenal. Pada suatu saat itu hanya tidak menambah lagi untuk menghabiskan lebih banyak dan lebih banyak waktu dalam mendapatkan beberapa persentase (atau kurang) dari waktu berjalan. Tetapi Anda harus menganalisis.

Dan saya dengan tulus setuju dengan poster-poster di atas: pastikan API Anda dipikirkan dengan baik sehingga tidak perlu banyak perubahan dan pastikan kodenya portabel dan dapat dipelihara (pikirkan tentang harus menganalisis kembali suatu algoritma yang Anda tulis dan seluk-beluk) dioptimalkan sepuluh tahun yang lalu). Dan pastikan Anda menggunakan praktik pemrograman yang baik dan perpustakaan standar. Peluangnya masuk akal seseorang sudah memikirkan algoritma yang paling efisien untuk aplikasi Anda.

Mengutip Donald Knuth: "optimasi prematur adalah akar dari semua kejahatan". Jadi buat profil kode Anda, tetapi jangan terlalu cepat.

GertVdE
sumber
Apakah Anda mengacu pada aturan Prinsip Pareto (80/20)? Jika demikian, apakah maksud Anda bahwa kami harus memfokuskan upaya pengoptimalan pada 20% kode yang menghasilkan 80% dari perlambatan? Atau maksud Anda jika Anda hanya dapat mengharapkan peningkatan kecepatan 20%, maka itu tidak layak untuk dioptimalkan?
Paul
Tidak, saya hanya menggunakannya sebagai semacam prinsip, tidak persis 80/20. Pada saat tertentu, Anda akan menghabiskan banyak upaya untuk mendapatkan hanya beberapa persentase sehingga tidak ada gunanya lagi.
GertVdE
3

Beberapa saran tambahan:

  1. Sebelum melakukan optimalisasi program kerja, pastikan Anda memiliki satu set kasus uji yang baik yang membantu menjaga integritas kode. Tidak ada gunanya mendapatkan hasil yang salah lebih cepat.
  2. Jika pengoptimalan Anda membuat kode lebih mudah dibaca, pertahankan versi aslinya, setidaknya dalam bentuk komentar, tetapi lebih baik sebagai versi alternatif untuk dipilih pada waktu kompilasi dan waktu berjalan. Kebutuhan pengoptimalan Anda dapat berubah saat masalah dan mesin Anda berkembang, dan kode asli mungkin menjadi titik awal yang lebih baik untuk pengoptimalan yang akan Anda lakukan lima tahun dari sekarang.
  3. Jika versi yang dioptimalkan ternyata berdampak minimal, tetapi membuat kode menjadi kurang mudah dibaca, kurang universal, atau kurang stabil, kembali ke versi aslinya. Anda kehilangan lebih dari yang Anda dapatkan.
khinsen
sumber