pemrograman openmp @2012,eko didik widianto … openmp 2. membuat thread 3. sinkronisasi dengan...
TRANSCRIPT
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: [email protected]
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