model pemrograman paralel -...

22
@2011 eko didik widianto (siskom undip) SK617 Pengolahan Paralel – 1 / 22 Model Pemrograman Paralel Eko Didik Widianto ([email protected]) Lab Embedded, Siskom - Undip

Upload: lamanh

Post on 12-Mar-2019

233 views

Category:

Documents


0 download

TRANSCRIPT

Page 1: Model Pemrograman Paralel - didik.blog.undip.ac.iddidik.blog.undip.ac.id/files/2012/02/TSK617-Kuliah3-ModelPemrog... · Review Kuliah Model Pemrograman Paralal ... (siskom undip)

@2011 eko didik widianto (siskom undip) SK617 Pengolahan Paralel – 1 / 22

Model Pemrograman Paralel

Eko Didik Widianto ([email protected])

Lab Embedded, Siskom - Undip

Page 2: Model Pemrograman Paralel - didik.blog.undip.ac.iddidik.blog.undip.ac.id/files/2012/02/TSK617-Kuliah3-ModelPemrog... · Review Kuliah Model Pemrograman Paralal ... (siskom undip)

Pengolahan Paralel

@2011 eko didik widianto (siskom undip) SK617 Pengolahan Paralel – 2 / 22

• 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/

Page 3: Model Pemrograman Paralel - didik.blog.undip.ac.iddidik.blog.undip.ac.id/files/2012/02/TSK617-Kuliah3-ModelPemrog... · Review Kuliah Model Pemrograman Paralal ... (siskom undip)

Bahasan

@2011 eko didik widianto (siskom undip) SK617 Pengolahan Paralel – 3 / 22

Arsitektur Memori ParalelHirarki MemoriMemory LatencyLocality dan ParalelismeReview Kuliah

Model Pemrograman ParalalModel Pemrograman: OverviewModel Shared MemoryModel ThreadProses dan ThreadModel Message PassingPenutup

Page 4: Model Pemrograman Paralel - didik.blog.undip.ac.iddidik.blog.undip.ac.id/files/2012/02/TSK617-Kuliah3-ModelPemrog... · Review Kuliah Model Pemrograman Paralal ... (siskom undip)

Arsitektur Memori Paralel

Arsitektur Memori Paralel

• Hirarki Memori

• Memory Latency

• Locality dan Paralelisme

• Review Kuliah

Model Pemrograman Paralal

@2011 eko didik widianto (siskom undip) SK617 Pengolahan Paralel – 4 / 22

Page 5: Model Pemrograman Paralel - didik.blog.undip.ac.iddidik.blog.undip.ac.id/files/2012/02/TSK617-Kuliah3-ModelPemrog... · Review Kuliah Model Pemrograman Paralal ... (siskom undip)

Hirarki Memori

Arsitektur Memori Paralel

• Hirarki Memori

• Memory Latency

• Locality dan Paralelisme

• Review Kuliah

Model Pemrograman Paralal

@2011 eko didik widianto (siskom undip) SK617 Pengolahan Paralel – 5 / 22

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

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

• Operasi:

◦ Read dan write ke register, very fast memory

◦ Aritmetika dan logika di register

Page 6: Model Pemrograman Paralel - didik.blog.undip.ac.iddidik.blog.undip.ac.id/files/2012/02/TSK617-Kuliah3-ModelPemrog... · Review Kuliah Model Pemrograman Paralal ... (siskom undip)

Memory Latency

Arsitektur Memori Paralel

• Hirarki Memori

• Memory Latency

• Locality dan Paralelisme

• Review Kuliah

Model Pemrograman Paralal

@2011 eko didik widianto (siskom undip) SK617 Pengolahan Paralel – 6 / 22

• Prosesor berkembang lebih cepat daripada memori

• Untuk mengatasi latensi memory

◦ Membatasi operasi memori dengan menyimpannya di memoriyang cepat (cache) dan reuse

• membutuhkan locality (temporal) di program

Page 7: Model Pemrograman Paralel - didik.blog.undip.ac.iddidik.blog.undip.ac.id/files/2012/02/TSK617-Kuliah3-ModelPemrog... · Review Kuliah Model Pemrograman Paralal ... (siskom undip)

Locality dan Paralelisme

Arsitektur Memori Paralel

• Hirarki Memori

• Memory Latency

• Locality dan Paralelisme

• Review Kuliah

Model Pemrograman Paralal

@2011 eko didik widianto (siskom undip) SK617 Pengolahan Paralel – 7 / 22

• Sebagian besar program menggunakan locality untuk aksesnya

◦ spatial locality: mengakses sesuatu yang dekat dengan aksessebelumnya

◦ temporal locality: menggunakan item yang sebelumnya diakses

• Hirarki memori berusaha untuk memanfaatkan locality untuk meningkatkanperformansi

Page 8: Model Pemrograman Paralel - didik.blog.undip.ac.iddidik.blog.undip.ac.id/files/2012/02/TSK617-Kuliah3-ModelPemrog... · Review Kuliah Model Pemrograman Paralal ... (siskom undip)

Arsitektur Memori Paralel

Arsitektur Memori Paralel

• Hirarki Memori

• Memory Latency

• Locality dan Paralelisme

• Review Kuliah

Model Pemrograman Paralal

@2011 eko didik widianto (siskom undip) SK617 Pengolahan Paralel – 8 / 22

Page 9: Model Pemrograman Paralel - didik.blog.undip.ac.iddidik.blog.undip.ac.id/files/2012/02/TSK617-Kuliah3-ModelPemrog... · Review Kuliah Model Pemrograman Paralal ... (siskom undip)

Implementasi Memori

Arsitektur Memori Paralel

• Hirarki Memori

• Memory Latency

• Locality dan Paralelisme

• Review Kuliah

Model Pemrograman Paralal

@2011 eko didik widianto (siskom undip) SK617 Pengolahan Paralel – 9 / 22

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

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

• di NUMA (non-UMA), CPU mempunyai kontroler memori sendiri. CPUmenggunakan Quick Path Interconnect

Page 10: Model Pemrograman Paralel - didik.blog.undip.ac.iddidik.blog.undip.ac.id/files/2012/02/TSK617-Kuliah3-ModelPemrog... · Review Kuliah Model Pemrograman Paralal ... (siskom undip)

NUMA dan Distributed

Arsitektur Memori Paralel

• Hirarki Memori

• Memory Latency

• Locality dan Paralelisme

• Review Kuliah

Model Pemrograman Paralal

@2011 eko didik widianto (siskom undip) SK617 Pengolahan Paralel – 10 / 22

• Perbedaan utama antara NUMA dan distributed

◦ Di distributed, prosesor tidak dapat mempunyai mapping kememori yang terhubung ke prosesor lain. Transfer data kememori 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 mesinSMP

Page 11: Model Pemrograman Paralel - didik.blog.undip.ac.iddidik.blog.undip.ac.id/files/2012/02/TSK617-Kuliah3-ModelPemrog... · Review Kuliah Model Pemrograman Paralal ... (siskom undip)

Model Pemrograman Paralal

Arsitektur Memori Paralel

Model Pemrograman Paralal• Model Pemrograman:Overview

• Model Shared Memory

• Model Thread

• Proses dan Thread

• Model Message Passing

• Penutup

@2011 eko didik widianto (siskom undip) SK617 Pengolahan Paralel – 11 / 22

Page 12: Model Pemrograman Paralel - didik.blog.undip.ac.iddidik.blog.undip.ac.id/files/2012/02/TSK617-Kuliah3-ModelPemrog... · Review Kuliah Model Pemrograman Paralal ... (siskom undip)

Model Pemrograman Paralel

Arsitektur Memori Paralel

Model Pemrograman Paralal• Model Pemrograman:Overview

• Model Shared Memory

• Model Thread

• Proses dan Thread

• Model Message Passing

• Penutup

@2011 eko didik widianto (siskom undip) SK617 Pengolahan Paralel – 12 / 22

• Model memberikan abstraksi di atas hardware dan arsitektur memoritertentu

• Model tidak spesifik untuk tipe arsitektur memori tertentu

◦ dapat diimplementasikan di sebarang hardware (secara teori)

Page 13: Model Pemrograman Paralel - didik.blog.undip.ac.iddidik.blog.undip.ac.id/files/2012/02/TSK617-Kuliah3-ModelPemrog... · Review Kuliah Model Pemrograman Paralal ... (siskom undip)

Implementasi Model

Arsitektur Memori Paralel

Model Pemrograman Paralal• Model Pemrograman:Overview

• Model Shared Memory

• Model Thread

• Proses dan Thread

• Model Message Passing

• Penutup

@2011 eko didik widianto (siskom undip) SK617 Pengolahan Paralel – 13 / 22

• Model shared memory di atas mesin memori terdistribusi

◦ Misalnya: Kendall Square Research (KSR) ALLCACHE

◦ Memori secara fisik terdistribusi, tapi dilihat dari user sebagaimemori 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 taskmempunyai akses langsung ke memori global

◦ Seringkali juga pengiriman message (MPI) dilakukan lewatjaringan mesin-mesin memori terdistribusi (cluster, etc)

Page 14: Model Pemrograman Paralel - didik.blog.undip.ac.iddidik.blog.undip.ac.id/files/2012/02/TSK617-Kuliah3-ModelPemrog... · Review Kuliah Model Pemrograman Paralal ... (siskom undip)

Model Memori Bersama

Arsitektur Memori Paralel

Model Pemrograman Paralal• Model Pemrograman:Overview

• Model Shared Memory

• Model Thread

• Proses dan Thread

• Model Message Passing

• Penutup

@2011 eko didik widianto (siskom undip) SK617 Pengolahan Paralel – 14 / 22

• Task berbagi bersama space alamat memori, dengan penulisan danpembacaan secara asinkron

• Mekanisme yang digunakan adalah semaphore / lock untukmengontrol akses ke shared memori

• Keuntungannya (dari sudut programmer): ownership data tidakdiperlukan, sehingga tidak perlu untuk menyatakan dengan eksplisitkomunikasi data antar task. Pengembangan program dapatdisederhanakan

• Kelemahannya adalah di performansi, yaitu akan lebih susah untukmemanage locality data

◦ Menjaga data lokal untuk prosesor yang mengirimnya akanmemerlukan alokasi/akses memori dan mempengaruhi trafikbus saat prosesor yang lain menggunakan data yang sama

Page 15: Model Pemrograman Paralel - didik.blog.undip.ac.iddidik.blog.undip.ac.id/files/2012/02/TSK617-Kuliah3-ModelPemrog... · Review Kuliah Model Pemrograman Paralal ... (siskom undip)

Implementasi Shared Memory

Arsitektur Memori Paralel

Model Pemrograman Paralal• Model Pemrograman:Overview

• Model Shared Memory

• Model Thread

• Proses dan Thread

• Model Message Passing

• Penutup

@2011 eko didik widianto (siskom undip) SK617 Pengolahan Paralel – 15 / 22

• Kompiler akan mentranslate variabel program user ke dalam alamatmemori aktualnya yang global

• Implementasi model di atas platform distributed belum ada, kecualiKSR ALLCACHE

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

Page 16: Model Pemrograman Paralel - didik.blog.undip.ac.iddidik.blog.undip.ac.id/files/2012/02/TSK617-Kuliah3-ModelPemrog... · Review Kuliah Model Pemrograman Paralal ... (siskom undip)

Model Thread

Arsitektur Memori Paralel

Model Pemrograman Paralal• Model Pemrograman:Overview

• Model Shared Memory

• Model Thread

• Proses dan Thread

• Model Message Passing

• Penutup

@2011 eko didik widianto (siskom undip) SK617 Pengolahan Paralel – 16 / 22

• Satu proses dapat mempunyai beberapa jalur eksekusi yangkonkuren

• Program utama dijadwalkan untukberjalan oleh OS, program load danmengambil semua kebutuhanresource sistem

• Program membuat thread yangdijadwalkan dapat dijalankan secarabersamaan

• Tiap thread mempunyai data lokal,namun shared resources dariprogram. Menghemat resources(bandingkan dengan clone)

• Komunikasi antar thread lewat memori

global

Page 17: Model Pemrograman Paralel - didik.blog.undip.ac.iddidik.blog.undip.ac.id/files/2012/02/TSK617-Kuliah3-ModelPemrog... · Review Kuliah Model Pemrograman Paralal ... (siskom undip)

Process, Thread, Multi-CPU

Arsitektur Memori Paralel

Model Pemrograman Paralal• Model Pemrograman:Overview

• Model Shared Memory

• Model Thread

• Proses dan Thread

• Model Message Passing

• Penutup

@2011 eko didik widianto (siskom undip) SK617 Pengolahan Paralel – 17 / 22

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

Page 18: Model Pemrograman Paralel - didik.blog.undip.ac.iddidik.blog.undip.ac.id/files/2012/02/TSK617-Kuliah3-ModelPemrog... · Review Kuliah Model Pemrograman Paralal ... (siskom undip)

Implementasi Model Thread

Arsitektur Memori Paralel

Model Pemrograman Paralal• Model Pemrograman:Overview

• Model Shared Memory

• Model Thread

• Proses dan Thread

• Model Message Passing

• Penutup

@2011 eko didik widianto (siskom undip) SK617 Pengolahan Paralel – 18 / 22

• Dari perspektif programmer, implementasi thread dapat dilakukandari:

◦ Pustaka dari subrutin yang dipanggil dari dalam source codeparalel

◦ Set compiler directive yang embed-kan di source code (serialatau paralel)

• Implementasi thread: POSIX Threads dan OpenMP

◦ Posix (pthread) menggunakan library, memerlukanpengkodean paralel

• Paralelisme eksplisit, memerlukan programmer yangmahir di paralel

◦ OpenMP, menggunaakn compiler directive; dapatmenggunakan kode serial

Page 19: Model Pemrograman Paralel - didik.blog.undip.ac.iddidik.blog.undip.ac.id/files/2012/02/TSK617-Kuliah3-ModelPemrog... · Review Kuliah Model Pemrograman Paralal ... (siskom undip)

OpenMP

Arsitektur Memori Paralel

Model Pemrograman Paralal• Model Pemrograman:Overview

• Model Shared Memory

• Model Thread

• Proses dan Thread

• Model Message Passing

• Penutup

@2011 eko didik widianto (siskom undip) SK617 Pengolahan Paralel – 19 / 22

#include <omp.h>#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 barrierif ( 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

◦ OpenMP source repository:http://sourceforge.net/projects/ompscr/

Page 20: Model Pemrograman Paralel - didik.blog.undip.ac.iddidik.blog.undip.ac.id/files/2012/02/TSK617-Kuliah3-ModelPemrog... · Review Kuliah Model Pemrograman Paralal ... (siskom undip)

Model Message Passing

Arsitektur Memori Paralel

Model Pemrograman Paralal• Model Pemrograman:Overview

• Model Shared Memory

• Model Thread

• Proses dan Thread

• Model Message Passing

• Penutup

@2011 eko didik widianto (siskom undip) SK617 Pengolahan Paralel – 20 / 22

• Set task menggunakanmemori lokalnya sendiri saatkomputasi

◦ Beberapa task dapatditempatkan di mesinfisik sama

• Task transfer data lewat pesankomunikasi

Page 21: Model Pemrograman Paralel - didik.blog.undip.ac.iddidik.blog.undip.ac.id/files/2012/02/TSK617-Kuliah3-ModelPemrog... · Review Kuliah Model Pemrograman Paralal ... (siskom undip)

Implementasi Message Passing

Arsitektur Memori Paralel

Model Pemrograman Paralal• Model Pemrograman:Overview

• Model Shared Memory

• Model Thread

• Proses dan Thread

• Model Message Passing

• Penutup

@2011 eko didik widianto (siskom undip) SK617 Pengolahan Paralel – 21 / 22

• Implementasi menggunakan library subrutin yang diembed-kan disource code

◦ Programmer bertugas menentukan semua paralelism

• Standar Message Passing Interface (MPI) direlease tahun 1994, danpart-2 di tahun 1996

◦ Tersedia di http://www-unix.mcs.anl.gov/mpi/

• MPI Tutorial: https://computing.llnl.gov/tutorials/mpi/

Page 22: Model Pemrograman Paralel - didik.blog.undip.ac.iddidik.blog.undip.ac.id/files/2012/02/TSK617-Kuliah3-ModelPemrog... · Review Kuliah Model Pemrograman Paralal ... (siskom undip)

Penutup

Arsitektur Memori Paralel

Model Pemrograman Paralal• Model Pemrograman:Overview

• Model Shared Memory

• Model Thread

• Proses dan Thread

• Model Message Passing

• Penutup

@2011 eko didik widianto (siskom undip) SK617 Pengolahan Paralel – 22 / 22

• Framework pemrograman pararel: OpenMP dan MPI