Terminologi Pemrosesan Paralel

[Ke Urutan Pembelajaran Paralel]

Pemrosesan Paralel (Parallel Processing)

  • Pemrosesan Paralel adalah pemrosesan informasi yang menekankan pada manipulasi secara serentak pada elemen-elemen data di satu atau lebih prosesor untuk memecahkan sebuah masalah.
  • 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

Super Komputer

  • Sebuah general-purpose computer yang mampu menyelesaikan 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 tetapi dalam jumlah yang cukup besar.

Throughput

  • Banyaknya keluaran yang dihasilkan per unit waktu
  • Peningkatan Throughput artinya :
    • Meningkatkan kecepatan operasi
    • Meningkatkan jumlah operasi yang dapat dilakukan
      dalam satu waktu tertentu (concurency)

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.

Data Parallelism

  • pemakaian unit multifungsi untuk melakukan operasi yang sama secara serentak terhadap sekumpulan data.

Speedup / Percepatan

Rasio/perbandingan antara terhadap waktu yang diperlukan untuk bagi algoritma yang sekuensial yang paling efisien dengan waktu yang diperlukan  untuk menjalankan operasional yang sama pada komputer paralel.

[Ke Urutan Pembelajaran Paralel]

Pengenalan dan Latar Belakang Komputasi dan Algoritma Paralel

[Ke Urutan Pembelajaran Paralel]

Pada terdahulu, teori-teori ilmu klasik dikembangkan berdasarkan obeservasi, teori dan experience/pengalaman.

  • Dari observasi yang dilakukan pada fenomena tertentu akan dihasilkan suatu hipotesa
  • Teori-teori dikembangkan untuk menerangkan fenomena
  • Dan akhirnya menggunakan Design Experimen untuk menguji teori nya. (Biasanya sering dilakukan secara fisik, dan berbiaya mahal, terkadang waktu yang lama dan tidak etis)

Saat ini Experimen lebih banyak dilakukan secara simulasi numerik, sehingga membutuhkan konstruksi komputasi yang sangat kuat. Baik fisik mesin komputer yang digunakan maupun algoritma yang paling efisien . Ukuran komputasi yang semakin meningkat secara significant akhirnya tidak dapat lagi dilakukan dengan hanya menggunakan komputer dengan single processor, tapi sudah memerlukan dukungan mesin komputasi yang memiliki lebih dari satu prosessor.

Contoh kebutuhan akan komputer paralel :

Oceanographer pada Oregon State University akan mensimulasikan secara numerik sirkulasi global dari samudra dengan membagi laut sebagai berikut:

  • 4096: dari timur ke barat
  • 1024 dari utara ke selatan
  • 12 lapisan laut

Hal ini berarti membutuhkan 4096 X 1024 X 12 ? ± 50 juta sel matrik. Jika setiap bagian (iterasi) butuh 10 menit dengan 30 milyar kalkulasi floating point maka tentu memerlukan komputer yang EXTREMELY HIGH SPEED

[Ke Urutan Pembelajaran Paralel]

Reset user root MySql

Login sebagai user root system

$ sudo -i
# _

Matikan service MySQL :

# service mysql stop

Hidupkan kembali service MySQL dengan melepas authentication/grant

# service mysql start --skip-grant-tables

Jika langkah di atas mengalamai kendala, silahkan lakukan hal berikut:

$ sudo service mysql start
$ cd /var/run
$ cp -rp ./mysqld ./mysqld.bak
$ sudo service mysql stop
$ sudo mv ./mysqld.bak ./mysqld
$ sudo mysqld_safe --skip-grant-tables --skip-networking &

Masuk ke MySQL sebagai user ‘root’ dan masuk ke database ‘mysql’:

# mysql -u root mysql
mysql>

Ubah password ‘root’:

mysql> FLUSH PRIVILEGES;
mysql> update user set Password=PASSWORD('passwordbaru') where user='root';
Query OK, 0 rows affected (0.00 sec)
Rows matched: 4  Changed: 0  Warnings: 0

Sekarang user : root dari MySQL sudah memiliki pasword baru, selanjutnya restart kembali MySQL ke mode normal:

# service mysql restart

Eclipse untuk PHP Editor (PDT)

Versi Eclipse terbaru saat tulisan ini diturunkan adalah Eclipse 3.7 dengan nama Indigo.

Untuk menggunakan Eclipse sebagai editor bagai script PHP Anda, maka perlu ditambahkan package yang disebut dengan PDT (PHP Development Tools), Eclipse 3.7 Indigo menggunakan PDT 3.0

Instalasi Tools ini tidak lah terlalu sulit.

 

Alur proses instalasi

  • Buka Help -> Install New Software.
  • Pilih situs  the Indigo update site.
  • Eclipse akan mengambil daftar plugin dari internet, tunggulah sebentar (tergantung kecepatan internet di tempat Anda), jika daftar fitur yang ada sudah ditampilkan semua – pilih/check 'PHP Development Tools'.
  • Pastikan bahwa 'Contact all update sites…' sudah di'pilih' (Checked).

  • Selanjutnya proses dilanjutkan dengan klik pada 'Next', kemudian pilih 'Next' lagi di layar berikutnyan.
  • Silahkan setujui jika ditanya tentang EULA.

Proses instalasi :

  • Instalasi selesai, silahkan Eclipse di restart.

  • Setelah restart pilihkan perspective PHP, Selesai !

 

Warning: date() on ZendServer

Apabila Anda menemukan error seperti ini ketika menggunakan fungsi date()  :

Warning: date() [function.date]: It is not safe to rely on the system’s timezone settings. You are *required* to use the date.timezone setting or the date_default_timezone_set() function. In case you used any of those methods and you are still getting this warning, you most likely misspelled the timezone identifier. We selected ‘Asia/Jakarta’ for ‘WIT/7.0/no DST’ instead in /home/toosa/public_html/basicphp/date1.php on line 2

Ini tandanya Zend Server Anda belum terisi dengan benar. Karena itu masuklah ke Administrasi Zend Server, masuk ke Server Setup lalu cari directive date.timezone , isilah sesuai dengan time zone yang Anda inginkan, misalnya Asia/Jakarta.

 

Install Zend Server 5.3 Community Edition (CE)

IMHO, Pada prinsip nya Zend Server fungsinya sama seperti setup sebuah Web Server + PHP biasa, yaitu Apache + PHP, hanya saja di enhance dengan pengendalian server PHP yang lebih baik, dan ditambahkan fitur-fitur yang lebih mendukung kebutuhan level Enterprise.

Apabila Anda sudah memasang Apache dan PHP standard dari apt-get aptitude, atau Synaptic, maka beberapa file  PHP akan diganti dengan PHP dari Zend, misalkan php5-curl akan diganti dengan php-5.3-curl-zend-server dan seterusnya.

Ok mari kita mulai dengan asumsi :

  1. Menggunakan OS Linux Ubuntu, kebetulan saya menggunakan Ubuntu 10.10
  2. Kita akan menggunakan Apache 2 dan PHP 5.3, jadi Zend server yang dipilih adalah ZendServer CE PHP 5.3.

Tidak ada masalah jika di server Anda sudah ada Apache dan PHP5 sebelumnya, nanti akan di replace pada saat instalasi.

Mari kita lakukan langkah-langkah sebagai berikut :

  1. Login lah sebagai root
  2. Setting file /etc/apt/sources.list , tambahkan
    • deb http://repos.zend.com/zend-server/deb server non-free
  3. Kemudian tambahkan Zend's repository public key dengan cara :
    • wget http://repos.zend.com/zend.key -O- |apt-key add –
  4. Jalankan sikronisasi dengan server repository Zend :
    • aptitude update
  5. Install Zend Server
    • aptitude install zend-server-ce-php-5.3

Hingga saat ini instalasi sudah selesai, mari kita lihat hasilnya dengan melihat :

http://localhost:10081/ZendServer

atau

https://localhost:10082/ZendServer

 

Anda akan ditanya persetujuan :

 

Lalu Next  :

 

Masukkan password dan selanjutnya akan ditanya email, NEXT …

setelah itu SELESAI 🙂

 

Memfungsikan PHP di userdir Apache Ubuntu 10.10

Ketika apache dan php di install di Linux Ubuntu 10.10, php memang sudah bisa dijalankan di /var/www, tetapi ketika kita mengaktifkan modul userdir agar /home/username/public_html bisa digunakan, ternyata baru .html yang bisa diaktifkan, sedangkan *.php belum bisa berjalan. ini karena secara default php5.conf belum mengaktifkan php di public_html.

Bukalah file /etc/apache2/mods-enabled/php5.conf :

<IfModule mod_php5.c>
    <FilesMatch "\.ph(p3?|tml)$">
        SetHandler application/x-httpd-php
    </FilesMatch>
    <FilesMatch "\.phps$">
        SetHandler application/x-httpd-php-source
    </FilesMatch>
    # To re-enable php in user directories comment the following lines
    # (from <IfModule …> to </IfModule>.) Do NOT set it to On as it
    # prevents .htaccess files from disabling it.
    <IfModule mod_userdir.c>
         <Directory /home/*/public_html>
             php_admin_value engine Off
         </Directory>
    </IfModule>
</IfModule>
 

Anda harus memberikan remark (#) seperti di bawah ini :

<IfModule mod_php5.c>
    <FilesMatch "\.ph(p3?|tml)$">
        SetHandler application/x-httpd-php
    </FilesMatch>
    <FilesMatch "\.phps$">
        SetHandler application/x-httpd-php-source
    </FilesMatch>
    # To re-enable php in user directories comment the following lines
    # (from <IfModule …> to </IfModule>.) Do NOT set it to On as it
    # prevents .htaccess files from disabling it.
   # <IfModule mod_userdir.c>
   #     <Directory /home/*/public_html>
   #          php_admin_value engine Off
   #     </Directory>
   # </IfModule>

</IfModule>

Terakhir jangan lupa merestart Apache nya :

$ /etc.init.d/apache2 restart

Start Using Zend Framework 1.11

Zend Framework is one of popular PHP Framework which mostly use for enterprise application. So it will be a little bit complex for the beginers. But don’t worry, I am a beginers too :). I assume that your server is the same with mine, it use linux/unix operating system and can be accessed by ssh/telnet. When I wrote this post, I still use ZF ver. 1.11.

Ok then, lets rock !

1. Get Zend Framework and prepare your site based on Zend Framework

We will get the latest zend framework ini minimal configuration , extract and rename it (I choose ZendFramework-1.11.9-minimal) to ZendFramework then place it under public_html directory (or you can place as you like).

# cd /home/username/public_html

# tar -zxvf  ZendFramework-1.11.9-minimal.tar.gz

# mv ZendFramework-1.11.9-minimal ZendFramework

We will use Zend Tools which located in ZendFramework/bin/zf.sh, so we need to create an alias. You need to modify /home/username/.bashrc by add the text bellow at the end of file :

alias zf.sh=/home/username/public_html/ZendFramework/bin/zf.sh

After you modify this file, you need to re-login. Now, every time You login, Zend tools is ready to use 🙂

Check your Zend Tools :

# zf.sh show version

Zend Framework Version: 1.11.9

2. Create a ZF project (let say “zfstart”).

# cd /home/username/public_html

# zf.sh create project zfstart

3. Create a symbolic link of your zend library to your project library directory

# cd /home/username/public_html/zfstart/library

# ln -s /home/username/public_html/ZendFramework/library/Zend

4. And finaly you will have zfstart project directory structure bellow:

5. Test your project

http://yourdomain/zfstart/public

Then you should see like this bellow :

Congratulation !

Masalah Perbaikan (Repair Problem)

Misalkan ada  sebuah sistem yang membutuhkan tepat n buah mesin, dan tidak boleh kurang dari n. Jika kurang maka system ini tidak dapat berfungsi alias gagal.

Untuk menjaga agar sistem ini dapat terus beroperasi dengan baik, maka disediakanlah mesin cadangan. Ketika ada sebuah mesin yang rusak, maka seketika itu pula mesin cadangan langsung digunakan, dan mesin yang rusak tadi langsung dibawa ke bengkel perbaikan mesin. Bengkel tersebut hanya bisa memperbaiki 1 (satu) buah mesin dalam satu waktu, selebihnya harus antri untuk diperbaiki kemudian. (Lihat gambar)

Semua lamanya waktu perbaikan adalah variabel random independent dengan distribusi G (Gamma). Setiap kali mesin digunakan, maka waktu yang dihabiskan sampai akhirnya mesin tersebut rusak adalah variabel random dan independent berdistribusi F (poisson).

Sistem ini dikatakan gagal apabila terjadi kondisi sebuah mesin rusak dan tidak ada mesin cadangan yang tersedia untuk menggantikannya.

Asumsikan bahwa pada awalnya terdapat n + s mesin yang berfungsi dengan baik, n buah yang beroperasi dan s buah sebagai cadangan, kita akan mensimulasikan sistem ini, demikian juga sebagai pendekatan E[T], dimana T adalah waktu ketika sistem nya gagal operasional.

Untuk mensimulasikan hal ini, kita akan menggunakan variabel berikut :

  1. Variabel waktu : t
  2. Variabel Status Sistem : r ( banyaknya mesin yang rusak pada waktu t)

Variabel Status sistem dapat berubah kapanpun, baik karena sebuah mesin yang sedang bekerja saat itu menjadi rusak, atau ketika suatu mesin yang rusak ternyata sudah selesai diperbaiki, dengan kata lain dikatakan bahwa sebuah kejadian terjadi ketika salah satu atau kedua persistiwa ini terjadi.

Untuk mengetahui kapan kejadian berikutnya akan terjadi, kita perlu terus mengikuti saat-saat ketika mesin yang sedang beroperasi menjadi rusak dan suatu saat ketika suatu mesin yang sedang diperbaiki ternyata sudah selesai dan siap beroperasi kembali.

Kita membutuhkan informasi tersebut untuk menentukan waktu terkecil dari n buah waktu kejadian mesin rusak, simpan informasi ini dalam sebuah daftar terurut. 

Daftar kejadian :  \( t_1\leq t_2\leq t_3 \leq …\leq t_n ,t^* \)

Dimana t1 , … , tn adalah waktu (berurutan) dimana  n buah mesin yang sekarang sedang beroperasi akan rusak, dan t* adalah waktu dimana mesin yang saat itu sedang diperbaiki akan selesai diperbaiki dan siap beoperasi lagi, jika tidak ada mesin yang sedang di perbaiki maka t* = \( \infty \)

Mari sekarang kita lakukan simulasinya :

Inisialisasi

Tentukan \(t=r=0, t^{*}=\infty \) ,

Bangkitkan \( X_1, … , X_n \) variabel independent yang memiliki distribusi F. Urutkan nilai-nilai ini dan \( t_i \) adalah nilai terkecil yang ke-i, i = 1, … , n.

Buat daftar kejadian : \( t_1, . . . , t_n , t^*\)

Selanjutnya kita akan berhadapan dengan dua kasus berikut :

Case 1 \( t_1 < t^*\)

Atur kembali : \( t = t_1\).

Atur : r = r + 1 (karena mesin yang lain ada yang rusak)

Jika r = s + 1, hentikan proses ini dan ambil data dari T = t ( ketika ada s + 1 mesin rusak, dan tidak ada cadangan)

Jika r < s + 1, bangkitkan variabel random X yang berdistribusi F. Variabel random ini akan menampilkan waktu kerja dari bengkel perbaikan yang akan digunakan kembali saat ini. Sekarang urutkan kembali nilai-nilai \( t_2,t_3,\cdots, t_n , t + X \) dan jadikan \( t_i \) sebagai nilai terkecil ke-i dari nilai-nilai tersebut, dimana i = 1, … , n.

Jika r = 1, bangkitkan variabel random Y yang mempunyai fungsi distribusi G dan atur t* = t + Y (hal ini diperlukan karena dalam kondisi ketika sebuah baru saja rusak adalah satu-satunya mesin yang beroperasi, dan dengan demikian perbaikan agak segera dilakukan padanya. Y akan menjadi lamanya waktu perbaikan dan karenanya perbaikan akan selesai pada saat t + Y).

Case 2 \( t^* \leq t_1\)

Atur: t = t*

Atur: r = r – 1

Jika r > 0, bangkitkan variabel random Y yang memiliki fungsi distribusi G, dan tampilkan kembali lamanya waktu perbaikan dari mesin yang baru saja masuk ke bengkel perbaikan, dan atur \( t^* = t + Y\)

Jika r = 0, atur \( t^* = \infty \).

Aturan di atas diilustrasikan pada gambar berikut :

<Gambar>

Setiap kali kita berhenti (yaitu pada saat r = s + 1), kita katakan bahwa sebuah operasi selesai dilakukan. Output dari operasional ini adalah nilai dari waktu gagal operasional T. Kita nanti kemudian akan memulai lagi dari awal dan mensimulasikan operasional berikutnya. Secara keseluruhan, misalkan kita melakukan kali operasional dengan ouput masing-masing \( t_1, T_2, … , T_k \), karena semua variabel random adalah independent dan setiapnya mewakili waktu kegagalan sistem, rata-ratanya \( \sum_{i=1}^{k}T_i/k \) adalam estimasi dari E[T], mean dari waktu kegagalan sistem.

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1 8 9 10 11 12