pemrograman openmp @2012,eko didik widianto … openmp 2. membuat thread 3. sinkronisasi dengan...

PemrogramanOpenMP

@2012,Eko DidikWidianto

Tentang OpenMP

Membuat Thread

Sinkronisasi

Lisensi

Pemrograman OpenMPKuliah#7 TSK617 Pengolahan Paralel - TA 2011/2012

Eko Didik Widianto

Teknik Sistem Komputer - Universitas Diponegoro

PemrogramanOpenMP

@2012,Eko DidikWidianto

Tentang OpenMP

Membuat Thread

Sinkronisasi

Lisensi

Review Kuliah

I Sebelumnya dibahas tentang: pustaka Posix Thread danaplikasinya

I Pustaka PthreadI API PthreadI Mengkompile program multithreadI Mengelola ThreadI Variabel MutexI Variabel Kondisional

PemrogramanOpenMP

@2012,Eko DidikWidianto

Tentang OpenMP

Membuat Thread

Sinkronisasi

Lisensi

Review KuliahI Pemrograman paralel di mesin shared memory

menggunakan model threadI Implementasi:

1. menggunakan Pustaka dari subrutin yang dipanggil daridalam source code paralel

I Posix (pthread), paralelisme eksplisit. Di awal direncanakanprogramnya paralel

2. menggunakan set compiler directive yang di-embed-kandi source code (serial atau paralel)

I OpenMP, dapat menggunakan kode serial

PemrogramanOpenMP

@2012,Eko DidikWidianto

Tentang OpenMP

Membuat Thread

Sinkronisasi

Lisensi

Kuliah tentang OpenMP

I Akan dibahas tentang pemrograman paralel dengan OpenMPmenggunakan kompiler directive

I Arsitektur memori: shared (SMP, symmetricmulti-processor)

I Model programming: threadI Pokok Bahasan: (kuliah #7 akan membahas item yang

ditebalkan)

1. Pengantar OpenMP2. Membuat Thread3. Sinkronisasi dengan critical, atomic4. Loop dan Worksharing5. Sinkronisasi dengan barrier, single, master, ordered6. Environment Data7. Menjadwalkan for dan section8. Model memori9. OpenMP 3.0

PemrogramanOpenMP

@2012,Eko DidikWidianto

Tentang OpenMP

Membuat Thread

Sinkronisasi

Lisensi

Kompetensi Dasar

I Setelah mempelajari bab ini, mahasiswa akan mampu:1. [C2] Mahasiswa memahami konsep pemrograman paralel

menggunakan OpenMP2. [C3] Mahasiswa akan mampu membuat program paralel

dari program serial menggunakan compiler-directive danpustaka-pustaka OpenMP

3. [C5] Mahasiswa akan mampu memprogram suatu aplikasikomputasi matrik menggunakan OpenMP serta menghitungfaktor speedupnya

I LinkI Website: http://didik.blog.undip.ac.id/2012/02/25/

kuliah-tsk-617-pengolahan-paralel-2011/I Email: didik@undip.ac.id

PemrogramanOpenMP

@2012,Eko DidikWidianto

Tentang OpenMP

Membuat Thread

Sinkronisasi

Lisensi

Acknowledment

I Materi dan gambar didapat dari:I Tim Mattson, Larry Meadows (2008): “A Hands-on

Introduction to OpenMP“I Website: http://openmp.org/wp/resources/

PemrogramanOpenMP

@2012,Eko DidikWidianto

Tentang OpenMP

Membuat Thread

Sinkronisasi

Lisensi

Bahasan

Tentang OpenMP

Membuat ThreadMembuat ThreadAplikasi Numerik

SinkronisasiSinkronisasi CriticalSinkronisasi AtomicFalse Sharing

Lisensi

PemrogramanOpenMP

@2012,Eko DidikWidianto

Tentang OpenMP

Membuat Thread

Sinkronisasi

Lisensi

OpenMP: API untuk Aplikasi Multithread

I Menyediakan set kompiler directive dan rutin pustakauntuk aplikasi pemrograman paralel

I Menyederhanakan penulisan program multi-thread (MT) dibahasa C, C++ dan Fortran

I Telah digunakan sebagai standar dalam aplikasipemrograman di prosesor SMP

PemrogramanOpenMP

@2012,Eko DidikWidianto

Tentang OpenMP

Membuat Thread

Sinkronisasi

Lisensi

OpenMP Stack

PemrogramanOpenMP

@2012,Eko DidikWidianto

Tentang OpenMP

Membuat Thread

Sinkronisasi

Lisensi

Elemen OpenMP

Sumber: http://en.wikipedia.org/wiki/OpenMP

PemrogramanOpenMP

@2012,Eko DidikWidianto

Tentang OpenMP

Membuat Thread

Sinkronisasi

Lisensi

Sintaks Utama OpenMP

I Sebagian besar construct di OpenMP adalah compilerdirective#pragma omp construct [clause [clause]. . . ]

I Contoh:#pragma omp parallel num_threads(4)

I Prototip fungsi dan tipe data didefinisikan di file headeromp.h#include <omp.h>

I Sebagian besar construct OpenMP merupakan blockterstruktur

I Blok terstruktur: sebuah blok yang berisi satu ataubeberapa statemen dengan satu titik masuk di bagian atasdan satu titik keluar di bagian terbawah

I Titik masuk dengan ’{’ dan titik keluar dengan ’}’

I Dalam blok terstruktur tersebut bisa memanggil exit()

PemrogramanOpenMP

@2012,Eko DidikWidianto

Tentang OpenMP

Membuat Thread

Sinkronisasi

Lisensi

Kompiler OpenMP

PemrogramanOpenMP

@2012,Eko DidikWidianto

Tentang OpenMP

Membuat Thread

Sinkronisasi

Lisensi

Latihan 1: Hello World (Serial)Pastikan environment telah siap (IDE, kompiler, linker, danlainnya)

PemrogramanOpenMP

@2012,Eko DidikWidianto

Tentang OpenMP

Membuat Thread

Sinkronisasi

Lisensi

Latihan 1: Hello World (Paralel)

PemrogramanOpenMP

@2012,Eko DidikWidianto

Tentang OpenMP

Membuat Thread

Sinkronisasi

Lisensi

Bagaimana Thread Berinteraksi?

I OpenMP adalah pustaka untuk pemrogramanmulti-threading menggunakan model alamat shared

I Thread saling berkomunikasi menggunakan variabel shared

I Sharing data yang tidak diinginkan menyebabkan kondisirace:

I race condition: when the program’s outcome changes asthe threads are scheduled differently

I Untuk mengontrol kondisi race:I Digunakan sinkronisasi untuk memproteksi konflik data

I Sinkronisasi akan mahal, sehingga:I Alternatif: memodifikasi program terutama akses data

shared untuk meminimalkan kebutuhan sinkronisasi

PemrogramanOpenMP

@2012,Eko DidikWidianto

Tentang OpenMP

Membuat Thread

Sinkronisasi

Lisensi

Data Race

I Dua thread berbeda mengakses lokasi memori yang sama(shared)

I Secara asinkronI Tanpa memegang lock eksklusifI Setidaknya terdapat satu akses penulisan (write/store)

PemrogramanOpenMP

@2012,Eko DidikWidianto

Tentang OpenMP

Membuat Thread

Sinkronisasi

Lisensi

Kondisi Race

I Diinginkan jumlah dari nilai fungsi s =N∑

i=0f (xi)

I Misalnya x=[3,5], f (x) = x2, dan s=0 (init)I Di akhir eksekusi, nilai s seharusnya 32 + 52 = 34

I Tapi nilainya bisa 34, 9 atau 25

I Operasi atomik adalah pembacaan dan penulisanI Tidak ada 1/2 dari satu bilangan, operasi += adalah atomikI Semua komputasi terjadi di register private

PemrogramanOpenMP

@2012,Eko DidikWidianto

Tentang OpenMP

Membuat ThreadMembuat Thread

Aplikasi Numerik

Sinkronisasi

Lisensi

Model Pemrograman OpenMP

I Fork-Join ParallelismeI Thread master membangkitkan beberapa thread (child)

yang dibutuhkan

PemrogramanOpenMP

@2012,Eko DidikWidianto

Tentang OpenMP

Membuat ThreadMembuat Thread

Aplikasi Numerik

Sinkronisasi

Lisensi

Bahasan

Tentang OpenMP

Membuat ThreadMembuat ThreadAplikasi Numerik

SinkronisasiSinkronisasi CriticalSinkronisasi AtomicFalse Sharing

Lisensi

PemrogramanOpenMP

@2012,Eko DidikWidianto

Tentang OpenMP

Membuat ThreadMembuat Thread

Aplikasi Numerik

Sinkronisasi

Lisensi

Thread Creation: Parallel Regions

I Membuat thread dengan construct parallelI Menggunakan fungsi runtime untuk setting jumlah thread,

mendapatkan thread ID

I Contoh: menggunakan fungsi omp_set_num_threads

I Tiap thread memanggil pooh(ID,A) untuk ID=0-3

PemrogramanOpenMP

@2012,Eko DidikWidianto

Tentang OpenMP

Membuat ThreadMembuat Thread

Aplikasi Numerik

Sinkronisasi

Lisensi

Thread Creation: Parallel Regions

I Menggunakan clause untuk setting jumlah threadI Contoh: #pragma omp parallel num_threads(4)

I Tiap thread memanggil pooh(ID,A) untuk ID=0-3

PemrogramanOpenMP

@2012,Eko DidikWidianto

Tentang OpenMP

Membuat ThreadMembuat Thread

Aplikasi Numerik

Sinkronisasi

Lisensi

Thread Creation: Parallel Regions

PemrogramanOpenMP

@2012,Eko DidikWidianto

Tentang OpenMP

Membuat ThreadMembuat Thread

Aplikasi Numerik

Sinkronisasi

Lisensi

Thread Creation: Parallel Regions

PemrogramanOpenMP

@2012,Eko DidikWidianto

Tentang OpenMP

Membuat ThreadMembuat Thread

Aplikasi Numerik

Sinkronisasi

Lisensi

Bahasan

Tentang OpenMP

Membuat ThreadMembuat ThreadAplikasi Numerik

SinkronisasiSinkronisasi CriticalSinkronisasi AtomicFalse Sharing

Lisensi

PemrogramanOpenMP

@2012,Eko DidikWidianto

Tentang OpenMP

Membuat ThreadMembuat Thread

Aplikasi Numerik

Sinkronisasi

Lisensi

Integrasi Numerik

PemrogramanOpenMP

@2012,Eko DidikWidianto

Tentang OpenMP

Membuat ThreadMembuat Thread

Aplikasi Numerik

Sinkronisasi

Lisensi

Serial Program PI

I File: serial/pi.c

PemrogramanOpenMP

@2012,Eko DidikWidianto

Tentang OpenMP

Membuat ThreadMembuat Thread

Aplikasi Numerik

Sinkronisasi

Lisensi

Paralel Program PI

I Buat program paralel untuk problem di atas!I Perhatikan data shared dengan data privateI Akan dibutuhkan rutin pustaka runtime:

I int omp_get_num_threads(); // mendapatkan jumlah threadI int omp_get_thread_num(); // mendapatkan thread ID atau

rankI double omp_get_wtime(); // mendapatkan time stamp

dalam detik sejak titik tertentu

PemrogramanOpenMP

@2012,Eko DidikWidianto

Tentang OpenMP

Membuat ThreadMembuat Thread

Aplikasi Numerik

Sinkronisasi

Lisensi

Paralel Program PII File: paralel/pi_spmd_simple.cI Menggunakan construct parallel dan array data untuk menyimpan jumlah

parsialI Algoritma SPMD (Single Process/Program Multiple Data)

PemrogramanOpenMP

@2012,Eko DidikWidianto

Tentang OpenMP

Membuat Thread

SinkronisasiSinkronisasi Critical

Sinkronisasi Atomic

False Sharing

Lisensi

Sinkronisasi

I Sinkronisasi digunakan untuk menghindarkan kondisi raceI Memproteksi akses ke shared data

I Tipe:I Sinkronisasi high-level

I criticalI atomicI barrierI ordered

I Sinkronisasi low-levelI flushI locks (simple, nested)

PemrogramanOpenMP

@2012,Eko DidikWidianto

Tentang OpenMP

Membuat Thread

SinkronisasiSinkronisasi Critical

Sinkronisasi Atomic

False Sharing

Lisensi

Bahasan

Tentang OpenMP

Membuat ThreadMembuat ThreadAplikasi Numerik

SinkronisasiSinkronisasi CriticalSinkronisasi AtomicFalse Sharing

Lisensi

PemrogramanOpenMP

@2012,Eko DidikWidianto

Tentang OpenMP

Membuat Thread

SinkronisasiSinkronisasi Critical

Sinkronisasi Atomic

False Sharing

Lisensi

Sinkronisasi: Critical

I Mutual exclusion: Only one thread at a time can enter acritical region

�oat res;#pragma omp parallel{

float B; int i, id, nthrds;

id = omp_get_thread_num();

nthrds = omp_get_num_threads();

for(i=id;i<niters;i+nthrds){

B = big_job(i);

#pragma omp critical // theads will wait their turns

consume (B, res); // Only one thread calls consume() at a time

}

}

I Threads akan menunggu gilirannyaI Hanya satu thread yang dapat memanggil consume()

PemrogramanOpenMP

@2012,Eko DidikWidianto

Tentang OpenMP

Membuat Thread

SinkronisasiSinkronisasi Critical

Sinkronisasi Atomic

False Sharing

Lisensi

Bahasan

Tentang OpenMP

Membuat ThreadMembuat ThreadAplikasi Numerik

SinkronisasiSinkronisasi CriticalSinkronisasi AtomicFalse Sharing

Lisensi

PemrogramanOpenMP

@2012,Eko DidikWidianto

Tentang OpenMP

Membuat Thread

SinkronisasiSinkronisasi Critical

Sinkronisasi Atomic

False Sharing

Lisensi

Sinkronisasi: Atomic

I Atomic provides mutual exclusion but only applies to theupdate of a memory location

#pragma omp parallel

{

double tmp, B;

B = DOIT();

tmp = big_ugly(B);

#pragma omp atomic

X += tmp; // Atomic only protects the read/update of X

}

PemrogramanOpenMP

@2012,Eko DidikWidianto

Tentang OpenMP

Membuat Thread

SinkronisasiSinkronisasi Critical

Sinkronisasi Atomic

False Sharing

Lisensi

Bahasan

Tentang OpenMP

Membuat ThreadMembuat ThreadAplikasi Numerik

SinkronisasiSinkronisasi CriticalSinkronisasi AtomicFalse Sharing

Lisensi

PemrogramanOpenMP

@2012,Eko DidikWidianto

Tentang OpenMP

Membuat Thread

SinkronisasiSinkronisasi Critical

Sinkronisasi Atomic

False Sharing

Lisensi

Paralel Program PI: Sinkronisasi

I Program paralel/pi_spmd_simple.c menggunakan arrayI performansi rendah karena false sharingI sum[id] unik untuk tiap thread, tapi tiap nilai array bisa saja

menggunakan jalur cache yang sama sehinggamenyebabkan cache trashing

I Setiap update di cache akan membuat invalid jalur shared ini

I Modifikasi program tersebut untuk menghindari falsesharing!

I Gunakan sinkronisasi

PemrogramanOpenMP

@2012,Eko DidikWidianto

Tentang OpenMP

Membuat Thread

SinkronisasiSinkronisasi Critical

Sinkronisasi Atomic

False Sharing

Lisensi

Paralel Program PI: SinkronisasiI File: paralel/pi_spmd_final.c

I Menghindari flase sharing karena pengunaan arraypenjumlahan

PemrogramanOpenMP

@2012,Eko DidikWidianto

Tentang OpenMP

Membuat Thread

Sinkronisasi

Lisensi

Lisensi

Creative Common Attribution-ShareAlike 3.0 Unported (CCBY-SA 3.0)

I Anda bebas:I untuk Membagikan — untuk menyalin, mendistribusikan,

dan menyebarkan karya, danI untuk Remix — untuk mengadaptasikan karya

I Di bawah persyaratan berikut:I Atribusi — Anda harus memberikan atribusi karya sesuai

dengan cara-cara yang diminta oleh pembuat karyatersebut atau pihak yang mengeluarkan lisensi.

I Pembagian Serupa — Jika Anda mengubah, menambah,atau membuat karya lain menggunakan karya ini, Andahanya boleh menyebarkan karya tersebut hanya denganlisensi yang sama, serupa, atau kompatibel.

I Lihat: Creative Commons Attribution-ShareAlike 3.0Unported License