Penyelesaian masalah knapsack dengan menggunakan multi-processor pada GPU

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.