IF Notes

UTS IF3130 2013-2016

10 min read

Back to IF3130 Sistem Paralel dan Terdistribusi

UTS 2013/2014

1. Instruction-Level Parallelism (ILP)

Jelaskan apa yang dimaksud dengan ILP, dan berikan contohnya.

  • Jawaban:

    Instruction-Level Parallelism (ILP) adalah kemampuan prosesor untuk mengeksekusi beberapa instruksi dari satu stream program secara bersamaan dalam satu clock cycle. Tujuannya adalah untuk meningkatkan throughput instruksi tanpa harus mengubah kode program secara eksplisit oleh programmer. Teknik utama untuk mencapai ILP adalah pipelining dan arsitektur superscalar (multiple-issue).

    • Contoh:

      Misalkan kita memiliki potongan kode berikut:

      a = b + c;  // Instruksi 1
x = y * z;  // Instruksi 2

      Instruksi 1 dan Instruksi 2 tidak memiliki dependensi data (hasil dari satu instruksi tidak digunakan oleh yang lain). Sebuah prosesor superscalar dengan dua unit eksekusi (misalnya, satu untuk penjumlahan dan satu untuk perkalian) dapat mengeksekusi kedua instruksi ini secara paralel dalam clock cycle yang sama, sehingga menyelesaikan pekerjaan lebih cepat daripada prosesor skalar yang harus mengeksekusinya secara berurutan.

2. Jumlah Thread vs. Jumlah Core

Pada sebuah sistem multicore, jelaskanlah apakah ada manfaatnya membuat program paralel dengan menggunakan jumlah thread yang lebih besar dibandingkan jumlah core fisik yang ada.

  • Jawaban:

    Ya, ada manfaatnya, terutama untuk menyembunyikan latensi (latency hiding). Manfaat utamanya adalah:

    1. Menangani Operasi I/O atau Blocking: Jika sebuah thread melakukan operasi yang memblokir, seperti membaca data dari disk, menunggu data dari jaringan, atau menunggu input pengguna, core yang menjalankan thread tersebut akan menganggur. Jika ada lebih banyak thread daripada core, sistem operasi dapat melakukan context switch dan menjalankan thread lain yang sudah siap di-core tersebut. Ini membuat core tetap sibuk dan produktif, sehingga meningkatkan utilisasi sistem secara keseluruhan.

    2. Meningkatkan Responsivitas: Pada aplikasi dengan antarmuka pengguna (GUI), satu thread dapat didedikasikan untuk menangani interaksi pengguna (menjaga agar UI tetap responsif), sementara thread-thread lain melakukan pekerjaan komputasi di latar belakang.

    Namun, perlu diingat bahwa membuat terlalu banyak thread juga memiliki kekurangan, yaitu peningkatan overhead dari context switching yang sering terjadi, yang justru dapat menurunkan performa.

3. Hukum Amdahl

Jika sebuah algoritma sekuensial diubah menjadi paralel, hanya 80% bagian algoritma tersebut yang dapat diparalelkan. Jelaskan berapa maksimum speedup yang dapat dicapai dengan menggunakan jumlah prosesor tak terbatas.

  • Jawaban:

    Ini adalah aplikasi langsung dari Hukum Amdahl.

    • Bagian paralel (p) = 80% = 0.8

    • Bagian serial (s) = 1 - p = 20% = 0.2

    Speedup maksimal (ketika jumlah prosesor mendekati tak terhingga) dibatasi oleh bagian serial dari kode. Rumusnya adalah:

    Jadi, maksimum speedup yang dapat dicapai adalah 5 kali, tidak peduli seberapa banyak prosesor yang ditambahkan.

4. Analisis Kode MPI

Diberikan kode MPI berikut. Jelaskan dengan singkat apa yang dihitung pada kode tersebut.

int main(int argc, char *argv[]) {
	int rank, received, myvalue, p, neighbor;
	MPI_Init(&argc, &argv);
	MPI_Status status;
	MPI_Comm_size(MPI_COMM_WORLD, &p); 
	MPI_Comm_rank(MPI_COMM_WORLD, &rank); 
	myvalue = rank; 
 
	for(int step = 1; step < p; step = step*2) {
		if( rank % step == 0) {
			if( isEven(rank/step)) { // isEven(x) mengembalikan 1 jika x even, // dan 0 jika x odd
				MPI_Recv(&received, 1, MPI_INT, rank+step, 0, MPI_COMM_WORLD, &status); 
				myvalue += received;
			} else {
				MPI_Send(&myvalue, 1, MPI_INT, rank-step, 0, MPI_COMM_WORLD); }
		} else { break;}
	} if(rank == 0) {
printf("%d\n", myvalue);
 
} return 0;
 
}

  • Jawaban:

    Kode tersebut menghitung penjumlahan total dari rank semua proses (yaitu, 0+1+2+…+(p−1)) menggunakan algoritma reduksi paralel dengan pola komunikasi recursive doubling atau butterfly.

    • Cara Kerja:

      1. Setiap proses diinisialisasi dengan nilainya sendiri (myvalue = rank).

      2. Dalam setiap langkah (step), jarak komunikasi antar proses digandakan.

      3. Proses-proses dibagi menjadi pasangan pengirim dan penerima. Proses dengan rank genap dalam grupnya (isEven(rank/step)) akan menerima nilai dari tetangganya dan menambahkannya ke nilainya sendiri. Proses dengan rank ganjil akan mengirim nilainya dan kemudian berhenti berpartisipasi.

      4. Proses ini berlanjut, dengan semakin sedikit proses yang aktif di setiap langkah, hingga semua nilai terakumulasi di proses rank 0.

      5. Akhirnya, rank 0 akan mencetak hasil penjumlahan total.

UTS 2015/2016

1. Multiple Issue Processors dan Pipelining

Bagaimana hubungan antara multiple issue processors dengan pipelining. Berikan ilustrasi, misalkan jumlah issues=4 dengan 5 tahapan pipeline IF, ID, EX, MEM, WB. Hitunglah CPI (cycle per instruction) nya.

  • Jawaban:

    • Hubungan: Pipelining adalah teknik yang memungkinkan sebuah prosesor untuk mengerjakan beberapa tahap dari instruksi yang berbeda secara bersamaan. Multiple issue processor (arsitektur superscalar) membawa konsep ini lebih jauh dengan memiliki beberapa pipeline (atau satu pipeline yang lebih lebar) untuk memulai lebih dari satu instruksi dalam satu clock cycle. Jadi, multiple issue adalah bentuk paralelisasi dari pipelining.

    • Ilustrasi (4-issue, 5-stage pipeline):

      Bayangkan sebuah “pabrik” dengan 4 jalur perakitan paralel. Setiap jalur memiliki 5 stasiun kerja (IF, ID, EX, MEM, WB).

      Clock CycleJalur 1Jalur 2Jalur 3Jalur 4
      1IF (Instr 1)IF (Instr 2)IF (Instr 3)IF (Instr 4)
      2ID (Instr 1)ID (Instr 2)ID (Instr 3)ID (Instr 4)
      3EX (Instr 1)EX (Instr 2)EX (Instr 3)EX (Instr 4)
      4MEM (Instr 1)MEM (Instr 2)MEM (Instr 3)MEM (Instr 4)
      5WB (Instr 1)WB (Instr 2)WB (Instr 3)WB (Instr 4)
      6(Instr 1-4 selesai)

    • Perhitungan CPI (Cycle Per Instruction):

      Dalam kondisi ideal (tanpa hazard atau dependensi), prosesor 4-issue dapat menyelesaikan 4 instruksi per clock cycle.

      CPI=Jumlah InstruksiJumlah Cycle​=4 instruksi1 cycle​=0.25

      CPI idealnya adalah 0.25.

2. Perbedaan MPI_Bcast dan MPI_Scatter

Jelaskan perbedaan antara perintah MPI_Bcast dan MPI_Scatter, berikan ilustrasi aliran data dari sender ke dest untuk kedua perintah tersebut.

  • Jawaban:

    • MPI_Bcast (Broadcast): Operasi “one-to-all”. Satu proses root mengirimkan salinan data yang identik ke semua proses lain (termasuk dirinya sendiri) dalam komunikator.

    • MPI_Scatter (Scatter): Operasi “one-to-many”. Satu proses root memiliki sebuah array data, lalu membagi array tersebut menjadi potongan-potongan dan mengirimkan satu potongan unik ke setiap proses.

    • Ilustrasi:

      Misalkan root=0 dan ada 4 proses.

      • MPI_Bcast:

        • Sebelum: P0 punya data [A]. P1, P2, P3 kosong.

        • Sesudah: P0 punya [A], P1 punya [A], P2 punya [A], P3 punya [A].

      • MPI_Scatter:

        • Sebelum: P0 punya data [A, B, C, D]. P1, P2, P3 kosong.

        • Sesudah: P0 punya [A], P1 punya [B], P2 punya [C], P3 punya [D].

3. Analisis Program MPI

Diberikan bagian kode program MPI berikut. Jelaskan apa yang dilakukan oleh program tersebut secara lengkap sampai program selesai. Apa yang dilakukan oleh setiap proses, misalkan ada 5 proses yang di spawn.

next = (rank + 1) % size; 
prev = (rank + size - 1) % size; 
if (0 == rank) { 
	message = 10;
	MPI_Send(&message, 1, MPI_INT, next, tag, MPI_COMM_WORLD);
} while (1) {
	MPI_Recv(&message, 1, MPI_INT, prev, tag, MPI_COMM_WORLD, MPI_STATUS_IGNORE); 
	if (0 == rank) {--message;}
	MPI_Send(&message, 1, MPI_INT, next, tag, MPI_COMM_WORLD); 
	if (0 == message) { break; }
}
 
if (0 == rank) {
	MPI_Recv(&message, 1, MPI_INT, prev, tag, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
}

  • Jawaban:

    Program ini mengimplementasikan algoritma token passing dalam topologi ring (cincin), di mana sebuah token (integer) beredar dan nilainya dimodifikasi hingga mencapai kondisi berhenti.

    • Alur Eksekusi dengan 5 Proses (P0, P1, P2, P3, P4):

      1. Inisialisasi: Setiap proses menentukan tetangga kanan (next) dan kiri (prev). Misalnya, untuk P1, next adalah P2 dan prev adalah P0. Untuk P4, next adalah P0.

      2. Awal: P0 mengirimkan token dengan nilai 10 ke P1.

      3. Sirkulasi Putaran 1-9:

        • P1 menerima token 10 dari P0, lalu mengirimkannya ke P2.

        • P2 menerima 10 dari P1, mengirimkannya ke P3.

        • P3 menerima 10 dari P2, mengirimkannya ke P4.

        • P4 menerima 10 dari P3, mengirimkannya ke P0.

        • P0 menerima 10 dari P4. Karena rank adalah 0, ia mengurangi nilai token menjadi 9, lalu mengirimkannya ke P1.

        • Proses ini berulang. Token beredar dengan nilai yang sama hingga kembali ke P0, di mana nilainya dikurangi satu.

      4. Sirkulasi Terakhir:

        • P0 akhirnya menerima token bernilai 1 dari P4. Ia menguranginya menjadi 0 dan mengirimkannya ke P1. Setelah itu, P0 keluar dari while loop.

      5. Pemberhentian Berantai:

        • P1 menerima token 0 dari P0, mengirimkannya ke P2, lalu keluar dari loop.

        • P2 menerima 0 dari P1, mengirimkannya ke P3, lalu keluar dari loop.

        • …dan seterusnya hingga P4 menerima 0 dan mengirimkannya kembali ke P0.

      6. Finalisasi: P0, yang sudah berada di luar loop, memiliki satu MPI_Recv terakhir untuk menerima token 0 yang sudah beredar penuh. Ini mencegah deadlock. Setelah itu, semua proses mencapai MPI_Finalize dan program berakhir.

4. OpenMP - Pencarian Nilai Maksimum

Jelaskan apa yang kurang tepat pada kode berikut ini dan perbaikilah:

#pragma omp parallel for
for ( i = 0; i < N; ++i ) {
	#pragma omp critical
	{ if (arr[i] > max) max = arr[i]; }
}

  • Jawaban:

    • Yang Kurang Tepat: Penggunaan #pragma omp critical untuk melindungi operasi sederhana seperti perbandingan dan penetapan nilai maksimum sangat tidak efisien. Ini menciptakan bottleneck karena hanya satu thread yang dapat memasuki critical section pada satu waktu, yang pada dasarnya membuat bagian terpenting dari loop menjadi sekuensial dan menghilangkan manfaat paralelisasi.

    • Perbaikan: Cara yang benar dan jauh lebih efisien untuk melakukan operasi reduksi seperti ini adalah dengan menggunakan clause reduction dari OpenMP. Ini memungkinkan setiap thread untuk memiliki salinan privat dari variabel max, mengerjakannya secara paralel, dan kemudian OpenMP akan secara otomatis menggabungkan semua hasil privat tersebut menjadi satu hasil global akhir.

    • Kode yang Diperbaiki:

      // Inisialisasi max dengan nilai yang sangat kecil
max = SOME_VERY_SMALL_VALUE; 
 
#pragma omp parallel for reduction(max:max)
for ( i = 0; i < N; ++i ) {
    if (arr[i] > max) {
        max = arr[i];
    }
}

5. CUDA - Bucket Sort

a. Jelaskan struktur data yang anda gunakan untuk implementasi bucket sort pada CUDA.

b. Jelaskan strategi (berupa algoritma dan penjelasannya) pembagian data ke dalam masing-masing bucket dengan menggunakan threads pada kernel CUDA.

  • Jawaban:

    a. Struktur Data:

    Untuk implementasi bucket sort paralel yang efisien di CUDA, kita memerlukan beberapa array di memori device (GPU):

    1. d_input_data: Array 1D yang berisi data mentah yang akan diurutkan.

    2. d_buckets: Array 1D besar yang akan menyimpan data setelah dibagi ke bucket. Ukurannya sama dengan d_input_data.

    3. d_bucket_offsets: Array 1D yang ukurannya sama dengan jumlah bucket. Array ini akan digunakan untuk menyimpan histogram (jumlah elemen per bucket) dan kemudian hasil dari prefix sum (indeks awal setiap bucket di dalam d_buckets).

    b. Strategi Pembagian Data (Algoritma):

    Strategi yang umum digunakan adalah pendekatan tiga kernel untuk menghindari race condition dan memaksimalkan paralelisme:

    1. Kernel 1: Membuat Histogram (Menghitung Ukuran Bucket)

      • Tujuan: Menghitung berapa banyak elemen data yang masuk ke setiap bucket.

      • Algoritma:

        • Input dibagi di antara semua thread. Setiap thread membaca satu atau lebih elemen dari d_input_data.

        • Untuk setiap elemen, thread menentukan nomor bucket-nya (misalnya, bucket_id = floor(value / bucket_range)).

        • Thread menggunakan operasi atomik (atomicAdd) untuk menambah counter pada d_bucket_offsets[bucket_id].

        • Setelah kernel ini selesai, d_bucket_offsets berisi jumlah elemen untuk setiap bucket.

    2. Kernel 2: Menghitung Posisi Awal Bucket (Prefix Sum/Scan)

      • Tujuan: Mengubah histogram menjadi alamat awal untuk setiap bucket di dalam array keluaran.

      • Algoritma:

        • Lakukan operasi parallel prefix sum (exclusive scan) pada array d_bucket_offsets. Algoritma scan yang efisien (seperti Blelloch) digunakan di sini.

        • Setelah kernel ini selesai, d_bucket_offsets[i] akan berisi total jumlah elemen dari bucket 0 hingga i-1, yang merupakan indeks awal untuk bucket i.

    3. Kernel 3: Menyebar Data ke Bucket (Scatter)

      • Tujuan: Menempatkan setiap elemen data ke posisi yang benar di dalam array d_buckets.

      • Algoritma:

        • Luncurkan kernel di mana setiap thread kembali membaca satu elemen dari d_input_data.

        • Thread menentukan nomor bucket dari elemen tersebut (bucket_id).

        • Thread mendapatkan posisi awal bucket dari d_bucket_offsets[bucket_id].

        • Untuk mendapatkan posisi yang tepat di dalam bucket, thread secara atomik menaikkan nilai di d_bucket_offsets[bucket_id] dan menggunakan nilai lama sebagai offset (atomicAdd mengembalikan nilai sebelum ditambah).

        • Posisi akhir = posisi_awal_bucket + offset_lokal.

        • Thread menulis elemen datanya ke d_buckets[posisi_akhir].

    Setelah ketiga kernel ini, data akan terdistribusi di dalam d_buckets di mana semua elemen dari bucket 0 berada di depan, diikuti oleh semua elemen dari bucket 1, dan seterusnya.

Graph View

Backlinks