Paralelisasi Algoritma Uniformization dengan MPI-CUDA

LIA FARHATUAINI, Dr-Ing, MHD. Reza M.I. Pulungan, M. Sc.

2019 | Tesis | MAGISTER ILMU KOMPUTER

Continuous-Time Markov Chains (CTMC) digunakan untuk menganalisis kinerja sistem dengan perilaku yang sangat kompleks. Semakin kompleks sistem yang dianalisis maka model yang dihasilkan akan semakin besar. Model yang besar membutuhkan waktu komputasi yang lama dan ruang memori yang besar untuk penyimpanan. Uniformization merupakan salah satu metode yang digunakan untuk menghitung probabilitas transient pada CTMC. Penelitian ini akan melakukan paralelisasi uniformization dengan menggunakan graphic processing unit (GPU) pada beberapa komputer dan MPI untuk komunikasi antar komputer. Partisi hypergraph digunakan untuk meminimalkan komunikasi yang terjadi antar komputer ketika melakukan operasi sparse matrix-vector multiplication (SpMV) yang berulang. Penggunaan MPI-CUDA pada paralelisasi algoritma uniformization dapat menyelesaikan model yang besar tetapi waktu komputasi 90% digunakan untuk komunikasi antar komputer ketika melakukan SpMV yang berulang. Paralelisasi MPI-CUDA menggunakan 3 node pada model dengan jumlah state 1344 membutuhkan waktu komputasi yang lebih cepat dibanding dengan menggunakan 2 node untuk semua nilai t dari 10 sampai 10000.

Continuous-Time Markov Chains (CTMC) are used to analyze system performance with very complex behavior. The more complex the system is analyzed, the bigger the model produced. Large models require long computing time and large memory space for storage. Uniformization is one method used to calculate transient probabilities at CTMC. This study will perform uniformization parallelization by using a graphic processing unit (GPU) on several computers and MPI for communication between computers. Hypergraph partitions are used to minimize communication that occurs between computers when performing repeated sparse matrix-vector multiplication (SpMV) operations. The use of MPI-CUDA in the parallelization of uniformization algorithms can solve large models but 90% computation time is used for communication between computers when doing repeated SpMV. MPI-CUDA parallelization uses 3 nodes in the model with the number 1344 requiring faster computation time than using 2 nodes for all t values from 10 to 10000.

Kata Kunci : Parallel computing,uniformization,CTMC,CUDA-Aware MPI,hypergraph partitioning