Review Jurnal: "ANALISIS KOMPUTASI PARALEL DAN SERIAL PADA ALGORITMA MERGE SORT"
Machudor Yusman, Aristoteles* dan Anie Rose Irawati
Jurusan Ilmu Komputer FMIPA Universitas Lampung, Bandar Lampung 35145
A. Tujuan Penelitian
Tujuan dari penelitian ini adalah mengurutkan objek dengan mengelompokkan data berdasarkan kuantil kontribusi penelitian. Manfaat dari penelitian ini adalah semoga peneliti dapat meningkatkan penerapan pengetahuan dalam penerapan ilmu statistika tentang mengurutkan objek dengan mengelompokkan data berdasarkan kuantil, dan sebagai refensi baik didapartemen maupun di perpustakaan
B. Metode Penelitian
- Algoritma Divide and ConquerAlgoritma divide and conquer sudah lama diperkenalkan sebagai sumber dari pengendalian proses paralel, karena masalah-masalah yang terjadi dapat diatasi secara independen. Banyak arsitektur dan bahasa pemrograman paralel mendesain implementasinya (aplikasi) dengan struktur dasar dari algoritma divide and conquer. Untuk menyelesaikan masalah-masalah yang besar, dan dibagi (dipecah) menjadi bagian yang lebih kecil dan menggunakan sebuah solusi untuk menyelesaikan problem awal adalah prinsip dasar dari pemrograman/strategi divide and conquer. Ilustrasi dengan teknik divide dan conquer terlihat pada Gambar 1.
Divide and conquer adalah varian dari beberapa strategi pemrograman topdown, tetapi keistimewaannya adalah membuat sub-sub problem dari problem yang besar, oleh karena itu strategi ini ditunjukkan secara berulang-ulang (recursively), didalam menerapkan algoritma yang sama dalam sub-sub problem seperti yang diterapkan pada masalah aslinya (original problem). Sebagaimana prinsip dasar algoritma perulangan dibutuhkan sebuah kondisi untuk mengakhiri perulangan tersebut. Biasanya untuk mengecek apakah problem sudah cukup kecil untuk diselesaikan dengan metode secara langsung. Mungkin dari segi ilustrasi kita, bahwa proses-proses pada komputer paralel tentunya memiliki proses/problem/job yang cukup kompleks sehingga harus dipecah-pecah menjadi sub-sub problem. Salah satu penerapan algoritma divide and conquer adalah pengurutan data dengan metode merge. Metode penelitian yang digunakan untuk eksperimen komputasi paralel yaitu algoritma merge sort paralel. Penelitian ini mengurutkan data sebanyak n bilangan yang dibuat dari bilangan random atau acak. Berikut ini ilustrasi atau alur cara kerja algoritma merge sort paralel dengan beberapa tahapan yakni : 1. master (induk) membangkitkan bilangan acak sebanyak n bilangan integer. 2. master (induk) mendistribusikan n/p data ke tiap prosesor. 3. untuk setiap proses melakukan sorting lokal. 4. hasil sorting dari setiap proses dilakukan merge ke master (induk) Ilustrasi atau alur cara kerja algoritma merge sort parallel dapat dilihat pada Gambar 2.
C. Pengujian
Pada bagian ini akan disampaikan mengenai hasil pengujian dan analisa kedua program yakni pengurutan dengan menggunakan Algoritma Merge Sort baik yang dilakukan secara serial dan secara paralel. Untuk melakukan pengujian digunakan suatu skenario pengujian yang dapat membandingkan hasil dari kedua program tersebut. Detail mengenai skenario pengujiannya dijelaskan sebagai berikut.
- Skenario PengujianPengujian dilakukan dengan mebandingkan nilai Speed Up dan Efisiensi dari sejumlah prosesor dengan banyaknya data yang diurutkan. Pengujian juga dilakukan dengan memperlihatkan hasil pengujian dengan menggunakan satu komputer dan dua komputer. Pada pengujian satu komputer dilakukan dengan melakukan simulasi terhadap dua prosesor dan empat prosesor. Sedangkan pengujian lainnya dilakukan benar-benar menggunakan dua komputer yang terhubung pada suatu jaringan peer to peer. Pada pengujian dengan dua komputer ini, setiap PC/Notebook terinstall Sistem Operasi Linux secara virtual dengan menggunakan Virtual Box versi 2.2. Adapun skenario pengujian yang dilakukan dapat dilihat pada Tabel 3.
- Hasil PengujianHasil pengujian dilakukan dengan menghitung nilai Speed Up dan Efisiensi penggunaan pemrograman secara serial dan paralel. Waktu eksekusi secara serial dan paralel ini yang akan dijadikan sebagai parameter untuk mendapatkan nilai Speed Up dan Efisiensi Algoritma Merge Sort secara paralel. Perbandingan nilai Speed Up dapat dilihat pada Tabel 4.
- Analisis Pengujian dengan Dua ProsesorPada Tabel 3 dapat dilihat bahwa untuk jumlah data 100 sampai dengan 100.000 waktu komputasi secara serial masih lebih kecil. Namun, secara umum nilai Speed Up dari jumlah data tersebut makin meningkat. Ini berarti bahwa proses paralel yang dilakukan memiliki hasil yang lebih baik seiring dengan bertambahnya jumlah data. Pada jumlah data 1.000.000 sampai dengan 5.000.000, waktu komputasi secara paralel jauh lebih kecil dibandingkan dengan waktu komputasi serial. Dengan waktu komputasi ini, akan memberikan pengaruh pada nilai Speed Up yang cenderung meningkat dari mulai 1.104318 pada data 1.000.000 sampai 6.519313 pada jumlah data sebanyak 4000.000. Dengan bertambahnya jumlah data, ternyata tidak selalu meningkatkan nilai Speed Up apabila jumlah prosesor yang digunakan selalu tetap. Pada jumlah data sebanyak 5.000.000 terlihat bahwa Speed Up mengalami penurunan dari 6.519313 menjadi 5.239401. Terjadinya penurunan ini diakibatkan oleh peningkatan jumlah data sebesar 1000.000 data yang berimbas pada peningkatan waktu komputasi paralel sebesar 3.352125 dan sedangkan waktu komputasi serial meningkat sebesar 9.56769. Apabila penambahan jumlah data ini terus dilakukan dengan jumlah prosesor tetap, maka dapat diperkirakan bahwa nilai Speed Up akan terus mengalami penurunan.
- Analisis Pengujian dengan Dua ProsesorPada Tabel 5 dapat dilihat bahwa untuk jumlah data 100 sampai degan 1000.000 waktu komputasi secara serial masih lebih kecil. Namun, secara umum nilai Speed Up dari jumlah data tersebut makin meningkat. Ini berarti bahwa proses paralel yang dilakukan memiliki hasil yang lebih baik seiring dengan bertambahnya jumlah data. Nilai Speed Up pada penggunaan empat prosesor cenderung meningkat dengan bertambahnya jumlah data yang diurutkan sampai pada jumlah data 5.200.000. Setelah itu, nilai Speed Up mengalami penurunan pada jumlah data lebih dari sama dengan 5.300.000. Ini berbeda dengan hasil yang diperoleh pada pemrosesan dengan dua prosesor . Berdasarkan pengujian yang dilakukan, penggunaan dua prosesor tidak mampu mengeksekusi sampai dengan jumlah data lebih dari 5.200.000. Bila dibandingkan dengan menggunakan dua prosesor sampai dengan jumlah data 5.200.000, secara umum nilai rata-rata Speed Up dari penggunaan empat prosesor adalah sebesar 1.980198, lebih kecil dari rataan nilai Speed Up dua prosesor sebesar 2.273738. Hal ini diperkirakan dipengaruhi oleh waktu komunikasi yang yang lebih banyak pada penggunaa empat prosesor dibandingkan dengan dua prosesor dengan jumlah data yang sama.
- Analisis Pengujian dengan Dua KomputerPada pengujian proses pengurutan dengan menggunakan dua komputer, terlihat bahwa jumlah data yang mampu untuk dijalankan dan dieksekusi lebih banyak dibandingkan dengan dua hasil sebelumnya yang menggunakan satu komputer. Ini menunjukkan bahwa penggunaan sumber daya secara nyata memiliki kinerja yang lebih baik bila dibandingkan dengan satu komputer yang dijadikan seakan akan sebagai dua prosesor yang berlainan. Nilai rataan dari Speed Up dari penggunaan dua komputer adalah 1.074. Nilai ini memang lebih kecil dibandingkan dengan hasil pengujian pada dua skenario sebelumnya yaitu 2.273 dan 1.980. Nilai ini sangat dipengaruhi oleh running time yang dimilki oleh proses paralel dan serial yang dihasilkan skenario ini yang juga lebih kecil dibandingkan dengan dua skenario sebelumnya. Namun, kelebihan dari skenario ini adalah kemampun dalam menyelesaikan jumlah data yang lebih banyak sampai dengan 6.000.000 data lebih banyak dari dua skenario sebelumnya. Di sisi lain, rataan waktu komputasi paralel pada dua kompter ini lebih kecil bila dibandingkan dengan skenario p=4 yaitu sebesar 3.684742. Namun nilai sedikit lebih besar bila dibandingkan dengan skenario p=2 yang memiliki rataan 3.52489. Hasil pengujian dengan dua komputer terlihat pada Tabel 6
D. Hasil Pembahasan
Berdasarkan hasil pengujian yang dilakukan dapat disimpulkan bahwa untuk jumlah data yang tidak terlalu besar, waktu komputasi serial justru berjalan lebih cepat bila dibandingkan dengan waktu komputasi paralel. Hal ini disebabka oleh waktu komunikasi untuk paralel yang menjadi overhead. Di sisi lain, skenario pengujian dengan dua komputer ternyata memberikan kehandalan dari sisi jumlah data yang mampu dieksekusi. Hasil pengujian menunjukkan bahwa dengan menggunakan dua komputer yang secara peer to peer jumlah data yang mampu diurutkan mencapai 6.000.000 data. Adapun, skenario dengan dua prosesor dan empat prosesor masing-masing hanya mampu mengurutkan data sampai dengan 5.200.000 dan 5.350.000 data. Dari ketiga skenario program yang dieksekusi didapatkan bahwa nilai Speed Up rata-rata dari ketiga skenario masing-masing adalah 2.273738, 1.980198 dan 1.074942. Dengan demikian, secara umum dapat disimpulkan bahwa proses komputasi untuk Algoritma Merge Sort yang dilakukan memiliki keberhasilan dalam menyelesaikan masalah pengurutan dengan algoritma ini.
Implementasi: "ANALISIS KOMPUTASI PARALEL DAN SERIAL PADA ALGORITMA MERGE SORT"
Merge sort adalah metode pengurutan yang menggunakan pola divide and conquer. Strateginya adalah dengan membagi sekelompok data yang akan diurutkan menjadi beberapa kelompok kecil terdiri dari maksimal dua nilai untuk dibandingkan dan digabungkan lagi secara keseluruhan.
- Algoritma dan Pseudocode
Algoritma Merge sort sebenarnya sederhana. bagi larik menjadi dua sama besar, urutkan bagian pertama, urutkan bagian kedua, lalu gabungkan. Sebagai contoh, jika terdapat data berupa 38, 27, 43, 3, 9,82, dan 10 maka ilustrasi pengurutannya adalah sebagai berikut:
Gambar Ilustrasi Merge Sort
Pseudocode untuk merge sort adalah sebagai berikut:
mergesort(data)
if data memiliki setidaknya dua elemen
mergesort (separuh kiri dari data);
mergesort (separuh kanan dari data ;
merge (kedua bagian ke dalam suatu urutan);
Sedangkan pseudocode untuk merge itu sendiri adalah:
Merge (array1, pertama, terakhir)
Tengah = (pertama + terakhir) / 2;
i1 = 0;
i2 = pertama;
i3 = tengah + 1;
While kedua sub larik dari array1 memiliki elemn
If array1[i2] < array1[i3]
temp[i1++] = array1 [i2++];
else
temp[i1++] = array1[i3++];
masukkan ke dalam temp sisa elemen dari array1;
masukkan ke array1 isi dari temp;
- Kompleksitas Algoritma
Kompleksitas algoritma untuk larik dengan n elemen dan jumlah pergeseran(T) dihitung melalui relasi rekursif berikut ini:
Adapun M(n) dihitung lewat cara berikut:
Memilih i = log n sedemikian sehingga n = 2i, maka diperoleh:
Kasus terburuk (worst case) terjadi bila selama pemanggilan fungsi rekursif merge, nilai terbesar dari setiap elemen terletak di larik yang berbeda[1], Hal ini memaksa fungsi merge untuk melakukan pengurutan secara berpindah-pindah antar larik, sebagaimana digambarakan berikut:
Kondisi Worst Case pada Merge Sort
Pada kondisi ini:
Kedua persamaan tersebut untuk selanjutnya diperluas seperti berikut
Dengan mengenali pola yang ada, maka dapat dituliskan persamaan:
Dengan 2i = n dan I = n log n dan memasukkan nilai awal persamaan:
Maka kompleksitas pada kondisi worst case adalah O (n log n ). Kasus terbaik (best case) untuk metode ini dijumpai pada kondisi dimana elemen memiliki nilai terbesar yang lebih kecil dibandingkan dengan seluruh nilai pada elemen yang lain, sebagaimana berikut ini :
Kondisi Best Case pada Merge Sort
Pada scenario ini hanya n/2 perbandingan dari elemen yang diperlukan. Menggunakan proses perhitungan yang sama sebagaimana dalam kasus terburuk, diperoleh:
Dengan kata lain, diperoleh juga kompleksitas yang sama, O (n log n).
Berikut merupakan contoh Implementasi Analisis Komputasi Paralel Pada Algoritma Merge Sort:
Gambar Source Code Program 1
Gambar Source Code Program 2
- Hasil Esekusi Program
Gambar data ke 1
Gambar data ke 2
- Analisis dan Kesimpulan:
Berdasarkan hasil pengujian yang dilakukan dapat disimpulkan bahwa Hasil pengujian menunjukkan dengan menggunakan 2 data untuk data ke 1 dengan inputan 5 data menghasilkan waktu untuk mengrurtkan 19.04 seconds. Sedangkan data ke 2 dengan inputan 10 data menghasilkan waktu untuk mengurutkan 22.88 seconds. Dengan demikian, secara umum dapat disimpulkan bahwa proses komputasi untuk Algoritma Merge Sort yang dilakukan memiliki keberhasilan dalam menyelesaikan masalah pengurutan dengan algoritma ini
Untuk project bisa didownload disini
Yudhistira Satrio Yudanto (16051204045)
Probo Candra Novian (18051204082)
Tidak ada komentar:
Posting Komentar