Praktikum 03
IF3230 - Sistem Paralel dan Terdistribusi
Petunjuk Penggunaan
$ make clean
$ make
$ ./dist/main <node-count> <filename>
untuk melakukan performance profiling bisa dengan
$ nvprof ./dist/main <node-count> <filename>
Pembagian Tugas
NIM | Nama | Fungsi Yang Dikerjakan |
---|---|---|
13517015 | I Putu Gede Wirasuta | Makefile, membuat calculate_sub_matrix menjadi kernel |
13517081 | M. Rifky I. Bariansyah | Eksperimen, memory management |
Laporan
Deskripsi solusi paralel
Solusi yang diimplementasikan tergolong coarse grained parallelism dengan detail sebagai berikut:
- Program melakukan inisialisasi adjacency matrix dengan mengalokasi managed memory sebesar
node_count
*node_count
dan mengisinya dengan nilairand()
yang memiliki seed 13517015. - Program mengalokasikan managed memory lain sebesar
node_count
*node_count
sebagai matrix yang akan menampung hasil algoritma dijkstra dari setiap node ke node lainnya. - Host akan menjalankan kernel
calculate_sub_matrix
yang menghitung jarak dari node start ke setiap node lain. Setiap kernel akan menghitung node yang sesuai dengan indeksnya sesuai perhitungan berikut
nodeIdx = (blockIdx.x * blockDim.x) + threadIdx.x + k * stride, k \in \mathbb{Z}
stride = blockDim.x * gridDim.x
- Hasil perhitungan langkah 3 akan disimpan pada matrix yang telah dialokasikan pada langkah 2.
- Host akan menunggu seluruh device selesai menjalankan kernel sebelum melanjutkan eksekusi, yaitu mencetak matrix distance ke file dan ke
stdout
(opsional).
Analisis solusi yang anda berikan
Alokasi managed memory hanya dilakukan sekali di host dan digunakan berkali-kali di kernel karena menurut jawaban stackoverflow ini, alokasi memori pada kernel akan memperlambat kinerja secara signifikan.
Kami juga memutuskan untuk menjalankan calculate_sub_matrix
secara paralel bukan suatu bagian di dalam algoritma dijkstra untuk meminimasi jumlah syncronization yang perlu dilakukan. Fungsi calculate_sub_matrix
sebenarnya hanyalah fungsi perantara yang menerjemahkan indeks suatu thread menjadi node yang harus dikerjakan dan menjalankan algoritma dijkstra dengan parameter yang sesuai. Selain itu, algoritma dijkstra yang diimplementasikan hanya melakukan operasi matematika sederhana yaitu penjumlahan dan perbandingan sehingga dapat dijalankan seluruhnya pada device.
Jumlah thread yang digunakan
Jumlah thread yang digunakan pada praktikum ini adalah sebesar 1024 thread/block dengan 1024 block. Jumlah ini dipilih karena beberapa pertimbangan berikut
- Server menggunakan GPU GTX 1080 dengan kapabilitas maksimum thread per block sebanyak 1024 dan maksimum grid size >>1024.
- Maksimal kasus uji sebanyak 3000 sebenarnya dapat dipenuhi dengan menghitung nilai dijkstra pada 3 block saja. Namun, dari beberapa variasi yang diujikan didapatkan bahwa dengan 1024 block didapatkan average execution time paling baik dan paling konsisten.
Pengukuran kinerja dalam ms
Serial
N | 1 | 2 | 3 | Average |
---|---|---|---|---|
100 | 3274.88 | 3223.23 | 3250.64 | 3249.583 |
500 | 93647.7 | 111736 | 93145.5 | 99509.73 |
1000 | 787852 | 865208 | 777466 | 810175.33 |
3000 | 4.6 * 10^7 | 4.6 * 10^7 | 4.7 * 10^7 | 4.633 * 10^7 |
Parallel
N | 1 | 2 | 3 | Average |
---|---|---|---|---|
100 | 17.44 | 17.369 | 17.441 | 17.416 |
500 | 697.94 | 701.8 | 698.26 | 699.1533 |
1000 | 5425.44 | 5775.16 | 5774.67 | 5658.423 |
3000 | 138207 | 140591 | 120469 | 133089 |
Analisis perbandingan kinerja serial dan paralel
Terdapat peningkatan kinerja yang signifikan hingga ~191 kali lebih cepat, dua hal yang menjadi faktor utama hal ini adalah
- Kapabilitas satu CUDA core yang sangat terbatas dibandingkan CPU (dari segi memory dan processing power) untuk >= 100 node. Hal ini menyebabkan waktu eksekusi serial yang melambat secara signifikan seiring bertambahnya jumlah node.
- Kapabilitas satu CUDA core yang mumpuni untuk menghitung beberapa node dengan jumlah < 100 dan managed memory sehingga data-parallelism berlangsung sangat baik.