Merancang Algoritma SIMD dari Nol

Perancangan algoritma SIMD

• Penjelasan tentang optimasi SIMD: SIMD berarti single instruction, multiple data, dan perlu berpikir seperti perancang sirkuit.
• SIMD sering dibahas dalam konteks performa dan HPC (komputasi berkinerja tinggi), tetapi bukan topik yang akrab bagi pemula.
• Di sebagian besar bahasa pemrograman, API pemrograman SIMD sulit digunakan.
• Algoritma SIMD sulit dipahami dengan pola pikir pemrograman prosedural, dan pemrograman fungsional dapat membantu.
• Isi utama membahas vb64, yang mengimplementasikan codec base64 menggunakan library std::simd milik Rust.

Batas fisik

• Komputer ada di dunia nyata dan terikat oleh hukum fisika.
• Pada era awal komputasi, performa bisa ditingkatkan dengan membeli komputer baru.
• Efek penskalaan Dennard runtuh, sehingga transistor yang lebih kecil berarti konsumsi daya yang lebih tinggi.
• Menambah jumlah core menjadi tren baru. Performa CPU dapat ditingkatkan melalui multithreading, tetapi ada overhead sinkronisasi.

Lambatnya kode prosedural

• Core komputer modern tidak mengeksekusi kode baris demi baris.
• Melalui paralelisme tingkat instruksi, beberapa operasi dapat dijalankan sekaligus jika tidak ada ketergantungan data.
• Paralelisme meningkat ketika compiler dapat menyelesaikan bahaya data.
• Percabangan dan operasi memori menimbulkan stall, dan ini membuat kode menjadi lambat.

SIMD dan lane

• SIMD dan vektor sering digunakan sebagai sinonim.
• Instruksi SIMD menggunakan vektor, yaitu array angka berukuran tetap, sebagai unit dasar.
• Setiap elemen vektor disebut lane, dan vektor SIMD biasanya berukuran kecil.

Operasi pada vektor nyata

• Vektor SIMD menyediakan operasi yang lebih kompleks daripada register biasa.
• Register vektor mendukung beragam operasi seperti operasi bit, aritmetika per-lane, perbandingan per-lane, shuffle, dan lainnya.
• Shuffle penting dalam pemrograman SIMD untuk memindahkan data ke posisi yang tepat.

Fungsi bawaan dan pemilihan instruksi

• Operasi yang tersedia saat menulis kode SIMD berbeda-beda tergantung arsitektur.
• Compiler menyelesaikan masalah pemilihan instruksi, yaitu menentukan instruksi mana yang akan digunakan untuk operasi yang diminta pengguna.
• Menulis kode SIMD yang portabel itu rumit, tetapi melalui deteksi fitur saat runtime, dimungkinkan menghasilkan kode optimal di berbagai prosesor.

Parsing dengan SIMD

• Teks dapat di-parse menggunakan SIMD, dan hasilnya bisa sangat cepat.
• Implementasi decoding base64 dengan SIMD dapat dijadikan contoh.
• Menghilangkan semua percabangan adalah inti dari proses membuat versi SIMD.

Pendapat GN⁺

Hal terpenting dari tulisan ini adalah bahwa pemrograman SIMD dapat meningkatkan performa dengan memproses data secara paralel, berbeda dari pendekatan pemrograman prosedural tradisional. SIMD sangat penting di bidang komputasi berkinerja tinggi, dan memahami cara menggunakan SIMD secara efektif dalam bahasa pemrograman modern seperti Rust bisa menjadi topik yang sangat menarik bagi software engineer. Ini karena melalui SIMD, kita dapat mempelajari cara mengoptimalkan algoritma yang kompleks dan mengatasi keterbatasan perangkat keras nyata.

[GN⁺]

Opini Hacker News

• Artikel yang sangat bagus untuk melihat contoh penggunaan SIMD portabel. Setelah mencoba mereproduksi benchmark di sistem Zen 3, saya mendapatkan peningkatan kecepatan yang sama. Di M1 mbp, peningkatan performa naik secara bertahap hingga maksimal 2x pada panjang input 110 byte. Keuntungannya memang lebih kecil daripada di x86_64, tetapi targetnya bisa dibilang tercapai. Namun, ini juga menegaskan bahwa Rust agak kurang nyaman untuk pekerjaan terkait SIMD dan pointer, serta rekayasa performa secara umum.
• Kadang mengejutkan bahwa meskipun sudah berusaha menulis program sebaik mungkin dalam C++, versi yang menggunakan SIMD bisa menunjukkan performa lebih dari 10x lebih cepat. Portabilitas kodenya memang berkurang, tetapi saya berharap compiler bisa melakukan auto-vectorization dengan lebih baik. Akan bagus juga jika bahasa pemrograman menambahkan dukungan anotasi agar urutan operasi tertentu bisa diatur ulang.
• Menunjukkan bahwa compiler gagal mengoptimalkan implementasi popcount tertentu menjadi satu instruksi, meskipun untuk implementasi lain hal itu kadang memungkinkan.
• _mm256_cvtps_epu32 bukan instruksi AVX2, melainkan instruksi AVX-512, dan pada AVX1 integer hadir dalam bentuk signed, sehingga instruksi yang dimaksud adalah _mm256_cvtps_epi32.
• Saya sangat suka minimap kecil di sisi kanan.
• Menilai ISPC lebih baik daripada menambahkan SIMD ke C++ atau Rust. Selain itu, ISPC juga mendukung dynamic dispatch, yang cukup sulit diimplementasikan sendiri.
• Mengajukan pertanyaan tentang bagaimana perbandingannya dengan fastbase64, sekaligus menyatakan ingin berbagi sikap optimistis penulis terhadap library SIMD portabel.
• Tulisan yang luar biasa, memberi kesan bahwa saya sendiri rasanya tidak akan pernah bisa menjadi sepintar ini.
• Disebutkan bahwa contoh pertama implementasi popcnt yang tidak divektorisasi menghasilkan "kode yang, terus terang saja, konyol", tetapi jika dikompilasi dalam mode rilis untuk target CPU native, tampaknya fungsi itu tetap berhasil divektorisasi dengan cukup baik.
• Mengajukan pertanyaan tentang apa keanehan paling mengejutkan saat memeriksa kode yang dihasilkan dari upaya Rust Simd yang cukup bagus ini.