Perpustakaan Digital ITB

SpGEMM (perkalian matriks sparse) memiliki aplikasi yang sangat luas, beberapa diantaranya yaitu sistem linear, machine learning, graf, dsb. Hanya saja, sifat acak dan banyaknya elemen bemilai nol dari matriks sparse mengakibatkan perkalian menggunakan algoritma perkalian matriks biasa menjadi sangat tidak efisien, baik dari sisi waktu eksekusi maupun penggunaan memori. Meskipun algoritma awal dioptimasi, tetap saja peningkatan yang mungkin terjadi tidak berarti karena secara fundamental perkalian dan penjumlahan dengan nol dalam skala yang sangat besar akan tetap boros sumber daya. Kondisi ini mengharuskan perancangan dan pengimplementasian teknik-teknik baru yang radikal demi meningkatkan nilai guna dari aplikasi utama secara keseluruhan. Salah satu teknik baru tersebut adalah TileSpGEMM. Dalam Tugas Akhir telah berhasil dikembangkan dan diimplementasikan algoritma SpGEMM variasi baru dari TileSpGEMM, yaitu pemSpGEMM. Terdapat dua perbedaan mendasar pada desain baru, yaitu eliminasi operasi atomic dan eksploitasi cache pada step 2 dan step 3. Hasil evaluasi menunjukkan terjadi peningkatan throughput pada 90% sampel. Pada beberapa kasus, peningkatan yang terjadi sangat signifikan, mencapa1 2x atau lebih. pemSpGEMM juga berhasil melakukan penurunan overhead konversi input sebelum algoritma dapat dijalankan, sebesar 85%. Penurunan overhead ini disebabkan oleh implementasi secara native di GPU oleh pemSpGEMM, dibandingkan TileSpGEMM yang masih di CPU.