7/30/2019 1. Pemrosesan Paralel

http://slidepdf.com/reader/full/1-pemrosesan-paralel 1/23

1

Pokok Bahasan 1

Konsep Pemrosesan Paralel

7/30/2019 1. Pemrosesan Paralel

http://slidepdf.com/reader/full/1-pemrosesan-paralel 2/23

2

Learning Outcomes

Pada akhir pertemuan ini diharapkan mahasiswaakan dapat:

• menyebutkan sebab pemrosesan paralel dilakukan

• menjelaskan istilah-istilah yang sering digunakan

dalam pemrosesan paralel• menjelaskan kompleksitas waktu, speed-up, cost,

dan efisiensi pemrosesan paralel

• memperkirakan unjuk kerja (performance) dari

sebuah pemrosesan paralel sederhana.

7/30/2019 1. Pemrosesan Paralel

http://slidepdf.com/reader/full/1-pemrosesan-paralel 3/23

3

Mengapa menggunakan pemrosesan paralel?

Fenomena Alam

Observasi

Hypotesis

Percobaan 

fisik Komputasi

numerik(simulasi)

Teori

Percobaan untuk Pembuktian

Perkembangan Science dan Komputasi Numerik

7/30/2019 1. Pemrosesan Paralel

http://slidepdf.com/reader/full/1-pemrosesan-paralel 4/23

4

12 lapisan 

4096 daerah 

1024

daerah 

Total sel: 50 juta sel tiga dimensi.Untuk simulasi 10 menit memerlukan 30 milyar perhitungan.

Padahal diperlukan simulasi perioda 1 tahun.

Simulasi perambatan panas pada

Belahan bumi Selatan

Mengapa menggunakan pemrosesan paralel?

7/30/2019 1. Pemrosesan Paralel

http://slidepdf.com/reader/full/1-pemrosesan-paralel 5/23

5

Model interaksi protein dengan air:Simulasi 1 pico detik, dengan Cray X/MPmemerlukan waktu 1jam.

Padahal diperlukan simulasi untuk 1 detik.

Dengan computer dan algoritma yang samadiperlukanwaktu 31 688 tahun untuk simulasi 1 detik.

Protein

Mengapa menggunakan pemrosesan paralel?

7/30/2019 1. Pemrosesan Paralel

http://slidepdf.com/reader/full/1-pemrosesan-paralel 6/23

6

Mengapa menggunakan pemrosesan paralel?

 Application trends

7/30/2019 1. Pemrosesan Paralel

http://slidepdf.com/reader/full/1-pemrosesan-paralel 7/23

7

Mengapa menggunakan pemrosesan paralel?

Kecepatan cahaya merupakan batas kecepatan gerak

C = 3 x 10

10

cm/s

Kecepatan proses

1011 data/s

Data input:

N data

Data output:

1011

data

3 cmInput: Output:

harapan

Prosesor:

Kecepatan proses

1011 data/s

Data input:

N data

Data output:

1010 data

3 cmInput: Output:

kenyataan

Prosesor:

Terbatasnya kecepatan transmisi data akan membatasi jumlah data yang

diproses meskipun telah diggunakan prosesor dengan kecepatan tinggi.

dalam 1 detik

7/30/2019 1. Pemrosesan Paralel

http://slidepdf.com/reader/full/1-pemrosesan-paralel 8/23

8

Mengapa menggunakan pemrosesan paralel?

Kecepatan proses

tiap prosesor:

1011 data/s1010 data

1010 data

1010 data

1010 data

1010 data

1010 data

1

2

3

4

5

total data dalam 1 detik:1010 x 10 = 1011 data

Kita gunakan

pemrosesan

paralel.

Lebih dari satu

prosesor yang

bekerja,

sehingga

batasantransmisi data

tersebut bisa

diatasi.Datanya banyak sekali, dan

kita perlu kecepatan tinggi.

Bagaimana ini?

6

7

8

910

1010 data

1010 data

1010 data

1010 data

data

data

data

datadata

data

data

data

datadata

7/30/2019 1. Pemrosesan Paralel

http://slidepdf.com/reader/full/1-pemrosesan-paralel 9/23

9

Parallel Processing (pemrosesan paralel):Pemrosesan informasi yang menitik beratkan padamanipulasi / pengolahan yang dilakukan pada waktuyang sama atas data dari sebuah proses atau lebihuntuk menyelesaikan satu masalah.

Parallel Computer:Multiple processor dalam sebuah computer yangmampu melaksanakan parallel processing. 

Super Computer:

General purpose computer yang mampumenyelesaikan sebuah permasalahan dalam waktu yangsangat cepat dibanding dengan computer yang adapada waktu tersebut.

Istilah

7/30/2019 1. Pemrosesan Paralel

http://slidepdf.com/reader/full/1-pemrosesan-paralel 10/23

10

Istilah

P1 P2 P3 P4

mulai

komunikasi

komputasi

komunikasi

sinkronisasi

akhir 

komunikasi serial

mulai

akhir 

7/30/2019 1. Pemrosesan Paralel

http://slidepdf.com/reader/full/1-pemrosesan-paralel 11/23

11

Istilah

Troughput: Produk yang dihasilkan persatuan waktu olehsuatu sistem proses.

Ouput: Produk yang dihasilkan oleh suatu sistemproses. 

Input: 

Masukan (data) yang akan diproses padasuatu sistem. 

Scalable Parallel: Suatu sistem paralel prosesor dimanapenambahan prosesor akan berakibat naiknyaspeedup sistem secara proporsional.

7/30/2019 1. Pemrosesan Paralel

http://slidepdf.com/reader/full/1-pemrosesan-paralel 12/23

12

Big-Oh

012

21

1-k k 

k  aaa...aa)T(

nnnnn k 

maka big-Oh dari T(n) adalah : )(k 

nO

3n 2)T( nn

maka big-Oh dari T(n) adalah : )2(n

O

T(n) adalah fungsi yang diturunkan dari algoritma

yang akan diukur Big-Oh nya, dan n adalah

variabel dalam algoritma yang paling dominan

dalam menentukan persamaan tersebut.

Untuk persamaan

Dan untuk

7/30/2019 1. Pemrosesan Paralel

http://slidepdf.com/reader/full/1-pemrosesan-paralel 13/23

13

Kompleksitas waktu

Kompleksitas waktu:

Adalah Big-Ohdari persamaan dengan variabel yangdominan dalam algoritma, persamaan ini menyatakanjumlah langkah yang harus dilalui oleh algoritmatersebut pada kondisi terjelek.

beginfor (i = 0 ; i < m ; i++)

for(j = 0 ; j < n ; j++){ p[i, j] = q[i, j] + r[i, j];

}end

Variabel yang dominan: m dan nKompleksitas waktu: O(mn)

n kali m kali

7/30/2019 1. Pemrosesan Paralel

http://slidepdf.com/reader/full/1-pemrosesan-paralel 14/23

14

Kompleksitas waktu

SUM (EREW PRAM)

Initial condition: List of n >= 1 elements stored in A[0 . . . . . (n-1)]

Final condition: Sum of elements stored in A[0]

Gobal variables: n, A[0 . . . . . (n-1)], j

begin 

spawn(P0, P1, P2, . . . P((n/2)-1)

for all Pi where 0

i

[n/2]-1 do for j 0 to [log n] – 1 do 

if i modulo 2 j = 0 and 2i + 2 j < n then 

 A[2i] A[2i] + A[2i + 2 j]

endif endfor 

endfor end

log (n/2)

Konstan dan bukan loop

log (n)

konstan

T(n) = log(n/2) + konstan + konstan x log(n)

Kompleksitas waktu = O(log n)

7/30/2019 1. Pemrosesan Paralel

http://slidepdf.com/reader/full/1-pemrosesan-paralel 15/23

15

Kompleksitas waktu

Lower Bound:  Adalah kompleksitas waktu tercepat secara

teoritis yangbisa dicapai oleh suatu algoritma.

Upper Bound:

 Adalah kompleksitas waktu tercepat yang

dapat dicapai oleh pembuat algoritma.

7/30/2019 1. Pemrosesan Paralel

http://slidepdf.com/reader/full/1-pemrosesan-paralel 16/23

16

Speed-up

   K  e  c  e  p  a   t  a  n

  p  e  n  y  e   l  e  s

  a   i  a  n

Jumlah pekerja

Secara intuisi, dapat dirasakan dalam sehari-hari bahwa jumlah pekerja

(prosesor) makin banyak, tidak selalu menjamin bahwa waktu

penyelesaian menjadi makin cepat. Cara pelaksanaan (algoritma) dan  juga

 jenis pekerjaan sangat menentukan kondisi tersebut.

8 prosesor sedang bekerja paralel,

maka masing2 prosesor mempunyaikemungkinan: menjalani komputasi,

komunikasi, dan nganggur (idle).

7/30/2019 1. Pemrosesan Paralel

http://slidepdf.com/reader/full/1-pemrosesan-paralel 17/23

17

Speed-up

Speedup: Perbandingan antara waktu yang diperlukan oleh skwensial algoritma yang

paling efisien dengan waktu untuk algoritma yang sama tapi dijalankan pada

computer dengan pipeline atau dan data parallel

Speedup =waktu penyelesaian skwensial

waktu penyelesaian paralel

7/30/2019 1. Pemrosesan Paralel

http://slidepdf.com/reader/full/1-pemrosesan-paralel 18/23

18

Speed-up

Speedup =Kompleksitas waktu skwensial

Kompleksitas waktu paralel

Dengan dipahaminya konsep kompleksitas waktu,

maka speedup dapat ditentukan juga dari perbandingan

kompleksitas waktu algoritma terbaik untuk skwensial

dengan kompleksitas waktu algoritma paralel untuk

kasus yang sama.

7/30/2019 1. Pemrosesan Paralel

http://slidepdf.com/reader/full/1-pemrosesan-paralel 19/23

19

Hukum Ahmdahl

HukumAhmdahl:

S ≤ 

1

f +1 - f 

p

S = speedup

f = bagian proses yang harus dilakukan secara skwensial

0 ≤ f ≤ 1 

p = jumlah prosesor 

7/30/2019 1. Pemrosesan Paralel

http://slidepdf.com/reader/full/1-pemrosesan-paralel 20/23

20

Hukum Ahmdahl

S ≤ 1

f +1 - f 

p

7/30/2019 1. Pemrosesan Paralel

http://slidepdf.com/reader/full/1-pemrosesan-paralel 21/23

21

Yang dimaksud dengan cost disini adalah suatu nilai yangdiperolehdari perkalian antara jumlah prosesor yang

digunakan dengan kompleksitas waktu dari algoritma

paralel yang dipakai.

Cost = jumlah prosesor x kompleksitas waktu paralel

Cost disebut optimal jika nilainya mempunyai order sama

dengan lower bound kompleksitas waktu algoritma

skwensialnya.

Cost

7/30/2019 1. Pemrosesan Paralel

http://slidepdf.com/reader/full/1-pemrosesan-paralel 22/23

22

Efisiensi

Jika optimal cost sulit dicari karena lower bound

kompleksitas waktu skwensial tidak diketahui, maka bisa

digunakan nilai efisiensi untuk mengevaluasi cost.

Efisiensi =Kompleksitas waktu skwensial yang diketahui

cost

Jika efisiensi > 1, maka menggunakan single prosesor 

bisa lebih cepat (cost tidak optimal). Jika efisiensi = 1,

cost masih diragukan. Cost optimal jika efisiensi <1.

7/30/2019 1. Pemrosesan Paralel

http://slidepdf.com/reader/full/1-pemrosesan-paralel 23/23

23

RESUME

Kompleksitas waktu, speed-up, cost, dan efisiensi dalampemrosesan paralel.

Kinerja (performance ) sebuah pemrosesan paralel menggunakan

hukum Ahmdahl dan pengertian cost.

Telah dibahas:

Mengapa harus menggunakan pemrosesan paralel

Istilah-istilah yang sering digunakan pada pemrosesan paralel

• 

• 

• 

•