1 | H a l a m a n

Metode Foster Dalam Mendesain Komputasi Paralel

Metode foster merupakan salah satu metode yang dapat digunakan untuk

memecahkan masalah yang berhubungan dengan komputasi paralel (quinn, 2003). Secara

umum metode ini memindahkan masalah dari perhitungan sekuensial menjadi beberapa

partisi perhitungan/data, membutuhkan komunikasi antar partisi yang ada, membuat proses

aglomerasi antar data serta memetakan partisi tersebut dalam beberapa prosesor yang ada,

sehingga metode Foster membagi pekerjaan dalam 4 langkah utama yaitu :

1. Partisi

2. Komunikasi

3. Aglomerasi, dan

4. Pemetaan (Mapping),

Proses-proses tersebut di ilustrasikan sebagai berikut :

Sumber : Quinn, 2003

Gambar 2.3. Metode Foster dalam mendesain algoritma paralel

2 | H a l a m a n

1. Partisi (Partition)

Partisi adalah proses memecahkan problem suatu perhitungan/data dalam masalah-

masalah yang lebih kecil. Terdapat 2 jenis partisi yang dapat digunakan pada proses

paralel, yaitu domain decomposition dan function decomposition, dimana pendekatan

partisi yang baik akan memecahkan masalah komputasi dan masalah data-centric.

a. Domain Decomposition

Jenis partisi ini, data dibagi dalam beberapa masalah yang lebih kecil, kemudian

ditentukan bagaimana proses hubungan komputasi antar data tersebut, dalam arti kata

lain data tersebut dipecah menjadi struktur data yang lebih kecil, misalnya suatu

matriks berukuran 100 x 100 di pecah menjadi matriks 4 x 4 sehingga jumlah sub

matriks yang ada ada 25 sub matriks berukuran 4 x 4, setiap sub matriks tersebut pada

gilirannya diserahkan kepada prosesor yang ada untuk di komputasikan secara

paralel, dalam hal ini proses domain decomposition diilustrasikan sebagai berikut :

3 | H a l a m a n

Sumber : Quinn, 2003

Gambar 2.4. Ilustrasi Proses Domain Decomposition

b. Functional Decomposition

Pada functional decomposition, proses komputasi dipecah menjadi bagian yang

lebih kecil lalu ditentukan bagaimana data yang ada pada bagian yang lebih kecil

tersebut dapat di proses ke dalam masing-masing prosesor yang ada. Proses ini dalam

sistem komputasi awal sering disebut dengan pass by reference sedangkan pada

domain decomposition sering juga di sebut sebagai pass by value.

Terdapat beberapa hal yang perlu diperhatikan dalam proses partisi dalam

komputasi paralel, yaitu :

1. Sedapat mungkin minimalisasikan proses komputasi ganda maupun sistem

penyimpanan ganda.

2. Pada proses yang sangat kecil (primitive task) sebaiknya dilakukan dengan ukuran

yang sama

3. Jumlah task/pekerjaan semakin banyak dapat meningkatkan resiko penyimpanan

Secara ilustrasi, functional decomposition digambarkan sebagai berikut :

Sumber : Quinn, 2003

Gambar 2.5. Ilustrasi Proses Functional Decomposition

4 | H a l a m a n

2. Komunikasi (Communication)

Pada proses ini, alur komunikasi antar pecahan yang terjadi pada proses partisi

dibentuk, penentuan struktur data dan nilai yang di passing ditentukan, dimana pada

proses ini terdapat 2 jenis bentuk komunikasi, yaitu :

1. Local Communication

2. Global Communication

a. Local Communication

Local communication adalah bentuk komunikasi dimana nilai sub pekerjaan

dengan sub pekerjaan lain di definisikan dan dibentuk secara local. Dalam hal ini

komunikasi terjadi dengan membuat kanal aliran data.

b. Global Communication

Pada global communication, data pekerjaan saling berkontribusi secara signifikan

dalam memory global, sehingga tidak dibutuhkan suatu kanal terlebih dahulu.

Beberapa hal yang perlu diperhatikan dalam merangcang komunikasi ini, yaitu :

Operasi komunikasi antar pekerjaan dianjurkan seimbang

Setiap komunikasi antar pekerjaan dilakukan sekecil mungkin

Jumlah pekerjaan yang ada dapat mempengaruhi kinerja komunikasi pralel

Jumlah pekerjaan yang ada dapat mempengaruhi proses komputasi paralel

3. Aglomerasi(Agglomeration)

Pada proses aglomerasi, group pecahan dari pekerjaan yang ada di bagi secara

rata ke dalam jumlah prosesor yang dibandingkan, seperti contoh suatu masalah di pecah

dalam 100 sub pekerjaan dimana proses tersebut membutuhkan 5 unit prosesor, maka

pada teknik aglomerasi pekerjaan tersebut di bagi 20 sub pekerjaan untuk setiap prosesor

yang ada, proses pembagian ini di serahkan kepada program MPI (Massage Passing

Interface).

Bagaimana proses aglomerasi dapat meningkatkan kinerja, dilakukan dengan cara

memperkecil komunikasi antar pekerjaan yang paling kecil yang kemudian di

konsolidasikan dalam suatu pekerjaan besar. Dalam hal ini kita juga dapat

5 | H a l a m a n

mengkombinasikan pekerjaan dalam bentuk group yang bersifat ‘send task’ dan ‘receive

task’ yang diigambarkan secara ilustrasi sebagai berikut :

Sumber : Quinn, 2003

Gambar 2.6. Ilustrasi Proses Aglomerasi

Terdapat beberapa hal yang perlu diperhatikan dalam proses aglomerasi, yaitu :

Aglomerasi dilakukan dalam algoritma paralel secara lokal

Replikasi komputasi dapat diperkecil saat proses komunikasi di definisikan

Replikasi data tidak berakibat terhadap skalabilitas

Aglomerasi pekerjaan sebangun dengan proses komputasi secara sekuensial

Jumlah pekerjaan yang besar pada proses partisi dapat meningkatkan ukuran

masalah

4. Pemetaan (Mapping)

Pada proses ini, hasil pekerjaan yang telah diproses secara local pada proses

aglomerasi di kumpulkan kedalam sejumlah prosesor. Situasi ini membutuhkan proses

pemetaan karena kebutuhan akan penomoran data atau pekerjaan perlu di susun terlebih

dahulu sebelum dipetakan.

Proses pemetaan ini dapat diilustrasikan sebagai berikut :

6 | H a l a m a n

Sumber : Quinn, 2003

Gambar 2.7. Ilustrasi Proses Pemetaan

A. Kinerja Algoritma Paralel

1. Kinerja Komputasi secara sekuensial

Kinerja procesor pada dasarnya dilakukan dengan cara menghitung waktu sebelum

dilakukan proses pekerjaan dimulai dan diakhiri saat proses pekerjaan selesai. Proses ini pada

dasarnya membagi sejumlah array ke dalam sub array dimana setiap sub array dikerjakan oleh

satu buah prosesor, secara berurutan dalam kurun waktu tertentu, yang diilustrasikan sebagai

berikut :

Sumber : https://computing.llnl.gov diakses tanggal 30 mei 2010

7 | H a l a m a n

Gambar 2.8. Ilustrasi proses sekuensial

2. Kinerja Komputer secara Paralel

Proses paralel adalah proses yang dilakukan pada p buah prosesor, sehingga data yang

ada dipecah dalam beberapa bagian, dimana setiap bagian data tersebut di serahkan ke prosesor

masing-masing untuk di olah yang diilustrasikan sebagai berikut :

Sumber : https://computing.llnl.gov diakses tanggal 30 mei 2010

Gambar 2.9. Ilustrasi proses paralel

Ukuran kinerja suatu proses paralel pada dasarnya tergantung atas 4 hal utama, yaitu :

a. Ukuran input

Ukuran input tentu menjadi penentu kinerja algoritma paralel. Ukuran input menjadi

penentu banyaknya procesor yang baik untuk digunakan agar komputasi dapat berlangsung

secara optimal.

b. Jumlah proses yang digunakan

Jumlah prosesor yang digunakan harus disesuaikan dengan ukuran input yang data

yang akan diproses. Processor yang terlalu banyak akan menyebabkan biaya komunikasi

tinggi, sehingga tidak efektif digunakan untuk komputasi dengan ukuran kecil.

8 | H a l a m a n

c. Waktu komputasi

Waktu komputasi adalah waktu yang digunakan untuk menghitung kinerja proses

paralel di banding dengan kinerja yang dilakukan pada proses sekuensial untuk ukuran input

yang sama.

1) Speedup

Mendesaian kedalam program parallel tidak lain bertujuan agar program yang

dijalankan agar lebih cepat dibandingkan dengan rancangan pada program sequencial.

Salah satu parameter untuk mengukur kinerja dari program parallel adalah dengan speed

up. Speed up sendiri di definisikan sebagai rasio perbandingan antara waktu eksekusi

pada program sekuensial dengan program parallel. Dapat dituliskan dalam persamaan

sebagai berikut (Quinn, 2003)

Dengan demikian speedup proses paralel dapat dinyatakan sebagai

........................................................................................... (1)

Adapun biaya (overhead) yang harus dikeluarkan untuk pemrosesan paralel di

hitung dengan rumus :

..................................................... (2)

Dimana :

P = banyaknya processor yang digunakan

2) Efisiensi

Dalam penggunaan processor untuk melakukan eksekusi program yang didesain

secara parallel dibutuhukan seberapa banyak processor yang digunakan sehingga tercapai

efisiensi, karena semakin banyak processor yang dilibatkan tidak akan banyak membantu

dalam memperoleh kecepatan dalam eksekusi program parallel dan bisa jadi akan

menambah biaya parallel.

timeexecution Parallel

timeexecution Sequential Speedup

9 | H a l a m a n

Gambar 2.10. Ilustrasi Efisiensi

Nilai efisiensi kinerja paralel dinyatakan sebagai perbandingan kinerja proses

secara sekuensial dibanding dengan biaya overhead (2) nya, sehingga didapatkan :

..................................................... (3)

3) Isoefisiensi

Dalam program parallel dengan penggunaan banyak processor sangat

diperhitungkan, tidak lain untuk mengurangi biaya dari komunikasi antar processor,

untuk menentukan seberapa banyak penggunaan processor yang efektif perlu dilakukan

perhitungan skalabilitas/isoefisiensi dari sistem parallel tersebut. Isoefisiensi sendiri

didefinisikan sebagai pengukuran pada sistem parallel terhadap meningkatnya

kemampuan akibat dari penambahan processor.

..................................................... (4)

Gambar 2.11. variasi dari

10 | H a l a m a n

isoefisiensi