TRIANGLE COUNTING PADA GRAF DENGAN MENGGUNAKAN ALGORITMA MATRIX MULTIPLICATION SECARA PARALEL PADA GPU

Graf, G(V,E), adalah himpunan titik/ vertex/ node (V) dan himpunan garis/ sisi (E). Tiga node yang saling terhubung dalam graf dapat memiliki peranan yang penting dalam analisis jaringan kompleks. Terdapat banyak kegunaan dari menghitung sebuah segitiga dalam graf. Beberapa diantaranya adalah jumlah segitiga dalam sebuah jaringan untuk menghitung transitivitas atau suatu sifat penting dalam memahami evolusi grafik dari waktu ke waktu lainnya. Lalu, untuk spam filtering. Meskipun sederhana, perhitungan jumlah segitiga telah menjadi suatu perhatian penting terlebih dalam data mining. Banyaknya segitiga dalam graf dapat dihitung menggunakan metode Matrix multiplication, metode ini dipilih karena memiliki akurasi yang tinggi dan sederhana. Namun kesederhanaan metode ini berdampak pada kompleksitas waktu komputasi yang tinggi. Oleh karena itu skema paralel dipilih dalam penelitian ini. CUDA berperan dengan kemampuan seperti merepresentasikan array 2D atau 3D dalam sebuah array 1D. Hal ini dicetuskan oleh beberapa peneliti untuk menghindari dalam batasan penelitian seperti besarnya suatu simpul. Serta mencari seberapa besar speedup yang didapatkan pada saat menghitung segitiga tersebut. Karena dengan mendapatkan speedup, akan diketahui bagaimana penambahan kecepatan dari setiap data yang dijalankan. Pada data kecil, speedup yang didapatkan akan turun ini dikarenakan waktu yang digunakan tidak sebanding dengan data yang terproses, sebaliknya jika data yang dimiliki besar untuk diproses maka hasil speedup akan tinggi. Performansi skema paralel direpresentasikan dalam speedup. Seperti pada data Opsahl, dengan jumlah vertex sebanyak 4941, dan jumlah segitiga sebanyak 651. Didapatkan speedup sebesar 145.484971 kali lebih cepat. Atau pada data paling kecil yakni Zebra dengan 27 vertex, dan 312 segitiga, speedup yang didapatkan sebesar 0.01462307 kali lebih cepat. Hal ini yang menjadi analisis mendalam dalam tugas akhir ini