# Petunjuk Penggunaan
!!!**Dengan asumsi semua langkah - langkah berikut dilakukan di salah satu server itb yang memiliki range IP Address** `167.205.35.150 - 167.205.35.155`!!!
1. Siapkan prereq yang dibutuhkan, yaitu:
- Compiler C
- OpenMPI

Jika anda menggunakan Linux atau WSL, anda dapat mendapatkan hal hal diatas dengan menggunakan perintah berikut:

$ sudo apt install gcc openmpi-bin libopenmpi-dev make

2. Clone repository berikut. anda bisa menggunakan ssh, https, ataupun mengunduh berkas berkas zipnya.
Jika anda memilih ssh:

	$ git clone [e-mail]:adyaksa/openmpi.git

Jika anda memilih https:

	$ git clone https://gitlab.informatika.org/adyaksa/openmpi.git

3. Compile file yang `dijkstra.c` untuk menjadi executable file. gunakan perintah berikut untuk melakukan kompilasi.

	$ make

atau

	$ make all

Sama saja. Perintah tersebut akan menghasilkan sebuah executable file dengan name `djikstra` sekaligus mengirimkan file tersebut ke seluruh server server lain yang berada pada range IP Address `167.205.25.150 - 167.205.35.155`
4. Jalankan executable file yang telah dikompilasi dengan perintah berikut.

	$ mpirun -np {number_of_process} --host_file {hostfile_name} dijkstra {number_of_node}

Dalam kasus ini, kamu menggunakan
- numberofprocess = 10
- hostfile_name = mpi_hostfile
- number_of_node = antara 100, 500, 1000, dan 3000

# Pembagian Tugas
Pada dasarnya tugas dikerjakan bersama - sama menggunakan peranti LiveShare, sehingga commit dan push hanya dilakukan oleh salah satu pihak dari kami berdua.
Untuk algoritma Dijkstra yang digunakan pun juga kurang lebih adalah modifikasi dari algoritma yang ada di Geeksforgeeks. Jadi bisa dibilang kalau **pembagian kerjanya sama merata yaitu 50 - 50.**

# Laporan
## Deskripsi Solusi Paralel
Pada dasarnya solusi yang ditawarkan oleh kelompok kita bisa dibilang cukup sederhana. Stuktur data dari graf adalah sebuah adjacent matrix dari node i ke node j, pun sebaliknya. Maka kami membuat sebuah fungsi dengan nama `dijkstra` yang menerima sebuah source node dan mengembalikan *shortest distance* dari source yang menjadi masukannya menuju seluruh node lainnya. Setalah itu, dari semua proses yang tersedia, setiap proses di assign untuk menjalankan dijkstra pada source yang berbeda - beda dan mengirimkan kembali array shortest distance yang mereka hasilkan. Khusus untuk proses dengan rank 0, memiliki tugas tambahan untuk menggabungkan hasil dari proses proses yang lain (termasuk dia sendiri). Solusi yang kami gunakan sangat terkait dengan penggunaan metode `Send` dan `Receive` milik OpenMPI.

## Analisis Solusi
Solusi yang kami buat dapat memanfaatkan core-core lain dengan baik. Dikarenakan pada solusi sekuensial penggunaan dijkstra untuk tiap-tiap source node tidak ada dependency antara satu sama lain, jika kami membagikan proses dijkstra untuk setiap source node ke proses yang berbeda-beda, maka mereka tidak memerlukan komunikasi antara satu proses dengan proses lainnya. Yang mereka cukup lakukan adalah mengirimkan kepada master process hasil dari algoritma dijkstra yang telah mereka buat i.e. shortest path dari source node yang mereka dapat ke setiap node lainnya.

Selain itu, dengan dipekerjakannya process rank 0 untuk ikut mengerjakan Dijkstra akan menambah efektivitas algoritma, dikarenakan process tersebut tidak perlu idle hanya menunggu proses lain menyelesaikan komputasi dijkstra untuk dikirim kepadanya.

## Jumlah Thread
Pada percobaan yang kami lakukan, kami menggunakan sebanyak 10 proses untuk semua node yang kami coba. Alasan menggunakan sebanyak 10 proses dikarenakan diantara banyak proses-proses lain yang kami lakukan, angka ini merupakan angka yang cukup optimal untuk menjalankan dijkstra pada 100 node. Jika kami menambahkannya, maka overhead pada tiap proses akan lebih banyak dan membuat algoritma kami menjadi lambat. Sebagai tambahan, kami juga sudah mencoba coba dengan beberapa angka lain seperti 30 dan 50, namun dengan 30 atau 50 proses, tidak dapat menjalankan program yang menerima 1000 atau 3000 node.

## Pengukuran Kinerja
Pengukuran kinerja kami lakukan dengan cara menghitung berapa lama waktu yang dibutuhkan untuk membuat shortest path matrix untuk tiap node tanpa menghitung waktu pembuatan graf.

## Analisis Serial vs Paralel