IF Notes

UTS IF3130 2024-2025

8 min read

Back to IF3130 Sistem Paralel dan Terdistribusi

Q1. Dasar Sistem Paralel

Diberikan sebuah sistem komputer 4 core, hyperthreaded (2 thread/core) dengan kecepatan 3 GHz, kecepatan komputasi 1 FLOP/cycle dan kecepatan akses memory/DRAM sebesar 1 word/cycle, dengan ukuran 1 word 8 byte. Komputer tersebut juga memiliki L3 cache dengan kecepatan/bandwidth akses 600 GB/s.

(a) Berapakah kecepatan/bandwidth akses DRAM pada sistem tersebut (dalam GB/s)?

Kecepatan akses DRAM dapat dihitung dengan mengalikan kecepatan clock, jumlah data yang diakses per siklus, dan ukuran data tersebut.

  • Kecepatan Clock: 3 GHz = 3 x 10⁹ cycles/detik

  • Akses per Siklus: 1 word/cycle

  • Ukuran Word: 8 byte

Perhitungan:

Bandwidth = (3 x 10⁹ cycles/detik) × (1 word/cycle) × (8 byte/word)

Bandwidth = 24 x 10⁹ byte/detik

Bandwidth = 24 GB/s

(b) Berapakah kecepatan komputasi maksimum sistem tersebut (dalam FLOP/s)?

Kecepatan komputasi maksimum (peak performance) dihitung dari jumlah core, kecepatan per core, dan kecepatan clock. Hyperthreading tidak meningkatkan jumlah operasi floating-point, melainkan membantu menyembunyikan latensi, sehingga kita menggunakan jumlah core fisik.

  • Jumlah Core: 4

  • Kecepatan Komputasi per Core: 1 FLOP/cycle

  • Kecepatan Clock: 3 GHz = 3 x 10⁹ cycles/detik

Perhitungan:

Kinerja Puncak = 4 core × (1 FLOP/cycle/core) × (3 x 10⁹ cycles/detik)

Kinerja Puncak = 12 x 10⁹ FLOP/s = 12 GFLOP/s

(c) Sebuah program memiliki arithmetic intensity sebesar 1 FLOP/byte. Berapakah kecepatan komputasi program ini jika semua akses data selalu berada pada DRAM?

Kinerja program dibatasi oleh nilai minimum antara kinerja puncak komputasi dan kinerja puncak memori (memory-bound performance).

  • Kinerja Puncak Komputasi: 12 GFLOP/s

  • Bandwidth DRAM: 24 GB/s

  • Arithmetic Intensity (AI): 1 FLOP/byte

Perhitungan Kinerja Puncak Memori:

Kinerja Memori = Bandwidth DRAM × AI

Kinerja Memori = (24 x 10⁹ byte/detik) × (1 FLOP/byte) = 24 x 10⁹ FLOP/s = 24 GFLOP/s

Kecepatan komputasi aktual adalah min(Kinerja Puncak Komputasi, Kinerja Puncak Memori).

Kecepatan = min(12 GFLOP/s, 24 GFLOP/s) = 12 GFLOP/s.

Program ini bersifat compute-bound.

(d) Berapakah kecepatan komputasi program pada point (c) di atas pada sistem komputer ini (dalam FLOP/s) jika semua akses data selalu berada pada L3 Cache?

Logikanya sama seperti point (c), namun menggunakan bandwidth L3 Cache.

  • Kinerja Puncak Komputasi: 12 GFLOP/s

  • Bandwidth L3 Cache: 600 GB/s

  • Arithmetic Intensity (AI): 1 FLOP/byte

Perhitungan Kinerja Puncak Memori (dari L3 Cache):

Kinerja Memori = Bandwidth L3 × AI

Kinerja Memori = (600 x 10⁹ byte/detik) × (1 FLOP/byte) = 600 x 10⁹ FLOP/s = 600 GFLOP/s

Kecepatan komputasi aktual adalah min(Kinerja Puncak Komputasi, Kinerja Puncak Memori dari L3).

Kecepatan = min(12 GFLOP/s, 600 GFLOP/s) = 12 GFLOP/s.

Program ini tetap bersifat compute-bound.

Q2. Pthread

(a) Anda ditugaskan untuk membuat program parallel dengan menggunakan Pthread. Jika setiap thread diizinkan untuk mengeksekusi satu instruksi atau lebih, berapa thread yang digunakan untuk perhitungan berikut. Jelaskan jawaban anda.

x++;
p = x + 5;
q = p + 3;
c++;

Untuk menentukan jumlah thread yang optimal, kita perlu menganalisis dependensi data:

  1. p = x + 5; bergantung pada hasil dari x++;.

  2. q = p + 3; bergantung pada hasil dari p = x + 5;.

  3. c++; tidak memiliki dependensi dengan operasi lainnya.

Ini membentuk dua rantai tugas independen:

  • Rantai 1: x++ → p = x + 5 → q = p + 3 (Harus sekuensial)

  • Rantai 2: c++ (Independen)

Karena ada dua rantai tugas yang bisa berjalan secara bersamaan, kita bisa menggunakan 2 thread untuk efisiensi maksimal:

  • Thread 1: Menjalankan x++; p = x + 5; q = p + 3;

  • Thread 2: Menjalankan c++;

(b) Sebutkan jumlah thread dalam potongan program berikut. Jelaskan jawaban anda.

int main(int argc, char **argv)
{
    pthread_t thread[2];
    fork();
    pthread_create(&thread[0], NULL, run, (void *)&argv[0]);
    pthread_create(&thread[1], NULL, run, (void *)&argv[1]);
    pthread_join(thread[0],NULL);
    pthread_join(thread[1],NULL);
    return 0;
}

Jumlah total thread adalah 6. Berikut penjelasannya:

  1. fork(): Panggilan fork() menduplikasi proses saat ini. Ini menciptakan 2 proses yang identik (proses induk dan proses anak).

  2. Eksekusi di Setiap Proses: Kedua proses tersebut akan melanjutkan eksekusi dari baris setelah fork().

  3. Thread per Proses: Di dalam setiap proses, ada 3 thread yang berjalan:

    • 1 main thread (yang menjalankan main()).

    • 2 worker thread yang dibuat oleh pthread_create.

  4. Total Thread: Karena ada 2 proses dan masing-masing memiliki 3 thread, totalnya adalah 2 proses × 3 thread/proses = 6 thread.

Q3. OpenMP

Pada potongan program berikut terdapat potensi masalah ketika dieksekusi. Identifikasi bagian program yang mempunya potensi masalah dan lakukan perbaikan sehingga potensi masalah bisa dihindari.

Kode Bermasalah:

#include <stdio.h>
#include <omp.h>
int main() {
    int sum = 0;
    #pragma omp parallel for
    for (int i = 0; i < 1000; i++) {
        sum += i;
    }
    printf("Sum: %d\n", sum);
    return 0;
}

Identifikasi Masalah:

Potensi masalah utama adalah Race Condition pada variabel sum. Variabel sum secara default bersifat shared, artinya semua thread mengakses dan memodifikasi satu lokasi memori yang sama. Operasi sum += i tidak bersifat atomic (terdiri dari baca-modifikasi-tulis). Akibatnya, pembaruan nilai dari satu thread dapat hilang karena ditimpa oleh thread lain, sehingga hasil akhir penjumlahan menjadi salah.

Perbaikan:

Masalah ini dapat diselesaikan dengan menggunakan klausa reduction untuk melakukan operasi penjumlahan secara aman dan efisien.

Kode yang Diperbaiki:

#include <stdio.h>
#include <omp.h>
int main() {
    int sum = 0;
    // Menambahkan klausa reduction untuk operasi penjumlahan (+) pada variabel sum
    #pragma omp parallel for reduction(+:sum)
    for (int i = 0; i < 1000; i++) {
        sum += i;
    }
    printf("Sum: %d\n", sum);
    return 0;
}

Dengan reduction(+:sum), OpenMP akan membuat salinan privat dari sum untuk setiap thread, melakukan penjumlahan lokal, lalu menggabungkan semua hasil privat tersebut ke variabel sum global di akhir.

Q4. MPI

Diketahui program berbasis MPI di bawah ini yang ingin menghitung total penjumlahan dari seluruh elemen array dengan ukuran 12 elemen:

#include <mpi.h>
#include <stdio.h>
 
int main(int argc, char** argv) {
    // MPI INIT
    // ..
    
    int data[12], local_data[3];
    int local_sum = 0, total_sum = 0;
    
    if (rank == 0) {
        for (int i = 0; i < 12; i++) {
            data[i] = i + 1;  // data = {1, 2, ..., 12}
        }
    }
    
    MPI_Scatter(data, 3, MPI_INT, local_data, 3, MPI_INT, 0, MPI_COMM_WORLD);
    
    for (int i = 0; i < 3; i++) {
        local_sum += local_data[i];
    }
    
    if (rank == 0) {
        total_sum = local_sum;
        for (int i = 1; i < size; i++) {
            int temp;
            MPI_Recv(&temp, 1, MPI_INT, i, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
            total_sum += temp;
        }
        printf("Total sum is %d\n", total_sum);
    } else {
        MPI_Send(&local_sum, 1, MPI_INT, 0, 0, MPI_COMM_WORLD);
    }
    
    MPI_Finalize();
    return 0;
}

(a) Berdasarkan program diatas, output apakah yang diharapkan keluar pada console/terminal?

Program ini menghitung jumlah dari angka 1 hingga 12.

  • Array data diinisialisasi dengan [1, 2, ..., 12] di proses 0.

  • MPI_Scatter membagi array ini ke 4 proses (asumsi dijalankan dengan 4 proses, karena 12 data / 3 per proses = 4 proses).

    • P0 mendapat [1, 2, 3], local_sum = 6

    • P1 mendapat [4, 5, 6], local_sum = 15

    • P2 mendapat [7, 8, 9], local_sum = 24

    • P3 mendapat [10, 11, 12], local_sum = 33

  • Proses 0 mengumpulkan semua local_sum: total_sum = 6 + 15 + 24 + 33 = 78.

Output yang diharapkan adalah:

Total sum is 78

(b) Apakah ada masalah pada program diatas? Jelaskan masalahnya jika ada dan saran perbaikannya.

Ya, ada masalah dari segi efisiensi dan skalabilitas, meskipun secara fungsional program ini benar.

Masalah:

Pola agregasi di mana satu proses (master, rank 0) menerima hasil dari semua proses lain satu per satu dalam sebuah loop for adalah tidak efisien. Proses 0 menjadi bottleneck karena harus menangani komunikasi secara sekuensial. Kinerja akan menurun drastis jika jumlah proses sangat besar.

Saran Perbaikan:

Gunakan operasi komunikasi kolektif MPI_Reduce yang jauh lebih efisien. MPI_Reduce biasanya diimplementasikan menggunakan algoritma berbentuk pohon (tree-based) untuk agregasi, yang secara signifikan mengurangi waktu komunikasi.

Perbaikan Kode:

Ganti seluruh blok if (rank == 0) dan else dengan MPI_Reduce dan satu printf.

// ... setelah loop for untuk local_sum
// Hapus blok if-else untuk MPI_Send dan MPI_Recv
 
// Gunakan MPI_Reduce untuk mengumpulkan semua local_sum ke total_sum di proses 0
MPI_Reduce(&local_sum, &total_sum, 1, MPI_INT, MPI_SUM, 0, MPI_COMM_WORLD);
 
// Hanya proses 0 yang mencetak hasil akhir
if (rank == 0) {
    printf("Total sum is %d\n", total_sum);
}
 
MPI_Finalize();
// ...

Q5. GPU

Bayangkan Anda diminta untuk mengoptimalkan sebuah program komputasi ilmiah yang melakukan pemrosesan terhadap citra medis berukuran besar (misalnya 8000 x 8000 piksel) dengan melakukan operasi yang sama pada setiap piksel, seperti filter sharpening, peningkatan kontras, dan thresholding.

(a) Jelaskan 2 alasan mengapa kasus ini cocok untuk diimplementasikan menggunakan GPU.

  1. Paralelisme Data Masif (Massive Data Parallelism): Operasi yang sama (filter, kontras) diterapkan secara independen pada jutaan piksel. Ini adalah contoh sempurna dari paralelisme data. Arsitektur GPU dengan ribuan core dirancang khusus untuk mengeksekusi satu instruksi yang sama pada banyak data yang berbeda secara bersamaan (model SIMT), sehingga setiap piksel dapat diproses oleh satu thread GPU.

  2. Orientasi Throughput Tinggi: Pemrosesan citra membutuhkan banyak kalkulasi. GPU adalah prosesor yang berorientasi pada throughput, artinya ia dirancang untuk menyelesaikan sebanyak mungkin tugas secara bersamaan, bukan menyelesaikan satu tugas secepat mungkin. Dengan bandwidth memori yang sangat tinggi dan kekuatan komputasi (FLOPS) yang besar, GPU dapat memproses seluruh piksel gambar jauh lebih cepat daripada CPU yang berorientasi pada latensi.

(b) Berikan 1 contoh kasus yang tidak cocok untuk diimplementasikan pada GPU.

Kasus: Menjalankan logika program yang bersifat sekuensial dan memiliki banyak percabangan yang tidak teratur, seperti parser untuk sebuah bahasa pemrograman atau menjalankan query database yang kompleks.

Alasan: GPU tidak efisien untuk tugas sekuensial di mana langkah berikutnya bergantung pada hasil langkah sebelumnya. Selain itu, jika thread-thread dalam satu grup eksekusi (Warp) mengambil jalur yang berbeda dalam sebuah if-else (disebut control divergence), GPU akan menserialisasi eksekusi setiap jalur, yang menghilangkan keuntungan paralelisme. CPU, dengan unit kontrol canggih dan branch prediction, jauh lebih cocok untuk tugas-tugas semacam ini.

Graph View

Backlinks