Paralelisasi Matrix Exponential dengan MPI-CUDA

JUAN RIZKY MANNUEL L, Dr-Ing. MHD. Reza M. I. Pulungan, M.Sc

2019 | Tesis | MAGISTER ILMU KOMPUTER

Perhitungan fungsi matriks mendapat perhatian yang luar biasa karena banyak penerapannya dalam bidang sains dan teknik di mana fungsi matrix exponential menjadi salah satu fungsi yang dipelajari. Salah satu penerapan matrix exponential yang dapat dipelajari dan diimplementasi adalah transient probabilities Continuous time Markov chains. Proses perhitungan matrix exponential dapat dilakukan dengan metode Padé approximation yang digabung metode scaling and squaring di mana membutuhkan operasi matriks dalam perhitungannya. Penelitian ini melakukan paralelisasi operasi mariks dengan menggunakan GPU dengan library CUDA serta CPU dengan library MPI dalam komunikasi antar node. Data matriks yang digunakan adalah dua model CTMC yaitu Simple Tandem Queueing dan Cyclic Polling Server. Percobaan dilakukan dengan mengubah nilai maksimum elemen matriks (lambda) berdasarkan nilai t sebagai peubah. Penggunaan MPI dan CUDA berperan dalam proses distribusi dan operasimatriks pada paralelisasi perhitungan matrix exponential. Waktu perhitungan dengan paralelisasi multi-node lebih cepat dari single node dengan waktu yang berbeda maksimal sekitar 31 detik (Tandem state = 861) dan 160 detik (Polling state = 1344). Waktu perhitungan juga meningkat seiring meningkatnya state dengan perbedaan maksimal 53 detik (perbandingan Tandem state = 780 dan 861) dan 863 detik (perbandingan Polling state = 576 dan 1344). Waktu perhitungan tiap lambda*t mengalami kenaikan waktu perhitungan dengan perbedaan kenaikan maksimal 16 detik (Polling state = 1344 pada lambda*t = 1000 dan 10000) dan 0.5 detik (Tandem state = 861 pada lambda*t = 1000 dan 10000) sehingga cenderung konstan dibandingkan dengan waktu pengujian keseluruhan.

The computation of matrix functions has received remarkable attention in the last decades because of its numerous applications in science and engineering where matrix exponential function is one of the function studied. One application of matrix exponential that can be learned and implemented is transient probabilities of Continuous time Markov chains. The calculation process matrix exponential can be achieved by Padé approximation combined with scaling and squaring method which require matrix operations in its calculations. This study did parallelization of matrix operations using GPU with CUDA library and CPU with MPI library to communication between nodes. The data matrix used is based on two models of CTMC, namely Simple Tandem Queuing and Cyclic Polling Server. Experiments carried out by changing the maximum value of the matrix element (lambda) based on the value of t as variables. The use of MPI and CUDA role in the distribution and parallelization of matrix operations in the calculation of matrix exponential. Calculation times with multi-node parallelization are faster than single node with a time difference of up to 31 seconds (state = 861 on Tandem) and 160 seconds (state = 1344 on Polling). Calculation time also increases with increasing state with a time difference of up to 53 seconds (comparison Tandem state = 780 and 861) and 863 seconds (comparison Polling state = 576 and 1344). Calculation time of each lambda*t with a time difference of up to 16 seconds (Polling state = 1344 on lambda * t = 1000 and 10000) and 0.5 seconds (Tandem state = 861 on lambda*t = 1000 and 10000) so relatively constant compared to the overall testing time.

Kata Kunci : Matrix Exponential, Padé approximation, Scaling and Squaring, CTMC, Komputasi paralel, MPI, CUDA, Sparse Matrix Multiplication.