toosa – Page 7 – OpenStat

Preorder Tree Traversal

2 April 2013 toosa Leave a comment

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

Dimana parallelisme nya ? Kita akan melihat bahwa cara pandang dengan vertex sebagai 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 pandang ruas/edge dari graph ini. Kita melihat bahwa ketika perjalanan kunjungan graph dilakukan, maka setiap ruas/edge akan dilewati 2 (dua) kali dengan arah yang berlawanan, turun dan naik. Jika kita pisahkan setiap ruas/edge ini menjadi 2, yang pertama menjadi ruas turun, dan yang satu lagi menjadi ruas naik, maka sekarang kita akan melihat persoalan preorder traversal ini menjadi sebuah persoalan singly-linked list.

Cara pandang terhadap ruas/edge inilah 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 sebuah singly-linked list. Setiap vertex/simpul dari singly-linked list ini akan berkait dengan ruas penelusuran naik atau ruas penelusuran turun di dalam tree.

Pada fase kedua, algoritma akan memberikan bobot kepada semua vertex/node dari singly-linked list yang baru dibuat tersebut. Pada algoritma preorder traversal, sebuah vertex/node diberi label/tanda segera saat dilewati traversal/penelusuran edge yang turun. (Vertex root adalah 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 ketika ruas/edge nya ditelusuri. Kemudian daftarkan element-element yang terakit dengan ruas/edge naik dengan bobot 0 (nol), karenanya hitungan node nya tidak akan bertambah ketika penelusuran pohon melaluinya saat menuju node yang sudah diberi label/tanda sebelumnya.

Pada fase ketiga kita menghitung rank dari daftar element untuk setiap elemen di sinly-linked list.

Langkah/fase keempat, prosesor2 yang memegang ruas turun menggunakan rank yang sudah dihitung olehnya untuk memberikan angka penelusuran/traversal preorder pada node-2 yang terkait dengannya (node di akhir ruas turun)

Implementasi alogritma ini menggunakan sturktur data yang tidak biasa dalam menampilkan pohon/tree nya.

Untuk setiap tree 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/edge yang ditelusuri. Sebuah pohon/tree dengan n buan node akan memiliki n-1 buah ruas/edge. Karena kita membagi setiap ruas/edge menjadi ruas turun dan ruas naik , maka algoritma ini membutuhkan 2(n-1) buah prosesor untuk menghitung 2(n-1) elemen dari singly-linked list.

Setelah semua prosesor dalam keadaan aktif, mereka akan segera membentuk linked list yang terkait dengan preorder traversal. Diberikan ruas/edge (i,j), setiap prosesor harus menghitung penerusnya/successor dari ruas/edge tersebut dalam penelusurannya. Jika parent[i]=j, ruasnya akan menuju kebagian atas dari pohon, dari node anak ke parent nya. Ruas naik memiliki tiga macam successor. Jika anak memiliki sebuah sibling ruas successor akan bergerak dari parent node menuju ke sibling nya, selain itu jika anak memiliki kakek/grandparent , maka ruas successor akan bergerak dari node parent ke node kakek/grandparent nya. 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

Paralel Algorithm PRAM, Preorder, Tree Traversal

Fade out layer dengan Gimp

31 March 2013 toosa Leave a comment

Ctt : artikel ini menggunakan Gimp 2.8.2 di Ubuntu 12.10

Untuk membuat fade out sebuah layer dengan Gimp tidaklah terlalu sulit, mari ikuti langkah-langkah sebagai berikut. Misalkan kita memiliki gambar sebagai berikut :

Source from : islamicmonitor.blogspot.com

Buka lah gambar tersebut sehingga muncul di jendela Gimp.

Aktifkan Toolbox dengan Dockable menu Layer (Windows > Docable Dialogs > Layers / Ctrl+L ). Kemudian tambahkan Layer Mask dengan cara click-kanan pada layer list gambar kita yang ada di Toolbox, lalu pilih Add Layer Mask.

Pilih White (full opacity), klik pada tombol “Add”. Langkah berikutnya adalah memilih fungsi Blend Tool dengan Gradient : FG to BG (RGB).

Ctt : Jika Tab Gradient belum muncul di Toolbox, Anda dapat memunculkan dengan cara click pada tanda segitiga kecil di kanan atas Tab list di Toolbox, lalu pilih Add Tab dan pilihlah Gradient.

Kemudian drag sebuah garis semu pada gambar yang akan diberi efek fade out.

Lalu akan menjadi sebagai berikut :Setelah fade-out ini cocok dan menjadi tetap, maka langkah terakhir adalah menetapkan perubahan ini dengan cara click kanan di layer list yang ada gambar kita, lalu pilih Apply Layer Mask.

Sehingga gambar kita menjadi :

Selamat mencoba !

Graphic fade out, gimp

Search Path di PostgreSQL

2 March 2013 toosa Leave a comment

Search Path (search_path) adalah daftar schema yang menjadi patokan bagi PostgreSQL untuk mencari objek yang digunakan, apakah itu table, view, dan sebagainya. Urutan daftar ini juga akan menentukan prioritas pencarian. Untuk menampilkan current search path :

#show search_path;
ossystem=# show search_path;
           search_path           
---------------------------------
 sys, public, helpdesk, hrd, sym
(1 row)

Untuk membentuk search_path kita mengunakan statement SET, contoh :

SET search_path TO my_schema, public;

Database, PostgreSQL

E: Could not get lock /var/lib/aptitude/lock – open …

8 December 2012 toosa Leave a comment

Error ini diperoleh pada saat sedang melakukan Upgrade paket-paket Ubuntu dengan menggunakan aptitude .

Pada saat aptitude sedang berproses melakukan upgrade, sayat tertidur dan membiarkan laptop hidup hingga akhrinya jaringan putus sendiri seiring dengan matinya laptop saya. Ternyata proses yang belum tuntas tadi meninggalkan sampah ‘lock’ . Karena itu ketika koneksi kembali lalu mencoba menghidupkan masuk ke aptitude lagi, maka muncullah pesan :

E: Could not get lock /var/lib/aptitude/lock – open (11: Resource temporarily unavailable)” error

Untuk memperbaiki hal ini saya lakukan beberapa hal sebagai berikut :

apt-get update
killall -9 apt-get aptitude
rm -f /var/lib/aptitude/lock

Semoga berguna, terimakasih.

Linux, Security and Optimizing, Ubuntu

How To Create a New User and Grant Permissions in MySQL

16 October 2012 toosa Leave a comment

I always forget the MySQL create database with UTF8 character set syntax, so here it is:

CREATE DATABASE `mydb` CHARACTER SET utf8 COLLATE utf8_general_ci;
GRANT ALL ON `mydb`.* TO `username`@localhost IDENTIFIED BY 'password';
FLUSH PRIVILEGES;

Alternatively, you can use ‘CREATE SCHEMA’ instead of ‘CREATE DATABASE’:

CREATE SCHEMA `mydb` CHARACTER SET utf8 COLLATE utf8_general_ci;
GRANT ALL ON `mydb`.* TO `username`@localhost IDENTIFIED BY 'password';
FLUSH PRIVILEGES;

I hope this helps someone else too!

Database, MySQL

Algoritma-algoritma PRAM

19 June 2012 toosa Leave a comment

[Ke Urutan Pembelajaran Paralel]

PRAM adalah singkatan dari Parallel Random Access Machine

Ini adalah salah satu model komputasi paralel. Model ini sangat sederhana, PRAM belum memperhitungkan jumlah prosesor dan komunikasi antar prosesor. Karena kompleksitas komunikasi ini tidak menjadi isu/masalah akhirnya para desainer/pembuat algoritma PRAM dapat lebih fokus pada paralalisme komputasinya.

Model Komputasi Serial

Model Komputasi Paralel PRAM

Algoritma-algoritma PRAM

Parallel Reduction
Prefix Sums
List Ranking
Preorder Tree Traversal
Merging Two Sorted Lists
Graph Coloring

Paralel Algorithm

Pengantar Komputasi Matrik

11 June 2012 toosa One comment

Komputasi Matrik telah menjadi dasar dalam berbagai komputasi sains. Salah satu komputasi matrik yang sangat penting adalah perkalian matrik. Beberapa bahasan komputasi matrik dalam kaitan dengan algoritma paralel akan kita bahas cukup banyak disini, diantaranya akan meliputi matrik transpos, perkalian matrik-vektor dan masalah konvolusi.

Algoritma perkalian matrik telah banyak digunakan diberbagai aplikasi sebagai salah satu komponen komputasinya, baik pada masalah numerik maupun non-numerik. Contoh non masalah non-numerik misalnya pada Teori Graph. Pada teori ini banyak menggunakan Perkalian Matrik Boolean.

Produk dari matrik A (p x q) dan matrik B (q x r) adalah matrik C (p x r) yang elemen-elemen nya didefinisikan sebagai berikut :

$\small C\left [ i,j \right ]=\sum_{0\leq k\leq q-1}^{.}A[i,k]\times B[k,j]$

Untuk $ 0 \leq i \leq p-1 $ dan $ 0 \leq j \leq r-1 $ dimana $ \vee $ berarti operasi exclusice-OR dan $ \wedge $ adalah operasi AND bitwise.

Jika A dan B adalah matrik Boolean, maka matrik produk C juga akan berupa boolean matrik

Dalam komputasi serial, batas bawah dari kompleksitas perkalian matrik dengan dua matrik n x n diketahui sebesar Ω(n²), karena ada n² elemen yang terlibat dalam menghasilkan matrik perkalian ini dan diperlukan waktu selama O(n²).

Dalam algoritma perkalian serial baik matrik pada umumnya maupun matrik boolean, akan membutuhkan O(n³) jika semua matrik yang terlibat berukuran n x n

Paralel Algorithm Pendahuluan, Perkalian Matrik

Perkalian Matrik pada model SIMD Mesh 2-D

5 June 2012 toosa Leave a comment

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 p_{ij ,}1 $ \leqslant $ i, j $ \leqslant $ n-1

Ouput : Elemen C[i,j] yang akan tersimpan di dalam prosesor p_{ij ,}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

Paralel Algorithm Parallel Algorithm, Perkalian Matrik, PRAM

Perkalian Matrik pada Model PRAM

5 June 2012 toosa Leave a comment

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 n 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 n² 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.

Paralel Algorithm Perkalian Matrik, PRAM

« 1 … 5 6 7 8 9 10 »