Nur Alam Hasabie

OpenMP

Repository



Dijkstra Parallel

Cara penggunaan

Masuk ke folder src
Jalankan perintah make pada direktori src yang akan menghasilkan executable di folder bin
Program kemudian akan menghasilkan keluaran waktu yang dibutuhkan untuk menjalankan algoritma dalam detik. Harap bersabar.
Hasil output ada di folder out/, dan dibedakan antara hasil parallel dengan sekuensial


Deskripsi Solusi Paralel
Terdapat dua cara mengubah Algoritma Dijkstra sekuensial menjadi algortima Dijkstra parallel :

Melakukan paralelisasi dengan membagi simpul-simpul ke beberapa proses, dan tiap proses menjalankan algoritma terhadap simpul-simpulnya
Melakukan paralelisasi dengan membagi simpul-simpul pada Algortima Dijkstra dari sebuah simpul sumber ke beberapa proses, dan melakukan pengubahan nilai jarak minimum global dari minimum jarak minimum lokal.

Kami berpendapat bahwa cara (2) merupakan cara yang lebih mampu menampilkan perubahan algoritma sekuensial menjadi parallel.
Algoritma Dijkstra parallel adalah sebagai berikut :

Membagi simpul-simpul V ke dalam proses-proses V, sehingga setiap proses memproses V/P simpul.
Setiap proses kemudian mencari lokal minimum
Prosedur Allreduce dipanggil , kemudian prosedur mengganti global minimum
Tiap proses kemudian mengganti nilai jarak simpul-simpulnya berdasarkan informasi global minimum baru.
Proses dilakukan sehingga seluruh simpul sudah dikunjungi. Matriks jarak sudah berisi informasi jarak terpendek dari suatu simpul ke simpul lainnya.


Analisis Solusi
Solusi akan memiliki kompleksitas O(V^2/P + Vlog(P)), dengan V adalah kompleksitas ruang graf dan P adalah jumlah proses/threads.
Untuk mengunjungi tiap simpul, dibutuhkan waktu O(V), dan pada tiap kunjungan dibutuhkan waktu O(V) (untuk update) + O(log(P)) (untuk menentukan minimum global).
Secara teoretis,  nilai P optimal pada P = V/log(e) , namun nilai ini dirasa aneh karena P > V.

Jumlah Thread
Kami mengadakan pengujian di dua buah sistem komputer, yakni :

Komputer lokal, dengan CPU Intel Quad-core
Komputer server sebanyak 5 buah.

Oleh karena itu, kami mengambil jumlah thread sebanyak 2,4 dan 5. Berdasarkan Amdahl's law, terdapat batas maksimum efisiensi, dan kami menghindari penggunaan thread yang terlalu banyak sehingga menyebabkan overhead berlebih dalam thread synchronization dan context switching.

Perbandingan Kinerja
Berikut adalah perbandingan kinerja parallel dengan sekuensial pada komputer lokal.

    
            N-nodes
            Serial
            Parallel, P=2 (ms) 
            Parallel, P=4 (ms) 
            Parallel, P=5 (ms) 
        
    
            100
            47.309
            43.307
            86.499
            395.766
        
        
            31.567
            30.946
            57.147
            383.49
            
        
            32.326
            31.270
            63.854
            384.571
        
        
            500
            1408.569
            923.586
            1208.453
            7606.861
        
        
            1350.843
            1032.324
            1186.994
            7518.716
            
        
            1378.718
            931.518
            1276.992
            7606.861
        
        
            1000
            11662.515
            6893.559
            8765.861
            33437.691
        
        
            14608.605
            6866.290
            8959.736
            35122.012
            
        
            11705.083
            6314.995
            8925.853
            35882.580
        
        
            3000
            308214.490
            87713.400
            78582.652
            344314.804
        
        
            311432.521
            87383.466
            87188.438
            347234.974
            
        
            309983.532
            85272.113
            92601.908
            349824.743
        
    
Berikut diberikan tabel hasil percobaan di komputer server.

    
            N-nodes
            Serial
            Parallel, P=2 (ms) 
            Parallel, P=4 (ms) 
            Parallel, P=5 (ms) 
        
    
            100
            12.345
            22.942
            227.098
            270.841
        
        
            12.112
            20.902
            262.319
            279.531
            
        
            11.675
            20.043
            258.911
            252.268
        
        
            500
            1349.300
            782.624
            6826.791
            7056.164
        
        
            1318.866
            806.957
            6713.547
            7250.220
            
        
            1341.243
            770.054
            6870.200
            7287.790
        
        
            1000
            10898.800
            4336.605
            28275.934
            30105.151
        
        
            10842.197
            4426.636
            28622.676
            29914.231
            
        
            10958.058
            4327.368
            28412.916
            29516.053
        
        
            3000
            296934.291
            89174.651
            314459.550
            469177.794
        
        
            297367.153
            89543.502
            317896.231
            384064.668
        
        
            300659.377
            89376.745
            318422.519
            379724.221
        
    
Analisis
Pertama, dapat dilihat bahwa program parallel berjalan lebih efisien seiring bertambahnya problem size. Dapat diambil kesimpulan sementara bawah program ini weakly scalable.
Kedua , program parallel memiliki kecepatan sekitar tiga-empat kali lipat untuk P=2, akan tetapi kecepatan yang demikian tidak terlihat pada problem size yang kecil. Hal ini dihipotesakan terjadi karena adanya overhead yang konstan , dan overhead semakin kecil dampaknya terhadap performa program keseluruhan saat problem size semakin besar.

Pembagian Tugas
Juniardi Akbar (13517075) :

Algoritma Dijkstra Sekuensial
Benchmarking
Laporan

Nur Alam Hasabie (13517096) :

Algoritma Dijkstra Parallel
Membuat makefile
Laporan
Timer


Referensi
[1] Pore, A. D. I. T. Y. A. (2014). Parallel implementation of Dijkstra’s algorithm using MPI library on a cluster.
[2] Ye, Zilong. "An Implementation of Parallelizing Dijkstra’s Algorithm."