Skip to content
Snippets Groups Projects
user avatar
Barbariansyah authored
6ea9d6f1
Forked from IF3230-2020 / CUDA
10 commits ahead of the upstream repository.
Name Last commit Last update
output
src
.gitignore
Makefile
README.md

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:

  1. Program melakukan inisialisasi adjacency matrix dengan mengalokasi managed memory sebesar node_count * node_count dan mengisinya dengan nilai rand() yang memiliki seed 13517015.
  2. Program mengalokasikan managed memory lain sebesar node_count * node_count sebagai matrix yang akan menampung hasil algoritma dijkstra dari setiap node ke node lainnya.
  3. 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
  1. Hasil perhitungan langkah 3 akan disimpan pada matrix yang telah dialokasikan pada langkah 2.
  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

  1. Server menggunakan GPU GTX 1080 dengan kapabilitas maksimum thread per block sebanyak 1024 dan maksimum grid size >>1024.
  2. 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

  1. 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.
  2. Kapabilitas satu CUDA core yang mumpuni untuk menghitung beberapa node dengan jumlah < 100 dan managed memory sehingga data-parallelism berlangsung sangat baik.