pengolahan paralel @2012,eko didik widianto pengolahan … · teknik sistem komputer - universitas...

Pengolahan Paralel

@2012,Eko DidikWidianto

Pengolahan Paralel

Konsep PengolahanParalel

Umpan Balik

LisensiPengolahan ParalelKuliah#2 TSK205 Sistem Digital - TA 2011/2012

Eko Didik Widianto

Teknik Sistem Komputer - Universitas Diponegoro

Pengolahan Paralel


Pengolahan Paralel


Umpan Balik

Lisensi

Tentang KuliahI Sebelumnya dibahas tentang:

I Deskripsi, tujuan, sasaran dan materi kuliah TSK-617Pengolahan Paralel

I Latar belakang perlunya riset dan teknik pengolahanparalel: kapasitas prosesor (Moore), manufacturability dandensitas power

I Umpan Balik: apa yang melatarbelakangi kenapapengolahan paralel diperlukan?

I Dalam kuliah ini, akan dibahas konsep pengolahanparalel:

I Definisi dan terminologi pengolahan paralelI Pemrosesan serial vs paralelI Sumber-sumber daya komputer paralel beserta

karakteristiknyaI Kebutuhan pengolahan paralel untuk computional scienceI Contoh aplikasi yang menggunakan sistem pengolahan

paralel yang ada saat iniI Taksonomi FlynnI Arsitektur Memori Paralel

Pengolahan Paralel


Pengolahan Paralel


Umpan Balik

Lisensi

Kompetensi Dasar

I Setelah mempelajari bab ini, mahasiswa akan mampu:1. [C2] Menjelaskan karakteristik sistem paralel dan

pengolahan paralel2. [C2] Menjelaskan sumber-sumber daya komputer paralel

dan karakteristiknya3. [C2] Menjelaskan contoh sistem yang menggunakan

pengolahan paralel dan menjabarkan faktor apa saja yangmelatarbelakanginya

I AcknowledmentMateri dan gambar didapat dari:

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

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

kuliah-tsk-617-pengolahan-paralel-2011/I Email: [email protected]

https://computing.llnl.gov/tutorials/parallel_comp/

http://didik.blog.undip.ac.id/2012/02/25/kuliah-tsk-617-pengolahan-paralel-2011/

http://didik.blog.undip.ac.id/2012/02/25/kuliah-tsk-617-pengolahan-paralel-2011/

mailto:[email protected]

Pengolahan Paralel


Pengolahan Paralel


Umpan Balik

Lisensi

Bahasan

Pengolahan ParalelTerminologiPemrosesan Serial vs ParalelKebutuhan KomputasiBenefit Pengolahan ParalelAplikasi Pengolahan Paralel

Konsep Pengolahan ParalelArsitektur KomputerTaksonomi FlynnArsitektur Memori Paralel

Umpan Balik

Lisensi

Pengolahan Paralel


Pengolahan ParalelTerminologi

Pemrosesan Serial vsParalel

Kebutuhan Komputasi

Benefit Pengolahan Paralel

Aplikasi Pengolahan Paralel


Umpan Balik

Lisensi

Bahasan



Umpan Balik

Lisensi

Pengolahan Paralel




Kebutuhan Komputasi




Umpan Balik

Lisensi

Definisi Pengolahan ParalelI Webopedia.com1

I The simultaneous use of more than one CPU to execute aprogram

I Wikipedia.com2

I The simultaneous use of more than one CPU or processorcore to execute a program or multiple computational threads

I Oxford Dictionary of ScienceI A technique that allows more than one process – stream of

activity – to be running at any given moment in a computersystem, hence processes can be executed in parallel. Thismeans that two or more processors are active among agroup of processes at any instant

I Parallel computing: a form of computation in which manycalculations are carried out simultaneously, operating onthe principle that large problems can often be divided intosmaller ones, which are then solved concurrently ("inparallel")3

1http://www.webopedia.com/TERM/P/parallel_processing.html2http://en.wikipedia.org/wiki/Parallel_processing3Almasi, G.S. and A. Gottlieb (1989). Highly Parallel Computing.

Benjamin-Cummings publishers, Redwood City, CA

Pengolahan Paralel




Kebutuhan Komputasi




Umpan Balik

Lisensi

Process, Thread, Multi-CPU

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

Pengolahan Paralel




Kebutuhan Komputasi




Umpan Balik

Lisensi

Bahasan



Umpan Balik

Lisensi

Pengolahan Paralel




Kebutuhan Komputasi




Umpan Balik

Lisensi

Pemrosesan Tunggal (Serial)

I Dijalankan di komputer tunggal dengan 1 CPUI Problem dipecah dalam instruksi dengan eksekusi

berurutan, hanya satu eksekusi dalam satu waktu

Pengolahan Paralel




Kebutuhan Komputasi




Umpan Balik

Lisensi

Pemrosesan Paralel

I Dijalankan menggunakan banyak CPUI Problem dipecah menjadi bagian yang dapat dikerjakan

secara bersamaanI Tiap bagian dipecah menjadi instruksi terurutI Instruksi tiap bagian dieksekusi secara simultan di CPU

berbeda

Pengolahan Paralel




Kebutuhan Komputasi




Umpan Balik

Lisensi

Karakteristik Pengolahan Paralel

Mempunyai kemampuan untuk:I Memecah problem ke dalam beberapa task yang dapat

dikerjakan secara simultanI Menjalankan multi instruksi program dalam satu waktuI Menyelesaikan problem lebih cepat di multi sumber

daya komputasi daripada sumber daya tunggal

Pengolahan Paralel




Kebutuhan Komputasi




Umpan Balik

Lisensi

Sumber Daya Komputing Paralel

4 5

4http://www.nersc.gov/nusers/resources/franklin/about.php5http://en.wikipedia.org/wiki/Beowulf_%28computing%29

Pengolahan Paralel




Kebutuhan Komputasi




Umpan Balik

Lisensi

Bahasan



Umpan Balik

Lisensi

Pengolahan Paralel




Kebutuhan Komputasi




Umpan Balik

Lisensi

Semesta adalah Paralel

I Semesta bersifat paralel, sehingga model paralel memberikanhasil terbaik -> pengolahan paralel

I proses fisik terjadi paralel: aliran fluida, pergerakan planet,pola cuaca, galaksi

I proses sosial terjadi paralel: koloni semut, assembly lines,trafik

Pengolahan Paralel




Kebutuhan Komputasi




Umpan Balik

Lisensi

Kebutuhan Pemrosesan: ComputationalScience

I Pemrosesan paralel merupakan ’the high end ofcomputing’

“An important development insciences is occurring at theintersection of computer science andthe sciences that has the potential tohave a profound impact on science. Itis a leap from the application ofcomputing . . . to the integration ofcomputer science concepts, tools,and theorems into the very fabricof science.” -Science 2020 Report,March 2006

Pengolahan Paralel




Kebutuhan Komputasi




Umpan Balik

Lisensi

Faktor Perubahan

I Terus meningkatnya daya komputasi secara eksponensial-> simulasi menjadi pilar ketiga dari science, melengkapiteori dan eksperimen

I Terus meningkatnya jumlah data eksperimen secareeksponensial -> teknik dan teknologi analisis data,visualisasi, jaringan dan kolaraborasi menjadi esensialdalam semua data aplikasi science

Pengolahan Paralel




Kebutuhan Komputasi




Umpan Balik

Lisensi

Simulasi: Pilar Ketiga dalam Science

I Metode scientific dan rekayasa tradisional(1) Mengerjakan teori atau desain di atas kertas(2) Melakukan eksperimen atau membangun sistem

I KelemahanI Terlalu susah, terlalu mahal, terlalu lambat (menunggu evolusi

galaksi), terlalu berbahaya (senjata, cuaca)I Paradigma komputasi:

(3) menggunakan komputer untuk mensimulasi dan menganalisisfenomena

I Menggunakan hukum fisik dan metode numerik yang efisienI Menganalisis hasil simulasi dengan perangkat dan metode

komputasional

Pengolahan Paralel




Kebutuhan Komputasi




Umpan Balik

Lisensi

Data Intensive

Pengolahan Paralel




Kebutuhan Komputasi




Umpan Balik

Lisensi

Peta CMB

I Merekam jejak unik primordial melalui suhu dan polarisasiI Mengekstrak fluktuasi suhu uKelvin merupakan tantangan

komputasi serius

Pengolahan Paralel




Kebutuhan Komputasi




Umpan Balik

Lisensi

Content-based Image Retrieval (KurtKeutzer)

I Aplikasi teknik computer vision untuk problem imageretrieval: mencari gambar digital dalam database yangbesar

Pengolahan Paralel




Kebutuhan Komputasi




Umpan Balik

Lisensi

Bahasan



Umpan Balik

Lisensi

Pengolahan Paralel




Kebutuhan Komputasi




Umpan Balik

Lisensi

Alasan Menggunakan Pengolahan Paralel

I Menghemat waktu dan biayaI Penggunaan lebih banyak resource untuk satu task akan

mempercepat waktu pengerjaan, dengan potensipenghematan biaya

I Cluster dapat dibangun dengan komponen komoditas danmurah

I Mengerjakan problem yang lebih besarI Banyak problem tidak bisa dipecahkan dengan komputer

tunggal, memori terbatas: Grand Challenge, web searchengine yang memproses jutaan transaksi perdetik

I Menyediakan concurrencyI Sumber daya pararel dapat melakukan banyak hal secara

simultan. Contoh: access grid yang menyediakan jaringankolaborasi global 6

6http://www.accessgrid.org

Pengolahan Paralel




Kebutuhan Komputasi




Umpan Balik

Lisensi

Alasan Menggunakan Pengolahan Paralel(Cont.)

I Menggunakan sumber daya non-lokalI Menggunakan sumber daya lewat jaringan/internet: BOINC,

SETI@home, Folding@homeI Keterbatasan pengolahan serial

I Kecepatan transmisi. Limit: kecepatan cahaya (30cm/ns),kabel tembaga (9cm/ns)

I Batas miniaturisasi: teknologi pemrosesan ICI Batas ekonomis: biaya semakin mahal untuk membuat

prosesor tunggal semakin cepat

Arsitektur komputer menggunakan paralelisme di level hardwareuntuk meningkatkan performansi:

I Unit eksekusi multipleI Pipeline instruksiI Multi-core

Pengolahan Paralel




Kebutuhan Komputasi




Umpan Balik

Lisensi

Daya Listrik Terkontrol

I Pergeseran paradigmaI Old:Mempercepat frekuensi merupakan metode utama

untuk meningkatkan performansi prosesorI New: Menambah paralellisme yang menjadi metode utama

Pengolahan Paralel




Kebutuhan Komputasi




Umpan Balik

Lisensi

Bahasan



Umpan Balik

Lisensi

Pengolahan Paralel




Kebutuhan Komputasi




Umpan Balik

Lisensi

BOINC: Voluntary Computing

I Berkeley Open Infrastructure for Network Computing(BOINC)7

I Active: 323,676 volunteers, 524,265 computersI 24-hour average: 5,744.07 TeraFLOPS

7http://boinc.berkeley.edu

Pengolahan Paralel




Kebutuhan Komputasi




Umpan Balik

Lisensi

Folding@Home

I Menganalisa data dari protein folding, misfolding, dan relateddiseases8

I Active: Lebih dari 400rb CPUI 8,045 TeraFLOPS

8http://folding.stanford.edu/

Pengolahan Paralel




Kebutuhan Komputasi




Umpan Balik

Lisensi

SETI@HomeI Search for Extraterrestrial Intelligence (SETI) 9

I Download dan menganalisa data teleskop radionI 730 TFlops

http://setiathome.berkeley.edu/ss_graphics.php9http://setiathome.berkeley.edu/

Pengolahan Paralel




Kebutuhan Komputasi




Umpan Balik

Lisensi

Distributed ComputingI Cluster computer: Beowulf

http://en.wikipedia.org/wiki/File:Beowulf.jpgI Grid Computing: GlobusI Cloud Computing: Nimbus, Eucalyptus, Openstack

Pengolahan Paralel


Pengolahan Paralel

Konsep PengolahanParalelArsitektur Komputer

Taksonomi Flynn

Arsitektur Memori Paralel

Umpan Balik

Lisensi

Bahasan



Umpan Balik

Lisensi

Pengolahan Paralel


Pengolahan Paralel


Taksonomi Flynn


Umpan Balik

Lisensi

Arsitektur von Neumann

I Paper tentang requirement dasar darikomputer elektronik (1936)

I Terdiri atas 4 komponen utama: 1) memori,2) unit kontrol, 3) aritmetic logic unit dan 4)input/output

I RAM (R/W) untuk menyimpan instruksi dandata

I Instruksi: data terkode yangmemberitahu komputer apa yang harusdikerjakan

I data: informasi yang digunakan olehprogram

I Unit kontrol mengambil instruksi/data darimemori, decode instruksi danmengkoordinasikan operasi

I ALU melakukan operasi aritmetika

I I/O interface ke operator

John von Neumann(1903-1957)

Pengolahan Paralel


Pengolahan Paralel


Taksonomi Flynn


Umpan Balik

Lisensi

Bahasan



Umpan Balik

Lisensi

Pengolahan Paralel


Pengolahan Paralel


Taksonomi Flynn


Umpan Balik

Lisensi

Taksonomi Flynn

I Klasifikasi arsitektur komputer (1966)I Membedakan arsitektur komputer

multiprocesor berdasarkan dimensi instruksidan data. Kemudian tiap dimensi dibagimenjadi single atau multiple

SingleInstruction

MultipleInstruction

Single Data SISD MISD

MultipleData

SIMD MIMD

Michael J. Flynn

(1903-1957)

Pengolahan Paralel


Pengolahan Paralel


Taksonomi Flynn


Umpan Balik

Lisensi

Single Instruction, Single Data (SISD)

I Komputer serial(non-paralel)

I Hanya satu instruksi yangdijalankan oleh CPUdalam satu siklus waktu

I Hnaya satu data yangdigunakan sebagain inputdalam satu siklus waktu

I Eksekusi deterministikI Contoh: PC single-core,

mainframe generasi lama

SISD

Pengolahan Paralel


Pengolahan Paralel


Taksonomi Flynn


Umpan Balik

Lisensi

Single Instruction, Multiple Data (SIMD)

I Tipe komputer paralelI Semua processing unit

(PU) mengeksekusiinstruksi yang sama dalamsatu waktu

I Tiap PU memproses dapatberoperasi dengan datayang berbeda

SIMD

I Untuk problem spesial: pemrosesan grafikI Sinkronous dan eksekusi deterministikI Tipe: prosesor array, vector pipelineI Contoh: Komputer dengan GPU

Pengolahan Paralel


Pengolahan Paralel


Taksonomi Flynn


Umpan Balik

Lisensi

Multiple Instruction, Single Data (MISD)

I Data tunggal diolah olehbeberapa PU

I Tiap PU mengolah datasecara independen

I Contoh: komputerexperimen Carnigie Mellon(1971)

MISD

I Beberapa penggunaan:I Operasi pemfilteran frekuensi secara multiple dari sinyal

tunggalI Penerapan algoritma kriptografi multipe untuk memecah

satu pesan terkode (ciphertext)

Pengolahan Paralel


Pengolahan Paralel


Taksonomi Flynn


Umpan Balik

Lisensi

Multiple Instruction, Multiple Data (MIMD)

I Hampir semua komputermodern masuk kategoriMIMD

I Tiap prosesor mungkinmengeksekusi instruksiyang berbeda

I Tiap prosesor mungkinmengolah data yangberbeda

MIMD

I Eksekusi bisa sinkronous atau asinkron, deterministik ataunon-deterministik

I Eksekusi deterministik di sistem paralel menjadi objek riset

I Contoh: multicore PC, cluster computer, grid computer

Pengolahan Paralel


Pengolahan Paralel


Taksonomi Flynn


Umpan Balik

Lisensi

Terminologi

I Task adalah bagian-bagian kerja komputasional, bisaberupa program atau set instruksi

I Parallel task adalah suatu task yang dapat dieksekusi olehmulti prosesor

I Pengolahan paralel: penggunaan multi prosesor secarasimultan

I Cluster komputer: kombinasi prosesor/komputerkomoditas sejenis untuk membangun sistem paralel

I Symmetric Multi Processor (SMP): arsitektur multiprosesor yang sharing satu space alamat tunggal (sharedmemory computing)

I Dikontrol oleh OS tunggalI Di multicore, arsitektur SMP diaplikasikan ke core

I Supercomputing: menggunakan mesin tercepat untukmenyelesaikan suatu problem besar

Pengolahan Paralel


Pengolahan Paralel


Taksonomi Flynn


Umpan Balik

Lisensi

Bahasan



Umpan Balik

Lisensi

Pengolahan Paralel


Pengolahan Paralel


Taksonomi Flynn


Umpan Balik

Lisensi

Arsitektur Memori Komputer Paralel

Arsitektur memori paralel:1. Shared memory: prosesor dapat mengakses semua

memori sebagai space alamat global1.1 Uniform Memory Access (UMA)1.2 Non-Uniform Memory Access (NUMA)

2. Distributed memory: prosesor mempunyai memori lokalsendiri. Inter-prosesor memori perlu networking

3. Hybrid distributed-shared memory: menggunakan shareddan distributed

Pengolahan Paralel


Pengolahan Paralel


Taksonomi Flynn


Umpan Balik

Lisensi

Process, Thread, Multi-CPU

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

I Baca juga: Understanding Memory(http://www.ualberta.ca/CNS/RESEARCH/LinuxClusters/mem.html)

I Alokasi memori: text, data (initialized), BSS (uninitialized),heap (dinamically) dan stack

Pengolahan Paralel


Pengolahan Paralel


Taksonomi Flynn


Umpan Balik

Lisensi

Shared Memory (UMA)

I Karakteristik: semua prosesor dapat mengakses semuamemori sebagai ruang alamat global

I Multi prosesor dapat beroperasi secara independennamun sharing memori

I Perubahan di lokasi memori oleh satu prosesor dapatdilihat oleh prosesor lain

I Prosesor identik, misalnya mesin SMPI Upto 8 prosesorI Mempunyai akses dan waktu akses yang

sama ke memoriI Kadang disebut CC-UMA (cache

coherent)I cache coherent: jika satu prosesor

update suatu lokasi di memori,semua prosesor mengetahuiupdate tsb

I Koherensi dilakukan di levelhardware

Shared Memory (UMA)

Pengolahan Paralel


Pengolahan Paralel


Taksonomi Flynn


Umpan Balik

Lisensi

Shared Memory (NUMA)

I Karakteristik: prosesor mempunyai bank alamat memori sendiriI Prosesor dapat mengakses memori lokal dengan cepat, memori

remote lebih lambatI Meningkatkan throughput memori selama mengakses data

lokal

I Seringkali dibuat denganmenghubungkan secara fisik 2atau lebih SMP

I Satu SMP dapat mengaksesmemori secara langsung ke SMPlain NUMA

I Tidak semua prosesor mempunyai waktu akses yang sama ke memoriI Akses memori lewat bus interconnect lebih lambat

I Jika cache coherence dilakukan, disebut CC-NUMA

Pengolahan Paralel


Pengolahan Paralel


Taksonomi Flynn


Umpan Balik

Lisensi

Shared Memory: Kelebihan, Kekurangan

I Kelebihan:I Space alamat memori global menyediakan perspektif

pemrograman user-friendly ke memoriI Sharing data antar task cepat dan uniform karena dekatnya

memori ke CPU

I Kekurangan:I Tidak scalable. Menambah CPU dapat meningkatkan trafik

di jalur shared memory-CPU. Di cc-(N)UMA, pertambahantrafik berkaitan dengan manajemen cache/memori

I Programmer bertanggung jawab untuk sinkronisasi yangmemastikan akses yang tepat ke memori global

I Akan bertambah semakin kompleks dan mahal seiringbertambahnya jumlah prosesor

Pengolahan Paralel


Pengolahan Paralel


Taksonomi Flynn


Umpan Balik

Lisensi

Distributed Memory

I Tiap prosesor mempunyai memori lokal sendiri

I Sehingga prosesor dapatberoperasi secara independen

I Perubahan ke lokal memori tidakmembawa efek ke memori lain

I Konsep cache coherencetidak berlaku

I Jika memerlukan interprosesor,tugas programmer secaraeksplisit mendefinisikanbagaimana dan kapan data akandikomunikasikan

Distributed

Pengolahan Paralel


Pengolahan Paralel


Taksonomi Flynn


Umpan Balik

Lisensi

Distributed Memory

I Kelebihan:I scalable jumlah prosesor dan ukuran memori dapat ditingkatkanI Tiap prosesor dapat mengakses memorinya tanpa interferensi dan

overhead, seperti di koherensi cacheI Cost effective: dapat menggunakan PC komoditas, off-the-self

processorI Kekurangan:

I tugas programmer semakin kompleks terkait detail komunikasi dataI Mapping data struktur berbasis memori globlal bisa susah

Pengolahan Paralel


Pengolahan Paralel


Taksonomi Flynn


Umpan Balik

Lisensi

Hybrid MemoryI Terdiri dari arsitektur memori shared dan distributed

I Komponen memori sharedbiasanya mesin SMP koheren

I Prosesor di mesin SMPmempunyai akses globalke memori mesintersebut

I Komponen distributed adalahjaringan SMP multiple

I SMP hanya tahumemorinya saja

I Komunikasi jaringandiperlukan untukmemindahkan data darisatu SMP ke lainnya

Hybrid

I Trend ke depan menggunakan tipe arsitektur memori ini

Pengolahan Paralel


Pengolahan Paralel


Umpan Balik

Lisensi

Umpan Balik

I Yang telah kita pelajari hari ini:I Definisi pengolahan paralel, karakteristik dan sumber daya

komputing paralelI Perbandingan antara pengolahan serial dan paralelI Pemrosesan Paralel diperlukan untuk simulasi yang

computational-intensiveI Benefit dan aplikasi pengolahan paralelI Taksonomi Flynn: SISD, SIMD, MISD, dan MIMDI Arsitektur memori paralel: shared, distributed, hybrid

I Yang akan kita pelajari di pertemuan berikutnya adalahmodel pemrograman paralel: shared memory (thread) dandistributed (message-passing)

I Pelajari: http://didik.blog.undip.ac.id/files/2012/02/TSK617-Kuliah3-ModelPemrogramanParalel.pdf

http://didik.blog.undip.ac.id/files/2012/02/TSK617-Kuliah3-ModelPemrogramanParalel.pdf

http://didik.blog.undip.ac.id/files/2012/02/TSK617-Kuliah3-ModelPemrogramanParalel.pdf

Pengolahan Paralel


Pengolahan Paralel


Umpan Balik

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

http://creativecommons.org/licenses/by-sa/3.0/

http://creativecommons.org/licenses/by-sa/3.0/

pengolahan paralel @2012,eko didik widianto pengolahan … · teknik sistem komputer - universitas...

Documents