Arsitektur


PENDAHULUAN

1. Kebutuhan akan Pengolahan Paralel

Motivasi :
-. Pengolahan data numerik dalam jumlah yang sangat besar.
-. Kebutuhan akan ketersediaan data yang senantiasa up to date.

Contoh 1.1. :

Simulasi sirkulasi global laut di Oregon State University.
Lautan dibagi ke dalam 4096 daerah membentang dari timur ke barat, 1024 daerah membentang dari utara ke selatan dan 12 lapisan. Berarti terdapat sekitar 50 juta daerah berdimensi tiga.
Satu iterasi mampu mensimulasikan sirkulasi lautan untuk jangka waktu 10 menit dan membutuhkan sekitar 30 milyar kalkulasi floating point. Para ahli kelautan ingin menggunakan model tersebut untuk mensimulasikan sirkulasi lautan untuk periode 1 tahun.

Pengolahan Paralel :
-. pengolahan informasi yang menekankan pada manipulasi data-data elemen secara simultan.
-. dimaksudkan untuk mempercepat komputasi dari sistem komputer dan menambah jumlah keluaran yang dapat dihasilkan dalam jangka waktu tertentu.

Komputer Paralel :
-. Komputer yang memiliki kemampuan untuk melakukan pengolahan paralel.

Throughput :
-. Banyaknya keluaran yang dihasilkan per unit waktu.

Peningkatan throughput dapat dilakukan dengan :
-. Meningkatkan kecepatan operasi
-. Meningkatkan jumlah operasi yang dapat dilakukan dalam satu waktu tertentu (concurrency).

2. Paradigma Pengolahan Paralel

2.1. M. J. FLYNN

Pengklasifikasian oleh Flynn, dikenal sebagai Taksonomi Flynn, membedakan komputer paralel ke dalam empat kelas berdasarkan konsep aliran data (data stream) dan aliran instruksi (instruction stream), sebagai : SISD, SIMD, MISD, MIMD.

SISD (Single Instruction stream, Single Data stream)
Komputer tunggal yang mempunyai satu unit kontrol, satu unit prosesor dan satu unit memori.

[Akl 1989]

SIMD (Single Instruction stream, Multiple Data stream)
Komputer yang mempunyai beberapa unit prosesor di bawah satu supervisi satu unit common control. Setiap prosesor menerima instruksi yang sama dari unit kontrol, tetapi beroperasi pada data yang berbeda.

[Akl 1989]
MISD (Multiple Instruction stream, Single Data stream)
Sampai saat ini struktur ini masih merupakan struktur teoritis dan belum ada komputer dengan model ini.

[Akl 1989]

MIMD (Multiple Instruction stream, Multiple Data stream)
Organisasi komputer yang memiliki kemampuan untuk memproses beberapa program dalam waktu yang sama. Pada umumnya multiprosesor dan multikomputer termasuk dalam kategori ini.

[Akl 1989]

2.2. T.G. LEWIS

T.G. Lewis membedakan komputer paralel ke dalam dua kelas, berdasarkan ada atau tidak adanya common global clock, sebagai : synchronous dan asynchronous.

Gambar 1.
Taksonomi Parallel Computing oleh T.G. Lewis dkk.
[Lewis,1992]

Synchronous :
-. Pada komputer paralel yang termasuk dalam kategri ini terdapat koordinasi yang mengatur beberapa operasi untuk dapat berjalan bersamaan sedemikian hingga tidak ada ketergantungan antar operasi.
-. Parallelism yang termasuk dalam kategori ini adalah vector/array parallelism, SIMD dan systolic parallelism.
-. Systolic parallel computer adalah multiprocessor dimana data didistribusikan dan dipompa dari memory ke suatu array prosesor sebelum kembali ke memory.

Asynchronous :

-. Pada komputer paralel yang termasuk dalam kategori asynchronous, masing-masing prosesor dapat diberi tugas atau menjalankan operasi berbeda dan masing-masing prosesor melaksanakan operasi tersebut secara sendiri-sendiri tanpa perlu koordinasi.
-. Paradigma yang juga termasuk dalam kategori ini adalah MIMD dan reduksi.
-. Paradigma reduksi adalah paradigma yang berpijak pada konseph graph reduksi. Program dengan model reduksi diekspresikan sebagai graph alur data. Komputasi berlangsung dengan cara mereduksi graph dan program berhenti jika graph akhirnya hanya mempunyai satu simpul.

2.3. MICHAEL J. QUINN

Quinn membedakan paralelisma ke dalam dua jenis : Data Parallelism dan Control Parallelism.

Data Parallelism :
penerapan operasi yang sama secara simultan terhadap elemen-elemen dari kumpulan data.

Control Parallelism :
penerapan operasi-operasi berbeda terhadap elemen-elemen data yang berbeda secara bersamaan. Pada control parallelism dapat terjadi aliran data antar proses-proses dan kemungkinan terjadi aliran data yang kompleks/rumit.
Pipeline merupakan satu kasus khusus dari control parallelism dimana aliran data membentuk jalur yang sederhana.

Gambar 4.
Ilustrasi perbandingan pipelining dengan data parallelism.
[Quinn 1994]

Contoh :

Perhatikan ke-empat taman yang harus dirawat berikut ini :

a. Tanaman Pagar b. Lapangan rumput c. Kebun bunga

Nama Pekerjaan Pekerja
1. Merapihkan tanaman pagar
Ali ,
Budi ,
Cipto,
Dadang,
Edi
2. Memangkas rumput
Frans,
Gugun
3. Menanam bibit bunga
Heru,
Indra,
Joko
4. Menyiram taman Ali

Pekerjaan 4 dapat dilakukan jika ketiga pekerjaan 1, 2 dan 3 telah selesai. Pekerjaan 1, 2 dan 3 dapat dilakukan secara bersamaan, sebagai contoh control parallelism. Masing-masing pekerjaan adalah contoh data parallelism. Sementara pekerjaan 4 dikerjakan pada sebuah taman, pekerjaan 1, 2 dan 3 dapat dikerjakan pada satu taman yang lain.

3. Terminologi
Pengolahan Paralel :
pengolahan informasi yang ditekankan pada manipulasi elemen data yang dimiliki oleh satu atau lebih dari satu proses secara bersamaan dalam rangka menyelesaikan sebuah problem.
Komputer Paralel :
komputer multi-prosesor dengan kemampuan melakukan pengolahan paralel.
Supercomputer :
sebuah general-purpose computer yang mampu me-nyelesaikan problem dengan kecepatan komputasi sangat tinggi. Semua superkomputer kontemporer adalah komputer paralel. Beberapa di antaranya memiliki prosesor yang sangat kuat dalam jumlah yang relatif sedikit, sementara yang lainnya dibangun oleh mikroprosesor dalam jumlah yang cukup besar.
Throughput :
banyaknya keluaran yang dihasilkan per unit waktu
Pipeline :
Pada komputasi pipelined, komputasi dibagi ke dalam sejumlah langkah yang masing-masing disebut sebagai segmen, atau stage. Output dari sebuah segmen menjadi input segmen yang lain.

4. Analisa Algoritma Paralel.

Pada saat sebuah algoritma digunakan untuk memecahkan sebuah problem, maka performance dari algoritma tersebut akan dinilai. Hal ini berlaku untuk algoritma sekuensial maupun algoritma paralel. Penampilan sebuah algoritma pengolahan peralel dapat dinilai dari beberapa kriteria, seperti running time dan banyaknya prosesor yang digunakan.

4.1. Running Time
Running time adalah waktu yang digunakan oleh sebuah algoritma untuk menyelesaikan masalah pada sebuah komputer paralel dihitung mulai dari saat algoritma mulai hingga saat algoritma berhenti. Jika prosesor-prosesornya tidak mulai dan selesai pada saat yang bersamaan, maka running time dihitung mulai saat komputasi pada prosesor pertama dimulai hingga pada saat komputasi pada prosesor terakhir selesai.

4.1.1. Counting Steps

Untuk menentukan runnging time, secara teoritis dilakukan analisa untuk menentukan waktu yang dibutuhkan sebuah algoritma dalam mencari solusi dari sebuah masalah. Hal ini dilakukan dengan cara menghitung banyaknya operasi dasar, atau step (langkah), yang dilakukan oleh algoritma untuk keadaan terburuknya (worst case).
Langkah-langkah yang diambil oleh sebuah algoritma dibedakan ke dalam dua jenis yaitu :

a. Computational step
Sebuah computational step adalah sebuah operasi aritmetika atau operasi logika yang dilakukan terhadap sebuah data dalam sebuah prosesor.

b. Routing step.
Pada routing step, sebuah data akan melakukan perjalanan dari satu prosesor ke prosesor lain melalui shared memory atau melalui jaringan komunikasi.

Contoh 4.1. :

Perhatikan sebuah file komputer dengan n entri berbeda.
Pada file tersebut akan diperiksa apakah x terdapat di dalamnya.

Dengan algoritma sekuensial, keadaan terburuknya (worst case) untuk menemukan x membutuhkan n langkah, dimana tiap langkah adalah membandingkan x dengan sebuah entri pada file. Keadaan terburuk terjadi jika x ternyata sama dengan entri terakhir pada file atau x tidak terdapat pada file tersebut.

Dengan EREW SM SIMD (Exclusive Read Exclusive Write Shared Memory SIMD) komputer dengan N prosesor, dimana N  n, pada worst casenya dibutuhkan log N + n/N langkah.

Misalkan P1 , P2 , … , PN prosesor-prosesor pada EREW SM SIMD komputer tersebut.
Proses pencarian entri yang sama dengan x adalah :
-. Broadcasting, x dikomunikasikan pada semua prosesor dengan cara
1. P1 membaca x dan mengkomunikasikan dengan P2.
2. P1 dan P2 secara simultan mengkomunikasikan x dengan P3 dan P4
3. P1, P2, P3 dan P4 secara simultan meng-komunikasikan x dengan P5 , P6 , P7 dan P8 .
Dan seterusnya hingga semua prosesor mengenal x.
Proses ini dilakukan dalam log N langkah.
-. Searching, File dimana x akan dicari dibagi ke dalam sub file dan secara simultan dilakukan pencarian oleh prosesor-prosesor :
P1 mencari pada n/N entri pertama,
P2 mencari pada n/N entri kedua,
P3 mencari pada n/N entri ketiga,
PN mencari pada n/N entri ke-N.
Proses ini membutuhkan n/N langkah.

Jadi total langkah yang dibutuhkan oleh algoritma tersebut adalah : log N + n/N langkah.

4.1.2. Speedup

Pengukuran speedup sebuah algoritma paralel adalah salah satu cara untuk mengevaluasi kinerja algoritma tersebut.
Speedup adalah perbandingan antara waktu yang diperlukan algoritma sekuensial yang paling efisien untuk melakukan komputasi dengan waktu yang dibutuhkan untuk melakukan komputasi yang sama pada sebuah mesin pipeline atau paralel.

Contoh 4.2. :
Dari contoh 4.1.
Running time proses searching dengan mesin sekuensial adalah O(n).
Running time dari proses searching pada komputer EREW SM SIMD adalah O(n/N).
Jadi speedup = O(N).

4.2. Banyaknya Prosesor (Number of Processor)
Semakin banyak prosesor yang digunakan semakin tinggi biaya untuk memperoleh solusi sebuah problem. Hal ini terjadi karena perlu dipertimbangkan biaya pengadaan prosesor dan perawatannya.
Jumlah prosesor yang tergantung dari n , n=ukuran problem, dinyatakan sebagai p(n). Kadang-kadang jumlah prosesor tidak tergantung pada ukuran problem.

Contoh 4.3. :
Perhatikan n bilangan x1,x2,…,xn yang akan dijumlahkan.
Dengan menggunakan komputer tree-connected SIMD dengan log n level dan n/2 daun, dibutuhkan pohon dengan ukuran (n-1) atau p(n) = n -1 .
Ilustrasi untuk n = 8.

Sedangkan pada contoh 4.1. , banyaknya prosesor, N , tidak tergantung pada ukuran problem, n .

Arsitektur Komputer

Dua element utama pd sistem komputer konvensional:
• Memory
• Processor

Klasifikasi Arsitektur komputer (Michael Flynn), berdasarkan karakteristiknya termasuk banyaknya processor, banyaknya program yang dapat dieksekusi dan struktur memori:

Single Intruction Stream, Single Data Stream (SISD)
Satu CPU yang mengeksekusi instruksi satu persatu dan menjemput atau menyimpan data satu persatu
Single Instruction Stream Multiple Data Stream (SIMD)
Satu unit kontrol yang mengeksekusi aliran tunggal instruksi, tetapi lebih dari satu Elemen Pemroses

Multiple Instruction Stream, Single Data Stream (MISD)
Mengeksekusi beberapa program yang berbeda terhadap data yang sama.
Ada dua kategori:
1. Mesin dengan Unit pemroses berbeda dengan instruksi yang berbeda dengan data yang sama (sampai sekarang tidak ada mesin yang seperti ini)
2. Mesin, dimana data akan mengalir ke elemen pemroses serial
Multiple Instruction Stream, Multiple Data Stream (MISD)
Juga disebut multiprocessors, dimana lebih dari satu proses dapat dieksekusi berikut terhadap dengan datanya masing-masing

Arsitektur Paralel
Dalam taksonomi arsitektur paralel ada dua keluarga arsitektur paralel yang banyak diterapkan adalah: SIMD dan MIMD, dimana untuk mesin yang murni MISD tidak ada.
Arsitektur SIMD
Mesin SIMD secara umum mempunyai karakteristik sbb:
• Mendistribusi proses ke sejumlah besar hardware
• Beroperasi terhadap berbagai elemen data yang berbeda
• Melaksanakan komputasi yang sama terhadap semua elemen data

Peningkatan kecepatan pada SIMD proporsional dengan jumlah hardware (elemen pemroses) yang tersedia.

Sebagai perbandingan, pada gambar dibawah, untuk sistem SISD (a), X1, X2, X3, dan X4 merepresentasikan blok instruksi, setelah mengeksekusi X1, tergantung dari nilai X, X3 atau X2 dieksekusi kemudian X4. Pada sistem SIMD, beberapa aliran data ada yang memenuhi X=? dan ada yang tidak, maka beberapa elemen akan melakukan X3 dan yang lain akan melakukan X2 setelah itu semua elemen akan melakukan X4.

Array Element pemroses atau biasa disebut Processor Array dapat berbeda satu sama lain berdasarkan:
• Struktur elemen pemroses
• Struktur unit kontrol
• Struktur memori
• Topologi interkoneksi
• Struktur input/output

Struktur umum dari 16 elemen pemroses dan unit kontrol tunggal dapat dilihat pada gambar berikut

Contoh komputer SIMD termasuk: ILLIAC IV, MPP, DAP, CM-2, MasPar MP-1, dan MasPar MP-2.

Tiga arsitektur pemroses array yang berbeda dapat dilihat pada gambar berikut.

MasPar MP-1
Dua bagian utama dalam arsitektur MasPar yaitu:
1. MasPar Front End (DEC3100 WS dgn ULTRIX)
2. Data Parallel Unit (DPU)
• Array Control Unit (ACU)
• Processor Element Array (PE Array) (64X64 =4096 PEs)

Array Control Unit (ACU) melaksanakan dua tugas:
1. Eksekusi instruksi trehadap data singular
2. Secara simultan memberi instruksi yang beroperasi pada data paralel untuk tiap PE

Arsitektur MISD

Prosesor pipeline adalah prosesor MISD yang bekerja berdasarkan prinsip pipelining. Pada pipeline proses dapat dibagi menjadi beberapa tahap dan beberapa proses dapat dilaksanakan secara simultan.
Pada gambar dibawah dapat dilihat perbedaan proses serial dengan pipeline

Waktu eksekusi lebih cepat dibandingkan dengan proses serial.
Prinsip pipelining dapat digunakan pada dua level yang berbeda:
 Pipeline unit aritmatika
 Pipeline unit kontrol
Seperti terlihat pada gambar dibawah:

Operasi pipeline dapat dilaksanakan secara siklus yaitu cyclic pipeline, dimana dapat dibagi dalam 5 tahap:
• Operasi baca (dari shared memories)
• Operasi transfer (memori ke elemen pemroses)
• Operasi eksekusi (di elemen pemroses)
• Operasi transfer (elemen pemroses ke memori)
• Operasi simpan (di shared memories)

Secara umum, prinsip pipeline dapat diterapkan pada beberbagai level, seperti:
• Level instruksi (unit pemrosesan instruksi)
• Level subsystem (unit aritmatika pipeline)
• Level system (level hardware/software)
Secara umum arsitektur pipeline dapat dilihat pada gambar dibawah ini

CDC Star 100
CPU terdiri dari dua unit aritmatika floating point pipeline

Systolic Array Processor
Merupakan arsitektur array pipeline multidimensional yang dirancang untuk mengimplementasikan fixed algorithm. Array systolic dibentuk dengan jaringan unit fungsional yang secara lokal terkoneksi. Array dapat beroperasi secara sinkronus dengan multidimensional pipelining.

Dengan beberapa topologi array systolic seperti pada gambar berikut.

Arsitektur MIMD
Sistem MIMD merupakan sistem multiprocessing atau multicomputer dimana tiap prosesor mempunyai unit kontrol dan program sendiri. Karakteristiknya:
• Proses didistribusikan ke beberapa prosesor independent
• Berbagi sumbar daya, termasuk memori, processor
• Operasi tiap processor secara independent dan simultan
• Tiap processor menjalankan programnya sendiri

Komputer MIMD: sistem tightly coupled (global memory) dan loosely coupled (local memory).

Intel iPSC Machines
Sistem iPSC terdiri dari: 1, 2 atau 4 unit komputesi (cube) dan prosesor host (cube manager). Cube merupakan processing nodes yang terinterkoneksi hypercube yang mempunyai memori dan prosesor sendiri.
Contoh: iPSC/1 terdiri dari 32 nodes, cube manager dan 16 Mbytes memory unshared. Tiap node mempunyai arsitektur seperti pada gambar berikut:

Symmetry Machine
SM dapat memperkejakan 30 processor, dimana merupakan contoh UMA MIMD (tightly coupled)

Carnegie-Mellon Multi-Mini_Processor (C.mmp)
Processor dikelompokkan ke dalam cluster local dan diorganisasikan kedalam struktur tree dan berkoneksi lewat Inter-Cluster Buses. Seperti terlihat pada gambar dibawah.

Arsitektur Hibrid SIMD-MIMD
Arsitektur hibrid SIMD-MIMD adalah sistem pemrosesan paralel dengan struktur yang dapat diubah sebagai satu atau lebih arsitektur SIMD dan /atau MIMD independen dengan ukuran yang bervariasi.

Ada tiga kategori utama arsitektur SIMD-MIMD:
1. PASM: Partionable SIMD-MIMD systems
2. VLIW: Very Long Instruction Word systems
3. MSIMD: Multiple SIMD systems

Arsitektur PASM
Arsitektur PASM dikembangkan unutk image processing. Komponen dasar arsitektur ini dapat dilihat pada gambar berikut.

System Control Unit bertanggung jawab terhadap penjadualan proses, alokasi sumber daya, modus paralelisme, dan koordinasi keseluruhan.
Microcontrollers mengontrol aktivitas, dimana masing-masing memiliki microprocessor dan dua unit memori untuk melaksanakan loading memori dan komputasi.
Microprocessors melaksanakan komputasi SIMD dan MIMD.
Memory modules digunakan untuk penyimpanan data dalam modus SIMD dan penyimpanan kedua data dan instruksi pada modus MIMD

Arsitektur VLIW
Elemen pemroses dibawah kontrol terpusat, tetapi individual elemen pemroses dapat melaksanakan operasi berbeda pada data yang berbeda. Instruksi yang sangat panjang pelaksanaannya dapat dilakukan secara paralel.

Arsitektur Aliran Data
Pada arsitektur aliran data, operasi dapat dilaksanakan dengan memperbolehkan instruksi dilaksanakan segera setelah operand dan sumber daya komputasinya tersedia. Bila data untuk beberapa instruksi datang secara berbarengan maka instruksi dapat dieksekusi secara paralel.

Arsitektur aliran data dibagi menjadi tiga kategori yagn berbeda:
1. Arsitektur statis; dapat mengevaluasi hanya satu graf program
2. Arsitektur statis yang dapat di rekonfigurasi ulang; mempunyai beberapa processor dimana interkoneksi logika antar processor dibuat setelah program diload, maka koneksi ini harus ditentukan pada saat kompilasi dan program yang diload tetap selama eksekusi
3. Arsitektur Dinamis; arsitektur ini mengijinkan program untuk dievaluasi secara dinamis, koneksi logika antar processor dapat berubah selama eksekusi berlangsung

NOTASI UNTUK ALGORITMA PARALEL

• Untuk Shared-Memory Model
Global
Local

• Untuk Distributed Memory Machine
Parameter  suatu konstanta yang sudah dikomunikasikan antar prosesor.

• Umum

+, x, 
if … else … endif ; while … endwhile ; for … endfor
for all …  data paralelism :
• SIMD : diasumsikan ada lockstep
• MIMD : diasumsikan berjalan asynchronous

•  menyatakan suatu prosesor store/retrieve nilai local dari prosesor lain.

• [x] a menyatakan nilai dari prosesor.
tmp  [s] a

SUMATION (HYPERCUBE SIMD):

Parameter n { Number of elements to add}
p { Number of processing elements}

Global j
Local local.set.size, local.value[1…n/p ], sum, tmp

Begin
For all Pi, where ()  i  p – 1 do
If i < (n modulo p) then
Local.set.size  n/p
Else
Local.set.size  n/p
Endif
Sum  0
Endfor
For j  1 to n/p do
For all Pi, Where 0  i  P-1 do
If local.set.size  j then
Sum  sum + local.value[j]
Endif
Endfor
Endfor
For j  log P-1 downto 0 do
For all Pi, Where 0  i  P-1 do
If i < 2j Then
tmp  [ i+2j] sum
sum  sum + tmp
Endif
Endfor
Endfor
END
Hasilnya ?

Bagaimana jika setiap elemen pemrosesan akan mempunyai copy-an dari global sum ? Kita dapat menggunakan fase broadcast di akhir algoritma. Setiap elemen pemrosesan  mempunyai global sum, nilai-nilainya dapat dikirimkan ke processor lainnya dalam log p tahapan komunikasi dengan membalikan arah edge pada pohon binomial.

Kompleksitas untuk menemukan jumlah (sum) dari n nilai,  (n/p + log p) pada model hypercube yang berarray prosesor.

SHUFFLE – EXCHANGE SIMD MODEL

Pada model ini, tidal ada dilatasi – 1 pada pohon binomial. Efisiensi algoritma ini jika jumlah digabungkan secara berpasangan. Angka logaritma dari tahapan penggabungan dapat menemukan total akhir. Setelah log p shuffle exchange, prosesor O memdapatkan total akhir prosesor.

SUMMATION (SHUFFLE-EXCHANGE SIMD) :

Parameter n { Number of elements to add }
P { Number of processing elements }
Global j
Local local.set.size, local.value[1…n/p ], sum,tmp
Begin
For all Pi, where ()  i  p – 1 do
If i < (n modulo p) then
Local.set.size  n/p
Else
Local.set.size  n/p
Endif
Sum  0
Endfor
For j  1 to n/p do
For all Pi, Where 0  i  P-1 do
If local.set.size  j then
Sum  sum + local.value[j]
Endif
Endfor
Endfor
For j  0 to log p-1 do
For all Pi, Where 0  i  P-1 do
Shuffle (sum)  sum
Exchange (tmp)  sum
Sum  sum + tmp
Endfor
Endfor
END

Waktu Kompleksitas :  (n/p + log p)

2-D Mesh SIMD Model

Untuk mendapatkan jumlah n nilai diantara p prosesor, diorganisasikan dalam p x p mesh, minimal satu prosesor pada mesh harus berisi total akhir.
Total jumlah dari tahap komunikasi untuk mendapatkan sub-total dari prosesor minimal 2(p-1).
Kompleksitas algoritma ini (n/p + p)

(Pseudocode (anggap n = l2 )
SUMMATION (2-D MESH SIMD) :

Parameter l { Mesh has size l x l }
Global i
Local tmp,sum
Begin
{each processor finds sum of its local values – code not shown}
For i  l-1 downto 1 do
For all Pj,i , Where 1  j  l do
{Processing elements in column i active}
tmp  south (sum)
sum  sum + tmp
Endfor
Endfor
END

Waktu Eksekusi Algoritma ini terbagi 2 :

• Waktu yang dibutuhkan untuk nilai awal pesan ( message – passing overhead)
• Waktu yang dibutuhkan untuk melaksanakan pemindahan data ( message latency)

Jika data yang di- broadcast sedikit, message – passing overhead mendominasi message latency.

Algoritma yang baik adalah yang meminimalkan jumlah komunikasi yang dilaksanakan oleh setiap prosesor. Jadi minimal untuk komunikasi membutuhkan log p.

Pohon binomial cocok untuk model broadcast ini, karena ada sebuah dilatasi-1 yang ditempelkan ke hypercube dari pohon binomial ( Lihat Gb. 6-11 dan 6 – 12)

Jika data yang di-broadcast besar, waktu pemindahan data mendominasi message-passing overhead . Pada pohon binomial-nya merupakan keadaan terburuk, dalam setiap waktu, tidak lebih dari p/2 dari p log p hubungan komunikasi yang digunakan.

Jika M adalah waktu yang dibutuhkan untuk melewatkan pesan dari satu prosesor ke lainnya, algoritma broadcast ini membutuhkan waktu M log p.

Jhonson and Ho (1989) membuat algoritma broadcast yang mengeksekusi waktu lebih cepat dari algoritma bimial log p.

Algoritmanya : setiap hypercube terdiri dari “log p edge-disjoint spanning tree” dengan node akar yang sama .
Algoritma memisahkan pesan ke dalam log p bagian dan broadcast setiap bagian ke node lain melalui pohon rentang binomial. (lihat Gb. 6-13)

Sehingga algoritma yang baru membutuhkan waktu M log p/log p = M.

HYPERCUBE BROADCAST (id,source,value) :

Parameter P {Number of processor}
Value id {Processor’s id number}
source {ID of source processor}
Reference value {value to be broadcast}
Local i {loop iteration}
partner {partner processor}
position {position in broadcast tree}

{This procedure is called from inside a for all statement}

Begin
position  id  source
For i  0 to log p-1 do
If position < 2i then
partner  id  2i
[partner] value  value
Endif
Endfor
END.

ALGORITMA-ALGORITMA
PARALLEL RANDOM ACCESS MACHINE
(PRAM = pea ram)

Algoritma yang dibahas :
1. Parallel reduction
2. Prefix sums
3. List ranking
4. Pre-order tree traversal
5. Merging two sorted lists
6. Graph coloring

Algoritma-algoritma PRAM memiliki 2 (dua) fase :
1. mengaktifkan sejumlah prosesor
2. prosesor yang sudah diaktifkan (pada fase 1), melaksanakan komputasi secara paralel
Gambar 2.4 Untuk mengubah 1 prosesor yang aktif ke p prosesor dibutuhkan log p langkah

Jumlah prosesor yang aktif merupakan lipat-2 (2n) dari prosesor tunggal atau logaritma dari basis 2.

Instruksi meta untuk mengaktifkan prosesor yang digunakan (dalam fase 1) :
spawn ()

Instruksi meta untuk melakukan komputasi secara paralel (dalam fase 2) :
for all
do

endfor

Pohon biner menjadi paradigma yang penting dalam komputasi paralel. Pada beberapa algoritma ada yang menggunakan aliran data top-down (akar –daun). Contoh :
 broadcast
akar mengalirkan (mengirimkan) data yang sama ke setiap daunnya
 divide-and-conquer
pohon menggambarkan adanya perulangan sub divisi suatu masalah ke sub masalah yang lebih kecil.

Algoritma lain yang mengalirkan data secara bottom-up (daun -akar) adalah operasi reduksi atau “fan-in”.

DEFINISI
Diberikan sekumpulan n nilai a1, a2, … ,an dan operator biner asosiatif , “reduksi” adalah proses menghitung dari :

a1  a2  …  an

Salah satu contoh dari operasi reduksi adalah penjumlahan paralel (parallel summation).

Parallel Reduction (Reduksi paralel)
Prosesor PRAM memanipulasi data yang disimpan dalam register global.

DEFINSI
Penjumlahan secara paralel merupakan salah satu contoh dari operasi reduksi.

CONTOH
Reduksi secara paralel dapat digambarkan dengan pohon biner. Sekelompok n nilai ditambahkan dalam log p langkah penambahan paralel.

Gambar 2.5 Implementasi algoritma penjumlahan, setiap node dari pohon merupakan elemen dalam array

PSEUDOCODE
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]
Global 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 2j = 0 and 2i + 2j < n then
A[2i]  A[2i] + A[2i + 2j]
endif
endfor
endfor
end
Gambar 2.7 Algoritma PRAM EREW untuk menjumlah n elemen dengan n/2 prosesor

GAMBARAN PSEUDOCODE
Gambar 2.6 Menjumlahkan 10 nilai

KOMPLEKSITAS
Rutin spawn :  n/2  doubling steps
Perulangan for yang sekuensial :  log n  kali

Waktu kompleksitas algoritma : (log n),
dengan n/2 prosesor.

PREFIX SUMS (sering disebut parallel prefixes, scan)
DEFINISI
Diberikan sekumpulan n nilai a1, a2, …, an dan operasi asosiatif , prefix sum adalah menghitung :
a1
a1  a2
a1  a2  a3

a1  a2  a3  …  an
Misal : diberikan operasi + dan array integer {3, 1, 0, 4, 2}, hasil prefix sum adalah array dari {3, 4, 4, 8, 10}.

CONTOH
Diberikan array A dari n huruf. Huruf-huruf besarnya akan diurut. (lihat gambar 2.8)
a) Array A berisi huruf besar maupun huruf kecil dan ada array tambahan T berukuran n. Huruf-huruf besar akan diletakkan di awal dari A secara terurut.
b) Array T berisi 1 untuk merepresentasikan huruf besar dan 0 untuk merepresentasikan huruf kecil
c) Array T dikomputasi dengan prefix sum, menggunakan operasi tambah. Setiap huruf besar L diletakkan di A[i], nilai dari T[i] adalah indeks dari L.
d) Array A setelah “packing”.

Gambar 2.8 ”Packing” elemen dengan aplikasi prefix sum.

PSEUDOCODE
PREFIX.SUMS (CREW PRAM):
Initial condition : List of n  1 elements stored in A[0 … (n -1)]
Final condition : Each element a[i] contains A[0]  …  A[i]
Global variables : n, A[0 … (n-1)], j
begin
spawn (P1, P2, …, Pn – 1)
for all Pi where 1  i  n – 1 do
for j  0 to log n – 1 do
if i – 2j  0 then
A[i]  A[i] + A[i – 2j]
endif
endfor
endfor
end
Gambar 2.9 Algoritma PRAM untuk menemukan prefix
sum dari n elemen dengan n-1 prosesor
GAMBARAN PSEUDOCODE
Gambar 2.10 Algoritma Prefix sum dari 10 nilai

KOMPLEKSITAS
Rutin spawn : log n – 1 instruksi
Perulangan for yang sekuensial :  log n  kali

Waktu kompleksitas algoritma : (log n),
dengan n – 1 prosesor.

List Ranking
Suffix sum adalah “variant” dari prefix sum, dimana elemen array digantikan dengan linked list, dan penjumlahan dihitung dari belakang (Karp & Ramachandran 1990).

DEFINISI
Jika elemen-elemen dari list berisi 0 atau 1 dan operasi asosiatif  merupakan penambahan, maka masalah ini biasa disebut list ranking.

CONTOH

Gambar 2.11 Posisi setiap item pada linked-list n elemen
dicapai dalam log n langkah pointer-jumping

PSEUDOCODE
LIST.RANKING (CREW PRAM):
Initial condition : Values in array next represent a linked list
Final condition : Values in array position contain original
distance of each element from end of list
Global variables : n, position[0 … (n – 1)], next[0 … (n – 1)], j
begin
spawn (P0, P1, P2, …, Pn-1)
for all Pi where 0  i  n – 1 do
if next[i] = i then position[i]  0
else position[i] 1
endif
for j 1 to log n do
position[i]  position[i] + position[next[i]]
next[i]  next[next[i]]
endfor
endfor
end
Gambar 2.12 Algoritma PRAM untuk menghitung jarak dari belakang/ akhir list untuk setiap elemen singly-linked list

GAMBARAN PSEUDOCODE
Untuk menunjukkan posisi list adalah dengan menghitung jumlah penelusuran antara elemen list dan akhir list. Hanya ada (n-1) pointer antara elemen list awal dan akhir list.

Jika satu prosesor diasosiasikan dengan setiap elemen list dan pointer lompatan secara paralel, jarak dari akhir list hanya ½ bagian melalui instruksi next[i]  next[next[i]]. Jika sebuah prosesor menambah hitungan ke link-traversalnya sendiri, position[i], hitungan link-traversal sekarang dari successornya dapat dicapai.

KOMPLEKSITAS
Rutin spawn : (log n),
Perulangan for : maksimal  log n  kali

Waktu kompleksitas algoritma : (log n),
dengan n prosesor.

Preorder Tree Traversal
DEFINISI
Secara sekuensial
PREORDER.TRAVERSAL(nodeptr):
begin
if nodeptr null then
nodecount codecount + 1
nodeptr.label nodecount
PREORDER.TRAVERSAL(nodeptr.left)
PREORDER.TRAVERSAL(nodeptr.right)
endif
end

Dimana paralelnya ?
Operasi dasarnya adalah pelabelan pada node. Label pada verteks sub pohon kanan tidak dapat diberikan sampai diketahui berapa banyak verteks yang ada di sub pohon kirinya, begitu sebaliknya.

Pelaksanaan penelusuran dari depan (preorder traversal), dikerjakan secara sistematis melalui semua edge pohon. Setiap edge selalu 2 (dua) kali melewati verteks, yang turun dari parent ke child dan kebalikkannya.

Penelusuran pohon berorientasi edge ini merupakan algoritma paralel yang cepat. (Tarjan & Vishkin, 1984).

CONTOH (lihat gambar 2.13)
Algoritma ini mempunyai 4 (empat) fase :
1. Algoritma membentuk singly-linked list. Setiap verteksnya mempunyai penelusuran edge turun maupun naik dari pohon
2. Memberikan bobot ke verteks-verteksnya,
penelusuran naik (upward) : 0
penelusuran turun (downward) : 1
3. Setiap elemen singly-linked list menghitung rank-nya dari list secara paralel
4. Prosesor yang diasosiasikan dengan edge yang turun menggunakan rank yang sudah dihitung sebagai nomor dari penelusuran preorder.

Gambar 2.13 Penelusuran dari depan (preorder traversal)
dari akar pohon

(a) pohon
(b) edge-edge pohon, yang turun dan yang naik
(c) membuat linked list berdasarkan edge berarah pohon.
edge turun berbobot 1; edge naik berbobot 0
(d) jumping pointer digunakan untuk menghitung total bobot setiap verteks dari akhir list. Elemen-elemen (E, G), (E, H), (A, C) merupakan edge turun. Prosesor mengatur elemen untuk nilai preorder-nya. Misalnya elemen (E,G) berbobot 4 yang artinya node pohon G merupakan node ke-4 dari akhir preorder traversal list. Pohon memiliki 8 node sehingga node pohon G berlabel 5 pada preorder traversal
(e) nilai-nilai penelusuran dari depan.

Implementasi dari algoritma paralel preorder traversal menggunakan struktur data yang tidak biasa untuk merepresentasikan pohon.
Gambar 2.14 Pohon berakar yang direpresentasikan dengan
struktur data

Parent : akar dari node yang ada di atasnya
Sibling : node yang merupakan tetangga sebelah kanan dari parent yang sama
Child : node paling kiri

PSEUDOCODE
PREORDER.TREE.TRAVERSAL (CREW PRAM):
Global n {Number of vertices in tree}
parent[1 … n] {Vertex number of parent node}
child[1 … n] {Vertex number of firts child}
sibling[1 … n] {Vertex number of edge}
succ[1 … (n -1)] {Index of successor edge}
position[1 … (n -1)] {Edge rank}
preorder[1 … n] {Preorder traversal number}
begin
spawn (set of all P(i,j) where (i,j) is an edge)
for all P(i,j) where (i,j) is an edge do
{Put the edges into a linked list}
if parent[i] = j then
if sibling[i]  null then
succ[(i,j)]  (j, sibling[i])
else if parent[j]  null then
succ[(i,j)]  (j, parent[j])
else
succ[(i,j)]  (i,j)
preorder[j]  1 {j is root of tree}
endif
else
if child[j]  null then succ[(i,j)]  (j, child[j])
else succ[(i,j)]  (j,i)
endif
endif
{Number of edges of the successor list}
if parent[i] = j then position[(i,j)]  0
else position[(i,j)]  1
endif
{Perform suffix sum on successor list}
for k  1 to log(2(n – 1)) do
position[(i,j)]  position[(i,j)] + position[succ(i,j)]
succ[(i,j)]  succ[succ[(i,j)]]
endfor
{Assign preorder values}
if i = parent[j] then preorder[j]  n + 1 – position[(i,j)]
endif
endfor
end
Gambar 2.15 Algoritma PRAM untuk label node pohon
berdasarkan posisi secara preorder traversal

GAMBARAN PSEUDOCODE
Sebuah pohon dengan n buah node memiliki n-1 buah edge. Karena setiap edge dibagi ke dalam edge yang “naik” dan “turun”, algoritma membutuhkan 2(n-1) prosesor untuk memanipulasi 2(n-1) elemen dari singly-linked list ke penelusuran edge-nya.
Pada saat prosesor diaktifkan, linked list dibentuk yang berisi elemen-elemen edge dari preorder traversal. Dengan edge (i, j), setiap prosesor harus menghitung successor (pengikut) dari edge dalam traversal.
Jika parent[i] = j maka edge bergerak naik pada pohon, dari node child ke node parent.
Edge-edge yang “naik” mempunyai 3 jenis successor :
 jika child memiliki sibling, maka egde successor berasal dari node parent ke node sibling,
 jika child memiliki grandparent, maka edge successor berasal dari node parent ke grandparent-nya,
 jika kedua kondisi di atas tidak ada, maka edge merupakan akhir dari preorder traversal.
Akar pohon diidentitaskan dan nomor preordernya adalah 1.
Jika parent[I] j, yaitu jika edge bergerak turun dari node parent ke salah satu child-nya, maka ada 2 macam edge successornya :
 jika node child memiliki node keturunan, edge successor berasal dari node child ke node grandchild
 jika node child merupakan daun, edge successor berasal dari node child itu sendiri ke parent-nya.
Nilai posisi akhir menunjukkan nomor node preorder traversal antara elemen list dan akhir list. Untuk menghitung setiap label dari node, setiap prosesor yang diasosiasikan dengan edge “turun” dikurangkan nilai position dari n+1. Penambahan 1 menyebabkan penomoran preorder traversal dimulai dari 1.

KOMPLEKSITAS
Carilah, berapa kompleksitas algoritma seluruhnya ?
Merging Two Sorted Lists
DEFINISI
Algoritma yang optimal adalah penggabungan daftar (list) untuk satu elemen setiap waktu. Untuk menggabungkan dua list secara terurut membutuhkan paling banyak n-1 perbandingan dari n/2 elemen. Waktu kompleksitasnya (n). (Secara sekuensial)

Dengan menggunakan algoritma PRAM, proses penggabungan dapat dicapai dalam waktu (n log n) yaitu setiap elemen list dialokasikan ke prosesornya sendiri. Setiap prosesor menemukan posisi elemen-elemen pada list yang lain dengan pencarian biner (binary search).

Karena setiap indeks elemen pada list diketahui, tempat pada gabungan list dapat dihitung saat indeks pada list lainnya diketahui dan du indeks ditambahkan. Semua n elemen dapat dimasukkan ke gabungan list dengan prosesornya sendiri-sendiri dalam waktu konstan.

CONTOH
Gambar 2.16 Dua list dengan n/2 elemen digabungkan
dalam waktu (log n)

PSEUDOCODE
MERGE.LISTS (CREW PRAM):
Given : Two sorted lists of n/2 elements each stored in
A[1] … A[n/2] and A[(n/2)+1] … A[n]
The two lists and their unions have disjoint values
Final condition : Merged list in locations A[1] … A[n]
Global A[1 … n]
Local x, low, high, index
begin
spawn(P1, P2, …, Pn)
for all Pi where 1  i  n do
{Each processor sets bounds for binary search}
if i  n/2 then
low  (n/2) + 1
high  n
else
low  1
high  n/2
endif
{Each processor performs binary search}
x  A[i]
repeat
index  (low + high)/2
if x high
{Put value in correct position on merged list}
A[high + i – n/2]  x
endfor
end
Gambar 2.17 Algoritma PRAM menggabungkan
dua list secara terurut.

GAMBARAN PSEUDOCODE
Prosesor yang dibutuhkan ada n buah, satu untuk setiap elemen dari dua list yang digabungkan. Secara paralel, prosesor ini menentukan indeks yang akan dicari. Prosesor yang diasosiasikan dengan elemen dari ½ array bagian bawah akan melakukan pencarian biner pada elemen dari ½ array bagian atas, begitupula sebaliknya.

Prosesor Pi diasosiasikan dengan array A[i] bagian bawah dari list. Nilai akhir prosesor “high” harus berada antara n/2 dan n. Elemen A[i] > i-1 elemen pada bagian bawah list.
Juga A[i] > high – (n/2) untuk elemen bagian atas list.
Sehingga A[i] diletakkan pada gabungan list setelah i + high – n/2 – 1 elemen lainnya, pada indeks i + high – n/2.

Begitu pula dengan array bagian atas list. Prosesor Pi diasosiasikan dengan array A[i] bagian atas dari list. Nilai akhir prosesor “high” harus berada antara 0 dan n/2. Elemen A[i] > i – (n/2 +1) elemen lainnya pada bagian atas list.
Juga A[i] > elemen high untuk bagian bawah list.
Sehingga A[i] diletakkan pada gabungan list setelah i + high – n/2 – 1 elemen lainnya, pada indeks i + high – n/2.

Karena semua prosesor menggunakan ekspresi yang sama untuk menempatkan elemen-elemennya, setiap prosesor merelokasi elemen-elemennya menggunakan instruksi yang sama di akhir algoritma.

KOMPLEKSITAS
Secara sekuensial : (n)
Secara paralel : (n log n)
Untuk membangun algoritma pada komputer paralel sebenarnya, “cost” algoritma paralel harus diperhitungkan.

Graph Coloring
DEFINISI
Pewarnaan graf merupakan graf dimana verteks-verteks dapat diwarnai dengan c warna sehingga tidak ada dua verteks yang berdekatan (bertetangga/ ajasensi) memiliki warna yang sama.

CONTOH
Diasumsikan graf dengan n buah verteks. Diberikan matriks ajasensi (bertetangga) mxn dan konstanta positif c, sebuah prosesor dibuat untuk setiap pewarnaan graf yang mungkin.
Prosesor P(i0, i1, i2, …, in-1) mengilustrasikan pewarnaan verteks 0 dengan warna i0, verteks 1 dengan warna i1 hingga verteks n-1 dengan warna in-1.

Gambar 2.18 Contoh algoritma pewarnaan graf CREW PRAM
Algoritma mendapatkan 2 warna untuk 3 buah verteks

PSEUDOCODE
GRAPH.COLORING (CREW PRAM):
Global n {Number of vertices}
c {Number of colors}
A[1…n][1…n] {Adjacency matrix}
candidate[1…c][1…c] … [1…c] {n-dimensional
boolean matrix}
valid {Number of valid colorings}
j, k
begin
spawn(P(i0, i1, i2, …, in-1)) where 0  iv < c for 0  v < n
for all P(i0, i1, i2, …, in-1) where 0  iv < c for 0  v 0 then print “Valid coloring exists”
else print “Valid coloring does not exist”
endif
end
Gambar 2.19 Algoritma CREW PRAM untuk menunjukkan
jika graf dengan n verteks diwarnai dengan c warna

GAMBARAN PSEUDOCODE
Setiap prosesor memulai nilainya pada array “candidate” berdimensi-n dengan 1. Waktu yang dipakai (n2) untuk mewarnai verteks yang diwakili 2 verteks yang berajasensi diberikan warna yang sama.
Jika A[j,k] = 1 dan ij = ik maka pewarnaan salah karena A[j,k] = 1 berarti verteks j dan k bertetangga (ajasensi) dan ij = ik berarti verteks j dan k berwarna sama. Jika hal ini terjadi, array “candidate” di-set 0.
Setelah n2 perbandingan, jika elemen lainnya pada array “candidate” masih 1, pewarnaan benar.
Dengan menjumlah semua elemen cn pada array “candidate”, dapat digambarkan bahwa pewarnaan benar (valid).

KOMPLEKSITAS
Rutin spawn : (log cn),
Perulangan loop for ganda : (n2),
Menjumlah semua elemen cn : (log cn)

Waktu kompleksitas keseluruhan :
(log cn + n2) = (n2 + n log c)
Karena c < n,
kompleksitas berkurang menjadi (n2).

PENGOLAHAN PARALEL

ALGORITMA SORTING

Sorting memeiliki kepentingan tambahan bagi perancang algoritma paralel; ia sering digunakan untuk melakukan permutasi data umum pada komputer dengan memori terdistribusi. Operasi pemidahan data ini dpt digunakan untuk menyelesaikan masalah pada:
• teori graf
• geometri komputasional
• image processing
dalam waktu optimal atau hampir optimal.

Algoritma yang akan dipelajari berikut merupakan internal sort – yaitu, tabel yang di-sort cukup kecil untuk masuk seluruhnya di memori primer. Semua algoritma berikut ini juga men-sort dengan membandingkan sepasang elemen.

ENUMERATION SORT

Asumsi:
• Tabel dengan n elemen: a0, a1, …, an-1
• Untuk 2 elemen ai dan aj, salah satu kondisi ini pasti benar: ai aj.
• Tujuan sorting: menemukan permutasi (0, 1, …, n-1) sedemikian sehingga a0  a1  …  an-1.

Enumeration sort:
• menghitung posisi akhir setiap elemen pada list yang di-sort dan membandingkannya dengan elemen lain dan menghitung jumlah elemen yang memiliki nilai lebih kecil.
• Jika j elemen memiliki nilai lebih kecil dari ai, maka j=i; yaitu, elemen ai adalah (j + 1) elemen pada list yang di-sort setelah a0, …, aj-1.
• Jika diberikan n2 prosesor, model CRCW PRAM dapat menghitung setiap pasang elemen dan menghitung posisi list setiap elemen dalam waktu konstan. Begitu mesin telah menghitung posisi setiap elemen, diperlukan satu langkah lagi untuk memindahkan elemen ybs ke lokasi yang telah urut.

ENUMERATION SORT (SPECIAL CRCW PRAM):

Parameter n {number of elements}
Global a[0…(n-1)] {elements to be sorted}
position[0…(n-1)] {sorted positions}
sorted[0…(n-1)] {Contains sorted
elements}
begin
spawn(Pi,j, for all 0  i, j < n)

for all Pi,j, where 0  i, j < n do
position[i]  0
if a[i] < a[j] or (a[i] = a[j] and i < j) then
position[i]  1
endif
endfor
for all Pi,0, where 0  i < n do
sorted[position[i]]  a[i]
endfor
end

Satu set n elemen dapat di-sort dalam waktu (log n) dengan n2 prosesor, jika dipakai model PRAM CRCW dengan write simultan ke lokasi memori yang sama menyebabkan jumlah nilai di-assign. Jika waktu yang diperlukan untuk spawn prosesor tidak dihitung, algoritma berjalan dengan waktu konstan.

BATAS BAWAH UNTUK PARALLEL SORTING

Teorema 1:
Anggap ada n elemen yang akan di-sort pada array prosesor yang disusun menjadi mesh satu dimensi. Juga asumsikan bahwa sebelum dan sesudah sort, elemen akan didistribusikan merata, satu elemen per prosesor. Dengan demikian, batas bawah kompleksitas waktu pada algoritma sorting yang mana pun adalah (n).

Bukti:
Lebar biseksi dari jaringan mesh satu dimensi adalah 1. Misalkan posisi yang ter-sort dari semua elemen yang pada awalnya ada pada satu sisi biseksi adalah pada sisi biseksi yang lain, dan sebaliknya. Maka seluruh n elemen harus melewati satu link untuk mencapai sisi yang lain. Karena link hanya dapat membawa satu elemen sekali, jumlah langkah yang diperlukan untuk menukar elemen melalui biseksi paling tidak adalah sebesar n. Dengan demikian, batas bawah kompleksitas jaringan mesh satu dimensi dengan syarat-syarat tersebut adalah (n).

Teorema 2:
Anggap ada n elemen yang akan di-sort pada array prosesor yang tersusun sebagai mesh dua dimensi. Juga anggap bahwa sebelum dan sesudah sort, elemen-elemen tsb terdistribusi merata, satu elemen per prosesor. Maka, batas bawah kompleksitas waktu untuk algoritma sorting yang mana pun adalah (n).

Bukti:
Lebar biseksi jaringan mesh dua dimensi dengan n node adalah lebih kecil atau sama dengan n. Misalkan posisi ter-sort dari semua elemen yang pada awalnya ada pada satu sisi biseksi adalah di sisi lain biseksi tsb, dan sebaliknya. Maka seluruh n elemen harus melalui salah satu dari tidak lebih n link untuk mencapai sisi lainnya. Karena satu link hanya dapat membawa satu elemen sekali, jumlah langkah yang diperlukan untuk menukar elemen melintasi biseksi paling tidak adalah n/n. Dengan demikian, batas bawah kompleksitas array prosesor bagaimanapun yang disusun sebagai mesh dua dimensi dan berjalan dengan ketentuan yang telah diberikan di atas adalah (n/n) = (n)

Teorema 3:
Anggap ada n = 2k elemen yang akan di-sort pada array prosesor yang tersusun sebagai jaringan shuffle-exchange. Juga anggap bahwa sebelum dan sesudah sort, elemen terdistribusi merata, satu elemen per prosesor. Batas bawah untuk algoritma sort mana pun adalah (log n).

Bukti:
Misalkan posisi ter-sort elemen yang pada awalnya berada pada node 0 adalah node n-1. Pemindahan elemen tsb dari node 0 ke node n-1 menuntut paling tidak log n operasi pertukaran dan paling tidak log n-1 operasi shuffle. Dengan alasan ini, batas bawah pada algoritma sorting berbassis shuffle-exchange dengan batas-batas di atas adalah (log n).

ODD-EVEN TRANSPOSITION SORT

Odd-even transposition sort dirancang untuk model array prosesor dengan elemen-elemen processing yang disusun menjadi mesh satu dimensi.

Anggap A = (a0, a1, …, an-1) adalah himpunan n elemen yang akan di-sort. Setiap n elemen processing berisi dua variabel lokal: a, elemen unik dari array A, dan t, variabel yang berisi nilai yang diambil dari elemen processing tetangganya.

Algoritma melakukan n/2 iterasi, dan setiap iterasi memiliki dua fase:
1. odd-even exchange: nilai a pada setiap prosesor bernomer ganjil (kecuali prosesor n-1) dibandingkan dengan nilai a yang tersimpan di prosesor berikutnya. Nlai-nilai ditukar, jika perlu, sehingga prosesor dengan nomer lebih kecil berisi nilai yang lebih kecil.
2. even-odd exchange: nilai a pada setiap prosesor bernomer genap dibandingkan dengan nilai a yang tersimpan di prosesor berikutnya. Nlai-nilai ditukar, jika perlu, sehingga prosesor dengan nomer lebih kecil berisi nilai yang lebih kecil.

Setelah n/2 iterasi, nilai-nilai harus ter-sort.

ODD-EVEN TRANSPOSITION SORT (ONE-DIMENSIONAL MESH PROCESSOR ARRAY):

Parameter n
Global i
Local a {element to be sorted}
t {element taken from adjacent processor}
begin
for i  1 to n/2 do
for all Pj, where 0  j  n-1 do
if j < n-1 and odd(j) then
{Odd-even exchange}
t  successor(a) {Get value from successor}
successor(a)max(a,t) {Give away larger val} a  min(a,t) {Keep smaller value}
endif

if even(j) then
{Even-odd exchange}
t  successor(a) {Get value from successor}
successor(a)max(a,t) {Give away larger val} a  min(a,t) {Keep smaller value}
endif
endfor
endfor
end

Odd-even transposition sort dari delapan nilai pada model array prosesor mesh satu dimensi:

Indeks: 0 1 2 3 4 5 6 7
Nilai awal: G H F D E C B A
Setelah odd-even exchange: G F <H D <E B <C A
Setelah even-odd exchange: F <G D <H B <E A <C
Setelah odd-even exchange: F D <G B <H A <E C
Setelah even-odd exchange: D <F B <G A <H C <E
Setelah odd-even exchange: D B <F A <G C <H E
Setelah even-odd exchange: B <D A <F C <G E <H
Setelah odd-even exchange: B A <D C <F E <G H
Setelah even-odd exchange: A <B C <D E <F G 1 (lihat gambar keempat)
Dengan demikian t(2n) = 1 + log n, jauh lebih lebih cepat dari O(n), yang merupakan waktu terbaik pada komputer sekuensial.

2. Jumlah prosesor
p(2n) menyatakan jumlah comparator pada (n, n)-merging network.
p(2) = 1 untuk n=1 (lihat gambar pertama)
p(2n) = 2p(n) + (n-1), untuk n>1
(lihat gambar keempat)
Dengan demikian p(2n) = 1 + n log n.

3. Biaya
t(2n) = 1 + log n dan p(2n) = 1 + n log n.
Total perbandingan yang dilakukan oleh (n, n)-merging network, yaitu, yang merupakan biaya jaringan, adalah:
c(2n) = p(2n) x t(2n)
= O(n log2 n)
Jaringan ini tidak optimal dalam hal biaya karena melakukan lebih banyak operasi dari O(n) yang dibutuhkan untuk merge sekuensial.

Pembahasan:
Properti merging network ini: Deret perbandingan telah ditentukan sebelumnya.
Analisis di atas menunjukkan bahwa (n, n)-merging network sangat cepat. Dua deret dengan masing-masing 220 elemen dapat di-merge dalam 21 langkah. Hal yang sama memerlukan lebih dari dua juta langkah pada komputer sekuensial.
Namun, kecepatan tsb didapat dengan prosesor yang sangat banyak. Untuk n = 220, (n, n)-merging network terdiri dari lebih dari dua puluh juta comparator.
Arsitektur jaringan sangat ireguler, penghubung comparator memiliki panjang yang bervariasi dengan n.
 Walaupun secara teoritis bagus, merging network tidak praktis jika n bernilai besar.

MERGING PADA MODEL CREW (Concurrent Read, Exclusive Write)

Merging Sekuensial

Dua deret bilangan
A = {a1, a2, …, ar}
B = {b1, b2, …, bs}
dengan urutan naik di-merge membentuk deret C yang juga urut naik.
• Merging dilakukan oleh satu prosesor.
• Digunakan dua pointer, 1 untuk setiap deret.
• Dibuat dua elemen fiktif ar+1 dan bs+1 yang bernilai tak hingga.

procedure SEQUENTIAL MERGE (A, B, C)
Step 1: (1.1) i  1
(1.2) j  1

Step 2: for k = 1 to r + s do
if ai < bj then (i) ck  ai
(ii) i  i+1
else (i) ck  bj
(ii) j  j+1
end if
end for

• Jumlah perbandingan: r + s
• Worst case: r = s = n, algoritma berjalan dalam waktu O(n).
• Procedure ini optimal.

Merging Paralel

• Dikerjakan oleh komputer CREW SM SIMD (Concurrent Read, Exclusive Write; Shared Memory; Single Instruction stream, Multiple Data stream).
• r  s
• Digunakan N prosesor: P1, P2, , PN.
• N  r
• Worst case: r = s = n; waktu O((n/N) + log n)
• Optimal biaya untuk N  n / log n.

Setiap prosesor dianggap mampu melakukan dua prosedur sekuensial berikut:
1. Prosedur SEQUENTIAL MERGE
2. Prosedur BINARY SEARCH:
• Mengambil deret input S = {s1, s2, …, sn} bilangan yg terurut naik dan suatu bilangan x.
• Jika x ada di S, prosedur mengembalikan indeks k dari elemen sk pd S sedemikian shg x = sk.
• Jika tidak, prosedur memberi nilai nol.
• Pd setiap tahap, dilakukan perbandingan antara x dan elemen S.
• Jika keduanya sama, prosedur berhenti atau setengah elemen pada deret diabaikan.
• proses diteruskan sampai jumlah elemen yg tertinggal adalah 0 atau 1.

procedure BINARY SEARCH (S, x, k)

Step 1: (1.1) I  1
(1.2) h  n
(1.3) k  0

Step 2: while i  h do
(2.1) m  (i + h)/2
(2.2) if x = sm then (i) k  m
(ii) i  h + 1
else if x < sm then h  m-1
else i  m + 1
end if
end if
end while

procedure CREW MERGE (A, B, C)

Step 1: {Pilih N – 1 elemen A yg membagi deret menjadi N subsequence dgn ukuran yg kurang lebih sama. Namai subsequence yg dibentuk oleh N-1 elemen ini A’. Subsequence B’ dari N-1 elemen B juga dipilih dgn cara yg sama. Step ini dilakukan sbb:}
for i = 1 to N-1 do in parallel
Processor Pi menentukan ai’ dan bi’ dari
(1.1) ai’  ai[r/N]
(1.2) bi’  ai[s/N]
end for

Step 2: {Merge A’ dan B’ menjadi deret triple V = {v1, v2, …, v2N-2}, di mana setiap triple terdiri dari elemen A’ atau B’ diikuti posisinya pada A’ atau B’ diikuti oleh nama deret asalnya, yaitu, A atau B. Hal ini dilakukan sbb:}

(2.1) for i = 1 to N-1 do in parallel
(i) Prosesor Pi memakai BINARY SEARCH pd B’ untuk menemukan j terkecil sedemikian sehingga ai’ < bj’.
(ii) if j exists then vi+j-1  (ai’, i, A)
else vi+N-1  (ai’, i, A)
end if
end for
(2.2) for i = 1 to N-1 do in parallel
(i) Prosesor Pi memakai BINARY SEARCH pada A’ untuk menemukan j terkecil sehingga bi’ < aj’
(ii) if j exist then vi+j-1  (bi’, i, B)
else vi+N-1  (bi’, i, B)
end if
end for

Step 3: {Setiap prosesor merge dan menyisipkan ke dalam C, elemen-elemen dari kedua subsequence, satu dari A dan satu dari B. Indeks kedua elemen (satu di A dan satu di B) di mana setiap prosesor mulai merging, terlebih dulu dihitung dan disimpan pada array Q yg menyimpan pasangan terurut. Langkah ini dilakukan sbb:}
(3.1) Q(1)  (1, 1)
(3.2) for i = 2 to N do in parallel
if v2i-2 = (ak’, k, A) then processor Pi
(i) memakai BINARY SEARCH atas B untuk menemukan j terkecil sedemikian shg bj < ak’.
(ii) Q(i)  (kr/N, j)
else prosesor Pi
(i) memakai BINARY SEARCH atas A untuk menemukan j terkecil sedemikian shg aj < bk’.
(ii) Q(i)  (j, kr/N)
end if
end for
(3.3) for i = 1 to N do in parallel
Prosesor Pi memakai SEQUENTIAL MERGE dan Q(i) = (x, y) untuk merge dua subsequence, satu mulai pd ax dan yg lain pd by dan menempatkan hasil merge pd array C mulai pd posisi x + y – 1. Merge diteruskan sampai
(i) elemen yg lebih besar atau sama dgn komponen pertama dari v2i ditemukan masing-masing pd A dan B (ketika i  N-1)
(ii) tidak ada elemen yg tersisa pd A atau B (ketika i = N)
end for.

Ada dua hasil observasi dari algoritma di atas:
• Jika ai dibandingkan dgn bj dan ai = bj, maka algoritma memutuskan bhw ai lebih kecil.
• Operasi consurrent read dilakukan ketika prosedur BINARY SEARCH dipanggil, yaitu pd step 2.1, 2.2, dan 3.2. Di sini, beberapa prosesor mengeksekusi binary search pd deret yg sama.

Analisis

Step 1: Dgn semua prosesor bekerja paralel, setiap prosesor menghitung dua subscript. Dgn demikian langkah ini memerlukan waktu konstan.
Step 2: Langkah ini terdiri dari dua aplikasi prosedur BINARY SEARCH pada deret dgn panjang N-1, masing-masing diikuti oleh statement assignment. Ini memerlukan waktu O(log N).
Step 3: Step 3.1 terdiri dari assignment waktu konstan, dan step 3.2 membutuhkan paling banyak waktu O(log s). Untuk menganalisa step 3.3, pertama kita meneliti bahwa V terdiri dari 2N-2 elemen yg membagi C menjadi 2N-1 subsequence dgn ukuran maksimum sama dgn (r/N + s/N). Ukuran maksimum ini terjadi jika, misalnya, satu elemen ai’ dari A’ sama dgn elemen bj’ dari B’; maka r/N elemen yg lebih kecil atau sama dgn ai’ (dan lebih besar atau sama dgn a’i-1) juga lebih kecil atau sama dgn bj’, dan dgn cara yg sama, s/N elemen yg lebih kecil atau sama dgn bj’ (dan lebih besar atau sama dgn b’i-1) juga lebih kecil atau sama dgn ai’. Pd step 3 setiap prosesor membentuk dua subsequence spt ini dari C yg ukuran totalnya tidak lebih besar dari 2(r/N + s/N), kecuali PN, yg hanya membuat satu subsequence C. berarti prosedur SEQUENTIAL MERGE paling banyak memerlukan waktu O((r + s)/N).
Worst case, r = s = n, dan karena n  N, waktu jalan algoritma didominasi oleh waktu yg dibutuhkan oleh step 3. Dgn demikian
t(2n) = O((n/N) + log n)
Karena p(2n) = N, c(2n) = p(2n) x t(2n) = O(n + N log n), dan algoritma optimal biaya ketika N  n/log n.

PENGOLAHAN PARALEL

SEARCHING

Dalam bentuknya yang paling dasar, masalah searching dinyatakan sbb.:
Jika ada satu deret S = {s1, s2, …, sn} yg terdiri dari integer dan ada integer x, diminta untuk menentukan apakah x = sk untuk sk yg ada di S.

procedure SEQUENTIAL SEARCH (S, x, k)
Step 1: (1.1) i  1
(1.2) k  0

Step 2: while (i  n and k = 0) do
if si = x then k  i end if
i  i+1
end while

Worst case: waktu = O(n)

SEARCHING DERET TERURUT
S = {s1, s2, …, sn} terurut naik, yaitu, s1  s2  …  sn.
Yang di-search adalah file dgn n record dan terurut berdasar field s.

si INFORMASI LAIN

EREW (Exclusive Read Exclusive Write) SEARCHING

• Tersedia N-prosesor komputer EREW SM SIMD untuk search S untuk elemen x, dgn 1 < N  n.
• Nilai x harus diketahui semua prosesor. Dipakai prosedur BROADCAST dlm waktu O(log N).
• Deret S dibagi menjadi N subsequence, masing-masing dgn panjang n/N.
• Semua prosesor melakukan prosedur BINARY SEARCH yg membutuhkan waktu O(log(n/N)) worst case.
• Elemen S dianggap berbeda semua, shg paling banyak satu prosesor menemukan sk sama dgn x dan mengembalikan k.
• Waktu total: O(log N) + O(log(n/N)) = O(log n)  sama dengan BINARY SEARCH yg berjalan pd satu prosesor, dgn demikian tdk ada penambahan kecepatan.

CREW (Concurrent Read Exclusive Write) SEARCHING

• Tersedia N-prosesor komputer CREW SM SIMD untuk search S untuk elemen x, dgn 1 < N  n.
• Algoritma sama dgn EREW, kecuali semua prosesor membaca x bersamaan dlm waktu konstan dan kemudian melakukan prosedur BINARY SEARCH pd subsequence masing-masing.
• Waktu: O(log(n/N)) worst case  lebih cepat dari BINARY SEARCH yg berjalan pd satu prosesor.

SEARCHING DERET ACAK

Deret S = {s1, s2, …, sn} tdk urut dan belum tentu memiliki elemen yg berbeda semua.
Search spt ini dinamakan juga query.
Search juga berguna untuk maintenance file, misalnya menyisipkan (insert) record baru dan men-delete record yg ada.

Searching pd komputer SM SIMD
Tersedia N-prosesor komputer untuk search S untuk elemen x, dgn 1 0 then k  ki end if
end for.

Analisis:

EREW:
• Step 1 diimpelemntasi dgn menggunakan prosedur BROADCAST danmemerlukan waktu O(log N).
• Step 2: prosedur SEQUENTIAL SEARCH memerlukan O(n/N) worst case.
• Step 3: prosedur STORE berjalan dlm waktu O(log N).
• Running time asimptotik total:
t(n) = O(log N) + O(n/N),
dan biaya sebesar:
c(n) = O(N log N) + O(n)
yg tdk optimal.

ERCW:
Step 1 dan 2 sama dgn kasus EREW, sementara step 3 membutuhkan waktu konstan. Running time asimptotik total tetap tdk berubah.

CREW:
Step 1 sekarang membutuhkan waktu konstan, sementara step 2 dan 3 sama dgn kasus EREW. Running time asimptotik total tetap tdk berubah.

CRCW:
Kedua langkah 1 dan 3 membutuhkan waktu konstan, sementara step 3 sama dgn kasus EREW. Running time total sekarang sebesar O(n/N), dan biaya sebesar:
c(n) = N x O(n/N) = O(n)
yg optimal.

PENGOLAHAN PARALEL

SEARCHING

Dalam bentuknya yang paling dasar, masalah searching dinyatakan sbb.:
Jika ada satu deret S = {s1, s2, …, sn} yg terdiri dari integer dan ada integer x, diminta untuk menentukan apakah x = sk untuk sk yg ada di S.

procedure SEQUENTIAL SEARCH (S, x, k)
Step 1: (1.1) i  1
(1.2) k  0

Step 2: while (i  n and k = 0) do
if si = x then k  i end if
i  i+1
end while

Worst case: waktu = O(n)

SEARCHING DERET TERURUT
S = {s1, s2, …, sn} terurut naik, yaitu, s1  s2  …  sn.
Yang di-search adalah file dgn n record dan terurut berdasar field s.

si INFORMASI LAIN

EREW (Exclusive Read Exclusive Write) SEARCHING

• Tersedia N-prosesor komputer EREW SM SIMD untuk search S untuk elemen x, dgn 1 < N  n.
• Nilai x harus diketahui semua prosesor. Dipakai prosedur BROADCAST dlm waktu O(log N).
• Deret S dibagi menjadi N subsequence, masing-masing dgn panjang n/N.
• Semua prosesor melakukan prosedur BINARY SEARCH yg membutuhkan waktu O(log(n/N)) worst case.
• Elemen S dianggap berbeda semua, shg paling banyak satu prosesor menemukan sk sama dgn x dan mengembalikan k.
• Waktu total: O(log N) + O(log(n/N)) = O(log n)  sama dengan BINARY SEARCH yg berjalan pd satu prosesor, dgn demikian tdk ada penambahan kecepatan.

CREW (Concurrent Read Exclusive Write) SEARCHING

• Tersedia N-prosesor komputer CREW SM SIMD untuk search S untuk elemen x, dgn 1 < N  n.
• Algoritma sama dgn EREW, kecuali semua prosesor membaca x bersamaan dlm waktu konstan dan kemudian melakukan prosedur BINARY SEARCH pd subsequence masing-masing.
• Waktu: O(log(n/N)) worst case  lebih cepat dari BINARY SEARCH yg berjalan pd satu prosesor.

SEARCHING DERET ACAK

Deret S = {s1, s2, …, sn} tdk urut dan belum tentu memiliki elemen yg berbeda semua.
Search spt ini dinamakan juga query.
Search juga berguna untuk maintenance file, misalnya menyisipkan (insert) record baru dan men-delete record yg ada.

Searching pd komputer SM SIMD
Tersedia N-prosesor komputer untuk search S untuk elemen x, dgn 1 0 then k  ki end if
end for.

Analisis:

EREW:
• Step 1 diimpelemntasi dgn menggunakan prosedur BROADCAST danmemerlukan waktu O(log N).
• Step 2: prosedur SEQUENTIAL SEARCH memerlukan O(n/N) worst case.
• Step 3: prosedur STORE berjalan dlm waktu O(log N).
• Running time asimptotik total:
t(n) = O(log N) + O(n/N),
dan biaya sebesar:
c(n) = O(N log N) + O(n)
yg tdk optimal.

ERCW:
Step 1 dan 2 sama dgn kasus EREW, sementara step 3 membutuhkan waktu konstan. Running time asimptotik total tetap tdk berubah.

CREW:
Step 1 sekarang membutuhkan waktu konstan, sementara step 2 dan 3 sama dgn kasus EREW. Running time asimptotik total tetap tdk berubah.

CRCW:
Kedua langkah 1 dan 3 membutuhkan waktu konstan, sementara step 3 sama dgn kasus EREW. Running time total sekarang sebesar O(n/N), dan biaya sebesar:
c(n) = N x O(n/N) = O(n)
yg optimal.

PENGOLAHAN PARALEL

OPERASI MATRIKS

Topik yang akan dibahas
• transpose
• perkalian

TRANSPOSE

Definisi:
a11 a12 a13 a14
A = a21 a22 a23 a24
a31 a32 a33 a34
a41 a42 a43 a44

a11 a21 a31 a41
AT = a12 a22 a32 a42
a13 a23 a33 a43
a14 a24 a34 a44

Prosedur sekuensial:
procedure TRANSPOSE (A)
for i = 2 to n do
for j = 1 to i-1 do
aij  aji
end for
end for.

Waktu: O(n2); jumlah langkah: (n2)
MESH TRANSPOSE

a11 a12 a13 a14

a21 a22 a23 a24

a31 a32 a33 a34

a41 a42 a43 a44

Awalnya: prosesor P(i,j) menyimpan elemen data aij.
Pada akhir komputasi: P(i,j) menyimpan aji.

Ide algoritma:
• Elemen diagonal tetap stasioner.
• Elemen di bawah diagonal dipindah ke posisi simetris di atas diagonal (tanda panah biasa).
• Elemen di atas diagonal dipindah ke posisi simetris di bawah diagonal (tanda panah terputus-putus).
• Setiap prosesor P(i,j) memiliki tiga register:
1. A(i,j) digunakan untuk menyimpan aij pd awalnya dan aji ketika algoritma berakhir.
2. B(i,j) digunakan untuk menyimpan data yg diterima dari P(i, j+1) atau P(i-1, j), yaitu, dari tetangga di kanan atau atasnya.
3. C(i,j) digunakan untuk menyimpan data yg diterima dari P(i, j-1) atau P(i+1, j), yaitu, dari tetangga di kiri atau bawahnya.

procedure MESH TRANSPOSE (A)
Step 1: do steps 1.1 and 1.2 in parallel
(1.1) for i=2 to n do in parallel
for j=1 to i-1 do in parallel
C(i-1,j)  (aij, j, i)
end for
end for
(1.2) for i=1 to n-1 do in parallel
for j=i+1 to n do in parallel
B(i,j-1)  (aij, j, i)
end for
end for.

Step 2: do steps 2.1, 2.2, and 1.2 in parallel
(2.1) for i=2 to n do in parallel
for j=1 to i-1 do in parallel
while P(i,j) receives input form its neighbours do
(i) if (akm,m,k) is received from P(i+1, j)
then send it to P(i-1, j)
end if
(ii) if (akm,m,k) is received from P(i-1, j)
then if i=m and j=k
then A(i,j)  akm {destination reached)
else send (akm,m,k) to P(i+1, j)
end if
end if
end while
end for
end for
(2.2) for i=1 to n do in parallel
while P(i,i) receives input form its neighbours do
(i) if (akm,m,k) is received from P(i+1, i)
then send it to P(i, i+1)
end if
(ii) if (akm,m,k) is received from P(i, i+1)
then send it to P(i+1, i)
end if
end while
end for
(2.3) for i=1 to n-1 do in parallel
for j=i+1 to n do in parallel
while P(i,j) receives input form its neighbours do
(i) if (akm,m,k) is received from P(i, j+1)
then send it to P(i, j-1)
end if
(ii) if (akm,m,k) is received from P(i, j-1)
then if i=m and j=k
then A(i,j)  akm {destination reached)
else send (akm,m,k) to P(i, j+1)
end if
end if
end while
end for
end for.

Analisis:
• Setiap elemen aij, i>j, harus menelusuri kolomnya ke atas sampai mencapai P(j,j) dan kemudian berjalan sepanjang baris hingga sampai di P(j,i). Hal yg sama berlaku untuk aij, j>i.
• Jalur terpanjang adalah yg dijalani oleh an1 (atau a1n) yg terdiri dari 2(n-1) langkah.
• Running time prosedur MESH TRANSPOSE: t(n) = O(n)
• p(n) = n2
• Cost: O(n3)  tidak optimal

Contoh:
x 1 2
A = -4 y 3
-5 -6 z

A = x A = 1 A = 2
B = B = B =
C = C = C =

A = -4 A = y A = 3
B = B = B = Keadaan awal
C = C = C =

A = -5 A = -6 A = z
B = B = B =
C = C = C =

A = x A = 1 A = 2
B = 1 B = 2 B =
C = -4 C = C =

A = -4 A = y A = 3
B = B = 3 B = Step 1
C = -5 C = -6 C =

A = -5 A = -6 A = z
B = B = B =
C = C = C =

A = x A = -4 A = 2
B = 2 B = B =
C = -5 C = C =

A = 1 A = y A = -6
B = B = B = Iterasi pertama step 2
C = C = C =

A = -5 A = 3 A = z
B = B = B =
C = C = C =

A = x A = -4 A = 2
B = B = B =
C = C = -5 C =

A = 1 A = y A = -6
B = 2 B = B = Iterasi kedua step 2
C = C = C =

A = -5 A = 3 A = z
B = B = B =
C = C = C =

A = x A = -4 A = -5
B = B = B =
C = C = C =

A = 1 A = y A = -6
B = B = B = Iterasi ketiga step 2
C = C = C =

A = 2 A = 3 A = z
B = B = B =
C = C = C =

SHUFFLE TRANSPOSE

Pertimbangan:
Speedup MESH TRANSPOSE hanya linier, dianggap kecil karena jumlah prosesor kuadratik.
Geometri yg berbeda dpt men-transpose matriks dalam waktu logaritmik.
n = 2q; matrik A(n x n)
Digunakan interkoneksi perfect suffle dgn n2 prosesor: P0, P1, Pn-1.
aij disimpan pada awalnya tersimpan di prosesor Pk, dengan k = 2q(i-1) + (j-1).

P9 P10 P11 P12 P13 P14 P15

a11 a12 a13 a14 a21 a22 a23 a24 a31 a32 a33 a34 a41 a42 a43 a44

P0 P1 P2 P3 P4 P5 P6 P7 P8

Setelah q operasi shuffle, prosesor Pk berisi elemen aji.
Pk dihubungkan ke Pm; m didapat dengan menggeser bit k ke kiri siklis.

Indeks prosesor k terdiri dari 2q bit. q most significant bit merepresentasikan i-1, dan q least significant bit menyatakan j-1.
Setelah q shuffle (yaitu q pergeseran siklis ke kiri), elemen yang tadinya ada pada Pk akan berada di prosesor yang indeksnya adalah:
s = 2q(j-1) + (i-1)

procedure SHUFFLE TRANSPOSE (A)
for i=1 to q do
for k=1 to 22q-2 do in parallel
Pk sends the element of A it currently holds to P2kmod(22q-1)
end for
end for.

Analisis:
• Iterasi: q waktu konstan
• Waktu: t(n) = O(log n)
• p(n)= n2; c(n) = O(n2 log n)  tdk optimal
• Tetapi interkoneksi shuffle lebih cepat dari mesh.

Jalannya elemen:
a11: P0  P0  P0 a12: P1  P2  P4
a13: P2  P4  P8 a14: P3  P6  P12
a21: P4  P8  P1 a22: P5  P10  P5
a23: P6  P12  P9 a24: P7  P14  P13
a31: P8  P1  P2 a32: P9  P3  P6
a33: P10  P5  P10 a34: P11  P7  P14
a41: P12  P9  P3 a42: P13  P11  P7
a43: P14  P13  P11 a44: P15  P15  P15

EREW TRANSPOSE

 merupakan algoritma yang cost-optimal.
• Algoritma menggunakan (n2-n)/2 prosesor dan berjalan pada komputer EREW SM SIMD.
• Matriks A berada di shared memory.
• Setiap prosesor memiliki dua indeks i dan j, dengan 2in dan 1ji-1.
• Semua prosesor beroperasi paralel dan prosesor Pij menukar dua elemen A, yaitu aij dan aji.

procedure EREW TRANSPOSE (A)
for i=2 to n do in parallel
for j=1 to i-1 do in parallel
aij  aji
end for
end for.

Analisis:
• Running time: t(n) = O(1)
• p(n) = O(n2); c(n) = O(n2)  optimal

Contoh:

P21

1 2 3

4 5 6

7 8 9

P32

P31

PERKALIAN MATRIKS DENGAN MATRIKS

Definisi:
A(m x n) x B(n x k) = C(m x k)
n
cij =  ais x bsj, 1  i  m, I  j  k
s=1

Algoritma sekuensial:

procedure MATRIX MULTIPLICATION (A, B, C)
for i=1 to m do
for j=1 to k do
(1) cij  0
(2) for s=1 to n do
cij  cij + (ais x bsj)
end for
end for
end for.

Waktu: O(n3)

PERKALIAN MESH

Digunakan m x k prosesor untuk mengalikan A(m x n) dengan B(n x k).
1. Matriks A dan B dimasukkan ke boundary processor di kolom 1 dan baris 1, berturut-turut.
2. Baris i matriks A ketinggalan satu satuan waktu dari baris i-1 untuk 2  i  m.
3. Kolom j matriks B ketinggalan satu satuan waktu dari kolom j-1 untuk 2  j  k.
4. Langkah 2 dan 3 untuk menjamin bahwa ais bertemu dengan bsj pada prosesor P(i, j) pada waktu yang tepat.
5. Di akhir algoritma, elemen hasil perkalian, cij, berada di prosesor P(i, j).

Pada awalnya, cij sama dengan nol.
Ketika P(i, j) menerima dua input a dan b, prosesor:
(I) mengalikan keduanya,
(ii) menambahkan hasilnya ke cij,
(iii) mengirimkan a ke P(i, j+1) kecuali j = k, dan
(iv) mengirim b ke P(i+1, j) kecuali i=m.

b13
b12 b23
b11 b22 b33
b21 b32 b43
b31 b42 b53
b41 b52
b51

a11 a12 a13 a14 a15

P(1,1) P(1,2) P(1,3)

a21 a22 a23 a24 a25

P(2,1) P(2,2) P(2,3)

a31 a32 a33 a34 a35

P(3,1) P(3,2) P(3,3)

a41 a42 a43 a44 a45

P(4,1) P(4,2) P(4,3)

procedure MESH MATRIX MULTIPLICATION (A, B, C)
for i=1 to m do in parallel
for j=1 to k do in parallel
(1) cij  0
(2) while P(i, j) receives two inputs a and b do
(i) cij  cij + (a x b)
(ii) if i < m then send b to P(i+1, j)
end if
(iii) if j < k then send a to P(i, j+1)
end if
end while
end for
end for.

Analisis:
• Dengan menganggap m  n dan k  n, run time: t(n) = O(n).
• p(n) = O(n2), c(n) = O(n3)  sama dengan prosedur sekuensial.

PERKALIAN MATRIKS SHUFFLE-EXCHANGE

Jika tersedia n3 = 23q prosesor pada model SIMD shuffle-exchange, dua matriks n x n dapat dikalikan dalam waktu (log n).

BAB IX
PENYELESAIAN SISTEM LINIER

I. PENDAHULUAN
1.1. Topik-topik Yang Dibahas :
1. Substitusi mundur (back substitution)
2. Reduksi ganjil-genap (odd-even reduction) atau reduksi siklis (cyclic reduction)

1.2. Metoda Pembahasan
1. Algoritma sequensial
2. Potensi paralelisasi
3. Algoritma paralel
4. Speedup

1.3. Terminologi :

i. Bentuk umum sistem linier :
A x = b, A matriks n  n, x, b vektor n  1
ii. Elemen matriks A baris ke-i kolom ke-j : atau a[i, j]
Elemen vektor x baris ke- i : atau x[i]
Elemen vektor b baris ke- i : atau b[i]
iii. Matriks A adalah segitiga atas (upper triangular) jika : = 0  i  j
iv. Matriks A adalah segitiga bawah (lower triangular) jika : = 0  i  j
v. Matriks A adalah tridiagonal jika dan hanya jika :
= 0  i  j  1
vi. Matriks A adalah diagonal dominan (diagonally dominant) jika :
    1  i  n
vii. Matriks A adalah simetri (symmetric) jika :
=  1  i, j  n
viii. Matriks A adalah definit positif (positive definite) jika ia simetri, diagonal dominan, dan  0  1  i  n
ix. Berikut ini adalah contoh matriks-matriks di atas :

Matriks segitiga atas Matriks segitiga bawah

Matriks tridiagonal Matriks diagonal dominan

Matriks simetri Matriks definit positif
II. SUBSTITUSI MUNDUR
2.1. Algoritma Sequensial
Contoh 9.1
Selesaikan sistem persamaan berikut :
1 + 1  1 + 4 = 8
 2  1 + 1 = 5
2  3 = 0
2 = 4
Jawab :
Vektor x = [ ] diperoleh melalui prosedur berikut :
1. hitung : = 4/2 = 2
2. substitusikan nilai ke semua persamaan di atasnya, koreksi ruas kanannya persamaan; hasilnya adalah :
1 + 1  1 = 0
2  1 = 3
2 = 6
3. ulangi langkah (1) dan (2) berturut-turut untuk dan
4. ulangi langkah (1) untuk
Dengan cara ini maka diperoleh :
x = [ ] = [9 -6 3 2]

Sistem di atas dapat dituliskan sebagai A x = b, dimana :
A = = matriks segitiga atas, b =
Untuk sistem segitiga atas berukuran n prosedur di atas dapat digeneralisasi menjadi algoritma sekuensial berikut :

Algoritma 9.1. BACK.SUBSTITUTION (SISD) :
Global n {ukuran sistem}
a[1.. n][ 1.. n] {elemen-elemen matriks A}
b[1.. n] {elemen-elemen vektor b}
x[1.. n] {elemen-elemen vektor x}
i {indeks kolom}
j {indeks baris}
1. begin
2. for i  n downto 1 do
3. x[i]  b[i]/a[i][i]
4. for j  1 to i 1 do
5. b[j]  b[j]  x[i]  a[j][i]
6. a[j][i]  0 {statement ini bersifat opsional}
7. endfor
8. endfor
9. end
Algoritma 9.1. melakukan operasi pembagian, perkalian, dan pengurangan. Banyaknya operasi pembagian adalah n (baris 3) sedangkan banyaknya operasi pengurangan dan perkalian (baris 5) adalah :
(n 1) + (n 2) + … + 2 + 1 = ½ n(n 1) (9.1)
sehingga kompleksitas algoritma 9.1. adalah (n ).
Instruksi pada baris 6 bersifat opsional, di antaranya untuk menayangkan matriks pada setiap iterasi.

2.2. Potensi Paralelisasi
Proses substitusi nilai ke tiga persamaan di atasnya pada penyelesaian contoh 9.1 di atas dapat dilakukan secara serempak.

2.3. Algoritma Paralel
Berdasarkan potensi paralelisasi maka algoritma paralel dapat disusun sebagai berikut :
Algoritma 9.2. BACK.SUBSTITUTION (UMA
MULTIPROSESOR) :
Global n {ukuran sistem}
p {banyaknya proses}
a[1.. n][ 1.. n] {elemen-elemen matriks A}
b[1.. n] {elemen-elemen vektor b}
x[1.. n] {elemen-elemen vektor x}
i {indeks kolom}
Lokal j {indeks indetifier proses}
k {indeks baris}
1. begin
2. for i  n downto 1 do
3. x[i] b[i]/ a[i][i]
4. forall P[j] where 1  j  p do
5. for k  j to i 1 step p do
6. b[k] b[k]  x[i]  a[k][i]
7. a[k][i]  0 {statement ini bersifat opsional}
8. endfor
9. endforall
10. endfor
11. end
Algoritma 9.2. melakukan n operasi pembagian. Banyak-nya operasi pengurangan dan perkalian adalah :
(n1)/p + (n2)/p + … + 2/p + 1/p = n(n-1)/p (9.2)
sehingga kompleksitas algoritma 9.2. adalah (n / p).
Berikut ini adalah tracing penerapan algoritma 9.2. terhadap sistem persamaan pada contoh 9.1. untuk p = 2 :

i = 4 : x[4] = b[4]/a[4][4] = 4/2 = 2  x[4] = 2
P[1] : k = 1 : b[1] = b[1] – x[4]  a[1][4] = 8 – 2  4 = 0
a[1][4] = 0
k = 3 : b[3] = b[3] – x[4]  a[3][4] = 0 – 2  (-3) = 6
a[3][4] = 0
P[2] : k = 2 : b[2] = b[2] – x[4]  a[2][4] = 5 – 2  1 = 3
a[2][4] = 0

i = 3 : x[3] = b[3]/a[3][3] = 6/2 = 3  x[3] = 3
P[1] : k = 1 : b[1] = b[1] – x[3]  a[1][3] = 0 – 3  (-1) = 3
a[1][3] = 0
P[2] : k = 2 : b[2] = b[2] – x[3]  a[2][3] = 3 – 3  (-3) = 12
a[2][3] = 0

i = 2 : x[2] = b[2]/a[2][2] = 12/(-2) = -6  x[2] = -6
P[1] : k = 1 : b[1] = b[1] – x[2]  a[1][2] = 3 – (-6)  1 = 9
a[1][2] = 0

i = 1 : x[1] = b[1]/a[1][1] = 9/(1) = 9  x[1] = 9

2.4. Speedup
Speedup algoritma 9.2. ini adalah :
S = , = p (9.3)
Menurut Amhdal, untuk jumlah prosesor tertentu nilai S akan meningkat menurut kenaikan ukuran matriks n. Gambar berikut adalah data akibat fenomena ini.

Gambar 9.1. Speedup paralelisasi algoritma substitusi mundur untuk berbagai ukuran matriks tridiagonal.

III. REDUKSI GANJIL-GENAP/REDUKSI SIKLIS :
3.1. Algoritma Sequensial
Contoh 9.2
Selesaikan sistem persamaan berikut :
16 + 4 = 8
4 + 11  5 = 7
2 + 14  6 = 13
5 + 18 = 24
Jawab
Vektor x = [ ] diperoleh melalui prosedur berikut :
1. eliminasi pada persamaan kedua dengan meng-gunakan persamaan pertama sehingga diperoleh :
16 + 4 = 8
10  5 = 5
2 + 14  6 = 13
5 + 18 = 24
2. ulangi langkah (1) untuk pada persamaan ketiga dan pada persamaan keempat. Hasilnya adalah :
16 + 4 = 8
10  5 = 5
15  6 = 12
20 = 20
3. selesaikan persamaan terakhir, dimulai dari penyelesaian pada persamaan keempat.
Dengan cara ini maka diperoleh :
x = [ ] = [0.225 1.100 1.200 1.000]
Sistem di atas dapat dituliskan sebagai A x = b, dimana :
A = = matriks tridiagonal, b =
Untuk sistem tridiagonal berukuran n prosedur di atas dapat digeneralisasi menjadi algoritma sekuensial berikut :
Algoritma 9.3. TRIDIAGONAL.SYSTEM.SOLVER (SISD) :
Global n {ukuran sistem}
f[2.. n], g[1.. n], h[1..( n -1)] {elemen matriks A}
b[1.. n] {elemen vektor b}
x[1.. n] {elemen vektor x}
1. begin
2. for i  1 to n 1 do
3. g[i+1]  g[i+1]  (f[i+1] / g[i]) x h[i]
4. b[i+1]  b[i+1]  (f[i+1] / g[i]) x b[i]
5. endfor
6. for i  n downto 2 do
7. x[i]  b[i] / g[i]
8. b[i 1]  b[i 1]  x[i] x h[i 1]
9. endfor
10. x[1]  b[1] / g[1]
11. end

Algoritma 9.3. mengandung 2 loop masing-masing dengan n1 iterasi. Setiap iterasi memerlukan waktu yang tetap. Kompleksitas algoritma dengan demikian adalah (n).
3.2. Potensi Paralelisasi
Perhatikan dua matriks berikut :
A= , A =
Matriks A adalah hasil transformasi dari matriks A. Matriks A terdiri dari dua matriks tridiagonal yang saling lepas sehingga penyelesaian kedua bagian vektor x dapat dilakukan secara serempak.

3.3. Algoritma Paralel
Algoritma paralel dibangun untuk mentransformasikan matriks A menjadi A . Pola umum struktur matriks tridiagonal berukuran n adalah :
+ =
+ + = 2  i  n-1 (9.4)
+ =
Untuk 3  i  n-2, persamaan (i-1), (i), dan (i+1) adalah :
+ + =
+ + =
+ + =
Dari persamaan (i-1) dan (i+1) dapat diperoleh :
= (1/ )( – – ) (9.4a)
= (1/ )( – – ) (9.4b)
Substitusi kedua persamaan ke persamaan (i) akan menghasilkan :
+ + = (9.5)
dimana :
= , = + + (9.6a)
= , = + + (9.6b)
= , = (9.6c)
Persamaan (9.6) juga berlaku untuk : , , , , , , kecuali untuk :
= + dan = + (9.6d)
= + dan = + (9.6e)
Ungkapan matriks persamaan (9.5) adalah A x = b yang merupakan transformasi dari Ax = b dimana :
A = (9.7)
Persamaan A x = b dapat disusun ulang menjadi = , dimana =
(9.8a)
= [ … ] (9.8b)
= [ ] (9.8c)
Berdasarkan pembahasan di atas maka dapat disusun sebuah algoritma seperti berikut di bawah ini.

Algoritma 9.4. CYCLIC.REDUCTION(SIMD) :
Global n {ukuran sistem}
f[2.. n], g[1.. n], h[1..( n -1)] {elemen A}
b[1.. n] {elemen b}
f [3.. n], g [1.. n], h [1..( n -2)] {elemen A }
b [1.. n] {elemen b }
p {# proses}
 [2.. n],  [1..( n -1)] {faktor skala}
x[1.. n] {elemen vektor x}
1. begin
2. for i  1 to n 1 do
3.  [i+1]  -f[i+1] / g[i]
4.  [i]  – h[i]/ g[i+1]
5. endfor
6. for i  2 to n 1 do
7. f [i+1]   [i+1]  f[i]
8. g [i]  g[i] +  [i]  h[i-1] +  [i]  f[i+1]
9. h [i-1]   [i-1]  h[i]
10. b [i]  b[i] +  [i]  b[i-1] +  [i]  b[i+1]
11. endfor
12. g [1]  g[1] +  [1]  f[2]
13. g [n]  g[n] +  [n]  h[n -1]
14. b [1]  b[i] +  [1]  b[2]
15. b [n]  b[n] +  [n]  b[n -1]
16. forall P[j] where 1  j  2 do
17. for i  2 to n 1 step 2 do
18. g [i+j]  g [i+j]
 (f [i+j) / g [i+j-2]) x h [i+j-2]
19. b [i+j]  b [i+j]
 (f [i+j) / g [i+j-2]) x b [i+j-2]
20. endfor
21. for i  n-2+j downto j+1 do step 2
22. x[i]  b [i] / g [i]
23. b [i  2]  b [i  2]  x[i] x h [i  2]
24. endfor
25. x[j]  b [j] / g [j]
26. endfor
27. end

Algoritma 9.4. terdiri dari 4 loop masing-masing dengan kompleksitas algoritma (n). Berikut ini adalah tracing penerapan algoritma 9.4. terhadap sistem persamaan pada contoh 9.2. :

looping 2-5 :
i = 1 :  [2] = -f[2] / g[1] = -4/16 = -1/4
 [1] = – h[1] / g[2] = -4/11
i = 2 :  [3] = -f[3] / g[2] = -2/11
 [2] = – h[2] / g[3] = 5/14
i = 3 :  [4] = -f[4] / g[3] = -5/14
 [3] = – h[3] / g[4] = 6/18 = 1/3

looping 6 – 11 :
i = 2 : f [3] =  [3]  f [2] = -2/11  4 = -8/11
g [2] = g[2] +  [2]  h[1] +  [2]  f[3]
= 11 – 1/4  4 + 5/14  2 = 75/7
h [1] =  [1]  h[2] = -4/11  (-5) = 20/11
b [2] = b[2] +  [2]  b[1] +  [2]  b[3]
= 7 – 1/4  8 + 5/14  13 = 135/14
i = 3 : f [4] =  [4]  f [3] = -5/14  2 = -5/7
g [3] = g[3] +  [3]  h[2] +  [3]  f[4]
= 14 – 2/11  (-5)+ 1/3  5 = 547/33
h [2] =  [2]  h[3] = 5/14  (-6) = -15/7
b [3] = b[3] +  [3]  b[2] +  [3]  b[4]
= 13 – 2/11  7 + 1/3  24 = 217/11

baris 12-15 :
g [1] = g[1] +  [1]  f[2] = 16 – 4/11  4 = 160/11
g [4] = g[4] +  [4]  h[3] = 18 – 5/14  (-6) = 141/7
b [1] = b[1] +  [1]  b[2] = 8 – 4/11  7 = 60/11
b [4] = b[4] +  [4]  b[3] = 24 – 5/14  13 = 271/14

Sampai tahap ini terbentuk matriks dan vektor berikut :

= , =
looping paralel 16 – 28, j = 1 :
sublooping 17-20
i = 2 : g [3] = g [3] – (f [3] / g [1])  h [1]
= (547/33) – ((-8/11) / (160/11))  20/11 = 550/33
b [3] = b [3] – (f [3] / g [1])  b [1]
= (217/11) – ((-8/11) / (160/11))  60/11 = 220/11
sublooping 21-24
i = 3 x[3] = b[3] / g[3] = (220/11) / (550/33) = 1.200
b[1] = b[1] – x[3]  h[1] = 60/11 – 1.200  20/11 = 36/11
instruksi 25 :
x[1] = b[1] / g[1] = (36/11) / (160/11) = 0.225

looping paralel 16 – 28, j = 2 :
sublooping 17-20
i = 2 : g [4] = g [4] – (f [4] / g [2])  h [2]
= (141/7) – ((-5/7) / (75/7))  (-15/7) = 20
b [4] = b [4] – (f [4] / g [2])  b [2]
= (271/14) – ((-5/7) / (75/7))  135/14 = 20
sublooping 21-24
i = 3 x[4] = b[4] / g[4] = 20 / 20 = 1.000
b[2] = b[2] – x[4]  h[2] = 135/14 – 1.000  (-15/7) = 165/14
instruksi 25 :
x[2] = b[2] / g[2] = (165/14) / (75/7) = 1.100

2.4. Speedup
Kompleksitas algoritma dapat juga dinyatakan melalui nilai total operasi floating point. Untuk algoritma 9.3. nilai total operasi floating point adalah :
= 9n – 8 (9.9)
sedangkan untuk algoritma 9.4. adalah :
= 16.5n – 22 (9.10)
sehingga speedup adalah :
= 0.545 (9.11)
Jika paralelisasi juga dilakukan pada langkah 2-5, 6-11, dan 12-16 maka total operasi floating point algoritma 9.4 adalah :
= 10.5n – 18 (9.12)
sehingga speedup adalah :
= 0.857 (9.13)
Baik (9.11) maupun (9.12) adalah nilai speedup yang buruk (< 1.0). Kedua nilai tersebut dihasilkan jika paralelisasi menggunakan 2 prosesor. Jika menggunakan 4 prosesor maka instruksi-instruksi yang dapat di-assign ke masing-masing prosesor adalah instruksi : 6-10, 12-15, dan, dengan sedikit perbedaan penanganan, langkah 16-25. Total operasi floating point dengan 4 prosesor adalah :
= 7.5n – 14 (9.14)
sehingga speedup adalah :
= 1.2 (9.15)
Nilai (9.15) ini adalah nilai maksimum untuk paralelisasi algoritma 9.4.

Tinggalkan Balasan

Please log in using one of these methods to post your comment:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s