Biaya pemeliharaan basis kode pemrograman SIMD

Pertanyaan:

Konsensus industri perangkat lunak adalah bahwa kode yang bersih dan sederhana merupakan dasar bagi kelangsungan jangka panjang dari basis kode dan organisasi yang memilikinya. Properti ini mengarah pada biaya perawatan yang lebih rendah dan peningkatan kemungkinan basis kode dilanjutkan.

Namun, kode SIMD berbeda dari kode aplikasi umum, dan saya ingin tahu apakah ada konsensus serupa mengenai kode bersih dan sederhana yang berlaku khusus untuk kode SIMD.

Latar belakang pertanyaan saya.

Saya menulis banyak kode SIMD (instruksi tunggal, banyak data) untuk berbagai tugas pemrosesan gambar dan analisis. Baru-baru ini saya juga harus mem-port sejumlah kecil fungsi-fungsi ini dari satu arsitektur (SSE2) ke yang lain (ARM NEON).

Kode ini ditulis untuk perangkat lunak yang dibungkus susut, oleh karena itu tidak dapat bergantung pada bahasa yang dipatenkan tanpa hak redistribusi yang tidak dibatasi seperti MATLAB.

Contoh struktur kode khas:

• Menggunakan tipe matriks OpenCV ( Mat) untuk semua memori, buffer dan manajemen seumur hidup.
• Setelah memeriksa ukuran (dimensi) argumen input, pointer ke alamat mulai dari setiap baris piksel diambil.
• Jumlah piksel, dan alamat mulai dari setiap baris piksel dari setiap matriks input dilewatkan ke beberapa fungsi C ++ tingkat rendah.
• Fungsi C ++ tingkat rendah ini menggunakan SIMD intrinsik (untuk Arsitektur Intel , dan ARM NEON ), memuat dari dan menyimpan ke alamat penunjuk mentah.
• Karakteristik dari fungsi C ++ tingkat rendah ini:
  • Satu dimensi secara eksklusif (berurutan dalam memori)
  • Tidak berurusan dengan alokasi memori.
    (Setiap alokasi, termasuk temporari, ditangani oleh kode luar menggunakan fasilitas OpenCV.)
  • Rentang panjang nama simbol (intrinsik, nama variabel, dll) kira-kira 10 - 20 karakter, yang cukup berlebihan.
    (Berbunyi seperti celoteh techno.)
  • Penggunaan kembali variabel SIMD tidak disarankan karena kompiler cukup bermasalah dalam kode parsing yang benar yang tidak ditulis dalam gaya pengkodean "tugas tunggal".
    (Saya telah mengajukan beberapa laporan bug kompiler.)

Apa aspek pemrograman SIMD akan menyebabkan diskusi berbeda dari kasus umum? Atau, mengapa SIMD berbeda?

Dalam hal biaya pengembangan awal

• Sudah diketahui bahwa biaya pengembangan awal dari kode C ++ SIMD dengan kinerja yang baik adalah sekitar 10x - 100x (dengan margin lebar) dibandingkan dengan kode C ++ yang ditulis dengan santai .
• Seperti tercantum dalam jawaban untuk Memilih antara kode kinerja vs yang dapat dibaca / bersih? , sebagian besar kode (termasuk kode yang ditulis dengan santai dan kode SIMD) pada awalnya tidak bersih atau cepat .
• Peningkatan evolusi dalam kinerja kode (baik dalam skalar dan kode SIMD) tidak disarankan (karena dilihat sebagai semacam pengerjaan ulang perangkat lunak ), dan biaya dan manfaatnya tidak dilacak.

Dalam hal kecenderungan
(misalnya prinsip Pareto, alias aturan 80-20 )

• Bahkan jika pemrosesan gambar hanya terdiri dari 20% dari sistem perangkat lunak (baik dalam ukuran kode dan fungsionalitas), pemrosesan gambar relatif lambat (bila dilihat sebagai persentase waktu CPU yang dihabiskan), menghabiskan lebih dari 80% waktu.
  • Ini disebabkan oleh efek ukuran data: Ukuran gambar tipikal diukur dalam megabita, sedangkan ukuran tipikal data non-gambar diukur dalam kilobyte.
• Di dalam kode pemrosesan gambar, seorang programmer SIMD dilatih untuk secara otomatis mengenali kode 20% yang terdiri dari hotspot dengan mengidentifikasi struktur loop dalam kode C ++. Dengan demikian, dari perspektif programmer SIMD, 100% dari "kode yang penting" adalah bottleneck kinerja.
• Seringkali dalam sistem pemrosesan gambar, ada beberapa hotspot dan mengambil proporsi waktu yang sebanding. Misalnya, mungkin ada 5 hotspot masing-masing mengambil (20%, 18%, 16%, 14%, 12%) dari total waktu. Untuk mencapai perolehan kinerja tinggi, semua hotspot harus ditulis ulang dalam SIMD.
  • Ini diringkas sebagai aturan balon-popping : balon tidak bisa muncul dua kali.
  • Misalkan ada beberapa balon, misalkan 5 balon. Satu-satunya cara untuk memusnahkan mereka adalah dengan membuangnya satu per satu.
  • Setelah balon pertama muncul, 4 balon sisanya sekarang terdiri dari persentase waktu eksekusi yang lebih tinggi.
  • Untuk memperoleh keuntungan lebih lanjut, seseorang harus meledakkan balon lainnya.
    (Ini bertentangan dengan aturan optimasi 80-20: hasil ekonomis yang baik dapat dicapai setelah 20% dari buah-buahan yang paling rendah harganya dipetik.)

Dalam hal keterbacaan dan pemeliharaan

• Kode SIMD jelas sulit dibaca.

  • Ini benar bahkan jika seseorang mengikuti setiap praktik terbaik rekayasa perangkat lunak misalnya penamaan, enkapsulasi, pembetulan-benar (dan membuat efek samping menjadi jelas), dekomposisi fungsi, dll.
  • Ini berlaku bahkan untuk programmer SIMD yang berpengalaman.

• Kode SIMD optimal sangat berkerut, (lihat komentar) dibandingkan dengan kode prototipe C ++ yang setara.

  • Ada banyak cara untuk memutarbalikkan kode SIMD, tetapi hanya 1 dari 10 upaya yang akan mencapai hasil yang dapat diterima dengan cepat.
  • (Yaitu, dalam nada keuntungan kinerja 4x-10x untuk membenarkan biaya pengembangan yang tinggi. Bahkan keuntungan yang lebih tinggi telah diamati dalam praktiknya.)

(Catatan)
Ini adalah tesis utama dari proyek MIT Halide - mengutip judul makalah ini kata demi kata:

"decoupling algoritme dari jadwal untuk memudahkan optimalisasi jaringan pemrosesan gambar"

Dalam hal penerapan ke depan

• Kode SIMD sangat terkait dengan arsitektur tunggal. Setiap arsitektur baru (atau setiap pelebaran register SIMD) membutuhkan penulisan ulang.
• Berbeda dengan mayoritas pengembangan perangkat lunak, setiap bagian dari kode SIMD biasanya ditulis untuk satu tujuan yang tidak pernah berubah.
  (Dengan pengecualian porting ke arsitektur lain.)
• Beberapa arsitektur mempertahankan kompatibilitas mundur sempurna (Intel); beberapa gagal dengan jumlah yang sepele (ARM AArch64, ganti vtbldengan vtblq) tetapi cukup untuk menyebabkan beberapa kode gagal dikompilasi.

Dalam hal keterampilan dan pelatihan

• Tidak jelas prasyarat pengetahuan apa yang diperlukan untuk melatih programmer baru untuk menulis dan memelihara kode SIMD.
• Lulusan perguruan tinggi yang telah mempelajari pemrograman SIMD di sekolah tampaknya membenci dan menganggapnya sebagai jalur karier yang tidak praktis.
• Membaca pembongkaran dan profil kinerja tingkat rendah dikutip sebagai dua keterampilan mendasar untuk menulis kode SIMD kinerja tinggi. Namun, tidak jelas bagaimana cara sistematis melatih programmer dalam dua keterampilan ini.
• Arsitektur CPU modern (yang berbeda secara signifikan dari apa yang diajarkan dalam buku teks) membuat pelatihan menjadi lebih sulit.

Dalam hal kebenaran dan biaya terkait cacat

• Fungsi pemrosesan SIMD tunggal sebenarnya cukup kohesif sehingga seseorang dapat membangun kebenaran dengan:
  • Menerapkan metode formal (dengan pena-dan-kertas) , dan
  • Memverifikasi rentang bilangan bulat keluaran (dengan kode prototipe dan dilakukan di luar waktu berjalan) .
• Proses verifikasi, bagaimanapun, sangat mahal (menghabiskan 100% waktu pada tinjauan kode dan 100% pada pengecekan model prototipe), yang tiga kali lipat biaya pengembangan yang sudah mahal dari kode SIMD.
• Jika suatu bug berhasil menyelinap melalui proses verifikasi ini, hampir tidak mungkin untuk "memperbaiki" (memperbaiki) kecuali untuk mengganti (menulis ulang) fungsi yang diduga cacat.
• Kode SIMD menderita tumpul cacat pada kompiler C ++ (mengoptimalkan pembuat kode).
  • Kode SIMD yang dihasilkan menggunakan templat ekspresi C ++ juga sangat menderita dari kerusakan kompiler.

Dalam hal inovasi yang mengganggu

• Banyak solusi telah diajukan dari kalangan akademisi, tetapi sedikit yang melihat penggunaan komersial yang meluas.

  • MIT Halide
  • Stanford Darkroom
  • NT2 (Numerical Template Toolbox) dan Boost.SIMD terkait

• Perpustakaan dengan penggunaan komersial yang tersebar luas tampaknya tidak terlalu mendukung SIMD.

  • Pustaka sumber terbuka tampaknya suam-suam kuku terhadap SIMD.
    • Baru-baru ini saya memiliki pengamatan langsung tentang hal ini setelah membuat profil sejumlah besar fungsi OpenCV API, pada versi 2.4.9.
    • Banyak perpustakaan pengolah gambar lainnya yang telah saya profil juga tidak menggunakan SIMD secara berlebihan, atau mereka kehilangan hotspot yang sebenarnya.
  • Perpustakaan komersial tampaknya menghindari SIMD sama sekali.
    • Dalam beberapa kasus, saya bahkan melihat pustaka pemrosesan gambar mengembalikan kode yang dioptimalkan SIMD di versi yang lebih lama ke kode non-SIMD di versi yang lebih baru, yang menghasilkan regresi kinerja yang parah.
      (Respons vendor adalah bahwa perlu untuk menghindari bug kompiler.)

Pertanyaan Programmer ini: Apakah kode latensi rendah terkadang harus "jelek"? terkait, dan saya sebelumnya menulis jawaban untuk pertanyaan itu untuk menjelaskan poin pandangan saya beberapa tahun yang lalu.

Namun, jawaban itu cukup banyak "peredaan" ke sudut pandang "optimasi prematur", yaitu ke sudut pandang bahwa:

• Semua optimasi prematur menurut definisi (atau, sifatnya jangka pendek ), dan
• Satu-satunya optimasi yang memiliki manfaat jangka panjang adalah menuju kesederhanaan.

Tetapi sudut pandang seperti itu diperdebatkan dalam artikel ACM ini .

Semua itu membuat saya bertanya:
Kode SIMD berbeda dari kode aplikasi umum, dan saya ingin tahu apakah ada konsensus industri yang sama mengenai nilai kode yang bersih dan sederhana untuk kode SIMD.

Saya tidak menulis banyak kode SIMD untuk diri saya sendiri, tetapi banyak kode assembler beberapa dekade yang lalu. AFAIK menggunakan SIMD intrinsik pada dasarnya adalah pemrograman assembler, dan seluruh pertanyaan Anda dapat diulangi hanya dengan mengganti "SIMD" dengan kata "assembly". Misalnya, poin yang sudah Anda sebutkan, sukai

• kode ini membutuhkan 10x hingga 100x untuk berkembang daripada "kode tingkat tinggi"

• itu terikat pada arsitektur tertentu

• kode tidak pernah "bersih" atau mudah untuk di refactor

• Anda membutuhkan ahli untuk menulis dan memeliharanya

• debugging dan pemeliharaan sulit, berkembang sangat sulit

sama sekali tidak "istimewa" untuk SIMD - poin-poin ini berlaku untuk semua jenis bahasa rakitan, dan semuanya adalah "konsensus industri". Dan kesimpulan dalam industri perangkat lunak juga hampir sama dengan assembler:

• jangan menulisnya jika Anda tidak perlu - gunakan bahasa tingkat tinggi di mana saja memungkinkan dan biarkan kompiler melakukan kerja keras

• jika kompiler tidak mencukupi, setidaknya merangkum bagian "tingkat rendah" di beberapa perpustakaan, tetapi hindari untuk menyebarkan kode ke seluruh program Anda

• karena hampir tidak mungkin untuk menulis assembler "mendokumentasikan sendiri" atau kode SIMD, cobalah untuk menyeimbangkan ini dengan banyak dokumentasi.

Tentu saja, memang ada perbedaan dengan situasi dengan kode perakitan "klasik" atau kode mesin: hari ini, kompiler modern biasanya menghasilkan kode mesin berkualitas tinggi dari bahasa tingkat tinggi, yang seringkali lebih baik dioptimalkan daripada kode assembler yang ditulis secara manual. Untuk arsitektur SIMD yang populer saat ini, kualitas kompiler yang tersedia adalah AFAIK jauh di bawah itu - dan mungkin tidak akan pernah mencapai itu, karena vektorisasi otomatis masih menjadi topik penelitian ilmiah. Lihat, misalnya, artikel ini yang menguraikan perbedaan dalam opimisasi antara kompiler dan manusia, memberikan pendapat bahwa mungkin sangat sulit untuk membuat kompiler SIMD yang baik.

Seperti yang telah Anda jelaskan dalam pertanyaan Anda, ada juga masalah kualitas dengan perpustakaan mutakhir. Jadi IMHO yang terbaik yang bisa kita harapkan adalah bahwa di tahun-tahun mendatang kualitas kompiler dan perpustakaan akan meningkat, mungkin perangkat keras SIMD harus berubah menjadi lebih "kompiler ramah", mungkin bahasa pemrograman khusus yang mendukung vektorisasi yang lebih mudah (seperti Halide, yang Anda sebutkan dua kali) akan menjadi lebih populer (bukankah itu sudah menjadi kekuatan Fortran?). Menurutnya Wikipedia , SIMD menjadi "produk massal" sekitar 15 hingga 20 tahun yang lalu (dan Halide berusia kurang dari 3 tahun, ketika saya menafsirkan dokumen dengan benar). Bandingkan ini dengan kompiler waktu untuk bahasa rakitan "klasik" yang diperlukan untuk menjadi dewasa. Menurut artikel Wikipedia inibutuh hampir 30 tahun (dari ~ 1970 hingga akhir 1990-an) hingga kompiler melebihi kinerja pakar manusia (dalam memproduksi kode mesin non-paralel). Jadi kita mungkin harus menunggu lebih dari 10 hingga 15 tahun sampai hal yang sama terjadi pada kompiler yang mendukung SIMD.

Organisasi saya telah menangani masalah yang pasti ini. Produk kami ada di ruang video, tetapi sebagian besar kode yang kami tulis adalah pemrosesan gambar yang juga berfungsi untuk gambar diam.

Kami "memecahkan" (atau mungkin "menangani") masalahnya dengan menulis kompiler kami sendiri. Ini tidak semanis kedengarannya pada awalnya. Ada set input terbatas. Kita tahu bahwa semua kode berfungsi pada gambar, sebagian besar gambar RGBA. Kami membuat beberapa kendala, seperti itu buffer input dan output tidak pernah bisa tumpang tindih, jadi tidak ada pointer alias. Hal-hal seperti itu.

Kami kemudian menulis kode kami di OpenGL Shading Language (glsl). Ia dikompilasi ke kode skalar, SSE, SSE2, SSE3, AVX, Neon, dan tentu saja glsl aktual. Ketika kami perlu mendukung platform baru, kami memperbarui compiler ke kode output untuk platform itu.

Kami juga melakukan pemasangan ubin gambar untuk meningkatkan koherensi cache, dan hal-hal seperti itu. Tetapi dengan menjaga pemrosesan gambar ke kernel kecil, dan menggunakan glsl (yang bahkan tidak mendukung pointer) kami sangat mengurangi kerumitan kompilasi kode.

Pendekatan ini bukan untuk semua orang, dan memiliki masalah sendiri (misalnya, Anda perlu memastikan kebenaran kompiler). Tapi itu berhasil dengan cukup baik bagi kami.

Tampaknya tidak menambahkan terlalu banyak overhead pemeliharaan jika Anda mempertimbangkan untuk menggunakan bahasa tingkat yang lebih tinggi:

Vector<float> values = GetValues();
Vector<float> increment = GetIncrement();

// Perform addition as a vector operation:
List<float> result = (values + increment).ToList();

vs.

List<float> values = GetValues();
List<float> increment = GetIncrement();

// Perform addition as a monadic sequence operation:
List<float> result = values.Zip(increment, (v, i) => v + i).ToList();

Tentu saja Anda harus menghadapi keterbatasan perpustakaan, tetapi Anda tidak akan memeliharanya sendiri. Bisa jadi keseimbangan yang baik antara biaya perawatan dan kinerja menang.

http://blogs.msdn.com/b/dotnet/archive/2014/04/07/the-jit-finally-proposed-jit-and-simd-are-getting-married.aspx

http://blogs.msdn.com/b/dotnet/archive/2014/05/13/update-to-simd-support.aspx

Saya telah melakukan pemrograman perakitan di masa lalu, bukan pemrograman SIMD baru-baru ini.

Sudahkah Anda mempertimbangkan untuk menggunakan kompiler yang sadar SIMD seperti Intel? Apakah Panduan Vektorisasi dengan Penyusun Intel® C ++ menarik?

Beberapa komentar Anda seperti "balon-popping" menyarankan menggunakan kompiler (untuk mendapatkan manfaat jika Anda tidak memiliki satu hot-spot).