OpenMPI
Praktikum 01 IF3230 - Sistem Paralel dan Terdistribusi OpenMPI - Dijkstra Algorithm
Petunjuk penggunaan program
Serial : Di dalam folder src, jalankan ./dijkstra_serial <banyakNode>
banyakNode menyatakan banyaknya node yang akan dibentuk menjadi graf
Paralel : ./dijkstra_paralel <banyakNode>
Pembagian Tugas
Johanes Boas Badia - 13517009 - Fungsi minDistance, generateRandomArray, printMatrix, printArray, djikstra, main Timothy - 13517087 - Fungsi minDistance, generateRandomArray, printMatrix, printArray, djikstra, main
Laporan Pengerjaan
- Deskripsi solusi paralel
Kami mengimplementasikan fungsi djikstra yang dapat mengeluarkan array yang berisi jarak terdekat sebuah node tertentu berdasarkan parameter yang diberikan ke seluruh node lain. Penyelesaian secara paralel dilakukan dengan membagi perhitungan djikstra tersebut ke seluruh host yang tersedia. Host Root akan membagi pekerjaan sebesar jumlah node / jumlah host. Setelah perhitungan selesai dilakukan, seluruh host akan mengembalikan hasil perhitungan dalam bentuk array melalui pemanggilan fungsi MPI_Gather.
- Analisis Solusi
Solusi yang kami berikan pada permasalahan kali ini belum merupakan solusi paling optimal yang dapat dibuat. Salah satu cara untuk meningkatkan efisiensi pengerjaan adalah dengan membagi perhitungan sebuah host ke beberapa thread terpisah agar perhitungan dapat diselesaikan dengan lebih cepat. Selain itu, kekurangan solusi yang kami tawarkan adalah jika terdapat sisa pembagian pekerjaan, sisa pekerjaan tersebut akan dikerjakan sepenuhnya oleh host root. Hal ini menyebabkan pembagian pekerjaan menjadi tidak merata.
- Jumlah Thread yang digunakan
Pada pengerjaan kali ini, jumlah thread yang digunakan adalah 4 thread untuk. Alasan pemilihan jumlah ini adalah untuk mempermudah implementasi pengerjaan program.
- Pengukuran Kinerja
Dibawah ini adalah hasil kinerja algoritma dijkstra yang dijalankan secara serial.
100 : 15044.345055 microsecond 500 : 1943482.592935 microsecond 1000 : 13679341.012030 microsecond 3000 : 352674510.051962 microsecond
Dibawah ini adalah hasil kinerja algoritma dijkstra yang dijalankan secara paralel.
100 : 12275.007088 microsecond 500 : 1313176.719006 microsecond 1000 : 5640392.467030 microsecond 3000 : 370075980.380992 microsecond
- Perbandingan Kinerja
Dapat dilihat dari hasil diatas, pengukuran kinerja algoritma secara paralel lebih cepat dibandingkan secara serial, karena proses djikstra dilakukan di 4 thread.