Mengenal dan memakai instruksi SIMD

Instruksi SIMD (Single Instruction Multiple Data) adalah jenis instruksi pada prosesor modern yang bisa melakukan operasi terhadap banyak data sekaligus (biasanya bentuknya adalah array/vector). Instruksi assembly dalam sebuah ISA biasanya hanya melakukan hal dasar berikut:

• Menyalin data dari memori/register ke memori/register
• Melakukan operasi terhadap satu atau lebih register dan menyimpan hasilnya di memori atau register (contoh: penjumlahan, perkalian, operasi bit, dsb). Beberapa operasi akan mempengaruhi flag pada CPU.
• Memindahkan alur eksekusi ke alamat tertentu dalam kondisi tertentu (biasanya berdasarkan flag)
• Melakukan manipulasi hardware spesifik (misalnya mengakses I/O, enable interrupt, enable paging, dsb)

Instruksi SIMD bisa melakukan load/save register dari/ke memori, melakukan manipulasi pada register, tapi satu instruksi bisa memproses banyak data sekaligus. Jika dilakukan dengan benar, ini bisa mempercepat program cukup signifikan. Instruksi SIMD tidak bisa melakukan branching ke banyak alamat sekaligus.

Sejarah SIMD ini cukup panjang: singkatnya tahun 1970an sudah dipikirkan ide ini dan sudah diimplementasikan di berbagai komputer besar, tapi baru masuk ke CPU untuk consumer di akhir abad lalu. Data yang diproses semuanya perlu berurutan (seperti array) dan biasanya disebut sebagai vector (tidak berhubungan dengan istilah vektor di matematika).

Saat ini hampir semua CPU modern sudah memiliki instruksi SIMD. Prosessor Intel sudah mulai mendapatkannya dari jaman MMX (tahun 1997), ARM memiliki NEON (versi awalnya sejak ARM6), sedangkan saat ini extension P untuk RISC-V belum final walau sudah diimplementasikan oleh berbagai CPU RISC-V di pasaran.

Untuk contoh di artikel ini, saya hanya akan membahas implementasi Intel, dan akan menggunakan versi yang paling awal, agar bisa dicoba semua orang. Perbedaan versi awal dan versi-versi berikutnya adalah: jumlah instruksi dan besar register (yang paling awal hanya 64 bit, lalu 128 bit, 256 bit dan sekarang AVX-512 besarnya 512 bit). Versi paling awal juga hanya mendukung operasi integer, dan berikut-nya mendukung floating point.

Assembly

Cara belajar terbaik SIMD adalah dengan memakai assembly langsung, dibantu dengan debugger. Lihat contoh kecil berikut ini, yang menunjukkan:

• Ada instruksi untuk meload data ke register khusus (dalam hal ini MM0 yang ada sejak MMX)
• Ada instruksi untuk menjumlahkan banyak data (8 data masing-masing ukurannya 8 bit)
• Ada instruksi untuk menyimpan dari register ke memori

#include <stdio.h>

int main() {
    char a[8] = {1, 2, 3, 4, 5, 6, 7, 8};
    char b[8] = {1, 1, 1, 1, 1, 1, 1, 1};
    char c[8];

    asm volatile (
        "movq    (%1), %%mm0\n"     /* Load the first array into mm0 */
        "movq    (%2), %%mm1\n"     /* Load the second array into mm1 */
        "paddb   %%mm1, %%mm0\n"    /* Add the bytes in mm1 to mm0 */
        "movq    %%mm0, (%0)\n"     /* Store the result back into the c array */
        "emms\n"                    /* Clear the MMX state to allow FP operations afterwards */
        :
        : "r"(c), "r"(a), "r"(b)
        : "%mm0", "%mm1"            /* Clobber list */
    );

    for(int i = 0; i < 8; i++) {
        if (i>0) printf(", ");
        printf("%d",  c[i]);
    }
    printf("\n");

    return 0;
}

Di dalam assembly di atas: paddb adalah instruksi SIMD-nya. Dengan satu instruksi itu, kita bisa menjumlahkan 2 buah array 8 elemen yang masing-masing elemen ukurannya 1 byte. Seperti bisa diduga, hasilnya adalah: 2,3,4,5,6,7,8,9 (tiap elemen ditambah satu). Instruksi p maksudnya parallel, add artinya menambahkan dan b artinya tambahkan tiap byte. Ada varian lain misalnya paddw yang menjumlahkan tiap word.

Meskipun contoh yang diberikan di sini adalah pada integer, biasanya instruksi vektor ini sangat berguna untuk data floating point. Contoh operasi yang bisa dipercepat adalah perkalian matriks. Instruksi SIMD bisa mempercepat komputasi untuk AI, tapi masih kalah dibandingkan dengan memakai GPU.

Ada banyak instruksi lain selain add, misalnya sub, xor, or, and, mul, div, shift, dsb. Instruksinya ada yang versi saturated, artinya jika nilainya sudah mentok, maka jangan ubah lagi nilainya. Contohnya begini: kita ingin membuat fade out sederhana (gambar transisi menjadi gelap), kita ingin tiap nilai dikurangi 1, tapi jika sudah sampai 0, jangan dikurangi lagi (operasi subtract biasanya akan wrap ke value maksimum) tapi tetap nol. Sebaliknya untuk add bisa dibatasi agar tidak lebih dari nilai maksimum.

Mari kita ubah sedikit contoh sebelumnya: paddb menjadi psubb dan saya ubah angka di array b.

#include <stdio.h>

int main() {
    unsigned char a[8] = {1, 2, 3, 4, 5, 6, 7, 8};
    unsigned char b[8] = {3, 3, 3, 3, 3, 3, 3, 3};
    unsigned char c[8];

    asm volatile (
        "movq    (%1), %%mm0\n"     /* Load the first array into mm0 */
        "movq    (%2), %%mm1\n"     /* Load the second array into mm1 */
        "psubb   %%mm1, %%mm0\n"    /* Add the bytes in mm1 to mm0 */
        "movq    %%mm0, (%0)\n"     /* Store the result back into the c array */
        "emms\n"                    /* Clear the MMX state to allow FP operations afterwards */
        :
        : "r"(c), "r"(a), "r"(b)
        : "%mm0", "%mm1"            /* Clobber list */
    );

    for(int i = 0; i < 8; i++) {
        if (i>0) printf(", ");
        printf("%d",  c[i]);
    }
    printf("\n");

    return 0;
}

Hasilnya menjadi: 254, 255, 0, 1, 2, 3, 4, 5. Nah jika instruksi psubb diubah menjadi psubusb (p = parallel, sub = subtract, u = unsigned, s = saturate, b = byte), maka hasilnya menjadi: 0, 0, 0, 1, 2, 3, 4, 5

Intrinsic

Untuk memudahkan agar tidak perlu menulis kode assembly langsung, kita bisa memakai “intrinsic”, yaitu macro yang nantinya akan jadi kode mesin. Macro ini biasanya sifatnya one to one dengan instruksi assembly, jadi biasanya intrinsic hanya bisa dipakai di satu arsitektur (jika ingin portabel bisa memakai library lain misalnya MIPP).

Untuk memakai intrinsic kita harus eksplisit memanggil fungsi (dalam hal ini _mm_add_pi8), jadi tetap perlu tahu instruksi dasar SIMD dan tahu nama instruksi serta parameternya.

#include <stdio.h>
#include <mmintrin.h>

int main() {
    char a[8] = {1, 2, 3, 4, 5, 6, 7, 8};
    char b[8] = {1, 1, 1, 1, 1, 1, 1, 1};
    char c[8];

    /* Load the vectors */
    __m64 vec_a = _mm_set_pi8(a[7], a[6], a[5], a[4], a[3], a[2], a[1], a[0]);
    __m64 vec_b = _mm_set_pi8(b[7], b[6], b[5], b[4], b[3], b[2], b[1], b[0]);

    /* Add the vectors */
    __m64 vec_c = _mm_add_pi8(vec_a, vec_b);

    /* Store the result */
    *(long long*)c = _m_to_int64(vec_c);

    /* Empty the multimedia state */
    _mm_empty();

    for(int i = 0; i < 8; i++) {
        if (i>0) printf(", ");
        printf("%d",  c[i]);
    }
    printf("\n");

    return 0;
}

Autovectorization

Alangkah bagusnya jika kita bisa menulis kode apa adanya, dan compiler bisa menggunakan instruksi SIMD secara otomatis. Dalam kasus tertentu ini bisa dilakukan, dengan menggunakan fitur autovectorization. Ini berlaku untuk semua arsitektur dan bisa otomatis, tapi tidak selalu optimal.

Pertama kita coba kode sederhana, tanpa vectorization. Saya memakai Compiler Explorer (godbolt.org) untuk melihat output assemblynya.

Terlihat kodenya pendek, tapi memakai loop (cmp/jne). Jika kita tambahkan parameter -ftree-autovectorize, hasilnya seperti ini:

Kenapa kodenya panjang? karena GCC tidak tahu apakah memori yang ditunjuk oleh a, b, dan c ini akan aligned atau tidak (ada di kelipatan lokasi memori tertentu atau tidak.

Agar aman, gcc akan menghasilkan dua kode: satu untuk SIMD, dan satu jika SIMD tidak bisa digunakan. Bagaimana kalau kita yakin bahwa memorinya pasti aligned? Apakah kodenya bisa dibuat lebih efisien? Jawabannya: bisa, kita bisa memaksa GCC menggunakan __builtin_assume_aligned seperti ini:

void do_add( unsigned char* pa, unsigned char *pb, unsigned char *pc) 
{
    unsigned char *a = (unsigned char *)__builtin_assume_aligned(pa, 16);
    unsigned char *b = (unsigned char *)__builtin_assume_aligned(pb, 16);
    unsigned char *c = (unsigned char *)__builtin_assume_aligned(pc, 16);
    for (int i=0; i < 8; i++) {
      c[i] = a[i] + b[i];
    }
}

Sekarang hasilnya seperti harapan, tapi tentunya tanggung jawab kita (pemanggil fungsi) untuk memastikan bahwa lokasi memori yang kita berikan memang aligned.

Perhatikan juga bahwa autovectorization ini tidak selalu berhasil. Untuk memastikan kita perlu melihat assembly yang dihasilkan. Beberapa hal yang penting:

• Batas loop harus jelas, jadi loop while tidak bisa divektorisasi. Kita bisa mencari dulu jumlah elemen yang akan diproses loop, lalu menggunakan instruksi for
• Isi loop tidak bisa memanggil fungsi lain
• kodenya harus sederhana

Bagian terakhir ini sulit, karena ada instruksi tertentu yang bisa divektorisasi dengan baik meskipun kelihatannya rumit. Kita bisa meminta compiler mengoutputkan laporan jika berhasil atau gagal melakukan autovectorization. Untuk GCC opsinya adalah -O3 -ftree-vectorize -fopt-info-vec -fopt-info-vec-missed. Contoh outputnya seperti ini:

Library Khusus

Dari tingkat kesulitannya, Level tersulit adalah memakai SIMD adalah via assembly, berikutnya yang lebih mudah adalah via intrinsic, dan memakai autovectorization dari compiler. Masih ada level lebih tinggi lagi: memakai library yang sudah ada.

Saat ini banyak library yang sudah diimplementasikan menggunakan SIMD. Ada yang khusus untuk prosessor tertentu (misalnya IPP untuk Intel), dan ada yang sudah cross platform. Contohnya: library multimedia ffmpeg memiliki implementasi SIMD.

Library yang dipakai berbagai bahasa high level (misalnya numpy di Python) biasanya sudah memakai versi yang menggunakan SIMD. Jika tidak yakin, coba cek source code library tersebut. Pertama bisa dicek di level assembly (adakah inline assembly yang memakai SIMD), apakah memakai intrinsic, dan terakhir apakah memakai flag compiler untuk optimasi SIMD.

Sering kali level yang saya pakai hanya memilih library yang memiliki versi SIMD. Berikutnya yang saya lakukan adalah memakai opsi autovectorization. Jika ada yang gagal, saya akan coba menulis ulang kodenya, dan jika yakin bahwa ada cara yang lebih baik dengan SIMD, baru saya coba memakai intrinsic.

Penutup

Artikel ini sekedar perkenalan praktis memakai SIMD. Jika tertarik dengan topik ini, ada banyak buku dan artikel lain yang bisa dibaca dan didalami. Secara praktis dari pengalaman saya belajar MMX sampai sekarang, saya hanya perlu assembly ketika melakukan reverse engineering.

Saya suka menulis topik assembly, meskipun peminatnya tidak banyak, karena dulu waktu saya belajar komputer dan programming, ilmu assembly ini sangat berguna untuk saya. Semoga saja tulisan saya ini juga berguna untuk para pemula yang mau mendalami sampai low level.