Hasil dan Pembahasan
Pada bagian ini peneliti mencoba
melakukan analisa terhadap program
perkalian matriks sebagai kasus.
Percobaan dilakukan dengan variasi besar ukuran matriks sehingga
mencapai ukuran maksimum. Variasi ukuran berupa variasi dimensi grid, block,
dan thread. Pada percobaan ini peneliti juga memanfaatkan shared memory di GPU.
Selain melihat akibat dari variasi dimensi grid, block, dan thread, peneliti
juga akan melihat perbandingan waktu komputasi dan error diantara setiap jenis
prosesor, yaitu CPU,
GPU non- shared, dan GPU dengan
shared memory.
Untuk melihat dampak dari variasi
ukuran digunakan program perkalian matriks yang menghasilkan output berupa
waktu yang dibutuhkan oleh GPU dengan shared-memory, GPU dengan non-shared
memory, dan CPU biasa dalam mengalikan matriks dengan ukuran yang berbeda-beda.
Selain itu program ini juga memberikan
output berupa error
yang terjadi pada penghitungan
matriks menggunakan GPU, baik dengan shared memory maupun dengan non- shared
memory. Program akan meminta input dari user terlebih dahulu (input 1 untuk
menghitung waktu eksekusi matriks, dan input 2 untuk mengecek selisih
error, dan 3
adalah untuk melihat nilai
variasi dari perubahan ukuran thread dan block).
Di bawah ini adalah grafik hasil
output program, garis merah menandakan error pada penggunaan non-shared memory
dan garis hijau menandakan error pada penggunaan shared memory.
Berdasarkan grafik pada gambar 4,
error yang terjadi pada
perhitungan menggunakan GPU,
baik menggunakan shared memory maupun non shared, tidak terlalu signifikan.
Pertumbuhan fungsi error juga dapat ditoleransi sebab bersifat linier. Hal ini
membuktikan bahwa akurasi hasil perhitungan
menggunakan GPU cukup
baik dengan tingkat error yang rendah serta pertumbuhan fungsi yang
linear. Selain melakukan perhitugan matriks dengan GPU dan CPU peneliti juga
melakukan uji coba dalam variasi jumlah thread yang digunakan pada penghitungan
perkalian matriks. Gambar 5 menunjukkan tampilan grafik pada output di atas,
garis merah menandakan error yang terjadi pada eksekusi yang menggunakan
non-shared memory dan garis hijau menandakan error yang terjadi pada eksekusi
yang menggunakan shared memory.
Dari data di atas tampak bahwa
running time GPU jauh lebih cepat dibandingkan dengan running time CPU. Hal ini
terjadi karena iterasi kedua, iterasi untuk mencari nilai callValue pada node sampai
root, dikerjakan secara
paralel dengan memanfaatkan fitur-fitur seperti shared memory yang
pengaksesan datanya lebih cepat dibandingkan dengan global memori. Shared
memory ini juga dimanfaatkan untuk melakukan reduksi pada proses penghitungan
callValue pada setiap node sehingga mengurangi jumlah memori yang dipakai.
Reduksi digunakan pada banyak algoritma paralel untuk meningkatkan paralelisme
program. Pada program ini, jika reduksi tidak dilakukan maka kemungkinan besar
penghitungan callValue akan dilakukan pada CPU. Hal ini tidak efisien karena
iterasi yang paling
banyak dilakukan ada pada bagian yang harus direduksi ini. Oleh sebab
itu, dengan memparalelkan iterasi kedua maka program akan berjalan jauh lebih
cepat.
Untuk mencari kompleksitas
algoritma ini, perlu dicari kompleksitas iterasi yang paling dominan. Iterasi
yang paling dominan terdapat pada
iterasi kedua yang
melakukan iterasi dari baris
NUM_STEPS-1 sampai root. Iterasi ini berupa
nested loop dengan
jumlah inner loop sebanyak 1.
Secara umum jumlah iterasi dapat
diperkirakan dengan cara seperti persamaan 1 berikut:
Sehingga kompleksitas algoritma
yang diperoleh adalah O(N2).
Dari data di atas dapat dilihat
bahwa setiap input bernilai dua kali input sebelumnya. Selain itu, perbandingan
output CPU dengan output CPU sebelumnya rata-rata bernilai 4. Maka,
Selanjutnya diperoleh
a = 2
sehingga kompleksitas menjadi O(N2). Kompleksitas yang diperoleh ini
cocok dengan kompleksitas yang diperkirakan
sebelumnya. Jadi, secara
umum kompleksitas algoritma Binomial
Tree Option adalah O(N2).
Kesimpulan
Penggunaan GPU dapat meningkatkan
efisiensi perhitungan pada suatu permasalahan yang melibatkan kalkulasi secara
berulang-ulang. Hal ini
dikarenakan tingkat homogenitas
pada data tersebut cukup tinggi sehingga perhitungan ini sangat cocok
dilakukan oleh GPU yang dapat mengeksekusi
data secara paralel
pada waktu yang bersamaan.
