# Tugas Besar 1 Sister

## 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

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

   sudo apt install gcc make

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

   git clone [e-mail]:ridwanhady/openmp.giti

Jika anda memilih https:

   git clone https://gitlab.informatika.org/ridwanhady/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`

4. Jalankan executable file yang telah dikompilasi dengan perintah berikut.

   ./dijkstra {number_of_process} {number_of_node}

Dalam kasus ini, kita menggunakan
- number_of_process = 2
- 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 mengisi matrix yang terletak pada global memory

### 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 mengisi shortest path matrix berdasarkan hasil dari algoritma dijkstra yang telah mereka buat i.e. shortest path dari source node yang mereka dapat ke setiap node lainnya.

### Jumlah Thread

Pada percobaan yang kami lakukan, kami menggunakan sebanyak 2 proses untuk semua node yang kami coba. Alasan menggunakan sebanyak 2 proses dikarenakan setelah menjalankan lebih dari 2 proses, tidak ada peningkatan performa sama sekali.



### 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

Berikut adalah hasil pengujian algoritma secara serial

1. Serial 100 Node


2. Serial 500 Node


3. Serial 1000 Node


4. Serial 3000 Node


Sedangkan berikut adalah hasil pengujian algoritma secara parallel

1. Paralel 100 Node


2. Paralel 500 Node


3. Paralel 1000 Node


4. Paralel 3000 Node


Berikut adalah tabel hasil rata rata dari pengujian tersebut.

| Jumlah Node | Serial(ms) | Parallel(ms) | % Peningkatan |
| :---------: | :---------: | :----------: | :-----------: |
| 100 | 14507.2 | 11296.2 | 128.4254882 |
| 500 | 1537029.2 | 288937.2 | 531.9596092 |
| 1000 | 12240462.4 | 4426122 | 276.5504973 |
| 3000 | 331826666.8 | 102763098.6 | 322.9044972 |

dari data diatas, didapatkan graf sebagai berikut:


Dari data data diatas, dapat ditarik beberapa kesimpulan:
1. Dengan N yang kecil (berkisar pada 100an), kecepatan komputasi secara parallel tidak jauh berbeda dengan serial, meskipun terlihat adanya peningkatan, namun peningkatan kecepatan yang dihasilkan tidak terlalu besar (20% lebih baik), bahkan untuk N dengan angka yang lebih kecil lagi, kami mencurigai bahwa kecepatan komputasi justeru turun. Hal ini disebabkan oleh adanya Overhead pada komputasi Parallel yang justru menjadi penghambat pada komputasi dijkstra dengan N yang sangat kecil.
2. N = 500 memiliki peningkatan yang terbesar dibanding yang lain, sekitar 5 kali lipat, sedangkan yang lain hanya sekitar 2-3 kali lipat. Sedangkan pada N = 1000 dan N = 3000, peningkatan tetap terjadi, namun tidak terlalu besar. Hal ini disebabkan oleh adanya Overhead, dan besarnya ukuran shortest distance dari suatu source yang semakin besar. Ditambah lagi, dengan digunakannya `long long` sebagai tipe data untuk menyimpan array, membuat array yang harus dikirimkan oleh tiap process lain semakin besar.

#TODO: Ganti kesimpulan