Abstract:
Dewasa ini, perkembangan Central Processing Unit (CPU) mengarah pada banyaknya inti
pemroses dan komputasi paralel. Meskipun begitu, jumlah inti pada CPU dengan harga yang
cukup terjangkau hanya mencapai 4 hingga 8 saja. Semenjak tahun 2006, NVIDIA telah membuat
perangkat Graphical Processing Unit (GPU) yang mereka rakit mampu membantu perhitungan
CPU dengan teknologi bernama CUDA. Bila dibandingkan dengan CPU, GPU memiliki inti
perhitungan yang banyak namun kecepatan perhitungannya rendah dan hanya mendukung
operasi aritmatika sederhana. Sebaliknya, CPU yang memiliki inti sedikit memiliki kecepatan
yang tinggi dan dapat melakukan perhitungan dan instruksi kompleks.
Dalam penelitian ini, akan dibahas sebuah permasalahan klasik dalam dunia pemrograman,
yakni masalah knapsack. Diberikan sejumlah barang yang masing-masing memiliki berat dan
nilai jual serta sebuah tas dengan kapasitas berat tertentu. Tujuan dari masalah ini adalah
mencari sejumlah barang dengan total berat tidak melebihi kapasitas tas tersebut, namun
menghasilkan nilai jual yang terbesar. Permasalahan ini dapat diselesaikan dengan algoritma
Dynamic Programming dan akan diimplementasikan secara paralel dengan bantuan GPU.
Implementasi dari algoritma ini telah dibangun dengan bantuan GPU untuk mempercepat
perhitungan. Meskipun begitu, terdapat bagian-bagian yang masih menggunakan CPU dalam
prosesnya. Pengujian perangkat dilakukan dengan kasus yang telah dihitung dan kasus acak.
Pengujian percepatan yang diperoleh juga diuji untuk beberapa kondisi tertentu, seperti jumlah
barang dan besarnya kapasitas tas yang harus diperhitungkan. Untuk komputasi yang sedikit,
algoritma ini mengalami degradasi perhitungan yang sangat besar karena cost interaksi CPU
dengan GPU yang besar. Sebaliknya, untuk perhitungan yang besar, perhitungan yang dilakukan
di GPU mengalami percepatan yang sangat tinggi, mencapai hingga sepuluh kali lipat.
