IF Notes

Latihan Soal 1 - Paralelisasi

3 min read

Back to IF3130 Sistem Paralel dan Terdistribusi

Soal:

  1. Jika sebuah algoritma sekuensial diubah menjadi paralel, hanya 60% bagian algoritma tersebut yang dapat diparalelkan. Jelaskan berapa maksimum speedup yang dapat dicapai dengan menggunakan jumlah prosesor tak terbatas.
  2. Pada sebuah sistem multicore, jelaskanlah apakah ada manfaatnya membuat program paralel dengan menggunakan jumlah thread yang lebih besar dibandingkan jumlah core fisik yang ada.
  3. 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_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)) // 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;
}

Jawab:

  1. Dengan hukum Amdahl: kali. Artinya, walau prosesornya tak terbatas, speedup terbatas hanya 2.5x dibandingkan full serial.

  2. Secara umum, jumlah thread yang optimum dalam komputasi paralel adalah mendekati atau sama dengan jumlah hardware thread yang tersedia (yaitu, jumlah core fisik, dikali dua jika mendukung Simultaneous Multithreading / Hyper-Threading). Namun, ada beberapa manfaat signifikan mengapa menggunakan jumlah thread yang lebih besar daripada jumlah core fisik (disebut juga over-subscription) sering kali diperlukan dan bermanfaat, terutama dalam aplikasi real-world yang kompleks:

    1. Mengatasi Latensi (I/O Bound Tasks) Sebagian besar program tidak 100% CPU-bound (hanya berfokus pada perhitungan); mereka sering kali harus menunggu operasi Input/Output (I/O), seperti:

    • Membaca atau menulis ke disk (SSD/HDD).

    • Mengirim atau menerima data melalui jaringan.

    • Menunggu respons dari basis data.

      Ketika sebuah thread sedang menunggu I/O, core yang menjalankan thread tersebut akan menganggur. Jika kita memiliki lebih banyak thread daripada core, sistem operasi dapat segera menjadwalkan (men-swap) thread lain yang siap bekerja ke core yang baru saja idle tersebut.

    Manfaat: Hal ini menjaga core tetap sibuk, meningkatkan utilization (pemanfaatan) CPU secara keseluruhan, dan menyamarkan (masking) waktu tunggu I/O (latency).

    1. Mengatasi Blocking Internal (Lock Contention) Dalam program paralel, thread sering kali harus saling berebut akses ke sumber daya yang sama (shared resources). Untuk menghindari konflik, thread menggunakan mekanisme lock (mutexes, semaphores, dll.). Ketika sebuah thread mencoba mengambil lock yang sedang dipegang thread lain, thread tersebut akan ter-blokir (berhenti sejenak).

    Manfaat: Jika kita memiliki thread berlebih, thread yang ter-blokir dapat digantikan oleh thread lain yang masih memiliki pekerjaan untuk dilakukan, mencegah stalling (penghentian) dan menjaga throughput program tetap tinggi.

    1. Mengatasi Load Imbalance Dalam beberapa kasus, sulit untuk membagi pekerjaan secara merata (perfectly balanced) di antara semua thread. Beberapa thread mungkin menyelesaikan tugas mereka lebih cepat daripada yang lain.

      Manfaat: Jika kita memiliki banyak thread kecil (disebut juga fine-grained threading), pekerjaan dapat dialokasikan lebih dinamis. Setelah satu thread selesai, ia bisa segera mengambil pekerjaan baru yang tersisa, daripada menunggu thread lain yang memegang pekerjaan besar.

    Secara umum, kalau threadnya kebanyakan (1000 thread banding 4 core, bisa overhead di context switching → Kurang ada manfaatnya

  3. Ambil contoh P = 2. Berarti, P0 untuk step 1 akan menerima dari rank+step, yang mana adalah P1. Namun, P1 akan mengirim ke rank+step, yang artinya kirim ke P2 → Blocking. Kodenya error bruh! Tapi kalau di blok else nya kita pakai rank-step, ini bisa berfungsi jadi Binary Tree Reduction.

Graph View

Backlinks