Seorang programmer akan memparalelkan sebuah kode serial, dengan hanya mengubah sebuah fungsi yang membutuhkan waktu 90% dari keseluruhan waktu jika dijalankan secara serial.
a. Hitunglah berapa speed up yang mungkin dicapai
b. Hitunglah speedup maksimum jika menggunakan 9 processor
Jawaban:
Berdasarkan Hukum Amdahl:
Bagian paralel (p) = 90% = 0.9
Bagian serial (s) = 1 - p = 10% = 0.1
a. Speedup Maksimal yang Mungkin Dicapai (Jumlah Prosesor Tak Terbatas)
Speedup maksimal dibatasi oleh bagian serial dari kode.
Speedupmax=s1=0.11=10x
Speedup maksimal yang mungkin dicapai adalah 10 kali.
b. Speedup dengan 9 Prosesor
Menggunakan rumus speedup dengan jumlah prosesor (p=9):
S(p)=s+p1−s1=0.1+90.91=0.1+0.11=0.21=5x
Speedup yang dicapai dengan 9 prosesor adalah 5 kali.
2. [OpenMP] - Analisis Dependensi Data
Diberikan potongan kode berikut:
int i, j, kfloat x[n][n][m];float scale = 2.0;...for (k=1; k<n; k++) for (j=1; j<n; j++) for (i=0; i<m; i++) x[i][j][k] = x[i][j][k-1] + x[i][j-1][k] * scale x[k][j][i] = x[k-1][j][i] + x[k][j-1][i] * scale
Jawaban:
Jujur ni aneh kok gada pertanyaannya, diliatin doang kah
Potongan kode tersebut dapat dianalisis dari segi dependensi data yang menghalangi paralelisasi sederhana.
Kedua pernyataan di dalam loop memiliki dependensi data lintas iterasi (loop-carried dependencies):
Dependensi pada k: Nilai x pada iterasi k bergantung pada nilai dari iterasi k-1.
x[i][j][k] bergantung pada x[i][j][k-1]
x[k][j][i] bergantung pada x[k-1][j][i]
Dependensi pada j: Nilai x pada iterasi j bergantung pada nilai dari iterasi j-1.
x[i][j][k] bergantung pada x[i][j-1][k]
x[k][j][i] bergantung pada x[k][j-1][i]
Karena adanya dependensi ini pada loop k dan j, kita tidak bisa memparalelkan loop k atau j secara langsung menggunakan #pragma omp parallel for. Melakukannya akan menyebabkan race condition karena urutan eksekusi menjadi tidak terjamin, padahal algoritma membutuhkan urutan sekuensial untuk j dan k.
Satu-satunya loop yang independen adalah loop terdalam, yaitu loop i. Loop i dapat diparalelkan karena setiap iterasi i mengakses elemen array yang berbeda dan tidak bergantung pada iterasi i lainnya.
Paralelisasi yang mungkin adalah sebagai berikut:
for (k=1; k<n; k++) { for (j=1; j<n; j++) { #pragma omp parallel for for (i=0; i<m; i++) { x[i][j][k] = x[i][j][k-1] + x[i][j-1][k] * scale; x[k][j][i] = x[k-1][j][i] + x[k][j-1][i] * scale; } }}
Namun, paralelisasi pada loop terdalam seringkali tidak efisien karena overhead pembuatan thread yang berulang kali. Kode ini memerlukan teknik paralelisasi yang lebih canggih seperti wavefront parallelism untuk loop j dan k.
3. [MPI] - Tipe Data Kolektif dan Turunan
a. Jelaskan perbedaan kegunaan fungsi MPI_Allreduce dan MPI_Allgather.
b. Buatlah suatu program MPI yang mendefinisikan tipe data Point (terdiri atas integer X dan integer Y). Program menerima input berupa nilai X dan Y, kemudian mengirimkan input tersebut ke seluruh proses. Data dikirimkan dalam bentuk tipe data Point, bukan dalam bentuk integer.
Jawaban (a): Perbedaan MPI_Allreduce dan MPI_Allgather
MPI_Allreduce: Digunakan untuk agregasi data. Fungsi ini mengambil satu elemen data dari setiap proses, melakukan operasi reduksi kolektif (seperti penjumlahan, pencarian nilai maksimum, dll.), dan kemudian mendistribusikan satu hasil akhir dari operasi tersebut ke semua proses. Contoh: menjumlahkan penjualan parsial dari setiap cabang untuk mendapatkan total penjualan global, lalu semua cabang menerima total penjualan global tersebut.
MPI_Allgather: Digunakan untuk pengumpulan data. Fungsi ini mengambil satu blok data dari setiap proses dan menggabungkannya (konsatenasi) menjadi sebuah array yang lebih besar. Array gabungan yang lengkap ini kemudian didistribusikan ke semua proses. Contoh: setiap proses menghitung sebagian dari array hasil, lalu semua proses menerima salinan lengkap dari keseluruhan array hasil.
Jawaban (b): Program MPI dengan Tipe Data Turunan
#include <mpi.h>#include <stdio.h>#include <stdlib.h>typedef struct { int x; int y;} Point;int main(int argc, char** argv) { int rank, size; Point data_point; MPI_Datatype mpi_point_type; MPI_Init(&argc, &argv); MPI_Comm_rank(MPI_COMM_WORLD, &rank); MPI_Comm_size(MPI_COMM_WORLD, &size); // --- Mendefinisikan Tipe Data Point --- int count = 2; // Jumlah elemen dalam struct (x dan y) int blocklengths[2] = {1, 1}; // Masing-masing elemen adalah 1 integer MPI_Aint displacements[2]; MPI_Datatype types[2] = {MPI_INT, MPI_INT}; // Hitung offset dari setiap member dalam struct MPI_Get_address(&data_point.x, &displacements[0]); MPI_Get_address(&data_point.y, &displacements[1]); displacements[1] -= displacements[0]; // Jadikan offset relatif terhadap awal struct displacements[0] = 0; // Buat dan commit tipe data baru MPI_Type_create_struct(count, blocklengths, displacements, types, &mpi_point_type); MPI_Type_commit(&mpi_point_type); // --- Proses Root (rank 0) menerima input --- if (rank == 0) { printf("Masukkan nilai X: "); fflush(stdout); scanf("%d", &data_point.x); printf("Masukkan nilai Y: "); fflush(stdout); scanf("%d", &data_point.y); } // --- Mengirimkan data Point ke semua proses --- // Proses root (0) mengirimkan, proses lain menerima MPI_Bcast(&data_point, 1, mpi_point_type, 0, MPI_COMM_WORLD); // --- Setiap proses mencetak data yang diterima --- printf("Proses %d menerima Point: X = %d, Y = %d\n", rank, data_point.x, data_point.y); // --- Cleanup --- MPI_Type_free(&mpi_point_type); MPI_Finalize(); return 0;}
4. [CUDA] - Arsitektur dan Kode Dasar
a. Jelaskan perbedaan desain arsitektur antara CPU dan GPU. Gambarkan skema umum arsitektur CPU dan GPU untuk mempertegas penjelasan perbedaan.
b. Lengkapilah code CUDA berikut ini.
#include <stdio.h>#include <stdlib.h>#include <math.h>__global__ void Mat_add(float A[], float B[], float C[], int m, int n) { int my_ij; my_ij = (1)________________________________________ C[my_ij] = A[my_ij] + B[my_ij];} /* Mat_add */void Read_matrix(float A[], int m, int n) { int i, j; for (i = 0; i < m; i++) for (j = 0; j < n; j++) scanf("%f", &A[i*n + j])} /* Read_matrix */void Print_matrix(char title[], float A[], int m, int n) { int i, j; printf("%s\n", title); for (i = 0; i < m; i++) { for (j = 0; j < n; j++) printf("%.1f ", A[i*n + j]); printf("\n"); } /* Print_matrix */int main(int argc, char* argv[]) { int m, n; float *h_A, *h_B, *h_C; /* variables in host */ float *d_A, *d_B, *d_C; /* variables in device */ size_t size; /* Size of matrices */ m = 512; n = 256; size = m * n * sizeof(float); /* Allocate matrices in host and device memory */ (2) ______________________________________________ m = 512; n = 256; size = m*n*sizeof(float); Read_matrix(h_A, m, n); Read_matrix(h_B, m, n); Print_matrix("A =", h_A, m, n); Print_matrix("B =", h_B, m, n); /* Copy matrices from host memory to device memory */ (3) ______________________________________________ /* Invoke kernel using m thread blocks, each contains n threads */ (4) ______________________________________________ /* Wait for the kernel to complete */ (5) ______________________________________________ /* Copy result from device memory to host memory */ (6) ______________________________________________ Print_matrix("The sum is: ", h_C, m, n); /* Free host & device memory */ (7) ______________________________________________ return 0;} /* main */
Jawaban (a): Perbedaan Arsitektur CPU dan GPU
CPU (Central Processing Unit): Didesain untuk latensi rendah. CPU memiliki beberapa core (inti) yang sangat kuat dan kompleks. Sebagian besar area chip didedikasikan untuk control logic (untuk menangani percabangan kompleks dan eksekusi out-of-order) dan cache berukuran besar. Tujuannya adalah untuk menyelesaikan satu atau beberapa thread sekuensial secepat mungkin.
GPU (Graphics Processing Unit): Didesain untuk throughput tinggi. GPU memiliki ratusan hingga ribuan core yang lebih sederhana. Sebagian besar area chip didedikasikan untuk unit eksekusi (ALU). GPU unggul dalam mengeksekusi instruksi yang sama pada banyak data secara bersamaan (SIMT - Single Instruction, Multiple Threads). Cache-nya lebih kecil dan control logic-nya lebih sederhana, dioptimalkan untuk throughput data paralel yang masif.