pengolahan paralel 1
TRANSCRIPT
![Page 1: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/1.jpg)
Pengolahan Paralel
1/58Ernastuti
PENGOLAHAN PARALEL
Ernastuti
![Page 2: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/2.jpg)
Pengolahan Paralel
2/58Ernastuti
LATAR BELAKANG • Banyak aplikasi2 membutuhkan kemampuan
komputasi yang jauh lebih besar darikemampuan komputer prosesor tunggal
• Ada 2 cara yang dapat dicapai untuk memenuhikebutuhan ini :
1) mengembangkan komputer prosesor tunggalmenjadi lebih cepat
2) melakukan komputasi paralel.
![Page 3: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/3.jpg)
Pengolahan Paralel
3/58Ernastuti
PENGOLAHAN PARALEL
Minat penelitian dalam Pengolahan paraleldiantaranya adalah sebagai berikut :
1) arsitektur paralel2) algoritma paralel3) bahasa pemograman paralel4) analisis kinerja paralel.
![Page 4: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/4.jpg)
Pengolahan Paralel
4/58Ernastuti
4 langkahpenyelesaian masalah komputasi
secara paralel:
Pertama , mengerti dasar komputasi didalam bidang aplikasitertentu.
Kedua , mendisain suatu algoritma paralel atau me-paralelkan algoritma sekuensial yang sudah ada.
Ketiga , memetakan algoritma paralel kedalam arsitekturkomputer paralel yang sesuai,
Keempat , melibatkan penulisan program paralel denganmemanfaatkan suatu pendekatan pemrogramanparalel yang aplikatif.
![Page 5: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/5.jpg)
Pengolahan Paralel
5/58Ernastuti
• Pokok persoalan utama arsitektur paraleladalah terletak pada disain
jaringan interkoneksi prosesor
• Idealnya didalam jaringan, setiap prosesor didisain terhubung dengansemua prosesor lainnya.
![Page 6: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/6.jpg)
Pengolahan Paralel
6/58Ernastuti
• Pada graph, jaringan interkoneksi idealdigambarkan sebagaicomplete graph : (fully connected)
Untuk p prosesor pada jaringan interkoneksicomplete graph , jumlah edge penghubungnyaadalah p x (p-1) edge.
• Jaringan interkoneksi seperti ini jelas sangatmahal. (semakin besar jumlah edge dikatakan semakin mahal )
![Page 7: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/7.jpg)
Pengolahan Paralel
7/58Ernastuti
Topologi Model jaringan interkoneksi yang lebih murah dari complete graph yang adasaat ini antara lain adalah
• linear & ring, shuffle exchange, hypercube,• star, de bruijn, binary tree, delta, • butterfly, mesh, omega dan pyramid
![Page 8: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/8.jpg)
Pengolahan Paralel
8/58Ernastuti
LINEAR + RING
Untuk mereduksi interconnect cost, dicoba membuat jaringan yang lebih jarang (sparse) :
![Page 9: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/9.jpg)
Pengolahan Paralel
9/58Ernastuti
MESH + TORUS: 2D, 3D
Kemudian diperluas ke suatu jaringan multidimensional :
![Page 10: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/10.jpg)
Pengolahan Paralel
10/58Ernastuti
HYPERCUBE ( n-CUBE)
![Page 11: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/11.jpg)
Pengolahan Paralel
11/58Ernastuti
TREEPada jaringan TREE hanya ada satu jalur untuk setiap 2 simpul.Semakin tinggi Tree, semakin beresiko akan terjadikomunikasi bottleneck pada level-level yang tinggi dalam tree.
![Page 12: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/12.jpg)
Pengolahan Paralel
12/58Ernastuti
SHUFFLE EXCHANGEPerfect shuffle menghubungkan processor Pi and Pj dengan cara komunikasi satu arah sbb :
j = 2*i , 0 ≤ i ≤ N/2 – 1 atauj = 2*i + 1 – N , lainnya.
![Page 13: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/13.jpg)
Pengolahan Paralel
13/58Ernastuti
DE BRUIJNA network consisting of N = dk processors, each labeled with a k-digit word(ak-1 ak-2 … a1 a0) where aj is a digit (radix d), i.e. aj is one of (0, 1, … , d-1)The processors directly reachable from (ak-1 ak-2 … a1 a0) are (ak-2 … a1 a0 q) and (q ak-1 ak-2 … a1) where q is another digit (radix d).Berikut adalah jaringan de Bruijn untuk d=2 dan k=3
![Page 14: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/14.jpg)
Pengolahan Paralel
14/58Ernastuti
BUTTERFLYA Butterfly network is made of (n + 1)*2n processors organized into n+1 rows,each containing 2n processors.
Rows are labeled 0…n. Each processor has 4 connections to other processors (except processors in top and bottom row).
Processor P(r, j), i.e. processor number j in row r is connected toP(r-1, j) and P(r-1, m)where m is obtained
by inverting the rth significant bit in the binary representation of j.
![Page 15: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/15.jpg)
Pengolahan Paralel
15/58Ernastuti
PYRAMIDA pyramid consists of (4d+1 – 1)/3 processors organized in d+1 levels so as:• Levels are numbered from d down to 0• There is 1 processor at level d• Every level below d has four times the number of processors
than the level immediately above it.
![Page 16: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/16.jpg)
Pengolahan Paralel
16/58Ernastuti
Untuk membandingkanmodel jaringan interkoneksidiperlukan beberapa kriteria
pengukuran.
![Page 17: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/17.jpg)
Pengolahan Paralel
17/58Ernastuti
Kriteriayang digunakan industri berkaitan
dengankomunikasi dan kompleksitaspada jaringan interkonekasi
adalah sebagai berikut
![Page 18: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/18.jpg)
Pengolahan Paralel
18/58Ernastuti
Standard criteria used by industry:
• Network diameter = Max. number of hops necessary to link up two most distant processors
• Network bisection width = Minimum number of links to be severed for a network to be into two halves (give or take one processor)
• Maximum-Degree of PEs = maximum number of links to/from one PE
• Minimum-Degree of PEs = minimum number of links to/from one PE
![Page 19: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/19.jpg)
Pengolahan Paralel
19/58Ernastuti
• 1) Diameter of the Network = jarak maksimumjalur terpendek diantara semua prosesor didalamjaringan
• 2) Degree of processor = jumlah maksimum edge penghubung yang keluar/masuk dari/ke prosesor
• 3) Bisection width of the network = Jumlah edge minimum yang diputus dari jaringan sedemikiansehingga network terbagi dua sama besar
![Page 20: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/20.jpg)
Pengolahan Paralel
20/58Ernastuti
Selain itu ada kriteria lain :Suatu model jaringan interkoneksi dikatakan lebih baik dari
yang lain bila
• lebih efisien (efficient) , • lebih tepat/cocok (convenient),• lebih mudah diimplementasi (regularity),• lebih mudah diperluas (expandable/modularity) • dan/atau tidak berpotensi bottleneck.
Kenyataannya tak ada jaringan interkoneksi yang memenuhi semua kriteria ini.
![Page 21: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/21.jpg)
Pengolahan Paralel
21/58Ernastuti
COMPARISON OF INTERCONNECTION NETWORKSIntuitively, one network topology is more desirable than another if it is :
• More efficient• More convenient• More regular (i.e. easy to implement)• More expandable (i.e. highly modular)• Unlikely to experience bottlenecks
• Clearly no one interconnection network maximizes all these criteria.Some tradeoffs are needed.
![Page 22: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/22.jpg)
Pengolahan Paralel
22/58Ernastuti
• Dengan menjaga diameter jaringan tetap kecilmaka akan memberikan lower bound padakompleksitas algoritma yang diimplementasikanpada jaringan.
• Akibatnya , untuk menjaga diameter tetap kecilberarti diperlukan sejumlah edge penghubunglebih besar pada setiap prosesor.
![Page 23: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/23.jpg)
Pengolahan Paralel
23/58Ernastuti
Contoh topologi jaringan interkoneksi dalamarsitektur paralel yang umum saat ini :
![Page 24: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/24.jpg)
Pengolahan Paralel
24/58Ernastuti
TopologiJaringan
Jumlahnode
Jumlahedge
Diameter Max-degree
Min-degree
Complete Graph
16 240 1 15 15
Tree 16 14 6 3 1
Mesh 16 24 6 4 2
Ring 16 16 8 2 2
Hypercube 16 32 4 4 4
Perbandingan jumlah edge, diameter, max-degree dan min degree untuk 5 model topologi jaringan 16 node.
![Page 25: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/25.jpg)
Pengolahan Paralel
25/58Ernastuti
• Saat ini, komputer-komputer yang mendukukng komputasiparalel telah tersedia secara komersil dengan berbagaimacam topologi.
• Topologi interkoneksi Hypercube merupakan topologiyang paling dominan/menonjol pada kelas komputerparalel ini.
• Ametek, Floating Point System, Intel ScienticComputers, NCUBE dan Thingking Machines adalah beberapa vendordari komputer Hypercube.
![Page 26: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/26.jpg)
Pengolahan Paralel
26/58Ernastuti
Model Model jaringanjaringan dapatdapat diukurdiukur, , salahsalah satunyasatunya, , daridari tradetrade--offoff ::
Network cost = Network cost = derajatderajat ∗∗ diameterdiameter
![Page 27: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/27.jpg)
Pengolahan Paralel
27/58Ernastuti
•• Model Model jaringanjaringan dengandenganderajatderajat simpulsimpul yang yang kecilkecil, ,
mempunyaimempunyai diameter yang diameter yang besarbesar. .
•• KebalikannyaKebalikannya, , model model jaringanjaringan yang yang mempunyaimempunyai diameter diameter kecilkecilbiasanyabiasanya memilikimemiliki derajatderajat simpulsimpul yang yang besarbesar..
![Page 28: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/28.jpg)
Pengolahan Paralel
28/58Ernastuti
Hypercube mempunyai karakteristik yang layak
![Page 29: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/29.jpg)
Pengolahan Paralel
29/58Ernastuti
NETWORK COSTNETWORK COSTNETWORK COST
Hypercube mempunyai karakteristik yang layak
![Page 30: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/30.jpg)
Pengolahan Paralel
30/58Ernastuti
Topologi jaringan interkoneksi multiprosesor yang populer saat ini
Linear arrayRing
2D meshHypercube
TreeStar
![Page 31: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/31.jpg)
Pengolahan Paralel
31/58Ernastuti
HYPERCUBE HYPERCUBE dimensidimensi 1,2,3 1,2,3 dandan 44
22 44 88 1616
Hypercube paling banyak menarik perhatian dan diteliti
secara intensif
Dimensi 1 Dimensi 2Dimensi 3
Dimensi 4
![Page 32: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/32.jpg)
Pengolahan Paralel
32/58Ernastuti
MODEL-MODEL KOMPUTASIyang mendasari komputer paralel
![Page 33: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/33.jpg)
Pengolahan Paralel
33/58Ernastuti
![Page 34: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/34.jpg)
Pengolahan Paralel
34/58Ernastuti
![Page 35: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/35.jpg)
Pengolahan Paralel
35/58Ernastuti
![Page 36: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/36.jpg)
Pengolahan Paralel
36/58Ernastuti
![Page 37: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/37.jpg)
Pengolahan Paralel
37/58Ernastuti
ALGORITMA SEQUENTIALPENJUMLAHAN
Penjumlahan (SISD)Begin
sum a0for i 1 to n-1 do
sum sum + aiendfor
end
![Page 38: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/38.jpg)
Pengolahan Paralel
38/58Ernastuti
HASIL KOMPUTASI ALGORITMA SEQUENTIAL
PENJUMLAHANMisal Input : ai = {1,2,3,4,5,6,7,8}Sum = a0 = 1i = 1 sum = sum + a1 = 1 + 2 = 3i = 2 sum = sum + a2 = 3 + 3 = 6i = 1 sum = sum + a3 = 6 + 4 = 10i = 1 sum = sum + a4 = 10 + 5 = 15i = 1 sum = sum + a5 = 15 + 6 = 21i = 1 sum = sum + a6 = 21 + 7 = 28i = 1 sum = sum + a7 = 28 + 8 = 36
![Page 39: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/39.jpg)
Pengolahan Paralel
39/58Ernastuti
Shared Memory & Interconnection Network
• In most interesting problems that we wish to solve on a SIMD computer, it is desirable for the processors to be able to communicate among themselves during the computation in order to exchange data or intermediate results.
This can be achieved in two ways, SIMD computers • where communication is through a shared memory, and• Where it is done via an interconnection network.
![Page 40: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/40.jpg)
Pengolahan Paralel
40/58Ernastuti
Parallel Randon Access Machine• Extend the traditional RAM (Random
Access Memory) machine
• Interconnection network between global memory and processors
• Multiple processors
Shared – Memory
P1 P2 Pp
![Page 41: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/41.jpg)
Pengolahan Paralel
41/58Ernastuti
Parallel Randon Access Machine
Characteristics
• Processors Pi (i (0 ≤ i ≤ p-1 )– each with a local memory– i is a unique identity for processor Pi
• A global shared memory – it can be accessed by all processors
![Page 42: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/42.jpg)
Pengolahan Paralel
42/58Ernastuti
Parallel Randon Access Machine
Types of operations: • Synchronous
– Processors work in locked stepat each step, a processor is active or idlesuited for SIMD and MIMD architectures
• Asynchronous– processors have local clocks– needs to synchronize the processors suited for MIMD architecture
![Page 43: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/43.jpg)
Pengolahan Paralel
43/58Ernastuti
Parallel Randon Access Machine• Example of synchronous operationAlgorithm : Processor i (i=0 … 3)
Input : A, Bi processor id
Output : C
Begin If ( B==0) C = A
Else C = A/BEnd
![Page 44: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/44.jpg)
Pengolahan Paralel
44/58Ernastuti
Hasil Eksekusi Algoritma
Step 1
A : 7B : 0C : 7
A : 2B : 1C : 0
A : 4B : 2 C : 0
A : 5B : 0C : 5
Processor 3Processor 2Processor 1Processor 0
Initial
A : 7B : 0C : 0
A : 2B : 1C : 0
A : 4B : 2 C : 0
A : 5B : 0C : 0
Processor 3Processor 2Processor 1Processor 0
(idle B ≠ 0) (idle B ≠ 0) (active B = 0)(active B = 0)
![Page 45: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/45.jpg)
Pengolahan Paralel
45/58Ernastuti
Parallel Randon Access Machine
Step 2
A : 7B : 0C : 7
A : 2B : 1C : 2
A : 4B : 2 C : 2
A : 5B : 0C : 5
Processor 3Processor 2Processor 1Processor 0
(active B ≠ 0) (active B ≠ 0) (idle B = 0)(idle B = 0)
![Page 46: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/46.jpg)
Pengolahan Paralel
46/58Ernastuti
Parallel Randon Access MachineRead / Write conflicts EREW : Exclusive - Read, Exclusive -Write
– no concurrent ( read or write) operation on a variable
CREW : Concurrent – Read, Exclusive – Write – concurrent reads allowed on same variable– exclusive write only
![Page 47: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/47.jpg)
Pengolahan Paralel
47/58Ernastuti
Parallel Randon Access Machine
ERCW : Exclusive Read – Concurrent Write
CRCW : Concurrent – Read, Concurrent – Write
![Page 48: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/48.jpg)
Pengolahan Paralel
48/58Ernastuti
Parallel Randon Access MachineConcurrent write on a variable X
• Common CRCW : only if all processors write the same value on X
• SUM CRCW : write the sum all variables on X
• Random CRCW : choose one processor at random and write its value on X
• Priority CRCW : processor with hign priority writes on X
![Page 49: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/49.jpg)
Pengolahan Paralel
49/58Ernastuti
Parallel Randon Access MachineExample:Concurrent write on X by processors
P1 (50 X) , P2 (60 X), P3 (70 X)
• Common CRCW ou ERCW : Failure
• SUM CRCW : X is the sum (180) of the writtenvalues
• Random CRCW : final value of X ∈ { 50, 60, 70 }
![Page 50: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/50.jpg)
Pengolahan Paralel
50/58Ernastuti
ALGORITMA PARALEL PENJUMLAHAN
![Page 51: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/51.jpg)
Pengolahan Paralel
51/58Ernastuti
ILUSTRASI KOMPUTASI ALGORITMA PARALEL PENJUMLAHAN
![Page 52: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/52.jpg)
Pengolahan Paralel
52/58Ernastuti
ALGORITMA SEQUENTIALPREFIX SUM
Input : A : array of integerOutput: pref_sum: array of integer
pref_sum[0] 0begin
for i 1 to npref_sum[ i ] pref_sum[i – 1] + A[ i ]
endforend
![Page 53: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/53.jpg)
Pengolahan Paralel
53/58Ernastuti
ILUSTRASI KOMPUTASI ALGORITMA SEQUENTIALPREFIX SUM
A[1,…,9] = {1,2,3,4,5,6,7,8,9}pref_sum[1] = 0 + 1 = 1pref_sum[2] = 1 + 2 = 3pref_sum[3] = 3 + 3 = 6pref_sum[4] = 6 + 4 = 10pref_sum[5] = 10 + 5 = 15pref_sum[6] = 15 + 6 = 21pref_sum[7] = 21 + 7 = 28pref_sum[8] = 28 + 8 = 36pref_sum[9] = 36 + 9 = 45
![Page 54: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/54.jpg)
Pengolahan Paralel
54/58Ernastuti
ALGORITMA PARALEL PREFIX SUM
![Page 55: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/55.jpg)
Pengolahan Paralel
55/58Ernastuti
ILUSTRASI KOMPUTASI ALGORITMA PARALEL PREFIX SUM
![Page 56: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/56.jpg)
Pengolahan Paralel
56/58Ernastuti
ALGORITMA PARALELPREFIX SUM
![Page 57: Pengolahan Paralel 1](https://reader033.vdokumen.com/reader033/viewer/2022052208/55721230497959fc0b902ed9/html5/thumbnails/57.jpg)
Pengolahan Paralel
57/58Ernastuti