Perkalian Matrik pada Mesh

Asumsikan bahwa kita akan mengalikan dua matrik A dan B yang berukuran n x n pada komputer SIMD Mesh Connected dengan n2 prosesor.

1. Batas bawah untuk Perkalian Matrik pada Mesh

Asumsi :

(A1) Setiap anggota matrik yang akan diperkalikan hanya diwakilkan hanya satu kali pada model komputasi

(A2) Tidak ada 2 (dua) anggota matrik yang sama disimpan pada prosesor yang sama

Teorema :

Berdasarkan asumsi A1 dan A2 di atas, dan tanpa menggunakan sembarang fasilitas broadcast, perkalian dari dua matrik A dan B yang berukuran n x n yang akan menghasilkan C yang juga berukuran n x n, paling tidak akan membutuhkan langkah pergerakan data, dimana \( \beta (2d) \geq n^2 \)

2. Perkalian Matrik pada Mesh dengan Koneksi Berkeliling (Wraparound)

Komputer Mesh Connected dengan Koneksi Berkeliling bisa digambarkan seperti gambar berikut :

matrix0007

Asumsi bahwa matrik yang akan diperkalikan berukuran n x n dan banyaknya prosesor di Mesh adalah n2 . pij adalah prosesor pada baris ke dan kolom ke j, dan terhubung dengan prosesor p(i-1)j , pi(j+1), p(i+1)j, dan pi(j-1), jika ada. Sebagai tambahan, diasumsikan bahwa pada bagian batas-batas tepian dari Mesh saling terhubung. Keterhubungan keliling ini menjadikan semua proses penjumlahan dan pengurangan menggunakan modulo n.

Algoritma MESH_MATRIX_MULT1

Input : anggota-2  A[i,j] dan B{i,j] dari matrik A dan B tersedia di prosesor pij, \( 0 \leq i, j \leq n – 1 \)

Ouput : Elemen C[i,j] dari produk matrix tersedia di prosesor pij , \( 0 \leq i, j \leq n – 1 \)

for i =1 to n – 1 dopar

for s = 1 to i do

for j = 0 to n -1 dopar

A[i,j] := A[i, {j+1) mod n]

odpar

od

odpar

forj = 1 to n – 1 dopar

for t = 1 to j do

for i = 0 to n -1 dopar

B[i,j] := B[(i+1) mod n, j]

odpar

od

odpar

for i = 0 to n – 1 dopar

for j = 0 to n – 1 dopar

C[i,j] := A[i,j] x B[i,j]

odpar

odpar

for k = 0 to n – 1 do

for i = 0 to n – 1 dopar

for j = 0 to n – 1 dopar

A[i,j] := A[i, (j+1) mod n]

B[i,j] := B[(i+1) mod n, j]

C[i,j] := A[i,j] x B[i,j]

odpar

odpar

od

Analisa Kompleksitas

 

 

 

 

Tampak jelas bahwai perulangan for paralel pertama membutuhkan tidak lebih dari O(n) waktu.

Kita bisa melakukan pergeseran baris (row-shifting) dalam n/2 langkah paralel dengan cara menggeser elemen tersebut ke kanan ketika angka perpindahan lebih besar dari n/2.

Begitupun, paralel kedua statemen for perpindahan kolomnya membutuhkan O(n) waktu. Kita belum memulai operasi aritmatika. Operasi aritmatika ditampilkan pada perulangan for yang ketiga dan keempat. Perulangan for yang ketiga secara nyata membutuhkan O(1) waktu paralel. Terakhir, perulangan for yang keempat membutuhkan O(n) waktu sejak badan dari perulangan for ini terdiri dari dua perulangan for paralel bersarang bisa diimplementasikan pada O(1) waktu. Karena itu, waktu keseluruhan kompleksitas algoritma MESH_MATRIX_MULTI adalah O(n) pada sebuah mesh dengan n2 prosesor. Dengan jelas, algoritma ini optimal untuk melihat ?(n) untuk bound yang lebih rendah pada waktu komputasi untuk perkalian matrik pada mesh dua dimensi. Nilai dari algoritma adalah O(n3 ) yang seperti algoritma straightforward serial matrix multiplication.

 

 

 

 

 

 

3. Perkalian Matrik pada Mesh tanpa Koneksi Berkeliling (Wraparound) 

 

 

 

 

Pada bagian ini, kita membahas algoritma perkalian matrik pada mesh dua dimensi yang terhubung dengan komputer tanpa koneksi wraparound. Pada model ini prosesor dihubungkan denga keempat yang terdekat kecuali prosesor yang ada di perbatasan yang juga terhubung dengan keduanya (Kasus : permasalahan disudut- sudut prosesor), atau ketiganya (perbatasan disetiap empat sudut prosesor).

Kita mengasumsikan bahwa algoritma dari elemen A dan B dikirim ke batas prosesor di dalam baris dan kolom pertama dari permasalahan masing- masing. Elemen- elemen dari matriks dikirimkan melalui baris 1 dari A setelah baris i-1, untuk 1 ? j ? n-1. Begitupun kolom j dari B dilaksanakan setelah kolom j-1, untuk 1 ? j ? n-1. ini menjelaskan dari gambar 6.3a untuk kasus- kasus matriks 2 x 2. tiap prosesor pij diatas menerima A[i,k] dan B[k,j, untuk 0 ? k ? n-1, melipatgandakan dan menambahkan hasil ke bagian hasil C[i,j] (C[i,j] menginisialkan ke 0 dari semula). Akhirnya, pij mengirim A[i,k] ke pi(j+1) jika 1 < n-1 dan B[k,j] ke p(i+1)j jika i < n-1. proses ini terus berulang hingga produk matriks C = A x B terpenuhi sebagai output. Algoritma paralel berdasarkan ide diatas seperti dibawah ini.

Algoritma MESH_MATRIX_MULT2

 

 

 

 

Input: elemen- elemen A[i,j] dan B[i,j,i] = 0,1,…,n-1 dari A dan B dikirimkan ke prosesor dari kolom paling kiri (j=0) dan baris paling atas (i-0), masing- masing.

Ouput: matriks C = A x B disimpan jadi elemen- elemen C[i,j] tersedia diprosesor pij,i,j = 0,1,…,n-1

For i = 0 to n-1 dopar

For j = 0 to n-1 dopar

C[i,j] := 0

Odpar

Odpar

For i = 0 to n-1

For j = 0 to n-1 dopar

While (pij receives A[i,k] and B[k,j], k ? (0,1,…,n-1) do

C[i,j] := C[i,j] + A[i,k] x B[k,j]

If i<n-1

Then send B[k,j] to p(i+1)j

Fi

If j < n-1

Then send A[i,k] to pi(j+1)

Fi

Od

Odpar

Odpar

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Simulasi dengan perantara Kejadian Diskrit

Elemen kunci dari simulasi kejadian diskrit adalah variabel-variabel dan kejadian-kejadian . Untuk melakukan simulasi kita secara kontinyu mengamati beberapa variabel tertentu. Secara umum, ada tiga jenis variabel yang sering digunakan, variabel waktu, variabel penghitung (counter),dan variabel status sistem (system state).

Variabel

[table id=1 /]

Ketika sebuah kejadian muncul, nilai dari variabel-variabel di atas akan berubah atau diperbaharui, dan kita akan mengambilnya sebagai keluaran untuk suatu data pengamatan. Untuk tujuan menentukan kapan kejadian berikutnya akan muncul, kita akan memelihara sebuah “daftar kejadian”, yang akan berisi daftar kejadian masa depan terdekat yang akan terjadi dan kapan kejadian tersebut dijadwalkan akan terjadi.

Ketika sebuah peristiwa terjadi, kita akan mengatur kembali waktu dan semua status serta variabel penghitung, serta mengambil data yang terkait. Dengan cara ini , kita akan dapat menelusuri/mengikuti sistem selama sistem itu berproses sepanjang waktu tertentu.

Dalam semua model antrian, kita mengambil anggapan bahwa para pelanggan akan datang mengikuti suatu proses poisson nonhomogeneous dengan fungsi intensitas terbatas \(\lambda (t), t > 0\). Ketika mensimulasikan model ini, kita akan menggunakan subrutin berikut ini untuk membangkitkan nilai dari variabel acak \( T_s \), ditentukan sama waktunya dengan kedatangan pertama kalinya setelah satuan waktu berlalu.

Misalkan \(\lambda \) sedemikian sehingga \(\lambda (t)\leq \lambda \) untuk semua t. Asumsikan bahwa \(\lambda (t), t > 0\), dan  \(\lambda \) sudah ditentukan, subrutin berikut ini akan membangkitkan nilai dari \( T_s \).

Subrutin untuk membangkitkan Ts

[table id=2 /]

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Paralel Algorithm Design and Analysis: Sebuah Urutan Pembelajaran

Sebuah usulan urutan pembelajaran Algoritma Dan Pemrosesan Paralel

  1. Pengenalan dan latar belakang
  2. Terminologi Komputer Paralel
  3. Models dan Paradigma Komputer Paralel
  4. Processor Arrays, Multiprocessors, dan Multicomputers
    1. Organisasi Processor
      1. Cube Connected Cycles Networks
      2. Shuffle-Exchange Networks
  5. Analisa Kompleksitas Algoritma Paralel
  6. Algoritma-algoritma PRAM
    1. Parallel Reduction
    2. Prefix Sums
    3. List Ranking
    4. Preorder Tree Traversal
    5. Merging Two Sorted Lists
    6. Graph Coloring
  7. Sorting
    1. Enumeration Sort
    2. Lower Bounds On Parallel Sorting
    3. Ood-even Transposition Sort Algorithm
    4. Bitonic Merge
    5. Bitonic Merge pada Shuffle-Exchange Nework
  8. Selection dan Searching
  9. Komputasi Matriks
    1. Pengantar Komputasi Matrik
    2. Perkalian Matrik secara umum
      1. Perkalian Matrik pada  model PRAM
      2. Perkalian Matrik pada Mesh
      3. Perkalian Matrik pada model SIMD Mesh 2-D
  10. Algoritma untuk Grap Tak Berbobot
  11. Algoritma untuk Grap Berbobot

Pendekatan Simulasi Kejadian Diskrit (The Discrete Event Simulation Approach)

Mensimulasikan suatu model probabilistik akan melibatkan pembangkitan mekanisme stokastik dari model yang bersangkutan dan kemudian melakukan pengamatan terhadap aliran resultante dari model tersebut sepanjang waktu tertentu.

Berdasarkan kepada alasan pembuatan simulasi tersebut, akan ada beberapa kuantitas pengamatan tertentu yang akan kita cari. Tetapi , walaupun demikian karena evolusi model yang mengikuti waktu itu sering kali melibatkan suatu struktur logis yang rumit dari elemen-elemennya, karenanya tidak selalu mudah untuk melakukan penelusuran/mengikuti perjalanan dari evolusi tersebut, demikian juga dalam menentukan kuantitas yang akan diamati.

Sebuah kerangka kerja (framework) umum, dibangun seputar ide dari “kejadian diskrit”, telah dibuat untuk membantu kita untuk mengikuti sebuah model sepanjang waktu dan menentukan kuantitas pengamatan yang relevan/wajar. Pendekatan pada simulasi yang berdasarkan pada kerangka kerja ini sering disebut dengan Pendekatan Simulasi Kejadian Diskrit.

Sistem Antrian dengan 2 (dua) Server Paralel

Sistem ini terdiri dari 2 (dua) server, dimana ketika pelanggan datang pada saat kedua server dalam keadaan sibuk, maka pelanggan tersebut akan masuk dalam antrian. Dan ketika salah satu server kosong/bebas, maka segera pelanggan yang datang lebih dahulu dalam antrian akan masuk ke dalam server yang kosong/bebas itu, tidak tergantung server nomor berapa yang sedang kosong. Distribusi layanan dari server ke i adalah \( G_i \), i=1,2 (lihat gambar)

2 paralel server

Misalkan kita akan mensimulasikan model ini, sambil mengamati waktu yang dihabiskan oleh setiap pelanggan didalam sistem dan banyaknya layanan yang diberikan/dilakukan oleh setiap server.

Karena disini kita memiliki lebih dari satu server, maka akan berdampak bahwa nanti ketika pelanggan meninggalkan sistem, urutannya mungkin tidak sama dengan urutan ketika dia datang. Karenanya untuk mengetahui pelanggan mana yang akan meninggalkan sistem pada saat layanannya selesai kita akan mencermati pelanggan mana saja yang sedang dalam sistem.

Kita akan memberi nomor pada setiap pelanggan yang baru saja sampai di sistem, yang pertama kali datang diberi nomor 1, berikutnya 2, dan selanjutnya. Kita akan menggunakan variabel-variabel berikut :

Variabel waktu  t

System State Variable  (SS)

Variabel yang mencatat kondisi sistem (System State) pada waktu tertentu.

( \( n, i_1, i_2, . . ., i_n \) )  jika ada n pelanggan di dalam sistem  \(i_1\) akan bersama dengan server 1, \(i_2 \) akan bersama dengan server 2, \( i_3 \) akan bersama dengan server 3 dan seterusnya.

Catatan : SS = (0) ketika sistem kosong/bebas, dan SS = (1,j,0) atau (1,0,j) ketika hanya pelanggan j dan dia sedang dilayani di server 1 atau server 2.

Counter Variables (variabel penghitung)

\( N_A \) : banyaknya kedatangan dalam waktu t .

\( C_j \) : banyaknya pelanggan yang dilayani oleh j, j= 1,2, dalam waktu t .

Output Variables

Variabel yang mencatat kejadian apa saja dan berapa yang dihasilkan dari sistem.

A(n) : waktu kedatangan dari pelanggan n, \( n \geq 1\)

D(n) : waktu keberangkatan pelanggan n, \( n \geq 1\)

Event list \( t_A , t_1 , t_2\)

Dimana \( t_A \) adalah waktu kedatangan berikutnya, dan \( t_1 \) adalah waktu penyelesaian dari pelanggan yang pada saat itu sedang dilayani oleh server i, i = 1, 2. Jika tidak ada lagi pelanggan yang saat itu berada di server i, maka kita jadikan \( t_i = \infty \), i = 1, 2. Berikut ini, daftar kejadian akan selalu berisi tiga variabel yaitu \( t_A , t_1 , t_2 \).

Untuk memulai simulasi, kita berikan nilai awal pada variabel-variabel dan daftar kejadian tersebut sebagian berikut :

Pemberian nilai awal (Initialize)

Set t = \( t_A = C_1 = C_2 = 0\)

Set SS = (0)

Bangkitkan \( T_0\), dan set \( t_A = T_0, T_1 = t_2 =\infty \).

Untuk mengupdate sistem. kita bergerak dalam waktu tertentu hingga kita mencapai event/kejadian berikutnya. Pada kasus-kasus berikut, $latex Y_i $ selalu berasal dari variabel acak yang berdistribusi \( G_i , i=1,2\)

Kasus 1 \( SS = (n, i_1, i_2, … , i_n) \) dan \( t_A = min (t_A, t_1, t_2 )\)

Reset : \( t = t_A\)

Reset : \( N_A = N_A + 1\)

Bangkitkan \( T_t \) dan reset \( t_A = T_t\)

Ambil output data \( A(N_A) = t\)

Jika SS = (0):

Reset : \(SS = (1, N_A,0)\)

Bangkitkan \( Y_1 \) dan reset \( t_1 = t + Y_1\)

Jika SS = (1, j, 0) :

Reset : \( SS = (2, j, N_A)\)

Bangkitkan \(Y_2 \) dan reset \(t_2\)

[ Sumber : Simulation, Sheldon M. Ross]