2012. Eko Didik Widianto. Teknik Sistem Komputer - Universitas Diponegoro

Pengolahan Paralel @2012,Eko Didik Widianto Pengolahan Paralel Konsep Pengolahan Paralel Umpan Balik

Pengolahan Paralel Kuliah#2 TSK205 Sistem Digital - TA 2011/2012

Eko Didik Widianto Teknik Sistem Komputer - Universitas Diponegoro

Lisensi

Tentang Kuliah I

Sebelumnya dibahas tentang: I

I

I

I

Deskripsi, tujuan, sasaran dan materi kuliah TSK-617 Pengolahan Paralel Latar belakang perlunya riset dan teknik pengolahan paralel: kapasitas prosesor (Moore), manufacturability dan densitas power Umpan Balik: apa yang melatarbelakangi kenapa pengolahan paralel diperlukan?

Dalam kuliah ini, akan dibahas konsep pengolahan paralel: I I I

I I

I I

Definisi dan terminologi pengolahan paralel Pemrosesan serial vs paralel Sumber-sumber daya komputer paralel beserta karakteristiknya Kebutuhan pengolahan paralel untuk computional science Contoh aplikasi yang menggunakan sistem pengolahan paralel yang ada saat ini Taksonomi Flynn Arsitektur Memori Paralel

Pengolahan Paralel @2012,Eko Didik Widianto Pengolahan Paralel Konsep Pengolahan Paralel Umpan Balik Lisensi

Kompetensi Dasar

Pengolahan Paralel @2012,Eko Didik Widianto Pengolahan Paralel

I

Setelah mempelajari bab ini, mahasiswa akan mampu: 1. [C2] Menjelaskan karakteristik sistem paralel dan pengolahan paralel 2. [C2] Menjelaskan sumber-sumber daya komputer paralel dan karakteristiknya 3. [C2] Menjelaskan contoh sistem yang menggunakan pengolahan paralel dan menjabarkan faktor apa saja yang melatarbelakanginya

I

Acknowledment Materi dan gambar didapat dari: I

Introduction to Parallel Computing di

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

Link I

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

kuliah-tsk-617-pengolahan-paralel-2011/ I

Email: [email protected]

Konsep Pengolahan Paralel Umpan Balik Lisensi

Bahasan


Pengolahan Paralel Terminologi Pemrosesan Serial vs Paralel Kebutuhan Komputasi Benefit Pengolahan Paralel Aplikasi Pengolahan Paralel Konsep Pengolahan Paralel Arsitektur Komputer Taksonomi Flynn Arsitektur Memori Paralel Umpan Balik Lisensi


Bahasan



Terminologi Pemrosesan Serial vs Paralel Kebutuhan Komputasi Benefit Pengolahan Paralel Aplikasi Pengolahan Paralel


Definisi Pengolahan Paralel I

I

I

I

Webopedia.com1 I The simultaneous use of more than one CPU to execute a program Wikipedia.com2 I The simultaneous use of more than one CPU or processor core to execute a program or multiple computational threads Oxford Dictionary of Science I A technique that allows more than one process – stream of activity – to be running at any given moment in a computer system, hence processes can be executed in parallel. This means that two or more processors are active among a group of processes at any instant

Parallel computing: a form of computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently ("in parallel")3

1 http://www.webopedia.com/TERM/P/parallel_processing.html 2 http://en.wikipedia.org/wiki/Parallel_processing 3 Almasi,

G.S. and A. Gottlieb (1989). Highly Parallel Computing. Benjamin-Cummings publishers, Redwood City, CA

Pengolahan Paralel @2012,Eko Didik Widianto Pengolahan Paralel Terminologi Pemrosesan Serial vs Paralel Kebutuhan Komputasi Benefit Pengolahan Paralel Aplikasi Pengolahan Paralel


Process, Thread, Multi-CPU



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

Bahasan





Pemrosesan Tunggal (Serial)

Pengolahan Paralel @2012,Eko Didik Widianto Pengolahan Paralel Terminologi Pemrosesan Serial vs Paralel Kebutuhan Komputasi

I

Dijalankan di komputer tunggal dengan 1 CPU

I

Problem dipecah dalam instruksi dengan eksekusi berurutan, hanya satu eksekusi dalam satu waktu

Benefit Pengolahan Paralel Aplikasi Pengolahan Paralel


Pemrosesan Paralel I

Dijalankan menggunakan banyak CPU

I

Problem dipecah menjadi bagian yang dapat dikerjakan secara bersamaan

I

Tiap bagian dipecah menjadi instruksi terurut

I

Instruksi tiap bagian dieksekusi secara simultan di CPU berbeda



Karakteristik Pengolahan Paralel


Mempunyai kemampuan untuk: I

I I

Memecah problem ke dalam beberapa task yang dapat dikerjakan secara simultan Menjalankan multi instruksi program dalam satu waktu Menyelesaikan problem lebih cepat di multi sumber daya komputasi daripada sumber daya tunggal


Pengolahan Paralel

Sumber Daya Komputing Paralel

@2012,Eko Didik Widianto Pengolahan Paralel Terminologi Pemrosesan Serial vs Paralel Kebutuhan Komputasi Benefit Pengolahan Paralel Aplikasi Pengolahan Paralel


4 5

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

Bahasan





Semesta adalah Paralel I

Semesta bersifat paralel, sehingga model paralel memberikan hasil terbaik -> pengolahan paralel I

I

proses fisik terjadi paralel: aliran fluida, pergerakan planet, pola cuaca, galaksi proses sosial terjadi paralel: koloni semut, assembly lines, trafik



Kebutuhan Pemrosesan: Computational Science I

Pemrosesan paralel merupakan ’the high end of computing’

Pengolahan Paralel @2012,Eko Didik Widianto Pengolahan Paralel Terminologi Pemrosesan Serial vs Paralel Kebutuhan Komputasi Benefit Pengolahan Paralel

“An important development in sciences is occurring at the intersection of computer science and the sciences that has the potential to have a profound impact on science. It is a leap from the application of computing . . . to the integration of computer science concepts, tools, and theorems into the very fabric of science.” -Science 2020 Report, March 2006

Aplikasi Pengolahan Paralel


Faktor Perubahan


I

I

Terus meningkatnya daya komputasi secara eksponensial -> simulasi menjadi pilar ketiga dari science, melengkapi teori dan eksperimen Terus meningkatnya jumlah data eksperimen secare eksponensial -> teknik dan teknologi analisis data, visualisasi, jaringan dan kolaraborasi menjadi esensial dalam semua data aplikasi science


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 Kelemahan I

Terlalu susah, terlalu mahal, terlalu lambat (menunggu evolusi galaksi), terlalu berbahaya (senjata, cuaca)

I Paradigma komputasi:

(3) menggunakan komputer untuk mensimulasi dan menganalisis fenomena I I

Menggunakan hukum fisik dan metode numerik yang efisien Menganalisis hasil simulasi dengan perangkat dan metode komputasional

Data Intensive



Peta CMB



I

Merekam jejak unik primordial melalui suhu dan polarisasi

I

Mengekstrak fluktuasi suhu uKelvin merupakan tantangan komputasi serius

Content-based Image Retrieval (Kurt Keutzer)



I

Aplikasi teknik computer vision untuk problem image retrieval: mencari gambar digital dalam database yang besar

Bahasan





Alasan Menggunakan Pengolahan Paralel

Pengolahan Paralel @2012,Eko Didik Widianto Pengolahan Paralel Terminologi

I

Menghemat waktu dan biaya I

I

I

Mengerjakan problem yang lebih besar I

I

Penggunaan lebih banyak resource untuk satu task akan mempercepat waktu pengerjaan, dengan potensi penghematan biaya Cluster dapat dibangun dengan komponen komoditas dan murah Banyak problem tidak bisa dipecahkan dengan komputer tunggal, memori terbatas: Grand Challenge, web search engine yang memproses jutaan transaksi perdetik

Menyediakan concurrency I

Sumber daya pararel dapat melakukan banyak hal secara simultan. Contoh: access grid yang menyediakan jaringan kolaborasi global 6

6 http://www.accessgrid.org

Pemrosesan Serial vs Paralel Kebutuhan Komputasi Benefit Pengolahan Paralel Aplikasi Pengolahan Paralel


Alasan Menggunakan Pengolahan Paralel (Cont.)

Pengolahan Paralel @2012,Eko Didik Widianto Pengolahan Paralel Terminologi Pemrosesan Serial vs Paralel

I

Menggunakan sumber daya non-lokal I

I

Menggunakan sumber daya lewat jaringan/internet: BOINC, SETI@home, Folding@home

Keterbatasan pengolahan serial I

I I

Kecepatan transmisi. Limit: kecepatan cahaya (30cm/ns), kabel tembaga (9cm/ns) Batas miniaturisasi: teknologi pemrosesan IC Batas ekonomis: biaya semakin mahal untuk membuat prosesor tunggal semakin cepat

Arsitektur komputer menggunakan paralelisme di level hardware untuk meningkatkan performansi: I I I

Unit eksekusi multiple Pipeline instruksi Multi-core

Kebutuhan Komputasi Benefit Pengolahan Paralel Aplikasi Pengolahan Paralel


Daya Listrik Terkontrol



I

Pergeseran paradigma I

I

Old:Mempercepat frekuensi merupakan metode utama untuk meningkatkan performansi prosesor New: Menambah paralellisme yang menjadi metode utama

Bahasan





BOINC: Voluntary Computing I

Berkeley Open Infrastructure for Network Computing (BOINC)7



I

Active: 323,676 volunteers, 524,265 computers

I

24-hour average: 5,744.07 TeraFLOPS

7 http://boinc.berkeley.edu

Folding@Home I

Menganalisa data dari protein folding, misfolding, dan related diseases8



I

Active: Lebih dari 400rb CPU

I

8,045 TeraFLOPS

8 http://folding.stanford.edu/

SETI@Home I

Search for Extraterrestrial Intelligence (SETI) 9 Download dan menganalisa data teleskop radion

I

730 TFlops

I



http://setiathome.berkeley.edu/ss_graphics.php 9 http://setiathome.berkeley.edu/

Distributed Computing I

Cluster computer: Beowulf



http://en.wikipedia.org/wiki/File:Beowulf.jpg I Grid Computing: Globus I

Cloud Computing: Nimbus, Eucalyptus, Openstack

Bahasan



Konsep Pengolahan Paralel Arsitektur Komputer Taksonomi Flynn Arsitektur Memori Paralel

Umpan Balik Lisensi

Pengolahan Paralel

Arsitektur von Neumann

@2012,Eko Didik Widianto Pengolahan Paralel

I Paper tentang requirement dasar dari

Konsep Pengolahan Paralel

komputer elektronik (1936)

Arsitektur Komputer

I Terdiri atas 4 komponen utama: 1) memori,

Taksonomi Flynn Arsitektur Memori Paralel

2) unit kontrol, 3) aritmetic logic unit dan 4) input/output

Umpan Balik Lisensi

I RAM (R/W) untuk menyimpan instruksi dan

data I

I

Instruksi: data terkode yang memberitahu komputer apa yang harus dikerjakan data: informasi yang digunakan oleh program

I Unit kontrol mengambil instruksi/data dari

memori, decode instruksi dan mengkoordinasikan operasi I ALU melakukan operasi aritmetika I I/O interface ke operator

John von Neumann (1903-1957)

Bahasan




Umpan Balik Lisensi

Pengolahan Paralel

Taksonomi Flynn

@2012,Eko Didik Widianto Pengolahan Paralel Konsep Pengolahan Paralel Arsitektur Komputer Taksonomi Flynn Arsitektur Memori Paralel

I Klasifikasi arsitektur komputer (1966)

Umpan Balik

I Membedakan arsitektur komputer

Lisensi

multiprocesor berdasarkan dimensi instruksi dan data. Kemudian tiap dimensi dibagi menjadi single atau multiple Single Instruction

Multiple Instruction

Single Data

SISD

MISD

Michael J. Flynn

Multiple Data

SIMD

MIMD

(1903-1957)

Single Instruction, Single Data (SISD)

Pengolahan Paralel @2012,Eko Didik Widianto Pengolahan Paralel Konsep Pengolahan Paralel

I

Arsitektur Komputer

Komputer serial (non-paralel)


Umpan Balik

I

Hanya satu instruksi yang dijalankan oleh CPU dalam satu siklus waktu

I

Hnaya satu data yang digunakan sebagain input dalam satu siklus waktu

I

Eksekusi deterministik

I

Contoh: PC single-core, mainframe generasi lama

Lisensi

SISD

Single Instruction, Multiple Data (SIMD)


I

Tipe komputer paralel

I

Semua processing unit (PU) mengeksekusi instruksi yang sama dalam satu waktu

I

Tiap PU memproses dapat beroperasi dengan data yang berbeda

I

Untuk problem spesial: pemrosesan grafik Sinkronous dan eksekusi deterministik

I

Tipe: prosesor array, vector pipeline

I

Contoh: Komputer dengan GPU

I


Umpan Balik Lisensi

SIMD

Multiple Instruction, Single Data (MISD)


I

I

I

I


Data tunggal diolah oleh beberapa PU

Arsitektur Komputer Taksonomi Flynn Arsitektur Memori Paralel

Tiap PU mengolah data secara independen Contoh: komputer experimen Carnigie Mellon (1971)

Umpan Balik Lisensi

MISD

Beberapa penggunaan: I

I

Operasi pemfilteran frekuensi secara multiple dari sinyal tunggal Penerapan algoritma kriptografi multipe untuk memecah satu pesan terkode (ciphertext)

Multiple Instruction, Multiple Data (MIMD)


I

I

Tiap prosesor mungkin mengeksekusi instruksi yang berbeda

I

Tiap prosesor mungkin mengolah data yang berbeda

I

Arsitektur Komputer Taksonomi Flynn Arsitektur Memori Paralel

Umpan Balik Lisensi

MIMD

Eksekusi bisa sinkronous atau asinkron, deterministik atau non-deterministik I

I


Hampir semua komputer modern masuk kategori MIMD

Eksekusi deterministik di sistem paralel menjadi objek riset

Contoh: multicore PC, cluster computer, grid computer

Terminologi


I

Task adalah bagian-bagian kerja komputasional, bisa berupa program atau set instruksi

I

Parallel task adalah suatu task yang dapat dieksekusi oleh multi prosesor

I

Pengolahan paralel: penggunaan multi prosesor secara simultan

I

Cluster komputer: kombinasi prosesor/komputer komoditas sejenis untuk membangun sistem paralel

I

Symmetric Multi Processor (SMP): arsitektur multi prosesor yang sharing satu space alamat tunggal (shared memory computing) I I

I

Dikontrol oleh OS tunggal Di multicore, arsitektur SMP diaplikasikan ke core

Supercomputing: menggunakan mesin tercepat untuk menyelesaikan suatu problem besar


Umpan Balik Lisensi

Bahasan




Umpan Balik Lisensi

Arsitektur Memori Komputer Paralel

Pengolahan Paralel @2012,Eko Didik Widianto Pengolahan Paralel Konsep Pengolahan Paralel Arsitektur Komputer

Arsitektur memori paralel: 1. Shared memory: prosesor dapat mengakses semua memori sebagai space alamat global 1.1 Uniform Memory Access (UMA) 1.2 Non-Uniform Memory Access (NUMA)

2. Distributed memory: prosesor mempunyai memori lokal sendiri. Inter-prosesor memori perlu networking 3. Hybrid distributed-shared memory: menggunakan shared dan distributed


Umpan Balik Lisensi

Process, Thread, Multi-CPU

Pengolahan Paralel @2012,Eko Didik Widianto Pengolahan Paralel Konsep Pengolahan Paralel Arsitektur Komputer Taksonomi Flynn Arsitektur Memori Paralel

Umpan Balik Lisensi

(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

Shared Memory (UMA) I I I

@2012,Eko Didik Widianto

Karakteristik: semua prosesor dapat mengakses semua memori sebagai ruang alamat global Multi prosesor dapat beroperasi secara independen namun sharing memori Perubahan di lokasi memori oleh satu prosesor dapat dilihat oleh prosesor lain

I Prosesor identik, misalnya mesin SMP I Upto 8 prosesor I Mempunyai akses dan waktu akses yang

sama ke memori I Kadang disebut CC-UMA (cache

coherent) I

I

cache coherent: jika satu prosesor update suatu lokasi di memori, semua prosesor mengetahui update tsb Koherensi dilakukan di level hardware

Shared Memory (UMA)

Pengolahan Paralel Konsep Pengolahan Paralel Arsitektur Komputer Taksonomi Flynn Arsitektur Memori Paralel

Umpan Balik Lisensi

Pengolahan Paralel

Shared Memory (NUMA)


I I

Karakteristik: prosesor mempunyai bank alamat memori sendiri Prosesor dapat mengakses memori lokal dengan cepat, memori remote lebih lambat I

Meningkatkan throughput memori selama mengakses data lokal

I Seringkali dibuat dengan

menghubungkan secara fisik 2 atau lebih SMP I Satu SMP dapat mengakses memori secara langsung ke SMP lain

NUMA

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

Jika cache coherence dilakukan, disebut CC-NUMA


Umpan Balik Lisensi

Shared Memory: Kelebihan, Kekurangan

Pengolahan Paralel @2012,Eko Didik Widianto Pengolahan Paralel Konsep Pengolahan Paralel

I

Kelebihan:

Arsitektur Komputer Taksonomi Flynn

I

I

I

Space alamat memori global menyediakan perspektif pemrograman user-friendly ke memori Sharing data antar task cepat dan uniform karena dekatnya memori ke CPU

Kekurangan: I

I

I

Tidak scalable. Menambah CPU dapat meningkatkan trafik di jalur shared memory-CPU. Di cc-(N)UMA, pertambahan trafik berkaitan dengan manajemen cache/memori Programmer bertanggung jawab untuk sinkronisasi yang memastikan akses yang tepat ke memori global Akan bertambah semakin kompleks dan mahal seiring bertambahnya jumlah prosesor

Arsitektur Memori Paralel

Umpan Balik Lisensi

Pengolahan Paralel

Distributed Memory


I

Tiap prosesor mempunyai memori lokal sendiri


I Sehingga prosesor dapat

Umpan Balik

beroperasi secara independen

Lisensi

I Perubahan ke lokal memori tidak

membawa efek ke memori lain I

Konsep cache coherence tidak berlaku

I Jika memerlukan interprosesor,

tugas programmer secara eksplisit mendefinisikan bagaimana dan kapan data akan dikomunikasikan

Distributed

Distributed Memory

Pengolahan Paralel @2012,Eko Didik Widianto Pengolahan Paralel Konsep Pengolahan Paralel Arsitektur Komputer Taksonomi Flynn Arsitektur Memori Paralel

I Kelebihan: I I

I

scalable jumlah prosesor dan ukuran memori dapat ditingkatkan Tiap prosesor dapat mengakses memorinya tanpa interferensi dan overhead, seperti di koherensi cache Cost effective: dapat menggunakan PC komoditas, off-the-self processor

I Kekurangan: I I

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

Umpan Balik Lisensi

Pengolahan Paralel

Hybrid Memory I


Terdiri dari arsitektur memori shared dan distributed

Pengolahan Paralel Konsep Pengolahan Paralel

I

Komponen memori shared biasanya mesin SMP koheren I

I


Umpan Balik Lisensi

Hybrid

Komponen distributed adalah jaringan SMP multiple I

I

I

Prosesor di mesin SMP mempunyai akses global ke memori mesin tersebut

Arsitektur Komputer

SMP hanya tahu memorinya saja Komunikasi jaringan diperlukan untuk memindahkan data dari satu SMP ke lainnya

Trend ke depan menggunakan tipe arsitektur memori ini

Umpan Balik


I

Yang telah kita pelajari hari ini:

Konsep Pengolahan Paralel Umpan Balik

I

I I

I I I

I

Definisi pengolahan paralel, karakteristik dan sumber daya komputing paralel Perbandingan antara pengolahan serial dan paralel Pemrosesan Paralel diperlukan untuk simulasi yang computational-intensive Benefit dan aplikasi pengolahan paralel Taksonomi Flynn: SISD, SIMD, MISD, dan MIMD Arsitektur memori paralel: shared, distributed, hybrid

Yang akan kita pelajari di pertemuan berikutnya adalah model pemrograman paralel: shared memory (thread) dan distributed (message-passing) I

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

Lisensi

Pengolahan Paralel

Lisensi


Creative Common Attribution-ShareAlike 3.0 Unported (CC BY-SA 3.0) I

Anda bebas:

Pengolahan Paralel Konsep Pengolahan Paralel Umpan Balik Lisensi

I

I

I

Di bawah persyaratan berikut: I

I

I

untuk Membagikan — untuk menyalin, mendistribusikan, dan menyebarkan karya, dan untuk Remix — untuk mengadaptasikan karya

Atribusi — Anda harus memberikan atribusi karya sesuai dengan cara-cara yang diminta oleh pembuat karya tersebut atau pihak yang mengeluarkan lisensi. Pembagian Serupa — Jika Anda mengubah, menambah, atau membuat karya lain menggunakan karya ini, Anda hanya boleh menyebarkan karya tersebut hanya dengan lisensi yang sama, serupa, atau kompatibel.

Lihat: Creative Commons Attribution-ShareAlike 3.0 Unported License

2012. Eko Didik Widianto. Teknik Sistem Komputer - Universitas Diponegoro

Recommend Documents