ANALISIS PERBANDINGAN KOMPUTASI SEKUENSIAL DAN KOMPUTASI PARALEL GPU MEMANFAATKAN TEKNOLOGI NVIDIA CUDA PADA APLIKASI PENGURUTAN BILANGAN ACAK MENGGUNAKAN ALGORITMA QUICKSORT 1 2 1
Retno Ayu Shintia Putri (50407705)
Dr. –Ing. Adang Suhendra, Ssi., Skom., MSc.
Mahasiswa Teknik Informatika, Fakultas Teknologi Industri, Universitas Gunadarma,
[email protected] 2
Dosen Tetap Universitas Gunadarma,
[email protected]
ABSTRAKSI Pengurutan merupakan suatu proses mengurutkan data sedemikian rupa sehingga menghasilkan deretan angka yang tersusun secara teratur menurut aturan tertentu. Algoritma sorting yang cukup sederhana dan dapat diterapkan dalam berbagai data adalah algoritma quicksort. Jika data yang akan disorting dalam jumlah banyak akan membutuhkan waktu eksekusi cukup lama jika dikerjakan secara sekuensial. Sehingga dengan perkembangan teknologi yang semakin tinggi, maka digunakanlah teknologi paralel yaitu suatu program tidak hanya dikerjakan oleh satu perangkat yaitu CPU saja tetapi juga memanfaatkan perangkat lain berupa graphic card atau dengan kata lainnya adalah GPU. Teknologi yang dapat digunakan untuk melakukan proses komputasi secara paralel pada GPU dari Nvidia adalah menggunakan teknologi CUDA. Sehingga berdasarkan waktu yang diperoleh dari hasil analisa, penulis dapat membandingkan waktu yang diperoleh antara program sekuensial dan paralel GPU apakah benar bahwa proses paralel GPU akan lebih cepat dibanding proses secara sekuensial.
Kata Kunci: Bilangan Acak,Algoritma Quicksort, Komputasi, GPU, CUDA
ABSTRACT Sorting is a process to sort the data in such a way as to produce a series of numbers arranged on a regular basis according to certain rules. Quicksort algorithm is it quite simple and
can be applied in a variety of data. If the data that will be sorting in large quantities will require a long execution time if done sequentially. So the higher the technological developments, it is used parallel technology which is a program not only done by a device that is the CPU, but also utilize other devices in the form of graphic card or the GPU. CUDA technology can be used to perform computations in parallel on a GPU from Nvidia. So that by the time obtained from the analysis, the authors could compare the time taken between sequential and parallel programs GPU is it true that the parallel GPU will be faster than a sequential process.
Keyword: Random Numbers, Quicksort Algorithm, Computation, GPU, CUDA
1.
PENDAHULUAN
Perkembangan zaman yang sangat pesat
mempengaruhi
teknologi
komputer
Teknologi
komputer
perkembangan diseluruh
yang
yaitu
merupakan
barisan
angka
yang
dihasilkan dari algoritma tertentu.
dunia.
Berdasarkan latar belakang diatas,
berkembang
maka dibuatlah program sorting dengan
ditandai dengan hadirnya teknologi GPU
menggunakan
yaitu suatu teknologi yang memanfaatkan
diterapkan pada bilangan acak agar dapat
kartu grafis (graphics card).
ini
bekerja secara sekuensial dan paralel GPU.
bertujuan agar dapat menghasilkan kinerja
Algoritma yang digunakan untuk melakukan
komputer jauh lebih cepat dibandingkan
sorting adalah algoritma quicksort.
Hal
proses yang sepenuhnya hanya dilakukan oleh CPU Proses pengurutan (sorting) adalah
suatu
algoritma
yang
Maka, dapat disimpulkan tujuan dari penelitian ini adalah mengimplementasikan algoritma
quicksort
secara
sekuensial
proses mengurutkan data sedemikian rupa
dengan menggunakan bahasa C++ serta
sehingga menghasilkan deretan angka yang
secara
tersusun secara teratur menurut aturan
CUDA yang dikeluarkan oleh Nvidia.
tertentu (Anton, 2010). Proses pengurutan
Sehingga
ini dapat dilakukan pada bilangan acak atau
diharapkan dapat mencapai satu kesimpulan
yang biasa disebut dengan bilangan random
dari sebuah analisa bahwa proses manakah
paralel
menggunakan
dengan
kedua
teknologi
program
ini
yang akan lebih cepat selesai yaitu secara
sekuensial
atau
parallel
GPU
dan
dihasilkan dari percobaan tersebut.
bagaimana speedup dan efisiensi yang
2.
LANDASAN TEORI
Proses Komputasi Komputasi adalah suatu teknik yang
satu sama lain. Sehingga untuk pekerjaan
digunakan untuk menyelesaikan masalah
yang kompleks, kurang baik jika dikerjakan
yang berkaitan dengan algoritma, numerik,
dengan menggunakan komputasi sekuensial
perhitungan dan lainnya yang dipecahkan
karena relatif cukup sulit dan membutuhkan
dengan menganalisispemecah dari masalah
waktu
yang ada. Proses komputasi terdiri dari 2
komputasi paralel adalah suatu proses
jenis,
dan
komputasi
dimana
instruksi-instruksi
komputasi paralel. Komputasi sekuensial
dijalankan
secara
berkesinambungan.
adalah
yang
Sehingga masalah yang besar dapat dibagi
dilakukan oleh komputer dengan bekerja
menjadi beberapa masalah yang lebih kecil
untuk
(submasalah), untuk kemudian diselesaikan
yaitu
suatu
komputasi
proses
memproses
sekuensial
komputasi
pekerjaannya
secara
sendiri-sendiri tanpa adanya komunikasi
yang
cukup
lama.
Sedangkan
secara serempak.
Sistem Kerja Graphic Processing mendengarkan
dikirimkan ke memori kartu grafis sebagai
instruksi, baik dari OS atau dari aplikasi,
tempat penyimpanan sementara. Kemudian
kemudian mengambil data digital yang
GPU akan mengambil data digital tersebut
diperlukan
mengkonversikannya
lalu mengubahnya menjadi pixel. Pixel
menjadi sebuah format yang dimengerti oleh
tersebut akan dikirim kembali ke Video
kartu grafis tersebut. Setelah itu, driver
RAM untuk disimpan. VRAM terhubung
menyalurkan data digital yang baru diformat
langsung pada digital to analog converter
Driver
grafis
dan
akan
untuk
(DAC). Converter ini juga biasa disebut
melakukan rendering. Data tersebut berjalan
RAMDAC yang bertugas menerjemahkan
menuju kartu VGA melalui slot pada
image ke signal analog agar bisa digunakan
motherboard
oleh
tersebut
kepada
kartu
grafis
(AGP/PCI-E).
Setelah
disalurkan ke kartu grafis, data akan
monitor.
Selanjutnya,
RAMDAC
mengirimkan gambar final kepada monitor
melalui kabel.
CUDA CUDA merupakan kependekan dari
CUDA
menggunakan
bahasa
“C”
Compute Unified Device Architecture yaitu
standar, dengan beberapa ekstensi yang
sebuah teknologi yang dikembangkan oleh
simpel.
NVIDIA untuk mempermudah utilisasi GPU
Adanya Shared Memory
untuk
Support penuh terhadap operasi integer
keperluan
Arsitektur
umum
CUDA
pengembang
ini
perangkat
(non-grafis). memungkinkan lunak
untuk
dan bitwise.
membuat program yang berjalan pada GPU buatan NVIDIA dengan syntax yang mirip
lebih cepat dari dan ke GPU.
dengan syntax C yang sudah banyak dikenal. CUDA
memiliki
beberapa
keunggulan,
Proses download dan readbacks yang
CUDA dapat mempercepat kerja suatu proses.
diantaranya adalah:
Selain dengan bahasa C, CUDA juga support dengan standar bahasa dan API lainnya.
Algoritma Quicksort Beberapa hal yang membuat quicksort
Melakukan proses langsung pada input
lebih baik daripada proses sorting lainnya :
(in-place)
memori.
Secara umum memiliki kompleksitas
O(n log n).
Algoritmanya sederhana dan mudah diterapkan
pada
pemrograman
dan
berbagai arsitektur
bahasa mesin
sedikit
tambahan
Bekerja dengan baik pada berbagai jenis input data (seperti angka dan karakter).
Algoritma quicksort juga memiliki beberapa kekurangan, seperti :
secara efisien.
dengan
Sedikit
kesalahan
dalam
Dalam prakteknya adalah yang tercepat
program
dari
beraturan (hasilnya tidak benar atau
berbagai
algoritma
pengurutan
dengan perbandingan, seperti merge sort dan heap sort.
membuatnya
penulisan
tidak pernah selesai).
bekerja
tidak
Memiliki ketergantungan terhadap data
yang dimasukkan, yang dalam kasus
penerapan
secara
rekursif
(memanggil dirinya sendiri) bila terjadi
2
Pada
terburuk memiliki kompleksitas O(n ).
kasus terburuk dapat menghabiskan
Secara umum bersifat tidak stable, yaitu
stack dan memacetkan program.
mengubah urutan input dalam hasil akhirnya (dalam hal inputnya bernilai sama).
3.
METODE DAN PERANCANGAN
Rancangan Algoritma Quicksort Secara Sekuensial Quicksort sekuensial,
yang
algoritma
bekerja yang
secara
digunakan
lebih besar dari pivot.
adalah:
yang berisi deretan angka yang nilainya
Deretan rendah dan deretan tinggi
Pada deretan bilangan acak, pilihlah
tersebut akan memanggil dirinya sendiri
salah satu angka yang akan dijadikan
secara berulang dengan menggunakan
pivot.
sebuah
Bagi deretan kedalam dua sub bagian
terurut.
yang terdiri dari “Deretan Rendah” yang
procedure
hingga
datanya
Hasil akhir dari proses sorting tersebut
berisi deretan angka yang nilainya lebih
akan digabungkan dengan urutan deretan
kecil dari pivot dan “Deretan Tinggi”
rendah, pivot dan deretan tinggi.
Rancangan Algoritma Quicksort Secara Paralel Quicksort yang bekerja secara paralel,
memilih pivot, sehingga proses tersebut
algoritma yang digunakan adalah:
juga dapat mengambil nilai tengah
Awalnya
setiap
proses
dimulai
Langkah
selanjutnya
menggunakan algoritma quicksort secara
beberapa tahapan, yaitu :
sekuensial
Broadcast
terdiri
dari
Kemudian kita akan mengganti nilai
Pada bagian ini, pivot yang telah dipilih di
pivot dengan nilai yang mendekati nilai
broadcast atau disebarkan kedalam proses-
tengah. Hal ini dapat dilakukan oleh
proses lainnya.
proses yang bertanggung jawab untuk
Membagi deretan menjadi dua sub bagian Setiap
proses
Setelah rekursi log P, setiap proses memiliki daftar
akan
membagi
bilangan
acak
yang
nilainya
deretan
sepenuhnya disjoint (peristiwa tidak saling
bilangan acak tersebut kedalam dua sub
lepas) dari nilai-nilai yang terjadi pada
bagian yaitu deretan angka dengan nilai
proses lainnya.
yang lebih kecil dari pivot dan nilai yang
Berikutnya adalah pada tiap proses
lebih besar dari pivot. Kemudian, proses
akan dilakukan penggabungan deretan angka
akan membagi bilangan-bilangan tersebut
yang telah diurutkan
kedalam
dua
kelompok
dan
akan
menjalankan algoritma rekursi. Menukar proses yang berdampingan
Persiapan Software Yang digunakan Agar
program
mejalankan teknologi CUDA adalah install
CUDA, harus dipersiapkan terlebih dahulu
Nvidia Graphics Driver 285.62, install
beberapa software yang digunakan. Proses
Nvidia CUDA Toolkit v3.2 dan Install GPU
installasi software yang digunakan untuk
Computing SDK 3.2
4.
dapat
menjalankan
UJI COBA DAN ANALISA GPU Nvidia GeForce GT 540M 2
Sebelum melakukan uji coba, terdapat spesifikasi software
khusus yang
dari
hardware
digunakan
agar
dan
GB
dapat
Hardware
2 GB Harddisk 640 GB
(Perangkat
Keras) Notebook ASUS N43SL Prosesor Intel Core i3 2310M 2.2 GHz
teknologi
Memori DDR3 1333 MHz SDRAM
Spesifikasi tersebut antara lain : Spesifikasi
mendukung
CUDA
menjalankan program secara paralel GPU.
yang
Spesifikasi
Software
(Perangkat
Lunak) Sistem Operasi Microsoft Windows 7 Ultimate 32bit Microsoft sebagai IDE
Visual
Studio
2008
NVIDIA Graphics Driver 285.62
NVIDIA GPU Computing SDK 3.2
NVIDIA CUDA Toolkit v3.2
Uji Coba Program Secara Sekuensial Rata-rata waktu yang didapat dari tiga
6
3072
2952.333
kali percobaan pada masing-masing jumlah
7
3584
3497.333
8
4096
4056.667
9
4608
4773
10
5120
5290.333
11
5632
5578.667
12
6144
6592.667
13
6656
7001.333
14
7168
7563
15
7680
8992.667
16
8192
9407
17
8704
9986.667
18
9216
10322.33
19
9728
11041
20
10240
11832.67
data secara sekuensial dapat dilihat pada tabel dibawah ini : Tabel 1. Tabel rata-rata waktu dari percobaan secara sekuensial Percobaan [ke-]
Jumlah Data
Rata-Rata waktu per 3x perulangan (ms)
1
512
540
2
1024
1075.333
3
1536
1575
4
2048
2070.667
5
2560
2803.667
Uji Coba Program Secara Paralel GPU Rata-rata waktu yang didapat dari tiga
6
3072
348.759
kali percobaan pada masing-masing jumlah
7
3584
414.134
8
4096
465.967
9
4608
506.016
10
5120
521.832
11
5632
568.049
12
6144
640.376
13
6656
646.23
14
7168
775.041
15
7680
830.554
16
8192
840.223
17
8704
944.05
18
9216
1120.841
19
9728
1156.468
20
10240
1305.295
data secara parallel GPU dapat dilihat pada tabel dibawah ini : Tabel 2. Tabel rata-rata waktu dari percobaan secara paralel GPU Percobaan [ke-]
Jumlah Data
Rata-Rata waktu per 3x perulangan (ms)
1
512
78.248
2
1024
155.822
3
1536
239.277
4
2048
280.876
5
2560
330.023
Speedup Setelah melakukan percobaan, maka
8
4096
9.896
dapat dihitung speedup yang dicapai pada
9
4608
9.915
10
5120
9.993
11
5632
10.006
Tabel 3.
12
6144
Tabel hasil perhitungan speedup
13
6656
10.237 10.37
14
7168
10.573
15
7680
10.659
16
8192
11.089
17
8704
18
9216
10.203 9.177
19
9728
9.055
20
10240
9.05
masing-masing jumlah data, seperti :
Percobaan [ke-]
Jumlah data
Speedup
1
512
7.018
2
1024
7.043
3
1536
7.21
4
2048
8.921
5
2560
8.979
6
3072
9.491
7
3584
9.768
Efisiensi Efisiensi yang dihasilkan dari jumlah
8
4096
10.308
data yang dilakukan pada uji coba akan
9
4608
10.328
10
5120
10.409
11
5632
10.423
Tabel 4.
12
6144
10.664
Tabel hasil perhitungan efisiensi
13
6656
10.802
14
7168
11.014
15
7680
11.103
ditampilkan pada tabel dibawah ini :
Percobaan [ke-]
Jumlah data
Efisiensi
16
8192
1
512
11.551
7.31
17
8704
2
1024
10.628
7.337
18
9216
3
1536
9.559
7.51
19
9728
4
2048
9.432
9.293
20
10240
5
2560
9.427
9.353
6
3072
9.887
7
3584
10.175
Hasil Analisa Berdasarkan data yang dihasilkan dari uji coba secara sekuensial dan parallel GPU,
maka waktu eksekusi yang diperoleh dapat digambarkan seperti grafik dibawah ini :
dapat mempercepat suatu proses dibanding jika
proses
sekuensial
tersebut karena
dikerjakan
ketika
secara
suatu
proses
dikerjakan secara paralel, instruksi-intruksi yang ada dalam proses tersebut dijalankan tidak
secara
secara
Gambar 1. Grafik lini proses sekuensial dan paralel
serempak
komunikasi
Dilihat dari grafik diatas, proses yang dilakukan secara sekuensial membutuhkan waktu yang jauh lebih lama dibanding proses yang dilakukan secara paralel GPU. Hal ini dikarenakan pemrosesan paralel
melainkan
dengan
antara
Penggunaan
GPU
masing-masing
satu
hardware
terjadinya
sama
lainnya.
juga
akan
mempengaruhi kinerja suatu proses paralel karena semakin tinggi spesifikasi hardware maka kinerja komputer paralel akan semakin baik dan cepat. Selain itu, jumlah core pada graphic card juga mempengaruhi proses komputasi paralel.
5.
Penutup
Kesimpulan Berdasarkan uji coba yang telah
dipengaruhi oleh spesifikasi hardware
dilakukan pada program quicksort yang
yang digunakan serta tugas atau task
bekerja secara sekuensial dan paralel GPU
apa saja yang sedang dikerjakan oleh
maka dapat ditarik beberapa kesimpulan,
komputer.
yaitu :
Nilai
dan
speedup
diperoleh
GPU lebih cepat dibanding program
meningkat sesuai dengan meningkatnya
yang dieksekusi secara sekuensial.
jumlah data yang digunakan. Namun,
yang
dihasilkan
dari
dua
dasarnya
yang
Waktu eksekusi program secara paralel
Grafik
pada
efisiensi
peningkatan nilai speedup dan efisiensi
percobaan diatas adalah grafik non linier.
tidak
Waktu eksekusi yang diperoleh secara
jumlah
sekuensial dan paralel GPU selain
adanya preprocessing.
dipengaruhi oleh jumlah data juga
akan
stabil data
dikarenakan yang
sedikitnya
digunakan
serta
Saran Penulis berharap untuk perkembangan
perbedaan waktu eksekusi antara komputasi
selanjutnya dilakukan uji coba dengan
sekuensial dan paralel GPU serta dapat
graphic card dan spesifikasi hardware
mengetahui apakah nilai speedup dapat
lainnya serta penggunaan data yang lebih
mencapai angka 24 sehingga tugas akhir ini
banyak dan beragam agar dapat mengetahui
dapat lebih bermanfaat.
Referensi [1]
Intoduction
to
CUDA.
NVIDIA,
486
Berbasis
Linux
Debian.
http://www.sdsc.edu/us/training/assets/docs/
http://www.komputasi.lipi.go.id/data/10142
NVIDIA-01-Intro.pdf.
24400/data/1123986635.pdf, 2005.
[2] NVIDIA CUDA 2.2 Installation and
[8] Mochamad Hariadi dan I Ketut Eddy
Verification on Microsoft Windows XP and
Purnama Anton Siswo. Analisa Pengaruh
Windows
Perubahan Parameter Dalam Proses Render
Vista.
NVIDIA,
http://developer.download.nvidia.com/.
Dengan
[3] NVIDIA CUDA C Programming Guide.
Processing
NVIDIA,
http://digilib.its.ac.id/public/ITS-
http://developer.download.nvidia.com/comp
Undergraduate-15535-2205100124-
ute/cuda/.
Paper.pdf.
[4]
Quicksort
Algorithm.
General
Purpose
Graphical
Unit
(GPGPU).
[9] dkk Auriza Rahmad Akbar, Herbet
http://cprogramminglanguage.net/quicksort-
Sianipar. Implementasi Paralel Merge Sort
algorithm-c-source-code.aspx.
Dengan
[5]
Quicksort
(Hours13).
Menggunakan
Perbandingannya
Dengan
MPICH2
Dan
Implementasi
http://digishared.blogspot.com/2010/05/quic
Sekuensial.
ksort-hours13.html.
http://auriza.site40.net/notes/docs/paralel/,
[6]
CUDA
Basics.
NVIDIA,
2009.
http://developer.download.nvidia.com/CUD
[10] Daniel Cederman and Philippas Tsigas.
A/training/, April 2009.
volume
[7] Bagus Irawan Ajinagoro. Aplikasi
http://www.cse.chalmers.se/research/group/
Sistem Paralel Menggunakan Prosesor Host
dcs/TechReports/gpuqsort.pdf, 2008.
01.
[11]
Yulisdin
Mukhlis
dan
Lingga
[17] Maria A. Kartawidjaja. Analisis Kinerja
Harmanto. Metode Sorting Bitonic Pada
Perkalian Matriks Paralel Menggunakan
GPU.
Metrik
http://openstorage.gunadarma.ac.id/
Isoefisiensi,
volume
10.
mwiryana/KOMMIT/per-artikel/02-02-007-
http://puslit2.petra.ac.id/ejournal/index.php/j
Metode02 Februari 2007.
te/article/viewFile/17788/17704,
[12] Bambang Siswoyo dan Riffa Haviani
2008.
Endang
[18]
Pujiatiningsih.
Analisis
Fachrie
Lantera.
Oktober
Kompleksitas
Perbandingan Algoritma Metode Pengurutan
Algoritma
Quicksort, Metode Pengurutan Selection
http://informatika.stei.itb.ac.id/
Sort dan Metode Pengurutan Heapsort.
rinaldi.munir/Matdis/2008-
http://elib.unikom.ac.id/files/disk1/16/jbptun
2009/Makalah2008/Makalah0809-019.pdf.
ikompp-gdl-s1-2004-endangpuji-769-
[19] Richard Membarth. CUDA Parallel
Jurnal.pdf.
Programming
[13] Alexander Greb and Gabriel Zachmann.
http://pdsgroup.hpclab.ceid.upatras.gr/files/,
http://www.mimuw.edu.pl/
Maret 2009. Hardware-Software-Co-Design
ps209291/kgkp/slides/ifi0611gress.pdf.
University of Erlangen-Nuremberg.
[14]
[20]
Abdullah
Hafidh.
Quick
Tutorial.
Miguel
Cardenas
Sort.
Number
Montes.
19.
First
http://abdullahhafidh.files.wordpress.com/20
Program Learning CUDA to Solve Scientific
11/02/, Februari 2011.
Problems.
[15] Salman Ul Haq. How to Run CUDA
cardenas/CUDA/T2-FirstProgram.pdf, 2010.
3.0
Centro
on
Visual
Studio
2008.
http://www.programmerfish.com/how-torun-cuda-3-0-on-visual-studio-2008/,
de
http://wwwae.ciemat.es/
Investigaciones
Medio-ambiantales 23
y
Energeticas
Technologicas,
Madrid, Spain.
Juni 2010.
[21] Greg Ruetsch and Brent Oster. Getting
[16] Adityo Jiwandono. Implementasi AES-
Started
ECB 128-bit untuk Komputasi Paralel pada
http://www.nvidia.com/content/cudazone/do
GPU Menggunakan Framework NVIDIA
wnload/, 2008.
CUDA.
[22] Ayushi Sinha. Sorting on CUDA.
http://informatika.stei.itb.ac.id/
With
CUDA.
rinaldi.munir/Kriptografi/2010-
Providence
2011/Makalah1/.
http://digitalcommons.providence.edu/, 2011
College,
