Praktikum 2 - Open MPI Radix Sort

Daftar Isi

• Praktikum 2 - Open MPI Radix Sort
  • Daftar Isi
  • Overview
  • Petunjuk Penggunaan
    • Prerequisites
    • Installing
    • Running The Program
  • Pembagian Tugas
    • 1. Tugas - Adylan Roaffa Ilmy
    • 2. Tugas - Ayrton Cyril
  • Laporan Pengerjaan
    • Deskripsi Solusi
    • Analisis Solusi
    • Pemetaan Thread & Jumlah Thread
    • Spesifikasi Hardware
    • Pengukuran Kinerja
    • Analisis Kinerja
  • Authors

Overview

Implementasi Radix Sort secara paralel pada OpenMPI. Radix Sort adalah algoritma sorting yang mengurutkan data menggunakan kunci bilangan (integer) dengan melakukan pengelompokan kunci berdasarkan angka yang memiliki kesamaan posisi dan nilai (ratusan dengan ratusan, puluhan dengan puluhan). Ide utama dari algoritma ini adalah melakukan pengurutan untuk setiap angka (digit) dari least significant digit sampai dengan most significant digit.

Petunjuk Penggunaan

Prerequisites

Berikut adalah library yang harus sudah di-install pada komputer anda.

1. GCC version 7+
2. CUDA Toolkit

Installing

1. Panggil command make pada root directory repository ini.
   Setelah melakukan pemanggilan command make, diharapkan akan ada output sebagai berikut:

   make clean
   make[1]: Entering directory '/data'
   make[1]: Leaving directory '/data'
   make build
   make[1]: Entering directory '/data'
   nvcc src/radixsort_paralel.cu src/cudaUtil/cudaUtil.cu src/radixSort/radixSort.cu src/util/util.cpp --device-c
   nvcc  radixsort_paralel.o util.o cudaUtil.o radixSort.o -o bin/radixsort_paralel.out
   gcc src/util/util.cpp src/radixsort_serial.c  -o radixsort_serial.o 
   make[1]: Leaving directory '/data'

   Apabila telah keluar output seperti di atas, program telah berhasil di-install.

Running The Program

1. Ketikkan bash run_cuda.sh <N> untuk menjalankan program Radix Sort dengan adalah jumlah elemen pada array yang ingin diurutkan.

2. Apabila program berhasil dijalankan, akan keluar output yang menandakan waktu yang dibutuhkan untuk melakukan algoritma Radix Sort.
   Contoh:

   $ bash run_cuda.sh 500000
   
   Sorted!
   
   Parallel execution time = 258747.
   
   Serial execution time = 751007.

Pembagian Tugas

1. Tugas - Adylan Roaffa Ilmy

2. Tugas - Ayrton Cyril

Laporan Pengerjaan

Deskripsi Solusi

1. Melakukan sorting radix sort dengan Most Significant Bit
2. Membagi element array yang sudah di sort ke setiap proses. Setiap thread dibagi serata mungkin dengan aturan tidak boleh ada kumpulan Most Significant Bit yang sama yang terpisah di 2 proses yang berbeda
3. Lakukan radix sort pada setiap masing-masing proses
4. Gabungkan kembali hasil sorting ke array pada root

Analisis Solusi

Dari hasil analisis yang paling berpengaruh dalam performa Radix Sort CUDA adalah dengan menggunakan GPU dalam melaksanakan pengurutan array. Overhead yang diakibatkan oleh fungsi cudaMalloc dan cudaMemcpy adalah hal yang menyebabkan algoritma Radix Sort terasa lambat apabila dijalankan secara parallel.

Pemetaan Thread & Jumlah Thread

Jumlah thread yang digunakan pada kasus ini adalah 256 thread. Hal ini dikarenakan pada CUDA GPU, thread harus dalam kelipatan 32. Dan berdasarkan percobaan yang telah kami lakukan, jumlah thread yang paling optimal dalam penyelesaian kasus Radix Sort adalah sejumlah 256 thread.

Spesifikasi Hardware

Percobaan digunakan dengan menggunakan Asus ROG GL552-VW dengan spesifikasi sebagai berikut

Pengukuran Kinerja

Satuan kinerja yang digunakan adalah ukuran waktu dengan satuan microseconds (μs). Berikut adalah hasil pengukuran kinerja algoritma Radix Sort yang dijalankan secara parallel dibandingkan dengan Radix Sort yang dijalankan secara serial. Hasil dicatat dilakukan dengan laptop.

• Pengetesan pada local

Analisis Kinerja

Seperti yang dapat dilihat pada bagian pengukuran kinerja di atas, dapat dilihat bahwa pengerjaan secara parallel hampir selalu dapat melampaui waktu pengerjaan Radix Sort dibandingkan dengan pengerjaan secara serial. Ini berarti algoritma parallel yang kami buat telah dapat melampaui baseline yang telah ditetapkan oleh pengerjaan secara serial.

Namun, dikarenakan dengan overhead fungsi cudaMalloc dan cudaMemcpy yang masing-masing berfungsi untuk melakukan alokasi dan melakukan copy pada GPU device, terkadang waktu eksekusi Radix Sort secara paralel dapat lebih lambat dibandingkan pengerjaan secara serial. Oleh karena itu, cudaMalloc dan cudaMemcpy merupakan sebab lambannya pengerjaan secara parallel menggunakan CUDA.

Authors

• Adylan Roaffa Ilmy - 13516016
• Ayrton Cyril Niwarlangga - 13516019