Preorder Tree Traversal

Preorder Traversal adalah proses kunjungan pada graph pohon dimana penandaan kunjungan dilakukan di awal yaitu ketika nodeuntuk pertama kali terkunjungi. Urutan kunjungan mengikuti kaidahdepth first search order. Secara sekilas persoalan preorder traversal seperti persoalan sekuensial.Coba perhatikan fungsi rekursif di bawah ini :

openstat_preorder_tree_traversal_algorithm1

Dimanaparallelismenya ? Kita akan melihat bahwa cara pandang denganvertexsebagai fokusnya akan menyebabkan kita melihat persoalan ini sebagai persoalan sekuensial murni yang tidak ada proses paralel nya.

Sekarang, mari kita lihat dengan cara pandang yang berbeda. Mari kita pandangruas/edgedari graph ini. Kita melihat bahwa ketika perjalanan kunjungan graph dilakukan, maka setiap ruas/edgeakan dilewati 2 (dua) kali dengan arah yang berlawanan,turundannaik. Jika kita pisahkan setiapruas/edgeini menjadi 2, yang pertama menjadi ruas turun, dan yang satu lagi menjadiruas naik,maka sekarang kita akan melihat persoalan preorder traversal ini menjadi sebuah persoalan singly-linked list.

Cara pandang terhadapruas/edgeinilah yang menjadikannya sebagai persoalan yang dapat diparalelkan dengan sebuah algoritma yang cepat. (dipublikasikan oleh Tarjan dan Vishkin 1984).

Selanjutnya mari kita bahas algoritma ini dengan lebih rinci. Algoritma ini memiliki 4 fase. Pada fase pertama, algoritma akan membentuk sebuahsingly-linked list.Setiapvertex/simpul dari singly-linked list ini akan berkait dengan ruas penelusuran naikatau ruas penelusuran turundi dalamtree.

openstat_preorder_tree_traversal_algorithm2

Padafase kedua, algoritma akan memberikan bobot kepada semua vertex/node dari singly-linked listyang baru dibuat tersebut. Pada algoritma preorder traversal, sebuah vertex/node diberi label/tanda segera saat dilewati traversal/penelusuran edge yang turun. (Vertexrootadalah pengecualian dan harus ditangani secara khusus). Untuk itu pada setiap vertex/node yang terkait dengan penelusuran edge turun diberi bobot 1 (satu)., artinya hitungan node nya bertambah ketikaruas/edgenya ditelusuri. Kemudian daftarkan element-element yang terakit denganruas/edge naikdengan bobot 0 (nol), karenanyahitungannodenya tidak akan bertambah ketika penelusuran pohon melaluinya saat menuju nodeyang sudah diberi label/tanda sebelumnya.

openstat_preorder_tree_traversal_algorithm3

Pada fase ketigakita menghitungrankdari daftar element untuk setiap elemen di sinly-linked list.

 

openstat_preorder_tree_traversal_algorithm4

Langkah/fase keempat, prosesor2 yang memegangruas turunmenggunakan rank yang sudah dihitung olehnya untuk memberikanangka penelusuran/traversal preorderpada node-2 yang terkait dengannya (node di akhir ruas turun)

openstat_preorder_tree_traversal_algorithm5

 

Implementasi alogritma ini menggunakan sturktur data yang tidak biasa dalam menampilkanpohon/treenya.

openstat_preorder_tree_traversal_algorithm7

 

Untuk setiaptree node,struktur data menyimpan : parent dari node, sibling langsung yang berada di kanannya (immediate sibling to the right) dan anak paling kiri (leftmost child).

Algoritma di bawah ini adalah algoritma PRAM untuk preorder tree traversal. Algoritma ini memasangkan setiap prosesor dengan setiap ruas/edgeyang ditelusuri. Sebuahpohon/treedengannbuan node akan memilikin-1buah ruas/edge. Karena kita membagi setiap ruas/edge menjadi ruas turun dan ruas naik, maka algoritma ini membutuhkan2(n-1)buah prosesor untuk menghitung 2(n-1) elemen dari singly-linked list.

Setelah semua prosesor dalam keadaan aktif, mereka akan segera membentuklinked listyang terkait dengan preorder traversal. Diberikan ruas/edge (i,j), setiap prosesor harus menghitung penerusnya/successordari ruas/edge tersebut dalam penelusurannya. Jikaparent[i]=j,ruasnya akan menuju kebagian atas dari pohon, darinodeanakkeparentnya. Ruas naik memiliki tiga macam successor. Jikaanakmemiliki sebuah siblingruas successor akan bergerak dari parent nodemenuju kesiblingnya, selain itu jika anakmemilikikakek/grandparent ,maka ruas successor akan bergerak dari node parent ke node kakek/grandparentnya. Jika kedua kondisi tersebut tidak terpenuhi maka artinya ruas berada di akhir/ujung dari pohon traversal, jadi selanjutnya kita letakkan sebuah loop di ujung dari daftar elemen ini. Dalam kasus ini kita juga mengetahui identitas dari node root/akar, dan kita jadikan nomor preordernya menjadi 0.

Berikutnya kita perhatikan kasus\(parent[i] \neq j\) ; dimana ruas bergerak turun di dalam pohon, dari node parent ke anaknya. Hanya ada dua macam successor edge. Jika node anaknya memiliki anak, maka successor nya adalah edge dari anak ke cucunya. Selain itu, node anak adalah daun dan successor adalah ruas dari anak menuju parent nya.

Setelah prosesor membentuk linked list, mereka akan memberikan nilai posisi 1 untuk elemen yang merupakan ruas turun dan 0 untuk elemen yang merupakan ruas naik.

Nilai akhir dari nilai posisi ini menunjukkan angka penelusuran preorder antara daftar elemen ke ujung dari list. Untuk menghitung lebel dari setiap node preorder traversal, setiap prosesor dihubungkan dengan ruas turun dan dikurangangi nilai position nya dari n+ 1. Penamahan 1 karena penomoran preorder traversal dimulai dari 1 bukan 0

openstat_preorder_tree_traversal_algorithm6

List Ranking

[Ke Urutan Pembelajaran Paralel]

Berikut ini adalah masalah bagaimana menghitungsuffix sumsdarii buah element terakhir dari sebuah daftar(list), dimana \inline 1\leq i\leq n untuk setiapnelement linked list

Suffix Sums ini adalah varian dariprefix sums, dimana terdapat sejumlah bilangan pada sebuah array yang ditampilkan dalam bentuklinked list, kemudian kita akan menghitung jumlah angka-angka tadi yang dimulai dari bagian akhir linked listnya, bukan dari depan.

Jika bilangan-bilangan yang berada di dalam array tersebut adalah 1 atau 0 saja, dan operasi asosiatif \inline \bigoplusnya adalah penjumlahan, maka persoalan ini sering disebut persoalanList Ranking. (Karp and Ramachandran 1990)

Salah satu cara untuk menentukan posisilist adalah dengan cara menghitung banyaknya link yang sudah dikunjungi antara element list dengan akhir dari list.

Jika kita menghubungkan sebuah prosesor dengan setiap element list dan jump pointers dalam pralel, jarak ke bagian akhir darilistakan tinggal setengah dengan perintah : \(next[i]\leftarrow next[next[i]] \)

Karena itu dengan hanya sebanyak lompatan logaritmik sajasudah cukup untuk melipatlist, sehingga setiap elementlist akan menunjuk ke element list yang terakhir.

List Ranking

Jika sebuah prosessor menambahkan kepada penghitunganlink-traversal nya sendiri, yaitu position[i], perhitungan link-traversal dari penerus yg dilaluinya, maka posisi list akan diperoleh.

Algorithma untuk permasalahan di atas dapat dilihat di bawah ini :

[Ke Urutan Pembelajaran Paralel]

Perkalian Matrik pada model SIMD Mesh 2-D

 

Berikut adalah algoritma perkalian matrik paralel yang disampaikan oleh Quinn

Algoritma MATRIX MULTIPLICATION (2-D MESH SIMD)

 

Global n (dimensi dari matrik), k

Local   a, b, c

begin

{stagger matrices}

for k $latex \leftarrow $ 1 to n – 1 do

for all P(i, j) where 1 \( \leqslant \) i, j \( \leqslant \) n do

if i > k then

a \(\Leftarrow\) east(a)

endif

if j > k then

b \(\Leftarrow\) south(b)

endif

endfor

endfor

{ Compute dot products }

for all P(i, j) where 1 \( \leqslant \) i, j \( \leqslant \) n do

c \(\leftarrow\) a x b

endfor

for k \(\leftarrow\) 1 to n – 1 do

for all P(i, j) where 1 \( \leqslant \) i, j \( \leqslant \) n do

a \(\Leftarrow\) east(a)

b \(\Leftarrow\) south(b)

c \(\leftarrow\) c + a x b

endfor

endfor

end

 

Berikut adalah alogritma Perkalian Matrik Paralel pada Komputer Mesh dengan koneksi memutar (wraparound) menurut Pranay Chaudhury

Komputer Mesh Connected dengan Koneksi Berputar (wraparound connection) di gambaran sebagai berikut :

 

(Gambar 6.2 : (a) Penempatan Data Awal; (b) pengaturan data sebelum proses perkalian matrik dimulai

Algorithm MESH_MATRIX_MULTI1

Input : Elemen A[i,j] dan B[i,j] dari matrik A dan B yang akan diperkalikan tersedia di dalam prosesor-prosesor pij , 1 \( \leqslant \) i, j \( \leqslant \) n-1

Ouput : Elemen C[i,j] yang akan tersimpan di dalam prosesor pij , 0 \( \leqslant \) i, j \( \leqslant \) 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

for j = 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 j = 1 to n – 1 dopar

     for i = 0 to n – 1 dopar

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

odpar

odpar

for k = 1 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] := C [i,j] + A[i,j] x B[i,j]

odpar

   odpar

odpar

Perkalian Matrik pada Model PRAM

Berikut adalah algoritma perkalian dua buah matrik yang mempunyai ukuran n x n pada model SIMD shared memory dan kemudian kita akan menganalisa pada batasan-batasan akses memory yang berbeda-beda.

Walaupun untuk penyederhanaan, disini dibahas menggunakan matrik yang berukuran n x n , tetapi kita bisa mengenralisir hal ini dengan mengasumsikan ukuran matrik A, B, dan C sebagai p x n, n x q dan p x q. Hal ini masih akan valid selama \(p \leq n \) dan  \(q \leq n \)

Algorithm PRAM_MATRIX_MULT

Input : dua buah matrik A dan B

Ouput : sebuah matrik C = A x B

for i = 0 to n – 1 dopar

for j = 0 to n – 1 dopar

C[i,j] := 0

for k = 0 to n – 1 do

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

od

odpar

odpar

 

Analisa Kompleksitas

Jika kita asumsikan model komputasi yang digunakan adalah EREW PRAM, maka pembacaan matrik A dan matrik B secara bersamaan dapat dilakukan dengan menggunakan buah prosesor dan dalam waktu O(log n) menggunakan algoritma PARALLEL_BCAST (bab 5.3.2 Chaudhuri)

Ada 2 (dua) pernyataan di dalam for-loops bersarang pada algoritma PRAM_MATRIX_MULT. Yang pertama adalah menginisalisasi semua elemen dari Matrik C menjadi 0 (nol) dan yang lainnya menghitung elemen-elemen di C menggunakan produk kumulatif. Sebuah produk kumulatif adalah operasi perkalian-tambah dalam bentuk c + a x b. Inisialisasi (pemberian nilai awal) dari C membutuhkan waktu O(1) dengan menggunakan n2 buah prosessor. Perkalian kumulatif dapat dilakukan secara mudah, dalam paralel, dengan pertama kali menghitung semua produk dalam bentuk A[i,k] x B[k,j] untuk k = 0, 1, . . ., n – 1 dalam waktu O(1) menggunakan n buah prosessor.