Laporan
Petunjuk penggunaan program
Untuk menjalankan program ini, cukup ketikkan make. Command make akan melakukan kompilasi dan kemudian akan menjalankan program yang telah dibuat pada Makefile.
Setelah dijalankan, user diminta untuk melakukan input jumlah node yang akan dibangun, seed yang akan digunakan untuk membangun gaf random. Output yang akan dihasilkan yaitu berupa waktu eksekusi dan juga matriks yang berisi jarak terpendek dari dan ke setiap node ke dalam file.
Pembagian tugas
- Abel Stanley 13517068 mengerjakan dijkstra paralel dan dijkstra serial.
- Renita Napitupulu 13517134 mengerjakan dijkstra paralel dan dijkstra serial.
Laporan pengerjaan
-
Solusi paralel yang diberikan yaitu dengan membagi perhitungan dijkstra sebanyak node yang dibangkitkan atau dapat juga dikatakan dengan membagi matriks menjadi sub bagian berdasarkan baris. Untuk eksekusi dari proses paralelnya yaitu dengan menggunakan #pragma omp for schedule(dynamic) nowait sehingga tidak ada assign pada awalnya node tertentu harus dikerjakan thread yang mana sehingga setelah sebuah thread selesai mengeksekusi satu proses dijkstra untuk satu node, thread tersebut akan mengeksekusi node lain secara random yang masih belum dieksekusi. Namun, untuk perhitungan dijkstra untuk satu node dipastikan hanya akan dijalankan oleh satu thread dengan perintah #pragma omp single. Selain itu, untuk memastikan bahwa solusi yang dihasilkan tetap sinkron, solusi yang ditawarkan juga menggunakan #pragma omp barrier.
-
Kami telah mencoba beberapa solusi lain dalam kasus ini. Solusi tersebut yaitu dengan cara mempartisi sub-problem berdasarkan kolom. Sehingga untuk perhitungan dijkstra yang dilakukan yaitu dengan menghitung jarak minimum lokal untuk setiap kolom dari matriks pada satu thread yang kemudian akan dicek kembali ke minimum global secara umum untuk menghasilkan jarak minimun akhir dari start node ke semua node lain. Namun, ternyata setelah dijalankan waktu eksekusi yang dihasilkan lebih lama dari solusi yang ditawarkan sebelumnya. Hal ini kemungkinan dikarenakan dengan solusi seperti ini, jumlah overhead yang terjadi untuk setiap thread lebih banyak dikarenakan dalam setiap thread dibutuhkan untuk melakukan looping lain untuk menghasilkan jarak minimum secara global. Dengan demikian, sejauh ini belum ada solusi yang mungkin lebih baik yang dapat kami tawarkan.
-
Untuk jumlah thread yang digunakan yaitu random, sesuai dengan hasil dari omp_get_num_threads(). Untuk jumlah thread yang digunakan dalam program ini yaitu 8 yang diperoleh dari omp_get_num_threads().
-
Pengukuran kinerja
-
Untuk serial:
-
100 nodes:
Algorithm execution time is 3000.000000 microseconds -
500 nodes:
Algorithm execution time is 1365000.000000 microseconds -
1000 nodes:
Algorithm execution time is 11220000.000000 microseconds -
3000 nodes:
Algorithm execution time is 384388000.000000 microseconds
-
-
Untuk paralel:
-
100 nodes:
Algorithm execution time is 9251.000000 microseconds -
500 nodes:
Algorithm execution time is 223472.000000 microseconds -
1000 nodes:
Algorithm execution time is 1661057.000000 microseconds -
3000 nodes:
Algorithm execution time is 54587956.000000 microseconds
-
-
Analisis perbandingan kinerja : Dari pengukuran kinerja yang telah dilakukan, dapat disimpulkan bahwa untuk jumlah node yang tergolong kecil, algoritma Djikstra dengan proses serial lebih cepat waktu eksekusinya sehingga tergolong lebih efektif. Hal ini karena adanya proses #pragma omp parallel yang dilakukan oleh proses paralel.
Namun, untuk jumlah node yang sudah tergolong besar, pendekatan dengan teknik paralel menghasilkan waktu eksesusi yang lebih cepat dibandingkan dengan serial. Hal ini dikarenakan adanya proses paralel yaitu dengan membagi proses-proses eksekusi ke dalam beberapa thread dan dikerjakan secara bersamaan dan tidak ada thread yang akan menganggur dalam eksekusinya sehingga waktu yang dibutuhkan untuk penyelesaiannya dapat menjadi lebih cepat dibandingkan dengan mengeksekusi secara satu per satu dalam teknik serial.