UTS IF3130 2018-2019

Back to IF3130 Sistem Paralel dan Terdistribusi

1. Hukum Amdahl

Diketahui sebuah program serial dapat dijalankan dengan waktu 600 second. Kode pada program serial tersebut dapat diubah ke paralel sebesar 80%. Hitunglah:

a. Berapa speedup yang dapat dicapai jika jumlah processor tidak terbatas.

b. Berapa efisiensi yang didapatkan jika memakai 8 processor.

Jawaban:

Berdasarkan Hukum Amdahl:
- Waktu serial ( $T_{ser ia l}$ ) = 600 s
- Bagian paralel (p) = 80% = 0.8
- Bagian serial (s) = 1 - p = 20% = 0.2
a. Speedup Maksimal (Jumlah Prosesor Tak Terbatas)

Speedup maksimal dibatasi oleh bagian serial dari kode.

$Sp ee d u p_{ma x} = \frac{1}{s} = \frac{1}{0.2} = 5 x$
- Speedup yang dapat dicapai adalah 5 kali.
b. Efisiensi dengan 8 Prosesor

Pertama, hitung speedup dengan 8 prosesor (p=8):

$S (p) = \frac{1}{s + \frac{1 - s}{p}} = \frac{1}{0.2 + \frac{0.8}{8}} = \frac{1}{0.2 + 0.1} = \frac{1}{0.3} \approx 3.33 x$

Kemudian, hitung efisiensi:

$E f i s i e n s i (E) = \frac{S ( p )}{p} = \frac{3.33}{8} \approx 0.416$ atau 41.6%.

2. Sinkronisasi PThread (Readers-Writers Problem)

Diketahui anda memiliki program serial yang ingin diubah menjadi paralel dengan PThread. Program ini didominasi membaca sebuah data dan jarang melakukan pengubahan data. Bagaimana cara anda untuk menghindari race condition pada saat melakukan pengubahan data namun disaat yang sama proses pembacaan data mendapatkan keuntungan pemrograman paralel. Berikanlah pula contoh potongan program pada saat pembacaan dan pengubahan data.

Jawaban:

Masalah ini adalah contoh klasik dari Readers-Writers Problem. Solusi yang paling efisien adalah menggunakan Readers-Writer Lock (pthread_rwlock_t). Mekanisme ini memungkinkan banyak thread untuk membaca data secara bersamaan (read lock), tetapi hanya mengizinkan satu thread untuk mengubah data pada satu waktu (write lock), dan tidak ada reader yang diizinkan saat writer aktif.

Keuntungan: Pembacaan data yang sering tidak akan saling memblokir, sehingga mendapatkan keuntungan paralelisme. Operasi penulisan yang jarang akan tetap aman dari race condition.

Contoh Potongan Program:

#include <pthread.h>
 
// Inisialisasi global
pthread_rwlock_t data_lock;
int shared_data;
 
// Fungsi yang dijalankan oleh thread pembaca
void* read_data(void* arg) {
    // Mengunci untuk membaca (banyak thread bisa masuk bersamaan)
    pthread_rwlock_rdlock(&data_lock);
 
    // Critical section untuk membaca
    printf("Data yang dibaca: %d\n", shared_data);
 
    // Melepas kunci
    pthread_rwlock_unlock(&data_lock);
    return NULL;
}
 
// Fungsi yang dijalankan oleh thread penulis
void* write_data(void* arg) {
    int new_value = *(int*)arg;
 
    // Mengunci untuk menulis (hanya satu thread yang bisa masuk)
    pthread_rwlock_wrlock(&data_lock);
 
    // Critical section untuk menulis
    shared_data = new_value;
    printf("Data diubah menjadi: %d\n", shared_data);
 
    // Melepas kunci
    pthread_rwlock_unlock(&data_lock);
    return NULL;
}
 
int main() {
    // Inisialisasi lock sebelum digunakan
    pthread_rwlock_init(&data_lock, NULL);
 
    // ... (pembuatan dan join thread) ...
 
    // Hancurkan lock setelah selesai
    pthread_rwlock_destroy(&data_lock);
    return 0;
}

3. Analisis Program MPI

Jelaskan apa yang dilakukan oleh program parallel dalam MPI dibawah (BUKAN menterjemahkan instruksi), dan jelaskan bagaimana masing-masing task selesai (EXIT), apakah bersama-sama, atau saling menunggu atau dengan cara lain.

int main(int argc, char *argv[]){
	int rank, size, a, b , message, tag = 201;
	MPI_Init(&argc, &argv);
	MPI_Comm_rank(MPI_COMM_WORLD, &rank);
	MPI_Comm_size(MPI_COMM_WORLD, &size); 
	a = (rank + 1) % size; 
	b = (rank + size - 1) % size; 
	if (0 == rank) { message = 10;
		MPI_Send(&message, 1, MPI_INT, a, tag, MPI_COMM_WORLD);
	} while (1) {
		MPI_Recv(&message, 1, MPI_INT, b, tag, MPI_COMM_WORLD, MPI_STATUS_IGNORE); 
		if (0 == rank) --message;
		MPI_Send(&message, 1, MPI_INT, a, tag, MPI_COMM_WORLD); if (0 == message)
		break;
	}
	if (0 == rank) MPI_Recv(&message, 1, MPI_INT, b, tag, MPI_COMM_WORLD, MPI_STATUS_IGNORE); 
	MPI_Finalize(); 
	return 0;
}

Jawaban:
- Apa yang Dilakukan Program:
  
  Program ini mengimplementasikan algoritma token passing dalam topologi ring (cincin).
  1. Setiap proses (rank) mengetahui tetangga kanannya (a) dan tetangga kirinya (b).
  2. Proses dengan rank 0 memulai dengan mengirim “token” (sebuah pesan integer bernilai 10) ke tetangganya (rank 1).
  3. Setiap proses masuk ke dalam loop tak terbatas, di mana ia menunggu untuk menerima token dari tetangga kirinya, lalu segera mengirimkannya ke tetangga kanannya.
  4. Setiap kali token melewati rank 0, nilainya dikurangi satu.
  5. Proses ini berlanjut sampai nilai token menjadi 0.
- Bagaimana Task Selesai (EXIT):
  
  Proses tidak selesai bersama-sama, melainkan secara berurutan (sequential) saat token bernilai 0 beredar di ring.
  1. Ketika rank 0 menerima token bernilai 1, ia menguranginya menjadi 0, mengirimkannya ke rank 1, lalu keluar dari while loop.
  2. rank 1 menerima token 0, mengirimkannya ke rank 2, lalu keluar dari while loop.
  3. Proses ini berlanjut mengelilingi ring, dengan setiap proses keluar dari loop-nya setelah menerima dan meneruskan token 0.
  4. Setelah keluar dari loop, rank 0 memiliki satu MPI_Recv tambahan untuk “menangkap” token 0 yang telah beredar penuh di ring, mencegah deadlock.
  5. Akhirnya, semua proses akan mencapai MPI_Finalize(). Fungsi ini adalah blocking, artinya semua proses akan menunggu satu sama lain di titik ini sebelum program benar-benar berakhir secara kolektif.

4. Perbedaan Operasi Kolektif MPI

Jelaskan perbedaan antara :

a. MPI_gather vs MPI_Allgather dan berikan ilustrasi (gambar).

b. MPI_reduce vs MPI_Allreduce dan berikan ilustrasi (gambar).

Jawaban:

a. MPI_Gather vs MPI_Allgather
- Perbedaan: MPI_Gather adalah operasi “many-to-one”, di mana semua proses mengirim data ke satu proses root. Hanya proses root yang menerima data gabungan. MPI_Allgather adalah operasi “many-to-all”; ini seperti MPI_Gather diikuti oleh MPI_Bcast, di mana semua proses menerima data gabungan.
- Ilustrasi:
  - Gather:
    - Sebelum: P0[A], P1[B], P2[C], P3[D]
    - Sesudah (root=0): P0[A,B,C,D], P1[B], P2[C], P3[D]
  - Allgather:
    - Sebelum: P0[A], P1[B], P2[C], P3[D]
    - Sesudah: P0[A,B,C,D], P1[A,B,C,D], P2[A,B,C,D], P3[A,B,C,D]
b. MPI_Reduce vs MPI_Allreduce
- Perbedaan: MPI_Reduce mengumpulkan data dari semua proses, melakukan operasi reduksi (misal, SUM, MAX), dan menyimpan hasil akhirnya hanya di proses root. MPI_Allreduce melakukan hal yang sama, tetapi hasil akhir dari operasi reduksi didistribusikan ke semua proses.
- Ilustrasi:
  - Reduce (Operasi: SUM):
    - Sebelum: P0[1], P1[2], P2[3], P3[4]
    - Sesudah (root=0): P0[10], P1[2], P2[3], P3[4]
  - Allreduce (Operasi: SUM):
    - Sebelum: P0[1], P1[2], P2[3], P3[4]
    - Sesudah: P0[10], P1[10], P2[10], P3[10]

5. OpenMP parallel for

Pada OpenMP, pragma PARALLEL dan FOR kadang-kadang bisa dituliskan jadi satu, kadang-kadang dituliskan terpisah (dibawahnya), jelaskan kapan dapat dituliskan dalam satu baris (jadi satu) dan kapan TIDAK boleh dituliskan dalam satu baris, berikan contoh.

Jawaban:
- Kapan Ditulis Satu Baris (#pragma omp parallel for):
  
  Digunakan ketika satu-satunya pekerjaan di dalam region paralel adalah sebuah loop for. Ini adalah shortcut yang praktis untuk membuat tim thread dan langsung membagi iterasi loop di antara mereka.
```
// Contoh: Hanya ada loop di dalam region paralel
#pragma omp parallel for
for (int i = 0; i < 100; i++) {
    // Lakukan pekerjaan paralel
}
```
- Kapan Ditulis Terpisah (#pragma omp parallel dan pragma omp for):
  
  Harus ditulis terpisah ketika ada pekerjaan lain di dalam region paralel selain loop for tersebut. Ini memungkinkan adanya kode yang dieksekusi oleh setiap thread (sebelum atau sesudah loop) atau adanya beberapa loop paralel di dalam satu region paralel yang sama.
```
// Contoh: Ada inisialisasi variabel privat per thread sebelum loop
#pragma omp parallel
{
    int thread_id = omp_get_thread_num();
    printf("Thread %d siap!\n", thread_id);
 
    // Direktif for hanya berlaku untuk loop di bawahnya
    #pragma omp for
    for (int i = 0; i < 100; i++) {
        // Lakukan pekerjaan paralel
    }
}
```

6. Penjadwalan Loop OpenMP

Alokasi task ke masing-masing thread dilakukan dengan tambahan perintah SCHEDULE(type,chunksize) :

a. sebutkan macam-macam type schedule dan jelaskan.

b. jika ada array 12 elemen berisi bilangan bulat 1,2,3,…,12 akan dialokasi pada 3 thread, berikan ilustrasi (gambar) dari i. schedule(STATIC,1) ii. schedule(STATIC,2) iii. schedule(STATIC,4)

Jawaban:

a. Tipe-tipe Schedule:
- STATIC: Iterasi dibagi menjadi blok-blok berukuran chunksize dan didistribusikan secara round-robin ke thread-thread sebelum loop dieksekusi. Baik untuk beban kerja yang seimbang.
- DYNAMIC: Iterasi dibagi menjadi blok-blok berukuran chunksize, tetapi didistribusikan secara dinamis saat runtime kepada thread yang sedang idle. Baik untuk beban kerja tidak seimbang, tetapi memiliki overhead lebih tinggi.
- GUIDED: Mirip DYNAMIC, tetapi ukuran chunk dimulai besar dan mengecil secara eksponensial. Ini adalah kompromi antara STATIC dan DYNAMIC.
- RUNTIME: Tipe jadwal dan ukuran chunk diambil dari environment variable OMP_SCHEDULE saat program dijalankan.
- AUTO: Kompilator dan sistem runtime yang menentukan jadwal terbaik.
b. Ilustrasi schedule(STATIC) dengan 12 elemen dan 3 thread:

Iterasi 1 2 3 4 5 6 7 8 9 10 11 12
i. schedule(STATIC, 1) T0 T1 T2 T0 T1 T2 T0 T1 T2 T0 T1 T2
ii. schedule(STATIC, 2) T0 T0 T1 T1 T2 T2 T0 T0 T1 T1 T2 T2
iii. schedule(STATIC, 4) T0 T0 T0 T0 T1 T1 T1 T1 T2 T2 T2 T2

Iterasi	1	2	3	4	5	6	7	8	9	10	11	12
i. schedule(STATIC, 1)	T0	T1	T2	T0	T1	T2	T0	T1	T2	T0	T1	T2
ii. schedule(STATIC, 2)	T0	T0	T1	T1	T2	T2	T0	T0	T1	T1	T2	T2
iii. schedule(STATIC, 4)	T0	T0	T0	T0	T1	T1	T1	T1	T2	T2	T2	T2

7. Divergensi CUDA (Stride = 1)

unsigned int t = threadIdx.x;
 
Unsigned unsigned int start = 2*blockIdx.x*blockDim.x; 
partialSum[t] = input[start + t]; 
partialSum[blockDim.x+t] = input[start+ blockDim.x+t]; 
for (unsigned int stride = 1; stride <= blockDim.x; stride *= 2) {
	__syncthreads(); 
	if (t % stride == 0) {
		partialSum[2*t]+= partialSum[2*t+stride];
	}
}

Untuk potongan kode kernel untuk operasi reduksi berikut ini, jika ukuran block size adalah 1024 dan ukuran warp 32, ada berapa warp kah dalam sebuah blok yang akan memiliki divergence saat iterasi dengan stride bernilai 1?

a. 0

b. 1

c. 16

d. 32

Jawaban: a. 0
Penjelasan: Divergence terjadi dalam sebuah warp jika beberapa thread mengambil jalur if sementara yang lain tidak. Pada iterasi dengan stride = 1, kondisi if (t % stride == 0) menjadi if (t % 1 == 0). Kondisi ini selalu benar untuk semua nilai t (ID thread). Oleh karena itu, semua thread di dalam semua warp akan mengeksekusi kode di dalam if. Tidak ada percabangan, sehingga tidak ada warp yang mengalami divergence.

8. Divergensi CUDA (Stride = 16)

Pada pertanyaan di atas, ada berapa wraps dalam sebuah blok yang memiliki divergence saat iterasi dengan stride bernilai 16?

a. 0

b. 1

c. 16

d. 32

Jawaban: d. 32
Penjelasan: Pada iterasi dengan stride = 16, kondisi if (t % 16 == 0) akan dievaluasi oleh setiap thread. Mari kita lihat satu warp (misalnya, thread 0-31):
- thread 0: 0 % 16 == 0 → Benar
- thread 1-15: t % 16 != 0 → Salah
- thread 16: 16 % 16 == 0 → Benar
- thread 17-31: t % 16 != 0 → Salah
  
  Karena dalam satu warp ada thread yang mengeksekusi if dan ada yang tidak, maka warp tersebut mengalami divergence. Pola ini berlaku untuk semua warp di dalam blok.
  
  Jumlah warp dalam blok = blockDim.x / 32 = 1024 / 32 = 32 warp. Semuanya akan mengalami divergence.

9. Inisialisasi Indeks CUDA yang Coalesced

Misal kita ingin menggunakan setiap thread untuk menghitung 2 (adjacent) elemen output dari penjumlahan vektor… Manakah kode berikut ini yang harus digunakan untuk inisialisasi variabel i agar akses memori yang benar dan coalesced…?

a. int i=(blockIdx.x*blockDim.x)*2 + threadIdx.x;

b. int i=(blockIdx.x*blockDim.x + threadIdx.x)*2;

c. int i=(threadIdx.x*blockDim.x)*2 + blockIdx.x;

d. int i=(threadIdx.x*blockDim.x + blockIdx.x)*2;

Jawaban: b. int i=(blockIdx.x*blockDim.x + threadIdx.x)*2;
Penjelasan: blockIdx.x*blockDim.x + threadIdx.x adalah formula standar untuk global thread ID (tid). Dengan i = tid * 2, setiap thread mendapatkan indeks awal yang unik untuk sepasang elemen.
- Thread 0 mendapat i=0 (akan proses elemen 0 dan 1).
- Thread 1 mendapat i=2 (akan proses elemen 2 dan 3).
- …
- Thread 31 mendapat i=62 (akan proses elemen 62 dan 63).
  
  Ketika seluruh warp (thread 0-31) mengeksekusi C[i] dan C[i+1], mereka secara kolektif akan mengakses elemen C[0] hingga C[63]. Ini adalah blok memori yang berurutan (contiguous), sehingga aksesnya menjadi coalesced.

10. Pemrosesan Elemen Kedua CUDA

Melanjutkan pertanyaan sebelumnya, apakah statement yang benar untuk setiap thread untuk memproses elemen kedua?

a. If (i<n) C[i+1] = A[i+1] + B[i+1];

b. If (i+1<n) C[i+1] = A[i+1] + B[i+1];

c. If (i+threadIdx.x < n) C[i+threadIdx.x] = A[i+threadIdx.x] + B[i+threadIdx.x];

d. if(i+blockDim.x < n) C[i+blockDim.x] = A[i+blockDim.x] + B[i+blockDim.x];

Jawaban: b. If (i+1<n) C[i+1] = A[i+1] + B[i+1];
Penjelasan: Elemen kedua yang harus diproses oleh sebuah thread adalah elemen yang bersebelahan dengan i, yaitu i+1. Sangat penting untuk melakukan pengecekan batas (if (i+1 < n)) untuk memastikan kita tidak menulis di luar batas array, terutama untuk thread terakhir yang mungkin hanya perlu memproses satu elemen jika n ganjil.

IF Notes

Explorer

UTS IF3130 2018-2019

Graph View

Backlinks