# Tugas Besar 1 Sister

## Petunjuk Penggunaan

!!!**Dengan asumsi semua langkah - langkah berikut dilakukan pada server itb yang memiliki dengan IP Address** `167.205.35.100`!!!

1. Siapkan prereq yang dibutuhkan, yaitu:
- Cuda Toolkit

Untuk menginstall cuda Toolkit, silahkan ikuti arahan pada link berikut <https://developer.nvidia.com/cuda-downloads>

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

   git clone [e-mail]:ridwanhady/cuda.git

Jika anda memilih https:

   git clone https://gitlab.informatika.org/ridwanhady/cuda.git

3. Masuk ke folder `src`. Hal tersebut dapat dilakukan dengan menggunakan perintah berikut.

    cd src

4. Compile file yang `dijkstra.cu` 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`

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

   ./dijkstra {number_of_node} {number_of_blocks} {number_of_threads}

Dalam kasus ini, kita menggunakan
- `number_of_blocks` = 10
- `number_of_threads` = 256
- `number_of_node` = antara 100, 500, 1000, dan 3000

6. Apabila program melaporkan adanya segmentation fault. pastikan telah terdapat folder `output` di dalam direktori `cuda`.

- **output/**
- src/
- dijkstra.cu
- Makefile
- img/
- .gitignore
- README.md

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

Sebelum menjalankan solusi paralel, kami melakukan pembangkitan graph hanya pada CPU, kemudian graph tersebut dicopykan ke masing - masing device yang tersedia. Dikarenakan struktur data graf berupa array 2 dimensi sementara cuda tidak menyediakan cara mudah untuk mencopy data 2 dimensi dari host ke device, maka data graf yang kami simpan berada dalam bentuk array 1 dimensi. Saat data akan diakses, maka ia akan secara otomatis diubah menjadi sebuah array 2 dimensi oleh sebuah fungsi bawaan C++.

Selanjutnya untuk algoritma dijkstra. 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 device - device dengan baik. Dikarenakan pada solusi sekuensial, perhitungan dijkstra hanya dilakukan di CPU. Sedangkan pada solusi parallel yang kami berikan, kami telah memanfaatkan GPU juga sebagai pendukung komputasi. Pada solusi kami terjadi komunikasi antara host-device, yaitu pengiriman data graf dan hasil shortest path dari algoritma Dijkstra. Dikarenakan solusi kami tidak memerlukan komunikasi antar thread melainkan hanya berupa komunikasi host-device, maka kami juga tidak perlu memanfaatkan shared memory dari cuda. Hal ini mengakibatkan alur pengiriman informasi menjadi lebih simpel, dimana kita dapat mengatur banyak block lebih bebas.

### Jumlah Thread

Pada dasarnya tujuan utama kami adalah untuk memaksimalkan kinerja pada kasus dengan 3000 Node. **256 thread dan 10 block** memiliki trade-off untuk menjalankan 3000 Node sekaligus kasus kasus dengan jumlah node lain, walau, benar disayangkan dengan pemilihan angka tersebut, pada solusi parallel dengan 100 node justru menjadi lebih lambat dari solusi serial. Namun kami telah membahas pula hasil tersebut pada bagian akhir mengenai analisa hasil percobaan.

### 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. Pengujian serial adalah menggunakan data pada pengujian sebelumnya, yaitu dengan menjalankan pada CPU biasa, dengan 1 process saja.

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) | % Perbandingan |
| :---------: | :---------: | :----------: | :------------: |
| 100 | 11286.2 | 38677 | 29.18065 |
| 500 | 1285486.8 | 862637 | 149.01820 |
| 1000 | 10627250.6 | 3540288 | 300.1803978 |
| 3000 | 313225875.2 | 89354600 | 350.5425297 |

Dari data data diatas, dapat diambil beberapa kesimpulan:

1. Dengan jumlah node yang kecil, jika kita menggunakan terlalu banyak thread dan block, kecepatan justru akan turun, bahkan pada percobaan kita, peningkatkan hampir 3 kali lipat lebih lambat dari pada serial.
2. Untuk data yang semakin besar, penggunaan CUDA untuk komputasi terbukti meningkatkan performa dengan sangat signifikan, yaitu sekitar 3 kali lipat daripada dijalankan secara serial. Sedangkan pada komputasi komputasi tugas sebelumnya, seperti OpenMP, hanya sekitar 2 kali lipat saja.
3. Diperlukan jumlah thread dan block yang sesuai dengan ukuran dari masing masing komputasi yang dibutuhkan, sehingga tidak bisa diseragamkan bagaimana pemilihan angka dari block dan thread tersebut.
4. Seluruh kinerja dari CUDA diatas, kami ketahui masih bisa ditingkatkan lebih lanjut lagi dengan menggabungkan solusi CUDA dan OpenMP atau MPI. Hal ini akan membuat komputasi baik pada Device maupun Host berjalan secara parallel dan terdistribusi. Namun hal ini masih diluar dari cakupan eksperimen ini.