UTS IF3130 2019-2020

Back to IF3130 Sistem Paralel dan Terdistribusi

[UMUM]

1. Analisis Kinerja dan Skalabilitas

Suatu program paralel mempunyai bagian yang tidak bisa diparalelkan sebanyak 20%, sedangkan 80% bisa dikodekan secara paralel. Misalkan program tersebut dijalankan di komputer dengan single core dan waktu eksekusinya Tser = n. Jika program tsb dijalankan pada multicore sebanyak p, maka:

a. Hitunglah Tpar dan SpeedUp (S) dari program tersebut (asumsi overhead nya= 0).

b. Andaikan program bisa diparalelkan 100%, tetapi ada tambahan overhead 1, jika jumlah corenya ditambah sebanyak k kali (menjadi kp processor), apakah program tersebut scalable? Jika ya, apakah strongly scalable atau weakly scalable? (tunjukkan dengan perhitungan)

Jawaban (a): Perhitungan Tpar dan SpeedUp

Ini adalah aplikasi langsung dari Hukum Amdahl.
- Fraksi serial (s) = 20% = 0.2
- Fraksi paralel (1-s) = 80% = 0.8
- Waktu eksekusi serial ( $T_{ser}$ ) = n
Waktu eksekusi paralel (Tpar) dihitung sebagai:

$T_{p a r} = (T_{ser} \times s) + \frac{T _{ser} \times ( 1 - s )}{p}$

$T_{p a r} = (n \times 0.2) + \frac{n \times 0.8}{p} = 0.2 n + \frac{0.8 n}{p}$

SpeedUp (S) dihitung sebagai:

$S = \frac{T _{ser}}{T _{p a r}} = \frac{n}{0.2 n + \frac{0.8 n}{p}}$

Dengan membagi pembilang dan penyebut dengan n, didapatkan $S = \frac{1}{0.2 + \frac{0.8}{p}}$
Jawaban (b): Analisis Skalabilitas

Asumsi: Program 100% paralel, Tser=n, overhead = 1.
- Waktu paralel awal ( $p$ prosesor): $T_{p a r} (p, n) = \frac{n}{p} + 1$
- Waktu paralel baru ( $k \times p$ prosesor): $T_{p a r} (k p, n) = \frac{n}{k p} + 1$
Untuk menguji skalabilitas, kita periksa efisiensi ( $E = \frac{S}{p} = \frac{T _{ser}}{p \times T _{p a r}}$ ).
- Strong Scalability (problem size n tetap):
  
  Efisiensi pada kp prosesor adalah:
  
  $E_{s t ro n g} = \frac{T _{ser}}{k p \times T _{p a r} ( k p , n )} = \frac{n}{k p \times ( \frac{n}{k p} + 1 )} = \frac{n}{n + k p}$
  
  Saat jumlah prosesor meningkat (k membesar), nilai n+kp akan membesar, sehingga efisiensi (Estrong) akan menurun. Program ini tidak strongly scalable.
- Weak Scalability (problem size n diskalakan, misal n′=kn):
  
  Kita menjaga agar beban kerja per prosesor tetap. Waktu paralel pada kp prosesor dengan problem size kn adalah:
  
  $T_{p a r} (k p, kn) = \frac{kn}{k p} + 1 = \frac{n}{p} + 1$
  
  Waktu eksekusi paralel tetap konstan ( $T_{p a r} (p, n) = \frac{n}{p} + 1$ vs $T_{p a r} (k p, kn) = \frac{n}{p} + 1$ . Karena waktu eksekusi tidak bertambah meskipun jumlah prosesor dan ukuran masalah ditingkatkan secara proporsional, program ini weakly scalable.

2. False Sharing

Jelaskan bagaimana terjadinya false-sharing, berikan contoh/ilustrasi. False sharing dapat menurunkan performansi, jelaskan alasannya.

Jawaban:
- Bagaimana Terjadi: False sharing terjadi pada sistem multiprosesor dengan memori cache yang koheren. Ini terjadi ketika dua atau lebih prosesor mengakses variabel yang berbeda, namun variabel-variabel tersebut secara kebetulan berada pada cache line (blok memori) yang sama. Meskipun secara logika tidak ada sharing data, perangkat keras menganggap seluruh cache line sebagai unit yang di-share.
- Ilustrasi/Contoh:
  
  Bayangkan sebuah array int data[2]; dimana data[0] dan data[1] berada dalam satu cache line.
  1. Prosesor 1 (Core 1) ingin memodifikasi data[0]. Core 1 memuat cache line yang berisi data[0] dan data[1] ke dalam cache-nya.
  2. Prosesor 2 (Core 2) ingin memodifikasi data[1]. Core 2 juga memuat cache line yang sama ke dalam cache-nya.
  3. Core 1 menulis ke data[0]. Sesuai protokol koherensi cache (misalnya MESI), salinan cache line di Core 2 sekarang menjadi tidak valid (invalidated).
  4. Core 2 sekarang ingin menulis ke data[1]. Karena salinan cache line-nya tidak valid, ini menyebabkan cache miss. Core 2 harus mengambil salinan terbaru dari cache line tersebut dari Core 1 atau memori utama.
  5. Ketika Core 2 menulis ke data[1], salinan di Core 1 menjadi tidak valid.
    
    Proses ini berlanjut, menyebabkan ping-pong effect di mana cache line terus-menerus dipindahkan antar cache prosesor.
- Alasan Penurunan Performa:
  
  Perpindahan cache line yang konstan ini menyebabkan latensi yang signifikan. Setiap kali sebuah cache line harus divalidasi dan diambil kembali dari cache lain atau memori utama, prosesor mengalami penundaan (stall) yang jauh lebih lama daripada jika data sudah ada di cache-nya. Hal ini meningkatkan lalu lintas pada bus interkoneksi dan secara drastis menurunkan performa, meskipun secara logis program tidak melakukan sharing data.

[MPI]

3. MPI Sendrecv dan Thread Safety

void Odd_even_iter(int local_A[], int temp_B[], int temp_C[], int local_n, int phase, int even_partner, int odd_partner, int my_rank, int p, MPI_Comm comm) { MPI_Status status;
	if (phase % 2 == 0) { if (even_partner >= 0) {
		MPI_Sendrecv(local_A, local_n, MPI_INT, even_partner, 0, temp_B, local_n, MPI_INT, even_partner, 0, comm, &status);
		if (my_rank % 2 != 0)
			Merge_high(local_A, temp_B, temp_C, local_n); elseMerge_low(local_A, temp_B, temp_C, local_n); }
		} else {
	//(----------------------dst--------------------)

a. Pada code diatas ada perintah MPI_Sendrecv(), perintah tersebut jika diganti dengan MPI_send() dan MPI_Recv() menjadi: (lengkapi i s/d iv).

void Odd_even_iter(int local_A[], int temp_B[], int temp_C[], int local_n, int phase, int even_partner, int odd_partner, int my_rank, int p, MPI_Comm comm) { MPI_Status status;
	if (phase % 2 == 0) { if (even_partner >= 0) { 
		if (my_rank % 2 != 0) {
			(i).............................................
			(ii)............................................
			Merge_high(local_A, temp_B, temp_C, local_n);
		} else {
			(iii)...........................................
			(iv)............................................
			Merge_low(local_A, temp_B, temp_C, local_n); }
		}
	} else {
	//(----------------------dst--------------------)

b. Perintah MPI_Sendrecv() adalah thread-safe, jelaskan yang dimaksud dengan thread-safe.

Jawaban (a): Mengganti MPI_Sendrecv

Untuk menghindari deadlock, satu proses harus mengirim terlebih dahulu sementara pasangannya menerima, lalu mereka bertukar peran. Dalam odd-even sort, proses ganjil (my_rank % 2 != 0) berkomunikasi dengan proses genap. Kita bisa menetapkan aturan bahwa proses dengan rank lebih tinggi mengirim lebih dulu, atau seperti di bawah ini, proses ganjil mengirim lebih dulu.

// (i) dan (ii) untuk my_rank ganjil
if (my_rank % 2 != 0) {
    // (i) Mengirim data ke partner genap
    MPI_Send(local_A, local_n, MPI_INT, even_partner, 0, comm);
    // (ii) Menerima data dari partner genap
    MPI_Recv(temp_B, local_n, MPI_INT, even_partner, 0, comm, &status);
    Merge_high(local_A, temp_B, temp_C, local_n);
} else { // (iii) dan (iv) untuk my_rank genap
    // (iii) Menerima data dari partner ganjil
    MPI_Recv(temp_B, local_n, MPI_INT, even_partner, 0, comm, &status);
    // (iv) Mengirim data ke partner ganjil
    MPI_Send(local_A, local_n, MPI_INT, even_partner, 0, comm);
    Merge_low(local_A, temp_B, temp_C, local_n);
}

Jawaban (b): Thread-safe

Thread-safe berarti sebuah fungsi atau pustaka dapat dipanggil secara bersamaan oleh beberapa thread dari dalam proses yang sama tanpa menyebabkan race condition, kerusakan data, atau perilaku tak terduga. Pustaka MPI yang thread-safe memastikan bahwa struktur data internal yang digunakannya untuk mengelola komunikasi dilindungi dari akses serentak. Ini memungkinkan programmer untuk menggunakan model pemrograman hibrida (misalnya MPI + OpenMP) di mana beberapa thread dalam satu proses MPI dapat melakukan panggilan komunikasi MPI secara independen dan aman.

[Shared Memory]

4. Sinkronisasi pada Linked List

Diberikan suatu linked list, manakah dari kasus di bawah ini yang bila dilakukan secara paralel berpotensi mengakibatkan masalah terkait critical section (I)? Sertakan penjelasan pada jawaban Anda (II) serta jelaskan bagaimana pemrograman menggunakan PThread menangani persoalan tersebut (III)! Bonus (IV): Apakah istilah umum dari problem sinkronisasi tersebut?

Jawaban:
- (I) Kasus Bermasalah:
  
  Kasus b, c, dan d berpotensi mengakibatkan masalah.
  - b. Proses Insert dan Delete. (Write-Write conflict)
  - c. Proses Delete dan IsMember. (Write-Read conflict)
  - d. Proses IsMember dan Insert. (Read-Write conflict)
- (II) Penjelasan:
  
  Masalah terjadi karena operasi Insert dan Delete adalah operasi tulis yang memodifikasi struktur pointer dari linked list. Operasi IsMember adalah operasi baca yang melintasi struktur pointer tersebut. Jika satu thread sedang memodifikasi pointer (misalnya, menghapus sebuah node) sementara thread lain sedang membacanya, thread pembaca bisa saja mengikuti pointer yang sudah tidak valid (menyebabkan crash) atau melewatkan node (hasil salah). Jika dua thread mencoba memodifikasi list secara bersamaan, struktur list bisa menjadi korup (misalnya, node hilang atau terbentuknya siklus).
- (III) Penanganan dengan PThread:
  
  Masalah ini ditangani dengan menggunakan mutex (pthread_mutex_t). Sebuah mutex digunakan untuk melindungi critical section (bagian kode yang mengakses linked list).
  1. Inisialisasi sebuah mutex global untuk linked list.
  2. Sebelum thread mana pun memanggil Insert atau Delete, ia harus mengunci mutex terlebih dahulu dengan pthread_mutex_lock().
  3. Setelah operasi selesai, thread tersebut harus melepaskan kunci dengan pthread_mutex_unlock().
    
    Ini memastikan bahwa hanya satu thread yang dapat memodifikasi linked list pada satu waktu, menjaga integritas data.
- (IV) Bonus - Istilah Umum:
  
  Istilah umum untuk masalah sinkronisasi ini adalah Readers-Writers Problem.

5. OpenMP critical vs atomic

Diberikan dua bagian kode program menggunakan OpenMP.
/* I */              /* II */
int count = 0;       int count = 0;
#pragma omp critical #pragma omp atomic
count++;             count++;
a. Apakah terdapat perbedaan pada kedua hasil count? Berikan penjelasan! b. Apa keuntungan penggunaan direktif atomic ketimbang critical? c. Pada keadaan apa direktif critical lebih baik digunakan ketimbang atomic?

Jawaban:
- a. Perbedaan Hasil: Tidak ada perbedaan pada hasil akhir count. Kedua direktif, critical dan atomic, menjamin mutual exclusion untuk operasi count++, sehingga mencegah race condition. Keduanya akan menghasilkan nilai count yang benar dan sama.
- b. Keuntungan atomic: Keuntungan utama atomic adalah performa. Direktif atomic memberikan petunjuk kepada compiler bahwa operasi tersebut dapat diimplementasikan menggunakan satu instruksi perangkat keras khusus yang atomik (misalnya, LOCK XADD pada x86). Instruksi ini jauh lebih ringan dan cepat daripada mekanisme penguncian (lock) umum yang digunakan oleh critical.
- c. Kapan critical lebih baik: Direktif critical lebih baik (dan satu-satunya pilihan) ketika critical section yang perlu dilindungi terdiri dari blok kode yang kompleks atau lebih dari satu pernyataan. atomic hanya dapat digunakan untuk operasi pembaruan memori tunggal yang sederhana (seperti x++, x=x+y), sedangkan critical dapat melindungi beberapa baris kode, termasuk pemanggilan fungsi.

[GPU]

6. Analisis Coalescing pada Perkalian Matriks

__global__ void MatrixMulKernel(float* M, float* N, float* P, int Width) { 
	int Row = blockIdx.y*blockDim.y+threadIdx.y; int Col = blockIdx.x*blockDim.x+threadIdx.x; 
	if ((Row < Width) && (Col < Width)) { 
		float Pvalue = 0; 
		for (int k = 0; k < Width; ++k) {
			Pvalue += M[Row*Width+k] * N[k*Width+Col];
		}
		P[Row*Width+Col] = Pvalue;
	}
}
Pilihlah mana yang benar dari pertanyaan berikut:

a. M[RowWidth+k] dan N[kWidth+Col] coalesced tapi P[RowWidth+Col] tidak b. M[RowWidth+k], N[kWidth+Col] dan P[RowWidth+Col] semua coalesced c. M[RowWidth+k] tidak coalesced tapi N[kWidth+Col] dan P[RowWidth+Col] coalesced d. M[RowWidth+k] coalesced tapi N[kWidth+Col] dan P[RowWidth+Col] tidak

Jawaban: b. M[RowWidth+k], N[kWidth+Col] dan P[Row*Width+Col] semua coalesced
Penjelasan:

Asumsi standar adalah warp (32 thread) memiliki threadIdx.y yang sama dan threadIdx.x yang berurutan.
- P[Row*Width+Col]: Row konstan dalam warp, Col berurutan. Alamat memori yang diakses berurutan. Ini adalah akses coalesced.
- M[Row*Width+k]: Selama loop k, Row konstan dalam warp. Semua thread dalam warp mengakses elemen M yang sama. Ini adalah broadcast, yang sangat efisien dan dianggap sebagai pola akses yang baik (mirip coalesced).
- N[k*Width+Col]: Untuk nilai k tertentu, Col berurutan dalam warp. Ini berarti warp mengakses elemen-elemen yang berurutan di dalam baris ke-k dari matriks N. Ini juga akses coalesced.
  
  Meskipun secara keseluruhan algoritma ini memiliki masalah lokalitas data (yang dipecahkan dengan tiling), transaksi memori individual per warp pada dasarnya sudah coalesced.

7. Perhitungan Jumlah Warp

Diberikan kode berikut untuk mengolah gambar 600x800 … Jika digunakan blok berukuran 16x16, tentukan jumlah warp yang digunakan saat eksekusi kernel di atas.

a. 37*16 b. 38*50 c. 38*8*50 d. 38*50*2

Jawaban: c. 38850
Penjelasan:
1. Dimensi Grid (dalam blok):
  - Jumlah blok pada sumbu x = ceil(lebar_gambar / lebar_blok) = ceil(800 / 16) = 50 blok.
  - Jumlah blok pada sumbu y = ceil(tinggi_gambar / tinggi_blok) = ceil(600 / 16) = ceil(37.5) = 38 blok.
2. Total Blok: 50 * 38 blok.
3. Threads per Blok: 16 * 16 = 256 thread.
4. Warp per Blok: threads_per_blok / ukuran_warp = 256 / 32 = 8 warp per blok.
5. Total Warp: Total Blok * Warp per Blok = (50 * 38) * 8 = 38 * 8 * 50.

8. Scope Shared Memory

Sebuah kernel dijalankan dengan menggunakan 1000 thread block yang masing-masing terdiri atas 512 thread. Jika sebuah variabel dideklarasikan sebagai shared memory variable, ada berapa versi kah variable tersebut selama eksekusi kernel?

a. 1 b. 1000 c. 512 d. 512000

Jawaban: b. 1000
Penjelasan:

Shared memory memiliki scope per-thread block. Setiap block memiliki salinan pribadi dari variabel shared memory yang dideklarasikan. Jika ada 1000 thread block yang dieksekusi, maka akan ada 1000 versi/instansi dari variabel tersebut.

9. Reduksi Bandwidth dengan Tiling

Pada kernel perkalian matriks di GPU dengan menggunakan tiling, jika digunakan tile berukuran 32x32, berapakah reduksi/pengurangan bandwidth memory yang digunakan untuk input matriks A dan B?

a. 1/8 dari penggunaan awal b. 1/16 dari penggunaan awal c. 1/32 dari penggunaan awal d. 1/1024 dari penggunaan awal

Jawaban: c. 1/32 dari penggunaan awal
Penjelasan:

Dengan tiling, sebuah blok tile (misalnya 32x32) dari matriks A dan B dimuat dari global memory ke shared memory yang jauh lebih cepat. Setiap elemen yang dimuat ke shared memory kemudian digunakan kembali sebanyak TILE_SIZE kali (dalam hal ini, 32 kali) oleh thread-thread di dalam blok tersebut. Tanpa tiling, setiap elemen harus dibaca dari global memory sebanyak 32 kali. Dengan tiling, setiap elemen hanya dibaca dari global memory satu kali per fase tiling. Ini mengurangi kebutuhan bandwidth memori global sekitar faktor TILE_SIZE, yaitu 32. Jadi, penggunaan bandwidth menjadi 1/32 dari penggunaan awal.

IF Notes

Explorer

UTS IF3130 2019-2020

[UMUM]

[MPI]

[Shared Memory]

[GPU]

Graph View

Table of Contents

Backlinks