Pengenalan SIMD

Lane vektor dan paralelisme data: satu instruksi yang memproses banyak nilai dalam waktu yang sama.

Daftar isi

Satu instruksi SIMD memproses banyak nilai dalam waktu yang sama, sehingga paralelisme menjadi bagian dari instruksi itu sendiri dan bukan urusan banyak thread. Topik ini membahas register vektor dan pembagian lane, perbedaan paralelisme data dengan paralelisme tingkat instruksi, emulasi instruksi penjumlahan vektor dengan 4 lane dan 8 lane, serta ekstensi SIMD nyata pada prosesor masa kini. Setelah membacanya, satu instruksi yang menjumlahkan empat pasang nilai dapat dibaca sebagai empat operasi serentak pada empat lane register yang sama.

Satu instruksi, banyak lane#

SIMD (Single Instruction, Multiple Data) adalah gaya instruksi yang menerapkan satu operasi atas banyak nilai sekaligus. Tempat penyimpanannya adalah register vektor yang lebar, umumnya 128 bit, 256 bit, atau 512 bit, sedangkan register biasa hanya menampung satu nilai untuk satu operasi. Register vektor terbagi menjadi lane, yaitu sel berukuran tetap yang masing-masing menampung satu nilai dan memiliki jalur hitungnya sendiri. Register 128 bit memuat empat lane berukuran 32 bit, sehingga satu instruksi aritmetika melibatkan empat pasang nilai. Lebar register menentukan jumlah pasangan yang tercakup dalam satu instruksi, dan nilainya berbeda antararsitektur.

Diagram berikut memperlihatkan satu instruksi vadd yang menjumlahkan dua register 128 bit. Setiap pasangan nilai bertemu pada lane yang sama, dan register hasil mengambil satu nilai dari setiap lane.

Satu instruksi vadd menjumlahkan empat pasang nilai secara serentak, satu pasangan per lane

Penjumlahan pada diagram itu berlangsung serentak, bukan empat instruksi yang mengantri. Perbedaannya terasa pada jumlah instruksi yang dikerjakan, yaitu empat penjumlahan selesai dalam satu kali langkah instruksi, sedangkan cara biasa membutuhkan empat instruksi penjumlahan yang dijalankan berturut-turut.

Paralelisme data versus paralelisme instruksi#

Paralelisme yang dikerjakan SIMD disebut paralelisme data (data parallelism), yaitu satu operasi yang sama diterapkan atas banyak elemen data. Pola ini muncul pada pemrosesan citra, sinyal suara, dan statistik deret angka, karena operasinya seragam untuk setiap elemen. Bila deretnya berisi ribuan nilai, instruksi vadd 4 lane cukup diulang dengan register yang memuat empat elemen berikutnya, sehingga jumlah instruksi yang dibutuhkan turun menjadi seperempat.

Paralelisme tingkat instruksi pada modul ini bekerja dengan cara yang berbeda. Pipeline, superscalar, dan out-of-order menyembunyikan latensi dengan menumpang instruksi yang berbeda dari satu aliran program, sedangkan SIMD memperlebar isi satu instruksi. Keduanya bekerja pada satu inti yang sama dan saling melengkapi, karena instruksi vadd melewati pipeline seperti instruksi lain, tetapi membawa empat hasil dalam satu kali lewat.

Batasan paralelisme data juga jelas, yaitu hanya cocok untuk kerja yang seragam atas data yang banyak. Program dengan percabangan yang berbeda untuk setiap elemen tidak memperoleh manfaat apa pun, dan SIMD bukan pengganti multithreading yang mendistribusikan pekerjaan ke beberapa inti sekaligus.

Emulasi vadd dengan 4 lane dan 8 lane#

Skrip berikut meniru instruksi vadd atas dua vektor berisi delapan nilai. Pemanggilan pertama meniru register 4 lane yang hanya menjangkau empat nilai pertama, sedangkan pemanggilan kedua meniru register 8 lane yang menyelesaikan seluruh vektor dalam satu instruksi. Keluarannya dicetak per lane. Python menjalankan emulasi ini secara berurutan, sedangkan perangkat keras yang sesungguhnya mengisi seluruh lane dalam satu langkah, dan kesenjangan itulah yang ingin diperlihatkan.

python simd.py

# Emulasi instruksi vadd SIMD dengan register 4 lane dan 8 lane.
# Python mengerjakan perhitungan ini secara berurutan, sedangkan
# perangkat keras yang sesungguhnya mengisi seluruh lane sekaligus.

def vadd(jumlah_lane, vektor_a, vektor_b):
    """Satu instruksi vadd: setiap lane menjumlahkan satu pasangan nilai."""
    potongan_a = vektor_a[:jumlah_lane]
    potongan_b = vektor_b[:jumlah_lane]
    hasil = [a + b for a, b in zip(potongan_a, potongan_b)]
    print(f"instruksi vadd pada register {jumlah_lane} lane:")
    for i, (a, b, c) in enumerate(zip(potongan_a, potongan_b, hasil)):
        print(f"  lane {i}: {a:2d} + {b:2d} = {c:3d}")
    return hasil

# dua vektor sumber berisi delapan nilai
A = [3, 8, 12, 5, 9, 14, 2, 7]
B = [10, 4, 6, 15, 1, 11, 13, 20]

vadd(4, A, B)
vadd(8, A, B)

text Keluaran

instruksi vadd pada register 4 lane:
  lane 0:  3 + 10 =  13
  lane 1:  8 +  4 =  12
  lane 2: 12 +  6 =  18
  lane 3:  5 + 15 =  20
instruksi vadd pada register 8 lane:
  lane 0:  3 + 10 =  13
  lane 1:  8 +  4 =  12
  lane 2: 12 +  6 =  18
  lane 3:  5 + 15 =  20
  lane 4:  9 +  1 =  10
  lane 5: 14 + 11 =  25
  lane 6:  2 + 13 =  15
  lane 7:  7 + 20 =  27

Pemanggilan pertama menghasilkan empat penjumlahan pada lane 0 sampai 3, dan empat pasang nilai sisanya membutuhkan instruksi kedua, sehingga seluruh vektor selesai dengan dua kali instruksi 4 lane. Pemanggilan kedua mencakup lane 0 sampai 7 dan menyelesaikan vektor yang sama dalam satu kali instruksi. Pola perhitungannya identik pada kedua lebar register, yaitu penjumlahan pada setiap lane tidak saling memengaruhi, dan hasil satu lane tidak pernah tumpah ke lane tetangganya. Perulangan atas vektor yang lebih panjang hanyalah pengulangan instruksi ini dengan register yang memuat pasangan berikutnya, sehingga pola 4 lane dan 8 lane tetap berlaku.

Ekstensi SIMD nyata#

SIMD bukan gagasan di atas kertas, karena setiap ISA utama membawanya dalam bentuk ekstensi. Prosesor ARM menyediakan NEON dengan register 128 bit, prosesor x86 menyediakan AVX dengan register 256 bit beserta varian AVX-512, dan RISC-V menetapkan ekstensi vektor yang lebarnya dapat dikonfigurasi per implementasi. Masing-masing membawa daftar instruksi sendiri untuk penjumlahan, perkalian, perbandingan, serta muat dan simpan vektor, tetapi konsep lane yang diperlihatkan di atas berlaku sama untuk semuanya.

Compiler modern dapat mengerjakan sebagian pekerjaan itu secara otomatis melalui vektorisasi otomatis (auto-vectorization), yaitu pengubahan perulangan biasa menjadi instruksi SIMD bila pola perulangannya cocok. Kemampuan ini membuat kebanyakan program memperoleh manfaat SIMD tanpa satu instruksi SIMD pun yang ditulis manual, meskipun pemanfaatannya bergantung pada struktur kode.

Kesalahan umum#

Tiga kekeliruan berikut paling sering muncul ketika SIMD baru dikenal, terutama pada saat memperkirakan keuntungan kecepatannya.

Mengira setiap perulangan otomatis menjadi SIMD. Vektorisasi otomatis menolak perulangan yang iterasinya saling bergantung, misalnya penjumlahan berjalan yang hasilnya dipakai oleh iterasi berikutnya. Perbaikannya adalah menyusun ulang perhitungan agar setiap elemen dapat dihitung secara bebas, misalnya menyimpan hasil antara pada vektor terpisah.
Mengira lane dapat mengambil nilai dari lokasi memori mana pun. Instruksi SIMD bekerja paling efektif atas data yang berdempetan dalam memori, karena satu muat vektor mengisi seluruh lane sekaligus. Perbaikannya adalah menata data dalam deret rapat sehingga nilai yang dijumlahkan berdekatan, misalnya deret catatan suhu yang disimpan berurutan.
Menukar SIMD dengan multithreading. SIMD memperlebar satu instruksi pada satu inti, sedangkan multithreading mendistribusikan pekerjaan ke beberapa inti. Perbaikannya adalah memilih alat menurut sifat beban kerjanya, dan keduanya tetap boleh dipadukan, misalnya kerja yang diperlebar SIMD lalu didistribusikan antarinti.

Ringkasan#

Register vektor lebar terbagi menjadi lane berukuran tetap, dan satu instruksi SIMD mengerjakan operasi yang sama pada seluruh lane sekaligus.
SIMD mewakili paralelisme data, sedangkan pipeline dan out-of-order mewakili paralelisme tingkat instruksi pada satu aliran program.
Satu instruksi vadd 4 lane menjumlahkan empat pasang nilai, dan register 8 lane menggandakan jumlah pasangan yang tercakup per instruksi.
NEON, AVX, dan ekstensi vektor RISC-V adalah wujud nyata SIMD, dan compiler dapat memanfaatkannya melalui vektorisasi otomatis.

Referensi#

RISC-V ISA Manual — RISC-V International — Spesifikasi ISA RISC-V yang memuat ekstensi vektor beserta seluruh instruksi yang dibawanya.
Computer Systems: A Programmer’s Perspective — Randal Bryant dan David O’Hallaron — Buku yang membahas instruksi vektor SIMD dan batas optimasinya pada bab optimasi program.