## PARALELISASI PERKALIAN MATRIKS SPARSE – VEKTOR DENGAN CUBLAS

## Murni
Pusat Studi Komputasi Matematika, Universitas Gunadarma Jl. Margonda Raya no. 100, Depok 16424, Jawa Barat murnipskm@staff.gunadarma.ac.id

## Abstrak
Perhitungan  perkalian  matriks-vektor  sangat  dibutuhkan  dalam  menyelesaikan berbagai  permasalahan  perhitungan  di  dunia  nyata,  seperti  dalam  menentukan solusi  dari  suatu  sistem  persamaan  linier.  Ukuran  matriks  yang  besar  dapat berdampak  pada  lamanya  proses  perhitungan  yang  dilakukan  sehingga berimplikasi  terhadap  akurasi  dari  hasil  perhitungan  yang  tidak  real-time. Adapun  matriks  sparse  yang  digunakan  pada  makalah  ini  adalah  sepuluh  buah matriks  yang  dibangkitkan  secara  acak.  Adapun  pemrograman  paralel  untuk melakukan  perhitungan  perkalian  matriks  sparse  dengan  vektor  menggunakan Compute  Unified  Device  Architecture  (CUDA)  dengan  library  cuBLAS. Berdasarkan  ujicoba  perkalian  sparse  matrix-vector  tersebut  diperoleh  hasil speed-up  mencapai 3380 × lebih  cepat  dengan  menggunakan  GTX-950M  serta 4286 × lebih cepat dengan menggunakan Quadro K4200.
Kata kunci: Matriks Sparse, CUDA, cuBLAS

## PARALLELIZATION OF SPARSE MATRIX-VECTOR MULTIPLICATION WITH CUBLAS

## Abstract
The  calculation  of  matrix-vector  multiplication  is  needed  in  solving  many  real- world  calculation  problems,  such  as  in  determining  the  solution  of  a  system  of linear  equations.  The  large  size  of  the  matrix  can  affect  the  length  of  the calculation  process  so  that  it  implies  the  accuracy  of  the  calculation  results  are not real-time. The sparse matrix used in this paper is the ten matrices generated randomly.  The  parallel  programming  used  is  Compute  Unified  Device Architecture  (CUDA)  with  cuBLAS  library.  Based  on  sparse  matrix-vector multiplication test results obtained speed-up reaches 3380 × faster by using GTX- 950M and 4286 × faster by using Quadro K4200.
Keywords : Sparse Matrix, CUDA, cuBLAS

## PENDAHULUAN
Banyak permasalahan dunia nyata dapat  diselesaikan  melalui  pendekatan kuantitatif  dengan  terlebih  dahulu  me- representasikannya  ke  dalam  model  ma- tematika. Adapun proses perhitungan dari model matematika yang terbentuk sering- kali  dilakukan  dengan  bantuan  komputer yang  berbasis  matriks  dan  vektor,  baik secara analitik maupun numerik. Contoh- nya ketika menentukan solusi dari sistem persamaan linier yang melibatkan operasi perkalian  antara  invers  matriks  dengan vektor.  Selain  itu,  besarnya  ukuran  mat- riks  dan  variasi  elemen  yang  terkandung dalam  suatu  matriks  tersebut  juga  me- munculkan  permasalahan  tersendiri  dari proses  komputasi  yang  dilakukan.  Ada- pun  ukuran  matriks  yang  besar  menye- babkan  latensi  dari  proses  perhitungan sehingga  hasil  yang  diperoleh  menjadi tidak real time [1,4]. Variasi elemen yang dimaksud terkait dengan proporsi elemen bukan  nol  yang  sangat kecil  dalam  suatu matriks  ( sparse  matrix ),  biasanya  tidak lebih  dari  2  %  [9,  10,  11],  dimana sebenarnya  proses  komputasi  dapat  di- sederhanakan  hanya  untuk  elemen-ele- men  yang  bukan  nol  saja. Sparse  matrix kerap  muncul  pada  berbagai  permasa- lahan  dunia  nyata  beberapa  diantaranya adalah  pada  bidang  bioinformatik,  eko- nomi, demografi, rekayasa struktural, pe- modelan  reaktor  nuklir,  dan  desain  kom- ponen komputer memory circuit . Dalam  makalah  ini,  perkalian matriks  dengan  vektor  dilakukan  melalui pemrograman paralel. Adapun pemrogra- man  paralel  untuk  melakukan  perhitung- an  perkalian sparse matriks  dengan vektor  tersebut  adalah  menggunakan CUDA dengan library cuBLAS.

## METODE PENELITIAN
Compute  Unified  Device  Archi- tecture (CUDA)  merupakan  salah  satu
platform  komputasi  paralel  dan  model pemrograman  yang  telah  dibuat  oleh NVIDIA  dan  diimplementasikan  oleh GPU. CUDA pertama kali diperkenalkan NVIDIA pada tahun 2006. Sebagai  salah satu  perusahaan  prosesor  grafis,  perusa- haan  ini  termotivasi  untuk  mengem- bangkan platform yang  dapat  digunakan untuk memaksimalkan penggunaan GPU.
Platform ini  diberi  nama  GPGPU
( General Purpose Computation on GPU). Namun,  karena  terkendala  API,  maka pada  tahun  2007  NVIDIA  mengeluarkan model standar pemrograman paralel pada GPU  yang  disebut  CUDA.  CUDA merupakan  ekstensi  minimal  dari  bahasa pemrograman C/C++ untuk mengarahkan proses  komputasi  dari  CPU  ke  GPU (GPU computing ).  Sejak  saat  itu, pemrograman  paralel  berbasis  CUDA GPU  menjadi  salah  satu  solusi  efektif atas kendala yang dihadapi pada implementasi  MPI dan OpenMP, dimana speed-up yang  dihasilkan  pada  imple- mentasi  dari  sejumlah  algoritma  men- capai  puluhan  hingga  ratusan  kali  [2,  3,
8].
CUDA  dikembangkan  dengan beberapa  tujuan  desain  pemikiran,  yaitu menyediakan satu set kecil ekstensi untuk bahasa  pemrograman  standar,  seperti C/C++, yang memungkinkan  implement- tasi  sederhana  dari  algoritma  paralel. Dengan  CUDA  programmer  C/C++ dapat  fokus  pada  tugas  paralelisasi  algo- ritma  dari  pada  menghabiskan  waktu pelaksanaannya.  Selain  itu,  terdapat dukungan  perhitungan  heterogen  pada CUDA,  yakni  aplikasi  menggunakan kedua  CPU  dan  GPU.  Bagian  sekuensial dari  aplikasi  dijalankan  pada  CPU,  dan bagian-bagian  paralel  dikerjakan  pada GPU.  CPU  dan  GPU  diperlakukan sebagai perangkat terpisah yang memiliki ruang  memori  mereka  sendiri.  Konfi- gurasi  ini  juga  memungkinkan  perhi- tungan  simultan  pada  CPU  dan  GPU tanpa  mengganggu  sumber  daya  memori [5].
CUDA  mampu  memiliki  ratusan core yang  secara  kolektif  dapat  menjalankan ribuan  komputasi. Core ini  telah  berbagi sumber  daya  termasuk  file  register  dan berbagi  memori.  Chip shared-memory memungkinkan  tugas-tugas  paralel  yang berjalan pada core ini untuk berbagi data tanpa  mengirimnya  melalui  bus  memori system.  Program  pada  NVIDIA  CUDA dieksekusi pada dua device yang berbeda, yakni  CPU  dan  GPU.  CUDA  memiliki fungsi  kernel,  yakni  fungsi  yang  di- panggil  dari  program host kemudian thread dieksekusi  secara  paralel  pada GPU.  Satu  kernel  dieksekusi  pada  satu waktu.  Pada  pemanggilan  fungsi  kernel terdapat thread sebagai  tempat  untuk eksekusi.  Adapun  fungsi  kernel  yang dieksekusi  pada device adalah  _global_ dan  _device_  sedangkan  fungsi  kernel yang dieksekusi pada host adalah _host_.
Pengelolaan block dan thread sangat diperlukan  untuk  mengoptimalkan  kiner- ja  pemrosesan  data.  Kumpulan thread membentuk block dan  kumpulan block
dinamakan Grid .  Banyaknya thread dalam satu block disebut dengan blocksize sedangkan kumpulan 32 thread dinamakan dengan warp .
Setiap block dan thread menggu- nakan  indeks  untuk  mengakses  elemen dalam  array,  sehingga  koleksi  semua saling kooperatif dalam menjalankan dan memproses  seluruh  data  set.  Thread CUDA  memanfaatkan  ID block dan thread untuk  menentukan  data  mana yang  akan  dihitung.  ID  block  dapat berupa  satu  dimensi  atau  dua  dimensi sedangkan  ID  thread  dapat  berupa  satu dimensi,  dua  dimensi,  atau  tiga  dimensi. Pemanfaatan block dan thread multi- dimensi dapat meminimalisir penggunaan memori saat melakukan operasi pada data multidimensi  [7].  Pada  masing-masing block ,  sekumpulan thread mampu  ber- bagi  data  dan  sinkronisasi. Block  thread dieksekusi  pada  SM  dan  beberapa block dapat  berjalan  bersamaan  pada  SM  yang sama.  Gambar  1  Menggambarkan  struk- tur grid, block dan thread pada CUDA.
Gambar 1. Struktur grid, block dan thread pada CUDA
Salah  satu library CUDA  yang sering  digunakan  adalah  cuBLAS  (CU- DA Basic Linear Algebra Subprograms ).
Penggunaan library cuBLAS dapat mem- permudah user dalam  memproses  data secara  paralel.  Terdapat  tiga  level  dalam cuBLAS  dalam  melakukan  operasinya. Level  1  CUBLAS  digunakan  untuk menghitung  operasi  yang  didasarkan pada  operasi  pada  vektor  dengan  vektor maupun  vektor  dengan  skalar.  Pada cuBLAS  level  1  ini  biasanya  digunakan fungsi  cublasSaxpy,  cublasIsamax,  dan cublasScoopy.  Level  2  cuBLAS  di- gunakan  untuk  menghitung  operasi  yang didasarkan  pada  operasi  pada  matriks dengan  vektor  dan  biasanya  digunakan fungsi  cublasSgemv.  Pada  level  3 CUBLAS  digunakan  untuk  menghitung operasi  yang  didasarkan  pada  operasi pada  matriks  dengan  matriks.  Pada CUBLAS level 3 ini biasanya digunakan fungsi cublasSgemm.

## HASIL DAN PEMBAHASAN
Misalkan  diberikan    matriks A sembarang  berukuran 𝑚 × 𝑛 dan  matriks B berukuran 𝑛 × 𝑙 seperti  terlihat  pada persamaan (4.1) sebagai berikut:
𝐴 = [ 𝑎 11 𝑎 12 𝑎 21 𝑎 22 ⋯ 𝑎 1𝑛 ⋯ 𝑎 2𝑛 ⋮ ⋮ 𝑎 𝑚1 𝑎 𝑚2 ⋱ ⋮ ⋯ 𝑎 𝑚𝑛 ] , 𝐵 = [ 𝑏 11 𝑏 12 𝑏 21 𝑏 22 ⋯ 𝑏 1𝑙 ⋯ 𝑏 2𝑙 ⋮ ⋮ 𝑏 𝑛1 𝑏 𝑛2 ⋱ ⋮ ⋯ 𝑏 𝑛𝑙 ] (1)
maka  hasil  perkalian  matriks A dengan matriks B adalah matriks C dengan ukuran 𝑚 × 𝑙 , yaitu:
𝐶 = [ 𝑐 11 𝑐 12 𝑐 21 𝑐 22 ⋯ 𝑐 1𝑙 ⋯ 𝑐 2𝑙 ⋮ ⋮ 𝑐 𝑚1 𝑐 𝑚2 ⋱ ⋮ ⋯ 𝑐 𝑚𝑙 ] (2)
Selanjutnya,  untuk  memudahkan perhitungan,  maka  hanya  diberikan contoh  implementasi  perkalian sparse matriks  dengan  vektor.  Jadi  matriks B pada  persamaan  (1)  dipilih  berukuran
𝑛 × 1 .  Matriks B berukuran 𝑛 × 1 ini selanjutnya  dinamakan  dengan  vektor 𝑥̅ . Dengan  demikian  hasil  perkalian sparse matriks A dengan  vektor 𝑥̅ akan menghasilkan  vektor  yang  berukuran 𝑚 × 1 seperti terlihat pada persamaan (3) berikut ini.
𝐴𝑥̅ = [ 𝑎 11 𝑎 12 𝑎 21 𝑎 22 ⋯ 𝑎 1𝑛 ⋯ 𝑎 2𝑛 ⋮ ⋮ 𝑎 𝑚1 𝑎 𝑚2 ⋱ ⋮ ⋯ 𝑎 𝑚𝑛 ] [ 𝑥 1 𝑥 2 ⋮ 𝑥 𝑛 ] = [ 𝑎 11 𝑥 1 + 𝑎 12 𝑥 2 + ⋯ + 𝑎 1𝑛 𝑥 𝑛 𝑎 21 𝑥 1 + 𝑎 22 𝑥 2 + ⋯ + 𝑎 2𝑛 𝑥 𝑛 ⋮ 𝑎 𝑚1 𝑥 1 + 𝑎 𝑚2 𝑥 2 + ⋯ + 𝑎 𝑚𝑛 𝑥 𝑛 ]
(3)
Perkalian sparse matriks  dengan vektor  pada  persamaan  (3)  akan  di- jalankan  secara  sekuensial  dan  paralel. Adapun  pemrograman  paralel  untuk melakukan  perhitungan  perkalian sparse matriks  dengan  vektor  tersebut  adalah menggunakan  CUDA  dengan  library cuBLAS. Dengan menggunakan cuBLAS library , blocksize otomatis  diatur  sendiri oleh  komputer  sedemikian  sehingga  di- peroleh hasil speed-up yang optimal.
Eksperimen yang dilakukan pada makalah  ini  terdiri  dari  beberapa  skena- rio,  yaitu  enam  (6)  buah  matrks  persegi serta  empat  (4)  buah  matriks  persegi panjang.  Adapun  skenario  lengkap  dapat dilihat pada Gambar 2. Berdasarkan hasil eksperimen  tersebut  dapat  diketahui  ka- rakteristik lain mengenai performa speed- up dari  algoritma  paralel  yang  telah didesain  sebelumnya. Speed-up dalam pemrograman paralel diformulasikan sebagai
𝑆𝑝(𝑃) = 𝑇 𝑠 𝑇 𝑝 (4) 𝑇 𝑠 adalah  waktu  eksekusi  sekuensial  dan 𝑇 𝑝 adalah waktu eksekusi paralel.
Berdasarkan skenario pada Gambar  1  serta  mesin  GPU  yang digunakan  pada  makalah  ini,  yaitu GeForce GTX-950M dan Quadro K4200, maka  diperoleh  hasil speed-up seperti tersaji pada Tabel 1.
Gambar 2. Skenario
Tabel 1.  Speed-Up Perkalian Sparse Matrix-Vector menggunakan cuBLAS Library
Dimensi Matriks A Speed-Up Perkalian Sparse Matrix-Vector GTX-950M Quadro K4200 64 x 64 114,7072278 205,1674837 100 x 100 275,9017652 515,9223044 500 x 500 1295,736301 1372,960538 1000 x 1000 2301,453565 2941,863815 2500 x 2500 3379,647023 3862,431376 10000 x 10000 3366,560705 4402,348603 128 x 96 240,0146077 447,2625199 512 x 1024 1222,055177 1332,30578 1024 x 1500 2318,594167 2896,24785 15968 x 16000 3260,295955 4285,573257

## SIMPULAN DAN SARAN
Berdasarkan  hasil  dan  pembahasan pada  makalah  ini,  dapat  disimpulkan  bahwa berdasarkan  data sparse  matrix-vector yang dibangkitkan secara acak, diperoleh speed-up mencapai 3380 × lebih  cepat dengan  menggunakan  GTX-950M  serta 4286 × lebih cepat dengan menggunakan Quadro  K4200.  Terlihat  bahwa  hasil speed-up menggunakan  Quadro  K4200 lebih  baik  dibandingkan  dengan  GTX-
950M.  Hal  ini  dikarenakan  spesifikasi mesin  GPU  Quadro  K4200  lebih  baik dibandingkan dengan GTX-950M. Walaupun  hasil speed-up yang  diperoleh sudah  sangat  baik  namun  p aralelisasi menggunakan CUDA dengan library cuBLAS tidak memperhatikan faktor komunikasi  yang  terjadi  antar  prosesor sehingga  proses  komputasi  yang  dilakukan menjadi  kurang  efisien  [3].  Oleh  sebab  itu,
untuk mengatasi permasalahan tersebut dapat digunakan teknik graph partitioning maupun hypergraph  partitioning untuk  mengubah matriks sparse awal  menjadi  blok  matriks dan  selanjutnya  digunakan  CUDA  untuk melakukan perhitungan.

## DAFTAR PUSTAKA
[1]  [Barney,  2015]  Barney,  B.  2015. Introduction  to  Parallel  Computing. Retrieved  June  2,  2015  from  High Performance  Computing: https :
// computing.llnl.gov/tutorials/paralle l_comp/
[2]  [Bustamam,  et  al,  2010]  Bustamam, A., Burrage, K., dan Hamilton, N.A. 2010. Fast Parallel Markov Clustering  in  Bioinformatics  Using Massively Parallel Graphics Processing  Unit  Computing. Second International  Workshop  on  High Performance  Computational  System Biology.
[3]  [Bustamam,  et  al,  2014]  Bustamam, A.,  Ardaneswari,  G.,  Tasman,  H., dan  Lestari,  D.  2014.  “Performance Evaluation  of  Fast  Smith-Waterman Algorithm  for  Sequence  Database Searches  using  CUDA  GPU-based Parallel Computing”. Journal of Next Generation  Information  Technology , Vol. 5, pp. 38 – 46.
[4]  [Coffin,  1992]  Coffin,  M.H.  1992. Parallel Programming: A New
Approach.  New  Jersey:  Silicon Press.
[5] [Ghorpade, et al, 2012] Ghorpade, J., Jitendra P., Madhura K., dan Amit B. 2012. “GPGPU Processing in CUDA Architecture”. Advanced  Computing
: An  International  Journal  (ACIJ). Vol. 3, No. 1.
[6] [Heath, et al, 1991] Heath, M.T., Ng, E.  dan  Peyton,  B.W.  1991.  “Parallel Algorithms for Sparse Linear Systems”. SIAM , Vol. 33, No. 3, pp. 420 – 460.
[7]  [Howes,  2012]  Howes,  G.,  G.  2012. GPU  Programming  Using  CUDA . Lecture Notes. Department of Physics  and  Astronomy.  University of Lowa.
[8]  [NVIDIA,  2007]  NVIDIA.  2007. CUDA  Programming  Guide.  Santa Clara: NVIDIA Corp.
[9]   [Saad, 2000] Saad, Y. 2000. Iterative Methods  for  Sparse  Linear  Systems. SIAM.
[10]   [Vazquez, et al, 2009] Vazquez, F., Garzon,  E.M.  dan  Martinez,  J.A. 2009.  The  Sparse  Matrix  Vector Product on GPU.
[11]  [Vazquez,  et  al,  2010]  Vazquez,  F., Ortega,  G.,  Fernandez,  J.J.  dan Garzon,  E.M.  2010.  Improving  the Performance  of  the  Sparse  Matrix Vector Product with GPUs.