## PROSEDUR PARALELISASI PERKALIAN MATRIKS PADA GRAPHICS PROCESSING UNIT (GPU)

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

## Abstrak
Perkalian  matriks  adalah  operasi  yang  sangat  sering  diperlukan  pada  berbagai permasalahan  komputasi.  Adapun  beberapa  permasalahan  yang  seringkali membutuhkan  perhitungan  numeris  yang  melibatkan perkalian  matriks , diantaranya  adalah  prakiraan  cuaca,  bidang  bioinformatik,  ekonomi  serta demografi . Perkalian  ini  dapat  dipercepat  dengan  menggunakan  pemrograman paralel.    Dengan  demikian,  makalah  ini  akan  membahas  mengenai  prosedur paralelisasi perkalian matriks yang dilakukan melalui pemrograman paralel pada Graphics  Processing  Unit  (GPU).  Prosedur  paralelisasi  perkalian  matriks  pada GPU  dilakukan  dengan  menentukan  jumlah  thread  yang  dibutuhkan  untuk melakukan komputasi pada GPU.
Kata Kunci: GPU, Matriks, Thread.

## PARALLELIZATION PROCEDURES OF MATRICES MULTIPLICATION IN GRAPHICS PROCESSING UNIT (GPU)

## Abstract
Matrix multiplication is a very frequent operation required on various computing problems.  As  for  some  problems  that  often  require  numerical  calculations involving  matrix  multiplication,  such  as  weather  forecasts,  bioinformatics, economics  and  demography.  This  multiplication  can  be  accelerated  by  using parallel programming. Thus, this paper will discuss the parallelization procedure of  matrix  multiplication  through  parallel  programming  in  Graphics  Processing Unit (GPU). The parallelization procedure of matrix multiplication in the GPU is done by determining the number of threads.
Keywords: GPU, Matrix, Thread.

## PENDAHULUAN
Banyak  permasalahan  dunia  nyata dapat  diselesaikan  melalui  pendekatan kuantitatif dengan terlebih dahulu merepresentasikannya  ke  dalam  model matematika.  Adapun  proses  perhitungan dari  model  matematika  yang  terbentuk seringkali  dilakukan  dengan  bantuan
komputer  yang  berbasis  matriks,  baik secara analitik maupun numerik. Perkalian  matriks  adalah  operasi  yang sangat  sering  diperlukan  pada  berbagai masalah  komputasi.  Adapun  beberapa permasalahan yang seringkali membutuhkan  perhitungan  numeris  yang
melibatkan perkalian matriks, diantaranya  adalah  prakiraan  cuaca, bidang  bioinformatik,  ekonomi  serta demografi.  Selain  itu,  besarnya  ukuran matriks  tersebut  juga  memunculkan permasalahan  tersendiri  dari  proses komputasi yang dilakukan. Ukuran matriks  yang  besar  ini  menyebabkan latensi  dari  proses  perhitungan  sehingga hasil  yang  diperoleh  menjadi  tidak real time [1, 2, 3].
Misalkan  diberikan  matriks 𝐴 berukuran 𝑚 × 𝑛 dan matriks B berukuran × 𝑙 .  Apabila  matriks A dikalikan  dengan  matriks B maka  akan menghasilkan  matriks C yang  berukuran 𝑚 × 𝑙 .  Perkalian  ini  dapat  dipercepat dengan menggunakan pemrograman paralel  [4].    Dengan  demikian,  makalah ini  akan  membahas  mengenai  prosedur paralelisasi perkalian matriks yang dilakukan  melalui  pemrograman  paralel pada Graphics Processing Unit (GPU).

## METODE PENELITIAN
Compute Unified Device
Architecture (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,  perusahaan  ini  termotivasi  untuk mengembangkan 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 implementasi  dari  sejumlah  algoritma mencapai puluhan hingga ratusan kali [5, 6, 7].
CUDA dikembangkan dengan beberapa  tujuan  desain  pemikiran,  yaitu menyediakan satu set kecil ekstensi untuk bahasa  pemrograman  standar,  seperti C/C++, yang memungkinkan implementasi  sederhana  dari  algoritma paralel.  Dengan  CUDA  programmer C/C++ dapat fokus pada tugas paralelisasi algoritma 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.  Konfigurasi  ini  juga memungkinkan perhitungan simultan pada  CPU  dan  GPU  tanpa  mengganggu sumber daya memori [8].
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 dipanggil 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 kinerja 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 menggunakan  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 multidimensi dapat meminimalisir penggunaan  memori  saat  melakukan operasi pada data multidimensi [9].  Pada masing-masing block , sekumpulan thread mampu  berbagi  data  dan  sinkronisasi. Block  thread dieksekusi  pada  SM  dan beberapa block dapat berjalan bersamaan pada  SM  yang  sama.  Gambar  1 Menggambarkan struktur grid,  block dan thread pada CUDA.
Gambar 1. Struktur Grid, Block dan Thread pada CUDA

## HASIL DAN PEMBAHASAN
Pada  makalah  ini  akan  dibahas mengenai  prosedur  paralelisasi  perkalian matriks  pada  GPU.  Namun  sebelum membahas  prosedur  ini,  perlu  diingatkan
kembali  bahwa  dalam  GPU  terdapat hierarki grid,  block dan thread .  Oleh karena itu sebelum melanjutkan prosedur perkalian sparse matriks  lebih  lanjut maka  perlu  diketahui  spesifikasi  CPU dan GPU yang akan digunakan.
Adapun program paralelisasi perkalian sparse matriks  ini  akan
dijalankan  pada  CPU  dan  GPU  dengan spesifikasi sebagai berikut: CPU : • Model Identifier : ASUS ROG GL552VX • Processor Name : Intel Core i7 • Processor Speed : 2.59 GHz • Number of Processor : 1 • Total Number of Cores : 4 • Software : OS X 10.9.5 (13F1911) GPU : • Mesin : GTX 950M • Arsitektur : Fermi • CUDA Cores : 640 • L2 Cache : 48 KiB • Bus Width : 256 bits
Berdasarkan  spesifikasi  di  atas maka  dapat  dilihat  performa  mesin  GPU yang  GeForce  GT-950M  dibandingkan
dengan  mesin  GPU  tipe  lainnya.  Berikut performa  beberapa  mesin  GPU  yang dapat dilihat pada Gambar 2.
Gambar 2. Performa GeForce GT-950M
Pada  Gambar  2  terlihat  bahwa performa mesin GPU tipe GeForce GTX- 950M  cukup  baik  dibandngkan  dengan yang  lainnya.  Selanjutnya,  berdasarkan spesifikasi  GPU  tipe  GeForce  GT-950M diketahui  bahwa  mesin  GPU  yang digunakan masing-masing memiliki arsitektur  Fermi  maka  kernel  yang dieksekusi maksimal menggunakan blocksize sebesar 1024. Dengan demikian,  apabila  dilakukan  perkalian matriks 𝐴 berukuran 𝑚 × 𝑛 dengan
matriks B berukuran 𝑛 × 𝑙 maka dibutuhkan  total thread sebesar 𝑚 × 𝑙 yang  akan  digunakan  dalam  menghitung entri-entri  dari  hasil  perkalian sparse matriks yang berukuran 𝑛 × 𝑙 . Berikutnya thread - thread pada  GPU tersebut dikelompokkan menjadi beberapa block dimana  sebuah block dapat  memiliki thread ( blocksize ) maksimal  sebesar  1024.  Selain  itu, terdapat  ketentuan  pada  GPU  yang mengharuskan blocksize sebesar
kelipatan  32  [7]. Thread dalam block yang sama bekerja sangat cepat sementara thread dalam block yang berbeda  bekerja  lebih  lambat  karena  ada faktor komunikasi melalui global memory . Thread tersebut  dapat  disusun menjadi  satu  dimensi,  dua  dimensi ataupun  tiga  dimensi.  Pemilihan  dimensi tersebut  tergantung  pada  permasalahan yang ada. Contohnya adalah permasalahan  yang  hasilnya  berupa vektor  akan  digunakan  satu  dimensi, permasalahan  yang  hasilnya  berupa matriks akan digunakan dua dimensi, dan terakhir untuk permasalahan yang hasilnya  berupa  volume  akan  digunakan tiga dimensi. Pada contoh yang diberikan sebelumnya  adalah  merupakan  perkalian matriks yang menghasilkan sebuah matriks,  maka  dalam  hal  ini thread akan disusun  dalam  dua  dimensi.  Dengan demikian, blocksize yang  digunakan dalam permasalahan ini adalah maksimal
sebesar 32 × 32 sesuai dengan spesifikasi  pada  GPU  yang  digunakan. Hal  ini  berarti  bahwa  masing-masing block mengandung maksimal 1024 thread dan semua block harus menggunakan  dimensi  yang  sama,  yaitu dimensi dua. Adapun penggunaan thread dalam  hal  ini  adalah  satu thread menghitung  perkalian  satu  baris  pada matriks A dengan  satu  kolom  pada matriks B. Setelah  banyaknya block terbentuk  maka  ukuran grid akan diperoleh,  yaitu  sebesar  banyaknya  baris block dikalikan dengan banyaknya kolom block [10].
Misalkan  diberikan  matriks 𝐴 berukuran 1500 × 1000 dengan  matriks B berukuran 1000 × 1500 .  Jika  matriks A  dan  B  tersebut  dikalikan  maka  akan diperoleh  matriks C berukuran 1500 × 1500 seperti  diilustrasikan  pada  Gambar
3.
Gambar 3. Matriks C berukuran 𝟏𝟓𝟎𝟎 × 𝟏𝟓𝟎𝟎
Berdasarkan Gambar 3, maka ada sebanyak 1500 × 1500 thread yang dibutuhkan dalam melakukan paralelisasi perkalian matriks A dengan B .
Selanjutnya,  sesuai  dengan  spesifikasi
GPU yang digunakan yaitu GeForce GT-
950M  maka blocksize yang  digunakan
dalam permasalahan ini adalah maksimal sebesar 32 × 32 .  Dengan  demikian, apabila  dalam  permasalahan  ini  diambil blocksize sebesar 32 × 32 maka  akan dibutuhkan  2209 block seperti  terlihat pada Gambar 4.
Gambar 4. Jumlah Block yang Dibutuhkan pada Perkalian Matriks 𝑨 berukuran 𝟏𝟓𝟎𝟎 × 𝟏𝟎𝟎𝟎
dengan Matriks B berukuran 𝟏𝟎𝟎𝟎 × 𝟏𝟓𝟎𝟎 Apabila jumlah block pada Gambar  4  dijabarkan  dimana  masing- masing block terdiri  dari  1024 thread yang  dibentuk  dalam  2  dimensi  maka banyaknya thread yang  disiapkan  ada sebanyak 1504 × 1504 .  Padahal  dalam hal  ini  hanya  dibutuhkan 1500 × 1500 thread. Dengan demikian terdapat 12.016
thread yang  tidak  terpakai.  Adapun ilustrasinya dapat dilihat pada Gambar 5, dimana  daerah  di  dalam  garis  merah merupakan  jumlah thread yang  dipakai dalam  perkalian  matriks  sedangkan daerah  di  luar  garis  merah  merupakan jumlah thread yang  tidak  terpakai.
Gambar 5. Ilustrasi Jumlah Thread yang Dipakai dan Tidak Dipakai

## SIMPULAN DAN SARAN
Berdasarkan  hasil  dan  pembahasan pada  makalah  ini,  dapat  disimpulkan  bahwa prosedur  perkalian  matriks  pada  GPU dilakukan  dengan  menentukan  jumlah thread yang dibutuhkan untuk melakukan komputasi  pada  GPU.  Kelemahan  dari prosedur  ini  adalah  tidak  mempertim- bangkan  permasalahan  komunikasi  antar prosesor. Oleh  sebab  itu,  untuk  mengatasi permasalahan  tersebut  dapat  digunakan teknik graph  partitioning maupun hyper-
graph  partitioning untuk  mengubah  matriks awal  menjadi  blok  matriks  yang  selanjutnya dilakukan perhitungan pada GPU.

## 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] [Coffin,  1992]  Coffin,  M.H.  1992. Parallel Programming: A New Approach.  New  Jersey:  Silicon Press.
[3] [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.
[4] [Saad, 2000] Saad, Y. 2000. Iterative Methods  for  Sparse  Linear  Systems. SIAM.
[5] [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.
[6] [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.
[7] [NVIDIA,  2007]  NVIDIA.  2007. CUDA  Programming  Guide.  Santa Clara: NVIDIA Corp.
[8] [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.
[9] [Howes,  2012]  Howes,  G.,  G.  2012. GPU  Programming  Using  CUDA. Lecture Notes. Department of
Physics  and  Astronomy.  University of Lowa. [10] [Sanders dan Kandrot,
2008] Sanders,  J.  dan  Kandrot,  E.  2008. CUDA by Example: An Introduction to General Purpose GPU Programming. New Jersey: Addison-
Wesley.