Review Jurnal Parallel Computation



Review Jurnal
Judul : “ANALISIS PERBANDINGAN KOMPUTASI SEKUENSIAL DAN KOMPUTASI PARALEL GPU MEMANFAATKAN TEKNOLOGI NVIDIA CUDA PADA APLIKASI PENGURUTAN BILANGAN ACAK MENGGUNAKAN ALGORITMA QUICKSORT”

      1.    Pendahuluan dan tujuan
Kehadiran perangkat GPU dengan perangkat komputasi yang dimilikinya telah mengahsilkan sebuah metode parallel yang dapat dilakukan pada perangkat GPU, sehingga dapat mempercepat proses jika proses tersebut hanya dilakukan pada CPU. Pengurutan (sorting) adalah proses mengurutkan data untuk menghasilkan deretan angka yang tersusun secara teratur menurut aturan tertentu (Anton, 2010). Algoritma yang digunakan untuk melakukan sorting adalah algoritma quicksort.
Berdasarkan pendahuluan diatas, penulis jurnal melakukan penulisan dengan tujuan :
       a.    Membuat program pengurutan quicksort yang dieksekusi secara sekuensial pada CPU
       b.    Membuat program pengurutan quicksort yang dieksekusi secara paralel dengan CUDA (GPU)
       c.    Menganalisis perbandingan kecepatan eksekusi program sekuensial dan parallel untuk menyimpulkan metode mana yang paling cepat dalam hal komputasi

       2.    Metode
       a.    Quicksort secara sekuensial
        Algoritma yang digunakan adalah :
  • Pada deretan bilangan acak, pilihlah salah satu angka yang akan dijadikan pivot.
  •  Bagi deretan kedalam dua sub bagian yang terdiri dari “Deretan Rendah” yang berisi deretan angka yang nilainya lebih kecil dari pivot dan “Deretan Tinggi”  yang berisi deretan angka yang nilainya lebih besar dari pivot.
  • Deretan rendah dan deretan tinggi tersebut akan memanggil dirinya sendiri secara berulang dengan menggunakan sebuah procedure hingga datanya terurut.
  •  Hasil akhir dari proses sorting tersebut akan digabungkan dengan urutan deretan rendah, pivot dan deretan tinggi.

       b.    Quicksort secara parallel (menggunakan CUDA)
        Algortima yang digunakan adalah :
  • Awalnya setiap proses dimulai menggunakan algoritma quicksort secara sekuensial
  • Kemudian ubah nilai pivot dengan nilai yang mendekati nilai tengah. Hal ini dapat dilakukan oleh proses yang bertanggung jawab untuk memilih pivot, sehingga proses tersebut juga dapat mengambil nilai tengah
  •  Langkah selanjutnya terdiri dari beberapa tahapan, yaitu :
    • Broadcast. Pada bagian ini, pivot yang telah dipilih di broadcast atau disebarkan kedalam prosesproses lainnya.
    • Membagi deretan menjadi dua sub bagian. Setiap proses akan membagi deretan bilangan acak tersebut kedalam dua sub bagian yaitu deretan angka dengan nilai yang lebih kecil dari pivot dan nilai yang lebih besar dari pivot. Kemudian, proses akan membagi bilangan-bilangan tersebut kedalam dua kelompok dan akan menjalankan algoritma rekursi.
    • Menukar proses yang berdampingan. Setelah rekursi log P, setiap proses memiliki daftar bilangan acak yang nilainya sepenuhnya disjoint (peristiwa tidak saling lepas) dari nilai-nilai yang terjadi pada proses lainnya. 
  • Berikutnya adalah pada tiap proses akan dilakukan penggabungan deretan angka yang telah diurutkan 



      3.    Hasil dan Pembahasan

Pada bagian ini akan dijabarkan hasil dari uji coba dan kesimpulan yang didapatkan. Berikut ini adalah sampel dari hasil uji coba pada komputasi secara sekuensial


Selanjutnya, adalah sampel dari hasil uji coba pada komputasi parallel dengan CUDA

Berdasarkan kedua hasil diatas, dapat dibandingkan perbandingan kedua metode sekuensi dan parallel berdasarkan grafik dibawah ini



Berdasarkan 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 dapat mempercepat suatu proses dibanding jika proses tersebut dikerjakan secara sekuensial karena ketika suatu proses dikerjakan secara paralel, instruksi-intruksi yang ada dalam proses tersebut dijalankan tidak secara masing-masing melainkan secara serempak dengan terjadinya komunikasi antara satu sama lainnya.


Berdasarkan uji coba yang telah dilakukan pada program quicksort yang bekerja secara sekuensial dan paralel GPU maka dapat ditarik beberapa kesimpulan, yaitu :

  • Waktu eksekusi program secara paralel GPU lebih cepat dibanding program yang dieksekusi secara sekuensial.
  • Grafik yang dihasilkan dari dua percobaan diatas adalah grafik non linier.
  • Waktu eksekusi yang diperoleh secara sekuensial dan paralel GPU selain dipengaruhi oleh jumlah data juga dipengaruhi oleh spesifikasi hardware yang digunakan serta tugas atau task apa saja yang sedang dikerjakan oleh komputer.


sumber jurnal : ANALISIS PERBANDINGAN KOMPUTASI SEKUENSIAL DAN KOMPUTASI PARALEL GPU MEMANFAATKAN TEKNOLOGI NVIDIA CUDA PADA APLIKASI PENGURUTAN BILANGAN ACAK MENGGUNAKAN ALGORITMA QUICKSORT.pdf

Kelompok 6 Softskill :
1. Eric Ashardi Utama (52412522)
2. Hambali Syahrul Basir(53412264)
3. Raden Septiana Faza (55412851)
4. Riyan Neba (56412506)
5.Yoshepin Febri Yanti (57412871)


0 comments:

Post a Comment