Perpustakaan Digital ITB

Di era perkembangan big data, kebutuhan komputasi data graf semakin tinggi. Dibutuhkan pemrosesan graph analytics secara cepat bahkan untuk sebuah personal computer. Salah satu kebutuhan graph analytics adalah algoritma penyelesaian masalah subgraf isomorfisme. Subgraf isomorfisme adalah algoritma untuk menentukan apakah sebuah graf adalah sub-struktur dari graf lainnya. Algoritma ini banyak digunakan dalam pemrosesan query basis data graf dan analisa substruktur pada graf seperti frequent subgraph pattern mining. Untuk mempercepat komputasi, telah dikembangkan algoritma subgraf isomorfisme paralel pada GPU dengan memanfaatkan skema filter -join secara paralel. Namun metode ini masih memanfaatkan pemanggilan kernel pada filter secara bertahap sehingga proses cukup memakan waktu. Pada tugas akhir ini, dikembangkan solusi baru dengan membuat proses pencarian dan eliminasi kandidat secara bersamaan (bulk) dengan memanfaatkan kemampuan komputasi pada GPU. Selain itu tugas akhir ini juga dirancang detil dari struktur data dan proses yang tidak dijelaskan secara detil oleh metode sebelumnya. Dilakukan pula penyesuaian algoritma dengan framework CUDA dan analisa karakteristik dataset terhadap kinerja. Dari pengujian didapat bahwa algoritma dapat mengoptimasi algoritma serial pada CPU 2.73 hingga lebih dari 1000 kali lebih cepat. Dibandingkan dengan algoritma GPU lain seperti GpSM, algoritma yang diusulkan mampu meningkatkan kinerja hingga 133.83 ms lebih cepat.