Mengapa Semua Pengembang Perlu Memahami SIMD

 (mitchellh.com)
1 poin oleh GN⁺ 2 jam lalu | 1 komentar | Bagikan ke WhatsApp
  • SIMD bukan teknik rumit yang hanya untuk perangkat lunak dengan performa tertinggi, melainkan sarana optimasi sehari-hari yang mempercepat loop biasa dengan memproses data berurutan beberapa nilai sekaligus
  • Kode SIMD umum mengikuti struktur 5 tahap: broadcast konstanta, iterasi per vektor, operasi paralel, reduksi/penyimpanan hasil, dan penanganan ekor skalar
  • Loop pencarian code point di Ghostty membandingkan 4, 8, atau 16 u32 sekaligus, dan secara teoretis dapat meningkatkan throughput hingga 4x pada ARM NEON, 8x pada AVX2, dan 16x pada AVX-512
  • Pada desktop Intel dengan AVX2, throughput terminal secara keseluruhan menjadi sekitar 5x lebih cepat, dan bila tidak ada lebar vektor yang didukung atau masih ada input tersisa, loop skalar lama akan menangani seluruh input atau sisanya
  • Auto-vectorization dari compiler dapat melewatkan peluang bahkan pada loop sederhana, jadi sebaiknya periksa dulu output yang sudah dioptimalkan, tetapi untuk hot loop penting, SIMD eksplisit dapat menjaga perilaku dan performa tetap dapat diprediksi

Apa yang dilakukan SIMD

  • SIMD memungkinkan CPU memproses banyak nilai secara paralel dengan satu instruksi
    • Alih-alih membandingkan byte satu per satu, Anda bisa membandingkan 4, 8, atau lebih sekaligus
    • Loop seperti for (byte in bytes), for (character in string), for (value in array) punya peluang untuk diubah menjadi pemrosesan per lebar vektor
  • Jika datanya ratusan, ribuan, atau jutaan byte, Anda bisa memperoleh percepatan lokal 4x, 8x, atau lebih bergantung pada lebar paralelnya
  • Jika datanya hanya beberapa atau puluhan elemen, menerapkan SIMD tidak layak dilakukan
  • simdutf dan simdjson memakai teknik SIMD yang kompleks, tetapi SIMD sehari-hari tidak perlu serumit itu
  • Contohnya menggunakan Zig, tetapi struktur 5 tahap ini juga berlaku di bahasa lain, dan tiap bahasa memiliki cara berbeda dalam mendukung instruksi SIMD

Struktur 5 tahap yang berulang

  1. Broadcast konstanta yang diperlukan ke semua lane, dan jika perlu inisialisasi akumulator vektor
  2. Iterasi input sebesar lebar vektor sekaligus
  3. Jalankan perbandingan atau operasi aritmetika secara paralel di semua lane
  4. Reduksi atau simpan hasil vektor sesuai algoritme
  5. Tangani sisa yang tidak muat dalam vektor penuh dengan ekor skalar (scalar tail) dari loop lama
  • Jika sudah terbiasa dengan struktur ini, Anda bisa memecah loop biasa ke dalam 5 tahap yang sama sehingga menulis SIMD menjadi sesederhana loop skalar
  • Jika tidak bisa dinyatakan sederhana dengan struktur ini, untuk saat ini lebih tepat melewatkan penerapan SIMD

Loop pencarian nyata di Ghostty

  • Ghostty mengonsumsi data dari array code point yang sudah didekodekan sampai menemukan nilai 0xF atau lebih kecil
    • Sebagian besar data terminal adalah karakter biasa yang akan ditampilkan, jadi ini diproses berkelompok
    • Loop ini mencari akhir rentang yang bisa ditampilkan berikutnya secepat mungkin
  • Implementasi skalar aslinya memeriksa code point satu per satu
while (end < cps.len and cps[end] > 0xF) end += 1;
  • Implementasi vektornya memakai vektor umum tanpa intrinsic khusus CPU, dan menambah 12 baris kode dibanding implementasi skalar
  • Peningkatan throughput yang diharapkan sesuai dengan jumlah lane vektor
    • ARM NEON dan Apple Silicon: hingga 4x
    • AVX2, yang didukung sebagian besar CPU x86 modern: hingga 8x
    • AVX-512, yang didukung sebagian CPU Intel dan AMD Zen 4 ke atas: hingga 16x
  • Pada desktop Intel dengan AVX2, throughput keseluruhan yang diukur dari input program terminal hingga status terminal akhir menjadi sekitar 5x lebih cepat
    • Tidak semua percepatan teoretis tercapai karena ada pekerjaan tambahan di sekitar SIMD
  • Karakter kontrol C0 juga ada setelah 0xF, tetapi 0xF adalah ambang yang dipakai di jalur kode Ghostty ini
    • ESC dan urutan kontrol lain ditangani di jalur terpisah

Tahap 1: Broadcast konstanta

if (simd.lanes(u32)) |lanes| {
    const V = @Vector(lanes, u32);
    const threshold: V = @splat(0xF);
  • simd.lanes(u32) di Ghostty mengembalikan jumlah u32 yang bisa diproses CPU target secara bersamaan
    • Tiap nilainya disebut lane
    • ARM mengembalikan 4, AVX2 mengembalikan 8, dan AVX-512 mengembalikan 16
    • Jika tidak ada ukuran vektor yang bisa dipakai, fungsi ini mengembalikan null dan melewati kode SIMD
  • @Vector(lanes, u32) membuat tipe vektor dengan jumlah lane tersebut
    • Jika lanes adalah 8, maka satu V memuat 8 u32 yang bisa diproses paralel
  • Karena perbandingan vektor memerlukan kedua sisi berupa vektor, @splat(0xF) menggandakan 0xF ke semua lane
{ 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF }
  • Algoritme ini tidak memerlukan akumulator vektor, tetapi algoritme lain bisa menginisialisasi akumulator pada tahap ini

Tahap 2: Iterasi satu vektor demi satu vektor

while (end + lanes <= cps.len) : (end += lanes) {
    const values: V = cps[end..][0..lanes].*;
  • Jika lanes adalah 8, loop hanya masuk ketika masih tersisa setidaknya 8 nilai, lalu memuat 8 nilai itu ke values
  • Di akhir tiap iterasi, end ditambah bukan 1, melainkan sebesar jumlah lane
  • Karena harus bisa memuat vektor penuh, jika hanya tersisa 5 nilai maka vektor 8 lane tidak akan dibaca
  • Nilai yang tidak masuk ke vektor akan ditangani oleh ekor skalar di tahap 5

Tahap 3: Perbandingan paralel di semua lane

const greater_than_threshold = values > threshold;
  • Karena values dan threshold sama-sama vektor, > membandingkan tiap lane yang bersesuaian sebagai satu operasi vektor
  • Jika 8 lane, maka 8 perbandingan yang setara dengan cps[end] > 0xF dijalankan secara paralel
values:                 { 0x41, 0x42, 0x43, 0x0A, 0x44, 0x45, 0x46, 0x47 }
threshold:              {  0xF,  0xF,  0xF,  0xF,  0xF,  0xF,  0xF,  0xF }
greater_than_threshold: { true, true, true, false, true, true, true, true }
  • Tidak ada loop internal eksplisit, dan hasilnya adalah vektor yang berisi boolean per lane
  • Selain perbandingan, struktur yang sama juga bisa diterapkan pada penjumlahan, perkalian, nilai minimum, maksimum, dan operasi lain yang didukung tipe vektor
  • Perbandingannya sendiri adalah satu operasi vektor, tetapi pemuatan vektor, reduksi hasil, dan pencarian lane yang gagal tetap memerlukan instruksi tambahan

Tahap 4: Reduksi hasil vektor

if (@reduce(.And, greater_than_threshold)) continue;
  • @reduce(.And, ...) menggabungkan semua boolean dengan and menjadi satu boolean
  • Jika semua lane bernilai true, lanjut ke vektor berikutnya; jika ada satu saja false, cari posisi pasti yang gagal
const mask: std.meta.Int(.unsigned, lanes) = @bitCast(greater_than_threshold);
end += @ctz(~mask);
break;
  • @bitCast mengubah vektor boolean menjadi mask integer 1 bit per lane
    • 1 berarti nilainya lebih besar dari 0xF
    • 0 berarti perbandingannya gagal
  • Jika mask dibalik, perbandingan yang gagal menjadi 1, dan @ctz menghitung jumlah bit 0 sebelum 1 pertama
values:                 { 0x41, 0x42, 0x43, 0x0A, 0x44, 0x45, 0x46, 0x47 }
greater_than_threshold: { true, true, true, false, true, true, true, true }
mask:                   {    1,    1,    1,     0,    1,    1,    1,    1 }
~mask:                  {    0,    0,    0,     1,    0,    0,    0,    0 }
  • Dalam contoh ini, @ctz(~mask) mengembalikan 3, dan memindahkan end ke lane ke-3 tempat karakter kontrol pertama 0x0A berada
  • Reduksi hasil adalah bagian yang paling berbeda antaralgoritme dalam 5 tahap ini
    • Penjumlahan dapat mereduksi akumulator vektor menjadi satu angka
    • Transformasi dapat menyimpan seluruh vektor ke buffer output
    • Pencarian ini membuat mask bit untuk menemukan posisi lane tertentu

Tahap 5: Penanganan ekor skalar

while (end < cps.len and cps[end] > 0xF) end += 1;
  • Jika panjang input bukan kelipatan tepat dari lebar vektor, loop skalar asli akan menangani sisanya
  • Setelah loop vektor 8 lane, bisa tersisa 0 sampai 7 nilai
  • Pada CPU yang simd.lanes(u32)-nya null, bagian SIMD dilewati dan loop skalar menangani seluruh input
  • Implementasi asli sekaligus menangani pemrosesan sisa dan fallback kompatibilitas
  • Vektor umum hanya menghilangkan sintaks khusus CPU, bukan berarti menghapus pembuatan kode khusus CPU
    • Zig menerjemahkan operasi vektor ke instruction set yang aktif pada target

Yang terlewat oleh auto-vectorization

  • Compiler dapat melakukan auto-vectorization pada kode sederhana seperti loop aritmetika teratur tanpa alur kontrol yang rumit
  • Sebelum menulis SIMD manual, Anda perlu mengompilasi versi skalar dengan opsi optimasi dan memeriksa kode yang dihasilkan
  • Compiler produksi sering melewatkan peluang vektorisasi, dan auto-vectorization sudah diteliti selama puluhan tahun, tetapi riset terbaru pun masih berangkat dari masalah ini
  • Jika sebuah loop cukup penting hingga percepatan 5x berarti besar, Anda dapat menulis vektorisasinya secara eksplisit agar perilakunya tetap dapat diprediksi
    • Ini membantu menghindari situasi ketika perubahan kode yang tidak terkait atau pembaruan compiler diam-diam mengembalikan loop vektor menjadi loop skalar

Sejauh mana SIMD perlu dikuasai pengembang

  • Saat menemukan hot loop yang mencari, membandingkan, menghitung, atau mentransformasikan data berurutan dalam jumlah besar, Anda perlu bisa mempertimbangkan pemrosesan per lebar vektor
  • SIMD sehari-hari mengikuti bentuk yang teratur: menyiapkan konstanta, memuat vektor, operasi paralel, reduksi hasil, dan ekor skalar
  • Jika bahasanya mendukung SIMD dengan baik, Anda bisa meningkatkan performa tanpa harus memahami assembly atau detail spesifik CPU secara langsung
  • Tingkat yang dibutuhkan semua pengembang bukanlah teknik rumit ala simdutf atau simdjson, melainkan kemampuan mengenali peluang SIMD dan memanfaatkan struktur umumnya

Bacaan terkait

1 komentar

 
GN⁺ 2 jam lalu
Komentar Hacker News

  • Tulisan yang bagus, tetapi memulai dengan mengatakan bahwa SIMD mudah dipahami dan semudah menulis loop for, lalu dari contoh pertama langsung mengubah satu baris kode skalar menjadi 12 baris terasa kurang meyakinkan
    Lebih baik jujur saja mengatakan bahwa SIMD itu sulit, tetapi hasilnya sepadan. Jika sasarannya pemula, istilah khusus SIMD seperti broadcast seharusnya tidak dipakai tanpa penjelasan sejak tahap 1, sementara tahap 5 yang menjelaskan penanganan ekor skalar tersusun dengan baik

    • SIMD dan contoh pertamanya, alih-alih sulit, lebih terasa sebagai pekerjaan yang jauh lebih merepotkan
      Kita harus memahami berapa banyak item yang bisa diproses hardware sekaligus, mengelompokkan pekerjaan sesuai ukuran itu, membongkar lagi hasilnya, menangani item tersisa secara terpisah, dan membuat konstanta sebagai vektor yang diduplikasi. Masing-masing tidak sulit, tetapi menambah beban kerja dan membuatnya merepotkan
    • Saya pernah belajar Parallel-C, yang dibuat di tengah demam Transputer sekitar tahun 1990, bahasa yang menambahkan fitur pemrograman paralel ke C
      Fitur favorit saya adalah par(; ; ), yang di bawah beberapa kondisi batas tertentu memungkinkan compiler memparalelkan loop for secara otomatis
    • Saya cukup dekat dengan pembaca sasaran sehingga membacanya dengan tertarik, tetapi tingkat kesulitannya naik terlalu cepat sampai terasa mirip meme menggambar burung hantu yang terkenal itu
    • SIMD sendiri sederhana; yang terasa canggung adalah cara menggunakan operasi paralel data di bahasa skalar
    • Salah satu kesalahan terbesar dalam pendidikan teknis adalah menyatakan sesuatu itu sederhana demi menghilangkan rasa takut terhadap topiknya. Jangan bilang itu sederhana, tunjukkan saja
      Jika topiknya memang rumit, pecahlah menjadi bagian yang lebih kecil dan lebih sederhana, lalu susun urutannya dengan baik agar orang bisa menaiki kurva belajar yang curam, sekaligus meyakinkan mereka bahwa itu memang sepadan

  • Saran yang lebih baik adalah semua orang perlu memahami pemrograman array. Optimasi SIMD umumnya memerlukan cara berpikir itu, dan teknik yang benar-benar khusus untuk packed SIMD ternyata tidak terlalu banyak
    Pemrograman array memudahkan compiler melakukan auto-vectorization, sehingga meski tidak menulis SIMD secara langsung, biasanya tetap menghasilkan kode dengan performa baik

    • Pemrograman array yang melakukan semua perbandingan lebih dulu lalu baru mencari kegagalan pertama tidak terlalu membantu ketika rentang eksekusinya pendek. Karena tidak menyediakan penghentian dini dengan sendirinya, banyak waktu bisa terbuang untuk perbandingan yang tidak perlu
    • Saya tidak suka bahasa closed-source dan MATLAB juga punya banyak kekurangan, tetapi di kampus menulis kode tervectorisasi untuk simulasi numerik secara efisien terasa sangat alami
      Pengalaman saya tidak banyak, tetapi Julia tampaknya paling dekat dengan bahasa yang lebih modern dan ekspresif dengan kemampuan vektorisasi serupa

  • Beberapa hari terakhir saya mengoptimalkan operasi matriks dalam proyek bioinformatika dengan AVX-512, dan hasilnya sangat memuaskan
    Kebanyakan aplikasi terhambat oleh proses membaca dataset besar dari memori, jadi alih-alih membacanya berulang kali untuk beberapa operasi, semuanya bisa diselesaikan sekaligus dengan register AVX dan kernel terfusi. Peningkatan 5x itu umum terjadi, dan meski saya memakai intrinsic secara langsung, operasi umum menjadi sangat mudah jika memakai crate wide: https://docs.rs/wide/latest/wide/

  • Mayoritas besar developer sama sekali tidak perlu belajar SIMD. Saya heran kenapa ini dibuat seolah semua developer harus tahu ini agar dianggap developer sungguhan

    • Setidaknya ada gunanya mengetahui bahwa SIMD itu ada dan apa kemungkinannya. Sebagai developer, Anda pasti pernah menulis hot loop yang sekadar menjumlahkan atau membandingkan nilai sederhana, dan pengetahuan bahwa compiler bisa mengoptimalkannya sesuai arsitektur CPU target berguna dalam banyak situasi

  • Judulnya lebih baik diubah menjadi “semua orang harus tahu kapan SIMD tidak diterapkan”
    Compiler modern sangat bagus dalam vektorisasi, tetapi bisa tiba-tiba mundur ke kode skalar hanya karena satu asumsi atau satu percabangan yang bergantung pada data. Mengetahui cara memeriksa laporan optimasi compiler mungkin lebih berharga daripada mengetahui cara menulis SIMD

    • Solusi untuk auto-vectorization yang buruk adalah menulis kode SIMD secara langsung, jadi saya ragu apakah mengetahui cara melihat laporan optimasi benar-benar lebih berharga dari itu
      Kalau cuma bisa mengidentifikasi masalahnya, akhirnya mentok di “sayang sekali”
    • Ini benar-benar baru saja terjadi: https://xcancel.com/mitchellh/status/2079672171321081908#m

  • Tahun lalu saya mulai mempelajari SIMD x86 dan ARM sambil membuat synthesizer audio: https://github.com/seclorum/SIMDSynth
    Arsitektur synthesizer multi-timbre dan polifonik sangat cocok untuk mempelajari prinsip SIMD karena menerapkan pemrosesan yang sama ke beberapa aliran data. Namun debugging cukup sulit, sehingga saya sangat membutuhkan simulator yang bisa membantu memahami status tiap pipeline pemrosesan, dan menyelidiki alat SIMD tampaknya memerlukan investasi besar lagi

  • Tulisannya bagus dan akan menyenangkan jika lebih banyak bahasa mendukung SIMD, tetapi dalam keadaan dua bahasa paling populer masih tidak mendukung SIMD secara native, ungkapan “semua programmer harus tahu” terasa agak aneh

    • Sulit memastikan bahwa bahasa paling populer juga adalah bahasa yang paling banyak dipakai oleh software engineer yang menjadi sasaran tulisan seperti ini

  • Meski Anda tidak berniat menulis SIMD sendiri atau berencana menyerahkannya ke AI, Anda tetap perlu tahu pekerjaan seperti apa yang bisa dipercepat dengan SIMD di hardware tertentu. Dengan begitu Anda bisa merancang algoritme dan struktur kode agar memungkinkan penerapan SIMD
    Dampak dependensi data, biaya memperlebar lebar elemen vektor dan cara menghindarinya, cara mengubah kondisi dan percabangan menjadi mask, serta sifat seperti “tidak ada instruksi pembagian” jauh lebih mudah dipahami jika pernah sedikit saja memakai SIMD secara langsung

    • Kapan SIMD menjadi lebih cepat tidak cukup sering dibahas
      SIMD bekerja baik saat memeriksa atau mengubah data kontinu berukuran besar sekaligus, tetapi jika Anda harus mengambil keputusan setiap beberapa byte input, performanya bisa sama saja atau malah lebih lambat daripada pendekatan skalar. SIMD bukan tombol akselerasi ajaib

  • Ini video yang berguna ketika Casey Muratori menjelaskan bagaimana tim pengembang The Witness menyelesaikan masalah performa nyata dengan SIMD: https://www.youtube.com/watch?v=Ge3aKEmZcqY

    • Presentasinya luar biasa, tetapi videonya terlalu panjang untuk direkomendasikan ke orang lain, jadi akan bagus jika ada versi tulisan yang fokus pada intinya
      Ini contoh bagus integrasi vertikal demi performa: setelah memahami kenapa abstraksi umum itu ada dan kenapa ia harus bersifat general-purpose, mereka menunjukkan bagaimana untuk kasus penggunaan tertentu orang bisa mengintegrasikan semuanya secara vertikal dari definisi masalah sampai SIMD dan mendapat keuntungan besar

  • Sebelum masuk ke mikro-optimalisasi seperti SIMD, struktur data dan pola akses harus ditinjau serius terlebih dahulu
    Dulu saya menerapkan SIMD pada kode Zig, tetapi model struktur datanya justru berlawanan dengan arah optimisasi, seperti memasang ban balap berperforma tinggi pada mobil rongsokan dengan mesin rusak. Itu adalah contoh klasik optimisasi prematur: tidak mengukur performa dan bahkan tidak mempertimbangkan lokasi alokasi memori
    Sekarang saya melihat data seperti tabel SQL dan merancang strukturnya dengan berfokus pada kemungkinan primary key serta pola akses. Dulu saya memakai tree yang menunjuk ke struct lain di heap, sehingga sekaligus menanggung kelemahan linked list, fragmentasi dari banyak vector di heap, dan biaya pembuatan/pembebasan yang lambat; bahkan Drop saja memakan porsi besar dari waktu eksekusi
    Tree selalu bisa dilinearkan, jadi saya meninjau pola akses/penyisipan, apakah itu benar-benar tree atau graf lain, dan apakah sebaiknya disimpan dalam Vec atau struct dari beberapa Vec. Hasilnya, kode menjadi lebih cepat dan lebih sederhana, data terkumpul dalam array homogen sehingga lebih mudah memanfaatkan optimisasi SIMD dari compiler dan cache L1, dan saat perlu saya juga bisa menulis kode SIMD tanpa branch secara langsung
    Referensi terkait: https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que...

    • Untuk membuat hot loop cepat dengan SIMD, penataan data dan struktur yang ramah cache adalah kuncinya
      Pada bottleneck yang nyata, alokasi memori, lookup virtual function table, dan indirection yang berlebihan harus dihindari. Bahkan vector di C++ juga tidak selalu menjadi pilihan terbaik jika bisa memicu alokasi yang tak terduga
    • Ini adalah masalah yang selalu saya hadapi sebagai performance engineer. Performa dimulai dari arsitektur, dan pada hot path dengan penataan data yang buruk, ada batas untuk performa yang bisa diperas
      Sebaliknya, kode berorientasi data hampir selalu mudah mendukung threading dan SIMD
    • Lebih mendasar lagi, pola akses memori itu penting
      Menariknya, kode CPU pada akhirnya juga ditulis dengan gaya GPU, dan salah satu caranya adalah memakai struct of arrays ala Parquet alih-alih array of objects
    • Tabel adalah cara yang efisien untuk mengimplementasikan graf umum, dan kecuali grafnya bisa dispesialisasi, itu adalah representasi terbaik yang saya ketahui