SoE dan BitonicSort MPI pada InGRID

grid_1 Pemrograman secara paralel dapat meningkatkan ketersediaan sumber daya komputasi, terutama memory dan processor. Salah satu mekanisme paralelisme ini dengan menggunakan Message Passing Interface (MPI). Untuk mengetahui sejauh mana keuntungan yang dihasilkan, diujicobakan algoritma Sieve of Eratosthenes dan Bitonic Sort secara paralel menggunakan MPI. Pengujian dan analisa dilakukan pada mesin Hastinapura di lingkungan cluster inGRID.


1. PENDAHULUAN

Teknik sederhana tetapi efisien dalam mencari bilangan prima adalah Sieve of Eratosthenes. Implementasi berbentuk program membuktikan teknik ini sangat efektif dan cepat untuk dijalankan oleh komputer. Namun bila digunakan dalam bilangan yang sangat besar, dibutuhkan pula sumber daya komputasi dan memory yang besar. Keterbatasan eksekusi dalam 1 komputer dapat dipecahkan dengan membaginya secara paralel dalam banyak komputer. Hasil pengolahan dari proses-proses yang tersebar kemudian dikumpulkan sebagai hasil akhir.

Pengurutan (sorting) merupakan operasi yang sangat umum dilakukan oleh komputer. Mengolah data menjadi lebih mudah apabila sudah dalam keadaan terurut. Pemrograman secara paralalel dapat meningkatkan banyaknya elemen maupun kecepatan pengurutan. Salah satu algoritma sorting paralel adalah Bitonic Sort. Algoritma ini sejak awal dirancang untuk bekerja paralel dalam suatu sortin network.

Tujuan akhir dari makalah ini adalah melakukan uji coba komputasi tersebar, bermula dari program yang dirancang secara sekuensial menjadi paralel. Pada bagian 2 akan dijelaskan algoritma Sieve of Eratosthenes, Bitonic Sort dan penggunaan Message Passing Interface (MPI) untuk membuatnya berjalan secara paralel. Uji coba program dalam cluster inGRID dan analisanya dibahas dalam bagian 3. Kesimpulan makalah ini terdapat pada bagian 4.

clip_image002

Gambar 1. Cluster komputer berbentuk grid.

2. LANDASAN TEORI

2.1. Sieve of Eratosthenes

Bilangan prima adalah suatu bilangan yang hanya memiliki 2 pembagi: 1 dan dirinya sendiri. Keistimewaan bilangan ini menjadi subyek penting dalam berbagai penelitian ilmuwan matematika. Dalam bidang kriptografi bilangan prima merupakan basis pembentuk algoritma, seperti terdapat dalam konsep kriptografi kunci-publik RSA. Dalam kaitan ini, pencarian bilangan prima termasuk mengetahui bilangan prima terbesar merupakan tantangan yang tidak pernah selesai.

Sieve of Eratosthenes adalah suatu teknik untuk menemukan seluruh bilangan prima hingga N bilangan yang efisien[2]. Diperkenalkan pertama kali oleh Eratosthenes of Cyrene (276 BC – 194 BC). Cara kerjanya sebagai berikut:

  • Inisialisasi suatu array sejumlah N dengan 0.
  • Ambil bilangan prima pembagi awal, yaitu 2, tandai setiap elemen array kelipatan 2 dengan 1. Sehingga elemen yang ditandai: [2] [4] [6] [8] … [N].
  • Lanjutkan dengan bilangan prima berikutnya, yaitu 3, tandai setiap elemen array kelipatan 3 dengan 1. Sehingga elemen yang ditandai: [3] [6] [9] [12] … [N].
  • Demikian seterusnya, misalnya 5, 7, 11, 13, 17 dan 19. Batasi bilangan prima maksimal adalah akar dari N, mengingat tidak ada elemen pembagi yang lebih besar dari akar N.
  • Elemen array yang tidak ditandai merupakan bilangan prima.

Bentuk pseudocode dari tahap-tahap di atas yaitu:

  1. Create list of unmarked natural numbers 2, 3, …, n
  2. k ¬ 2
  3. Repeat: a) Mark all multiples of k between k2 and n; b) k <- smallest unmarked number > k; Until k2 > n
  4. The unmarked numbers are primes.

Kompleksitas dari Sieve of Eratosthenes adalah Ο (n ln ln n). Namun algoritma ini butuh tempat yang besar, sebanding dengan N bilangan, sehingga kompleksitasnya Ο (n). Beberapa teknik lain digunakan untuk membuat efisiensi dari tempat penyimpan, misalnya menggunakan operasi bit ketimbang byte, teknik segmented sieve atau pun pengembangan lebih lanjut menjadi algoritma Sieve of Atkin. Teknik-teknik tersebut tidak digunakan dalam makalah ini.

2.2. Sorting Network dan Bitonic Sort

Sorting network adalah suatu model jaringan perbandingan (comparison network), yang selalu mengurutkan setiap masukannya.[5] Dalam hal ini operasi perbandingan dan pengurutan berjalan secara bersamaan. Jaringan perbandingan terdiri dari kawat dan pembanding / komparator. Kawat menyalurkan nilai dari suatu tempat ke tempat lain, sedangkan komparator membandingkan 2 input dan menghasilkan 2 output.

Komponen kunci dari sorting network adalah sebuah komparator. Komparator adalah suatu perangkat dengan 2 input x dan y dan 2 output x’ dan y’. Pada komparator menaik, x’ = min[x, y] dan y’ = max[x, y], sedangkan pada komparator menurun x’ = max[x, y] dan y’ = min[x, y]. Ketika 2 elemen memasuki input komparator, mereka diperbandingkan dan bila perlu dipertukarkan sebelum mencapai output. Setiap kolom pada komparator melakukan permutasi dan output yang didapat dari kolom final telah diurutkan secara menaik atau menurun.

clip_image004

Gambar 2. Bentuk umum sorting network.

Bitonic Sort adalah suatu algoritma pengurutan paralel menggunakan sorting network. Suatu bitonic sequence adalah suatu rangkaian (sequence) yang terurut menaik kemudian terurut menurun atau terurut menurun kemudian menaik. Rangkaian <1,4,6,8,3,2> dan <9,8,3,2,4,6> adalah contoh bitonic sequence. Bitonic sort bergantung pada penyusunan bitonic sequence menjadi sebuah rangkaian terurut. Kompleksitas waktu dari bitonic sort sesuai dengan kedalaman jaringannnya, yaitu Θ(log2n).

clip_image006

Gambar 3. Sorting network dari bitonic sort.

Berikut tahap-tahap pengurutan dalam bitonic sort:

  • s = áa0,a1,…,an-1ñ adalah bitonic sequence sehingga : a0 ≤ a1 ≤ ··· ≤ an/2-1 dan an/2 ≥ an/2+1 ≥ ··· ≥ an-1.
  • Dengan demikian subsequences dari s adalah: s1 = ámin{a0,an/2}, min{a1,an/2+1}, …, min{an/2-1, an-1}ñ; s2 = ámax{a0, an/2}, max{a1, an/2+1}, …, max{an/2-1, an-1}ñ
  • Bagi bitonic sequence dalam 2 subsequences seperti di atas, disebut bitonic split. Perhatikan bahwa s1 dan s2 adalah bitonic dan setiap elemen s1 kurang dari setiap elemen s2.
  • Lakukan bitonic split secara rekursif pada s1 dan s2 untuk mendapat rangkaian terurut. Proses ini disebut juga bitonic merge.

Dalam bentuk source program, langkah-langkah di atas diterjemahkan seperti di bawah. Fungsi-fungsi berjalan secara rekursif.

private void bitonicSort(int lo, int n, boolean dir) {
  if (n>1) {
    int m=n/2;
    bitonicSort(lo, m, ASCENDING);
    bitonicSort(lo+m, m, DESCENDING);
    bitonicMerge(lo, n, dir);
  }
}

private void bitonicMerge(int lo, int n, boolean dir) {
  if (n>1) {
    int m=n/2;
    for (int i=lo; i<lo+m; i++)
      compare(i, i+m, dir);
    bitonicMerge(lo, m, dir);
    bitonicMerge(lo+m, m, dir);
  }
}

2.3. Message Passing Interface

Message Passing Interface (MPI) adalah suatu spesifikasi library pemrograman untuk message-passing, yang diajukan sebagai standar oleh berbagai komite dari vendor, pelaksana dan pemakai.[4] MPI digunakan secara luas mengingat: a) telah memiliki standar; b) dirancang berkinerja tinggi pada mesin-mesin paralel; c) tersedia secara bebas maupun komersial; d) dikembangkan banyak pihak; e) informasi penerapan dan pengujian tersedia.

Dalam pemodelan menggunakan message-passing, suatu proses (process) adalah sebuah pencacah program dan ruang alamat. Proses dapat memiliki banyak thread (pencacah program dan memory lokal) yang saling berbagi ruang alamat. MPI dalam hal ini berfungsi sebagai alat komunikasi di antara proses, yang saling memiliki ruang terpisah. Komunikasi ini terutama berupa sinkronisasi dan perpindahan data antar proses. Informasi dari domain komunikasi seluruh proses disimpan di sebuah variabel yang disebut communicators, misalnya MPI_COMM_WOLRD yang mencakup keseluruhan proses. Paralelisme dalam MPI bersifat Multiple Instruction Multiple Data (MIMD).

Program yang dijalankan paralel menggunakan MPI harus dirancang secara khusus, yaitu menggunakan algoritma paralel, dan saling berkomunikasi menggunakan fungsi-fungsi yang tersedia. Fungsi-fungsi MPI yang digunakan dalam makalah ini sebagai berikut:

  • MPI_Init, MPI_Finalize: memulai dan mengakhiri MPI.
  • MPI_Comm_rank, MPI_Comm_size: mencatat dan identifikasi proses dalam domain.
  • MPI_Send, MPI_Recv, MPI_Sendrecv: mengirim dan menerima data antar proses.
  • MPI_Bcast: menyebarkan data dari proses induk ke proses-proses lain.
  • MPI_Reduce: mengumpulkan variabel dari setiap proses menjadi satu.

clip_image008

Gambar 4. Operasi penjumlahan pada MPI_Reduce.

2.4. Algoritma Sieve of Eratosthenes Paralel

Algoritma Sieve of Eratosthenes dapat dijalankan secara paralel menggunakan teknik MPI. Dengan demikian ketersediaan array dan daya komputasi dapat meningkat sebanding dengan komputer yang digunakan. Proses yang dibutuhkan adalah menyesuaikan algoritma dari berjalan secara sekuensial menjadi paralel.

Tahap awal dalam pengubahan ini adalah membagi array penyimpan untuk tiap-tiap proses. Mengingat faktor pembagi dari N bilangan terbatas hingga akar dari N tersebut, maka maksimal proses yang dapat dibuat sebanding dengan faktor pembagi tersebut. Misalnya untuk maksimal bilangan 25, maka maksimum banyak proses adalah 5, dengan tambahan +1 untuk root (proses induk dengan id=0), dan +2 sebagai batas toleransi. Bila terlalu banyak akan ditampilkan ‘too many process’.

clip_image010

Gambar 5. Perbandingan array global dan lokal

Setelah array global dibagi-bagi menjadi array-array lokal dari masing-masing proses, root bertindak sebagai generator bilangan prima dan menyebarkan (menggunakan MPI_Bcast) bilangan tersebut ke setiap proses. Secara bersamaan setiap proses menandai masing-masing array sesuai bilangan prima itu dan kelipatannya. Dalam hal ini, tiap-tiap proses menunggu pasokan bilangan prima dari root sebelum bekerja, sehingga kecepatan keseluruhan proses sangat bergantung pada root.

Setelah semua elemen array selesai ditandai, masing-masing proses menghitung berapa elemen array yg tidak tercentang, yang merupakan bilangan prima. Hasil penghitungan ini, menggunakan MPI_Reduce dengan operasi MPI_SUM, selanjutnya dijumlah secara keseluruhan dan dikembalikan kepada root. Hasil akhirnya didapat total seluruh bilangan prima.

Berikut penyesuaian pseudocode dari tahap-tahap di atas:

  1. Create list of unmarked natural numbers 2, 3, …, n
  2. k ¬ 2
  3. Repeat: (a) Mark all multiples of k between k2 and n; (b) k ¬ smallest unmarked number > k { hanya root }; (c) Process 0 broadcasts k to rest of processes { hanya root }; Until k2 > n
  4. The unmarked numbers are primes
  5. Reduction to determine number of primes.

Contoh pencarian bilangan prima dengan N = 25 dan banyak P = 4. Masing-masing proses membentuk array berukuran 6 elemen. Bilangan prima yang disebarkan ke seluruh proses adalah 2, 3, dan 5.

  1. [2] [3] [4] [5] [6] [7]
  2. [8] [9] [10] [11] [12] [13]
  3. [14] [15] [16] [17] [18] [19]
  4. [20] [21] [22] [23] [24] [25]

clip_image012

Gambar 6. Komunikasi data antar proses.

3. EKSPERIMEN PADA INFRASTURKTUR inGRID

3.1. Program Sieve of Eratosthenes

Program MPI untuk algoritma SoE dijalankan pada infrastruktur inGrid, yaitu pada mesin Hastinapura yang terdapat di UI. Eksperimen menggunakan jumlah prosesor 1, 2, 4, 8 dan 16, untuk jumlah bilangan prima yang akan dicari dari 1 sampai N, dengan N adalah 1, 10, 20, 40, 80, 100, 120, 150, 200 dan 400 juta. Eksperimen dilakukan untuk masing-masing N, diukur waktu eksekusinya untuk berbagai jumlah prosesor di atas. Maksimum memori yang digunakan untuk masing-masing prosesor adalah 400 MB, dan maksimum waktu eksekusi (time out) adalah 60 menit.

Dari eksperimen ini, akan diperoleh hasil akhir berupa jumlah bilangan prima yang terdapat pada rentang tersebut, beserta waktu eksekusinya, yaitu waktu saat program mulai dijalankan, sampai hasil diperoleh.

Tabel 1 berikut memperlihatkan rekapitulasi data hasil eksperimen. Waktu eksekusi yang tercatat dalam detik. Hasil eksperimen ini dituangkan dalam grafik untuk memudahkan analisis, seperti ditunjukkan pada Gambar 7 dan 8. Untuk lebih memperjelas gambar, beberapa seri data pada grafik tidak ditampilkan, seperti dapat dilihat pada gambar 9.

Percepatan (speed up) dari berbagai jumlah prosesor dihitung terhadap eksperimen menggunakan 1 prosesor, dengan menghitung perbandingan waktu eksekusinya, yaitu t1/tNP. Hasilnya dituangkan pada table 2 di bawah ini.

Rentang

Jumlah Processor

Jml bil prima

N (juta)

1

2

4

8

16

dlm rentang

1

0.029505

0.209939

0.209939

0.284228

0.327557

78498

10

0.674503

0.674503

0.476186

0.476186

0.76454

664579

20

1.443902

1.028436

0.853495

0.801884

0.809487

1270607

40

2.954333

2.063607

1.503859

1.320411

1.448884

2433654

80

6.145092

3.882123

2.513914

2.080314

1.792569

4669382

100

7.792314

4.801691

2.989546

2.431798

2.033791

5761455

120

9.54269

5.607161

3.602585

2.559509

2.386266

6841648

150

11.900224

6.881171

4.056835

3.066018

 

8444396

200

15.783852

9.121491

5.416781

3.916809

 

11078937

400

32.878467

18.093218

9.767608

 

 

21336326

Tabel 1. Waktu eksekusi algoritma SoE untuk berbagai jumlah prosesor dan data

Rentang data

Jumlah Processor

N (juta)

2

4

8

16

1

0.140540824

0.140540824

0.103807507

0.090075926

10

1

1.416469615

1.416469615

0.882233761

20

1.403978468

1.691752149

1.800637

1.783724754

40

1.431635481

1.964501326

2.237434405

2.039040392

80

1.582920479

2.444432069

2.953925225

3.428092308

100

1.622827042

2.606520856

3.20434263

3.83142319

120

1.701875512

2.648845204

3.728328363

3.99900514

150

1.729389373

2.933376388

3.881328812

 

200

1.730402628

2.913880402

4.029773216

 

400

1.817170776

3.366071509

 

 

Tabel 2. Percepatan (speed up) proses komputasi algoritma SoE

3.2 Program Bitonik Sort

Program MPI untuk bitonik sort dijalankan pada mesin Hastinapura di dalam infrastruktur inGrid Universitas Indonesia. Eksperimen menggunakan jumlah prosesor 1, 2, 4, 8 dan 16, untuk jumlah data yang akan diurutkan N, adalah 400 ribu, 800 ribu, 1, 10, 40, dan 80 juta. Pemilihan jumlah N ini bertujuan untuk mencari pada posisi mana performa sistem konsisten, dan pada posisi mana dapat terjadi penyimpangan. Eksperimen dilakukan untuk masing-masing N, diukur waktu eksekusinya untuk berbagai jumlah prosesor di atas. Maksimum memori yang digunakan untuk masing-masing prosesor adalah 400 MB, dan maksimum waktu eksekusi (time out) adalah 60 menit.

Output program adalah data jumlah prosesor dan node yang digunakan, jumlah data yang diolah, serta waktu eksekusi. Tabel 3 berikut memperlihatkan rekapitulasi data hasil eksperimen. Waktu eksekusi yang tercatat dalam detik. Hasil eksperimen ini dituangkan dalam grafik untuk memudahkan analisis, seperti ditunjukkan pada Gambar 13 sampai 15.

Sebagaimana program sebelumnya, percepatan proses eksekusi juga dihitung untuk program bitonik sort, untuk memperlihatkan performa multiprocessor dibandingkan dengan single processor, seperti dituangkan dalam Tabel 4 berikut ini.

Jml Data

Jumlah procesor

1

2

4

8

16

400 rb

0.145508

0.091369

0.060384

0.04316

0.031702

800 rb

0.307508

0.191594

0.126312

0.088012

0.258274

1 jt

0.388561

0.241023

0.160388

0.110778

0.277831

10 jt

4.791725

2.79589

1.798392

1.219792

0.930371

40 jt

20.118933

11.912527

7.700639

5.181174

3.607057

80 jt

42.255616

25.271351

16.15291

10.608337

7.083671

Tabel 3. Waktu Eksekusi Program Bitonik Sort

Jumlah data

Jumlah processor

2

4

8

16

400 rb

1.592531384

2.409711182

3.371362373

4.589868147

800 rb

1.604998069

2.434511369

3.493932646

1.190627009

1 jt

1.612132452

2.422631369

3.507564679

1.398551638

10 jt

1.713846038

2.664449686

3.928313188

5.150337876

40 jt

1.688888764

2.612631627

3.883083834

5.57765874

80 jt

1.672075862

2.61597545

3.983246007

5.965214364

Tabel 4. Percepatan Proses Eksekusi (speed up) Bitonik Sort

4. ANALISA

4.1. Program Sieve of Eratosthenes

Untuk jumlah prosesor 1, waktu eksekusi meningkat dengan bertambahnya jumlah data, seperti terlihat pada Gambar 5 di bawah ini. Menggunakan lebih dari 1 prosesor, waktu eksekusinya berubah (lebih cepat) tetapi tidak signifikan untuk data sampai 20 juta, yaitu antara 0.8 sampai 1.02 detik, untuk jumlah prosesor 2 sampai 16. Tetapi bila data kurang dari 10 juta, menggunakan 1 prosesor malah masih lebih baik, dibandingkan dengan 8 atau 16 prosesor. Untuk data 10 juta, performa terbaik dicapai dengan menggunakan 4 atau 8 prosesor.

Untuk jumlah data 20 juta sampai 40 juta, performa terbaik adalah menggunakan 8 prosesor, dan mulai dari jumlah data 80 juta dalam percobaan ini, performa terbaik ditunjukkan oleh 16 prosesor. Namun, eksekusi gagal (tidak mendapatkan hasil) pada saat jumlah data N mencapai 150 juta untuk 16 prosesor, dan 400 juta untuk 8 prosesor. Hal ini dimungkinkan karena maksimum memori yang diset untuk proses eksekusi adalah 400 MB, sehingga pada saat memori mencapai maksimum dari proses komputasi, maka proses eksekusi akan terhenti (over floap).

Bila diperhatikan lebih detil dari table 1 dan gambar 7-9, maka mulai jumlah data 80 juta, waktu eksekusi telah menunjukkan pola kestabilan dan fungsi eksponensial tertentu. Artinya, performa proses komputasi untuk multiprosesor sudah linear dengan waktu eksekusinya, dalam arti semakin banyak jumlah processor, semakin cepat waktu komputasinya. Overhead dari waktu komunikasi yang melebihi waktu komputasi tidak lagi mempengaruhi performa algoritma secara keseluruhan. Dengan kata lain, ada peningkatan performa yang signifikan dengan menggunakan multiprosesor dibandingkan dengan menggunakan satu prosesor (komputasi serial).

Percepatan komputasi dapat dilihat pada Tabel 2 dan gambar 10-12. Dapat dijelaskan bahwa percepatan komputasi secara signifikan dan konsisten juga dimulai dari jumlah data N=80 juta. Sedangkan pada data 10 dan 40 juta, percepatan cenderung menurun pada saat menggunakan 16 prosesor. Hal ini mungkin terjadi karena waktu untuk komunikasi dan pembagian kerja tiap-tiap prosesor mengalami overhead sehingga proses komputasi secara keseluruhan menjadi tidak optimal. Percepatan yang paling tinggi untuk data 10 sampai 40 juta dicapai dengan menggunakan 8 prosesor.

clip_image014

Gambar 7. Peningkatan waktu eksekusi dengan bertambahnya data

clip_image016

Gambar 8. Grafik waktu eksekusi algoritma SoE untuk berbagai jumlah prosesor dan data

clip_image018

Gambar 9. Waktu eksekusi untuk jumlah N yang dipilih

clip_image020

Gambar 10. Grafik percepatan waktu eksekusi algoritma SoE

clip_image022

Gambar 11. Grafik percepatan waktu eksekusi untuk data yang dipilih

clip_image024

Gambar 12. Grafik percepatan waktu eksekusi untuk data yang dipilih

Faktor-faktor eksternal juga dicurigai menjadi penyebab kurang presisinya bentuk grafik percepatan maupun waktu eksekusi seperti telah disajikan pada gambar 7-12. Faktor luar tersebut antara lain adalah proses yang dijalankan oleh masing-masing prosesor bisa jadi tidak seimbang, misalnya saat program ini dijalankan, ada beberapa prosesor yang terlibat pada komputasi program ini, juga tengah menjalankan proses komputasi pada tugas-tugas yang lain. Sehingga beban yang dialami oleh prosesor tersebut bisa jadi lebih berat dari prosesor lainnya yang idle, sehingga mengganggu atau memperlambat proses komputasi sesuai dengan memori yang terpakai.

Waktu ideal yang tepat untuk pengukuran kinerja komputasi adalah pada saat mesin hanya menjalankan satu tugas, yaitu tugas komputasi algoritma ini. Dengan demikian, masing-masing prosesor memiliki resource yang sama yang dimanfaatkan untuk komputasi, sehingga beban komputasi yang dijalankan seimbang.

4.2. Program Bitonik Sort

Sebagaimana program SoE, sekilas plot data waktu eksekusi seperti pada gambar 13 – 15, menunjukkan tendensi yang sama. Semakin besar jumlah data, maka proses eksekusi menghabiskan waktu semakin banyak. Seperti terlihat pada Gambar 14, terjadi anomaly untuk jumlah prosesor 16, yaitu waktu eksekusi justru menjadi lebih lambat untuk jumlah data 800 ribu dan 1 juta, sedangkan untuk jumlah data 400 ribu, waktu eksekusi konsisten dibandingkan dengan jumlah prosesor 1, 2, 4 dan 8. Perkiraan keanehan ini lebih kuat kepada jumlah prosesor yang diberdayakan untuk melakukan komputasi yang mencapai setengah kapasitas mesin Hastinapura, di mana mungkin saja sebagian prosesor yang terpakai, juga tengah menjalankan proses eksekusi program lainnya. Bila keadaan ideal, diharapkan grafik waktu yang dihabiskan untuk proses pada 16 prosesor akan di bawah grafik untuk 8 prosesor.

clip_image026

Gambar 13. Waktu Eksekusi Bitonik Sort terhadap jumlah data

Plot waktu eksekusi terhadap jumlah prosesor disajikan pada gambar 16 dan 17 di bawah ini. Gambar 17 memperlihatkan bagaimana inkonsistensi terjadi pada eksperimen menggunakan 16 prosesor. Seperti telah disebutkan, andaikan data konsisten, seharusnya grafik untuk seri 800 ribu dan 1 juta terus menurun proporsional seperti grafik untuk seri 400 ribu. Diperlukan beberapa kali percobaan dan dengan kondisi ideal untuk membuktikan hal tersebut. Namun karena keterbatasan waktu dan sumber daya yang dipakai bersama, maka kondisi ideal untuk eksperimen untuk saat ini belum dapat diperoleh.

Percepatan proses eksekusi dibandingkan dengan menggunakan single processor disajikan pada gambar 18 – 20, berdasarkan hasil eksperimen yang telah direkapitulasi pada table 4. Dari table percepatan secara umum, peningkatan waktu eksekusi hampir konstant terhadap jumlah data untuk masing-masing prosesor (garis horizontal menyatakan bahwa percepatan bersifat tetap/konstan).

clip_image028

Gambar 14. Waktu eksekusi untuk jumlah data 400 ribu sampai 1 juta

clip_image030

Gambar 15. Waktu eksekusi untuk jumlah data 10 – 80 juta

clip_image032

Gambar 16. Waktu eksekusi bitonik sort terhadap jumlah prosesor

clip_image034

Gambar 17. Waktu eksekusi bitonik sort untuk data 400 ribu – 1 juta terhadap jumlah prosesor

clip_image036

Gambar 18. Percepatan proses eksekusi terhadap jumlah data

clip_image038

Gambar 19. Percepatan proses eksekusi terhadap jumlah prosesor

clip_image040

Gambar 20. Percepatan proses ekseskusi untuk data 400 ribu, 800 ribu dan 1 juta

Bila diperhatikan dengan lebih detil, maka percepatan proses eksekusi menggunakan multiprosesor terhadap jumlah prosesor berbentuk linear. Hal ini dapat diartikan bahwa peningkatan waktu eksekusi bertambah secara linear seiring dengan pertambahan jumlah prosesor dalam orde 2^n, tetapi tidak akan linear untuk orde integer (misalnya 1, 2, 3, 4 prosesor dan seterusnya). Hal ini disebabkan bitonik sort memang bekerja berdasarkan orde tersebut, seperti telah dijelaskan pada bagian teori. Sekali lagi, anomaly yang terjadi seperti ditunjukkan pada gambar 18 untuk jumlah data 800 ribu dan 1 juta masih perlu dibuktikan dengan beberapa kali percobaan di dalam kondisi yang mendekati ideal.

5. KESIMPULAN

Analisa yang dilakukan terhadap algoritma SoE pada komputasi paralel telah menunjukkan bahwa performa terbaik komputasi tidak linear antara jumlah data dengan jumlah prosesor. Hal ini disebabkan adanya cost yang harus dikeluarkan untuk komputasi, berupa waktu komunikasi dan pembagian tugas untuk masing-masing prosesor. Performa terbaik baru tercapai secara linear setelah jumlah data mencapai 100 juta (dalam percobaan ini). Namun eksperimen lebih lanjut perlu dilakukan untuk memperoleh jumlah data terdekat yang lebih presisi dalam hal pencapaian performa terbaik yang linear tersebut.

Kapasitas maksimum memori proses yang terbatas, juga menyebabkan terbatasnya jumlah data maksimum yang dapat diproses dengan menggunakan lebih banyak prosesor. Eksperimen lebih lanjut diperlukan untuk membuktikan bahwa ada kaitan antara maksimum memori prosesor yang digunakan dengan besarnya jumlah data yang dapat diproses.

Pada percobaan bitonik sort, hasil eksperimen untuk jumlah data yang dipilih telah menunjukkan performa yang meningkat dengan bertambahnya jumlah prosesor dalam orde 2^n. Overhead waktu komunikasi antara prosesor tidak terlihat di sini. Mungkin overhead akan terjadi pada jumlah data kecil. Anomali yang terjadi masih perlu diselidiki dengan beberapa percobaan dalam kondisi yang mendekati ideal, di mana hanya proses komputasi program ini saja yang dilakukan oleh prosesor, sehingga hasilnya dapat lebih baik.

Secara umum, komputasi parallel menunjukkan peningkatan performa yang signifikan dengan semakin besarnya jumlah data yang diolah. Tetapi ada nilai ambang (threshold) dari jumlah data, di mana performa terbaik justru dicapai dengan menggunakan komputasi serial (1 prosesor). Nilai tersebut sangat berhubungan dengan overhead komunikasi yang terjadi pada saat pembagian tugas dan agregasi hasil komputasi di akhir proses jika menggukanan multiprosesor.

Program bitonik sort sangat cocok diterapkan pada system komputasi parallel untuk data berukuran besar, karena menunjukkan kestabilan performa dan konsistensi peningkatan waktu eksekusi secara konstan.

REFERENSI

  1. Michael J. Quinn. Parallel Programming in C with MPI and OpenMP. Oregon State University. 2001.
  2. http://www.nist.gov/dads/HTML/sieve.html. Tgl akses: 23/10/2008.
  3. http://en.wikipedia.org/wiki/Prime_number. Tgl akses: 21/10/2008.
  4. http://www-unix.mcs.anl.gov/mpi/. Tgl akses: 23/10/2008.
  5. H. Cormen et. all. Introduction to Algorithms, second edition. MIT Press. 2003.
  6. Grama et. all. Introduction to Parallel Computing, second edition. Pearson Education. 2003
  7. Harry Jordan and Gita Alaghband, Fundamentals of Parallel Processing: Algorithms Architectures, Languages, Prentice Hall, 2003.

1 Komentar »

  1. - said

    Tulisan yang bermanfaat. Bolehkah saya meminta alamat email anda?

RSS feed for comments on this post · TrackBack URI

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s