Model Pemrograman Paralel

Model Pemrograman Paralel Eko Didik Widianto ([email protected]) Lab Embedded, Siskom - Undip

@2011 eko didik widianto (siskom undip)

SK617 Pengolahan Paralel – 1 / 22

Pengolahan Paralel • Pokok Bahasan ◦ Konsep dan terminologi ◦ Arsitektur memori paralel ◦ Model pemrograman paralel ◦ Desain program paralel ◦ Memprogram paralel • Referensi: ◦

Introduction to Parallel Computing: https://computing.llnl.gov/tutorials/parallel_comp/



Bahasan Arsitektur Memori Paralel Hirarki Memori Memory Latency Locality dan Paralelisme Review Kuliah Model Pemrograman Paralal Model Pemrograman: Overview Model Shared Memory Model Thread Proses dan Thread Model Message Passing Penutup



Arsitektur Memori Paralel

• Hirarki Memori • Memory Latency • Locality dan Paralelisme • Review Kuliah Model Pemrograman Paralal

Arsitektur Memori Paralel



Hirarki Memori Arsitektur Memori Paralel

• Hirarki Memori • Memory Latency • Locality dan Paralelisme • Review Kuliah

•

Kode yang berjalan di satu prosesor seringkali hanya membutuhkan prosesor 10-20% dari kapasitas peaknya (loss performansi)

◦

Model Pemrograman Paralal

Hal ini sebagian besar terjadi di sistem memori. Memindahkan data membutuhkan waktu lebih lama daripada operasi aritmetika maupun logika

• Operasi: ◦ Read dan write ke register, very fast memory ◦ Aritmetika dan logika di register @2011 eko didik widianto (siskom undip)


Memory Latency Arsitektur Memori Paralel


• Prosesor berkembang lebih cepat daripada memori • Untuk mengatasi latensi memory ◦ Membatasi operasi memori dengan menyimpannya di memori yang cepat (cache) dan reuse • @2011 eko didik widianto (siskom undip)

membutuhkan locality (temporal) di program SK617 Pengolahan Paralel – 6 / 22

Locality dan Paralelisme Arsitektur Memori Paralel


• Sebagian besar program menggunakan locality untuk aksesnya ◦ spatial locality: mengakses sesuatu yang dekat dengan akses sebelumnya

◦ temporal locality: menggunakan item yang sebelumnya diakses • Hirarki memori berusaha untuk memanfaatkan locality untuk meningkatkan performansi



Arsitektur Memori Paralel Arsitektur Memori Paralel




Implementasi Memori Arsitektur Memori Paralel


• di UMA (Uniform Memory Access), CPU berinteraksi dengan MCH untuk mengakses memori. I/O juga. Bottleneck: bus, isu skalabilias

◦ Dikenal dengan prosesor SMP, semua prosesor identik dan mempunyai akses yang sama ke semua area memori

• di NUMA (non-UMA), CPU mempunyai kontroler memori sendiri. CPU menggunakan Quick Path Interconnect @2011 eko didik widianto (siskom undip)


NUMA dan Distributed Arsitektur Memori Paralel

• Hirarki Memori • Memory Latency • Locality dan Paralelisme • Review Kuliah

• Perbedaan utama antara NUMA dan distributed ◦ Di distributed, prosesor tidak dapat mempunyai mapping ke memori yang terhubung ke prosesor lain. Transfer data ke memori lain dilakukan dengan protokol jaringan


◦ di NUMA, prosesor mungkin bisa • Klasifikasi memori NUMA: memori lokal dan memori remote • NUMA umumnya dibuat dengan menghubungkan secara fisik mesin SMP



Arsitektur Memori Paralel Model Pemrograman Paralal • Model Pemrograman: Overview

• Model Shared Memory • Model Thread • Proses dan Thread • Model Message Passing • Penutup




Model Pemrograman Paralel Arsitektur Memori Paralel Model Pemrograman Paralal • Model Pemrograman: Overview


• Model memberikan abstraksi di atas hardware dan arsitektur memori tertentu • Model tidak spesifik untuk tipe arsitektur memori tertentu ◦ dapat diimplementasikan di sebarang hardware (secara teori)



Implementasi Model Arsitektur Memori Paralel Model Pemrograman Paralal • Model Pemrograman: Overview

• Model shared memory di atas mesin memori terdistribusi ◦ Misalnya: Kendall Square Research (KSR) ALLCACHE


◦ Memori secara fisik terdistribusi, tapi dilihat dari user sebagai memori shared tunggal (space alamat global) ◦ Disebut juga shared virtual memory • Model message passing di atas mesin memori shared ◦ Misalnya: MPI di atas mesin NUMA, di mana tiap task mempunyai akses langsung ke memori global ◦ Seringkali juga pengiriman message (MPI) dilakukan lewat jaringan mesin-mesin memori terdistribusi (cluster, etc)



Model Memori Bersama Arsitektur Memori Paralel Model Pemrograman Paralal • Model Pemrograman: Overview


• Task berbagi bersama space alamat memori, dengan penulisan dan pembacaan secara asinkron • Mekanisme yang digunakan adalah semaphore / lock untuk mengontrol akses ke shared memori • Keuntungannya (dari sudut programmer): ownership data tidak diperlukan, sehingga tidak perlu untuk menyatakan dengan eksplisit komunikasi data antar task. Pengembangan program dapat disederhanakan • Kelemahannya adalah di performansi, yaitu akan lebih susah untuk memanage locality data ◦ Menjaga data lokal untuk prosesor yang mengirimnya akan memerlukan alokasi/akses memori dan mempengaruhi trafik bus saat prosesor yang lain menggunakan data yang sama



Implementasi Shared Memory Arsitektur Memori Paralel Model Pemrograman Paralal • Model Pemrograman: Overview


• Kompiler akan mentranslate variabel program user ke dalam alamat memori aktualnya yang global • Implementasi model di atas platform distributed belum ada, kecuali KSR ALLCACHE Sumber: http://en.wikipedia.org/wiki/Kendall_Square_Research



Model Thread Arsitektur Memori Paralel Model Pemrograman Paralal • Model Pemrograman: Overview


• Satu proses dapat mempunyai beberapa jalur eksekusi yang konkuren

•

•

•

•

Program utama dijadwalkan untuk berjalan oleh OS, program load dan mengambil semua kebutuhan resource sistem Program membuat thread yang dijadwalkan dapat dijalankan secara bersamaan Tiap thread mempunyai data lokal, namun shared resources dari program. Menghemat resources (bandingkan dengan clone) Komunikasi antar thread lewat memori global



Process, Thread, Multi-CPU Arsitektur Memori Paralel Model Pemrograman Paralal • Model Pemrograman: Overview


(source: http://www.javamex.com/tutorials/threads/how_threads_work.shtml)



Implementasi Model Thread Arsitektur Memori Paralel Model Pemrograman Paralal • Model Pemrograman: Overview

• Dari perspektif programmer, implementasi thread dapat dilakukan dari:


◦ Pustaka dari subrutin yang dipanggil dari dalam source code paralel ◦ Set compiler directive yang embed-kan di source code (serial atau paralel) • Implementasi thread: POSIX Threads dan OpenMP ◦ Posix (pthread) menggunakan library, memerlukan pengkodean paralel •

Paralelisme eksplisit, memerlukan programmer yang mahir di paralel

◦ OpenMP, menggunaakn compiler directive; dapat menggunakan kode serial



OpenMP Arsitektur Memori Paralel Model Pemrograman Paralal • Model Pemrograman: Overview


#include #include <stdio.h> #include <stdlib.h> int main (int argc, char *argv[]) { int th_id, nthreads; #pragma omp parallel private(th_id) { th_id = omp_get_thread_num(); printf("Hello World from thread %d\n", th_id); #pragma omp barrier if ( th_id == 0 ) { nthreads = omp_get_num_threads(); printf("There are %d threads\n",nthreads); } } return EXIT_SUCCESS; }

• Sumber: ◦ http://en.wikipedia.org/wiki/OpenMP ◦ http://computing.llnl.gov/tutorials/openMP @2011 eko didik widianto (siskom undip)

◦ OpenMP source repository: http://sourceforge.net/projects/ompscr/SK617 Pengolahan Paralel – 19 / 22

Model Message Passing Arsitektur Memori Paralel Model Pemrograman Paralal • Model Pemrograman: Overview


• Set task menggunakan memori lokalnya sendiri saat komputasi ◦ Beberapa task dapat ditempatkan di mesin fisik sama • Task transfer data lewat pesan komunikasi



Implementasi Message Passing Arsitektur Memori Paralel Model Pemrograman Paralal • Model Pemrograman: Overview


• Implementasi menggunakan library subrutin yang diembed-kan di source code ◦ Programmer bertugas menentukan semua paralelism • Standar Message Passing Interface (MPI) direlease tahun 1994, dan part-2 di tahun 1996 ◦ Tersedia di http://www-unix.mcs.anl.gov/mpi/ • MPI Tutorial: https://computing.llnl.gov/tutorials/mpi/



Penutup Arsitektur Memori Paralel Model Pemrograman Paralal • Model Pemrograman: Overview

• Framework pemrograman pararel: OpenMP dan MPI




Model Pemrograman Paralel

Recommend Documents