Analisis Waktu Bitonic Sort MPI Pada InGRID

image Pengurutan merupakan komponen yang penting dalam banyak aplikasi komputer, oleh karena itu, pengurutan menjadi topik yang populer dalam ilmu komputer. Pengurutan secara paralel telah menjadi subyek penelitian yang ekstensif dalam tiga dekade terakhir ini, karena pemrograman paralel dapat meningkatkan ketersediaan sumber daya komputasi, terutama memory dan processor. Bitonic Sort merupakan suatu algoritma pemrograman yang dirancang untuk bekerja secara paralel.Paper ini membahas penerapan algoritma Bitonic Sort dengan menggunakan Message Passing Interface (MPI) pada mesin Hastinapura dalam infrastruktur inGrid, dan menganalisa waktu komputasi paralelnya.

1. PENDAHULUAN

Pekerjaan mengurutkan data merupakan masalah mendasar pada hampir seluruh kegiatan pengolahan data, baik manual maupun berbantuan komputer. Dalam dunia komputasi, pengurutan data (sorting) menjadi topik tersendiri yang mendapat banyak perhatian, bahkan menjadi bahan ajar dalam dasar ilmu komputer. Semakin berkembangnya teknologi, teknik pengurutan data pun berkembang. Bitonic Sort merupakan salah satu teknik pengurutan paralel yang muncul pertama kali [1].

Pada dasarnya, pemrograman secara paralel ber-tujuan meningkatkan ketersediaan sumber daya kom-putasi, terutama memory dan processor. Asumsinya, dengan mengunakan dua komputer atau prosesor, diharapkan tenaga komputasi yang tersedia dapat berlipat ganda sebanyak dua kalinya. Namun dalam prakteknya kondisi ideal ini tidak selalu tercapai, mengingat pengaturan program untuk dapat bekerja secara paralel membutuhkan kerumitan dan beban kerja tersendiri. Dalam hal ini program parallel menimbulkan suatu permasalahan baru, yaitu apakah program lebih banyak bekerja atau bicara (berkomunikasi). Suatu titik yang ideal tercapai bila antara kedua sisi ini berjalan secara optimal.

Saat ini, perkembangan komputasi paralel sudah sedemikian pesat, tidak hanya berjalan pada satu mesin dengan beberapa prosesor saja, melainkan sudah berkembang ke dalam suatu infrastruktur yang terpisah oleh klaster-klaster, dan terhubung melalui jaringan internet berkecepatan tinggi. Seiring berkembangnya teknologi komputasi paralel seperti grid computing, algoritma Bitonic Sort pun dikembangkan untuk dapat diimplementasikan pada infrastruktur tersebut.

Makalah ini bertujuan melakukan analisa perhi-tungan waktu komputasi dari program Bitonic Sort yang berjalan secara paralel menggunakan MPI. Untuk itu, disusunlah suatu laporan teknis mengenai uji coba dan analisa performa komputasi Bitonic Sort yang dibagi ke dalam beberapa bagian sebagai berikut. Bagian 2 akan menjelaskan komunikasi data di MPI, algoritma Bitonic Sort dan mekanisme penghitungan waktu komputasinya. Hasil-hasil pengujian program yang dilakukan pada mesin Hastinapura di dalam klaster inGRID dan analisanya dibahas pada bagian 3. Dan bagian terakhir berisi kesimpulan dan saran mengenai topik bahasan pada makalah ini.

2. LANDASAN TEORI

2.1. Message Passing Interface (MPI)

Message Passing Interface (MPI) adalah suatu spesifikasi library pemrograman untuk meneruskan pesan (message-passing), yang diajukan sebagai standar oleh berbagai komite dari vendor, pelaksana dan pemakai [3,5]. 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 dalam berbagai bahasa pemrograman dan sistem telah 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 commun-cators, misalnya MPI_COMM_WOLRD yang mencakup keseluruhan proses. Paralelisme dalam MPI bersifat Multiple Instruction Multiple Data (MIMD).

Pemrograman paralel menggunakan MPI bersifat eksplisit, yaitu ditentukan dalam program secara jelas. Dalam melakukan komunikasi data antar proses, pembuat program perlu menentukan mekanisme apa yang digunakan dari fungsi-fungsi yang tersedia. Disediakan beberapa fungsi dasar untuk keperluan ini, yaitu MPI_Send (mengirim), MPI_Recv (menerima), dan MPI_Sendrecv (mengirim dan menerima sekali-gus). Fungsi-fungsi ini masuk dalam kelompok ko-munikasi titik-ke-titik (point-to-point). Komunikasi dalam MPI bersifat kooperatif, yaitu tiap-tiap proses saling bekerjasama.

Parameter data atau message dalam fungsi-fungsi komunikasi memiliki struktur dasar, yaitu:

  • Alamat buffer data untuk mengirim atau menerima.
  • Ukuran dari buffer data.
  • Jenis data pada buffer, berupa konstanta tertentu misalnya MPI_INTEGER, MPI_CHAR dan MPI_DOUBLE.
  • Proses tujuan, berupa suatu integer rank dari proses.
  • Tag dari message, dapat digunakan sebagai penanda oleh proses.

Operasi dari fungsi-fungsi komunikasi titik-ke-titik memiliki 2 mode, yaitu blocking dan non-blocking. Pada bentuk blocking maka proses akan menunggu operasi kirim dan terima data selesai, sedangkan non- blocking menggunakan event untuk memberitahu proses ketika terjadi kirim atau terima data. Dalam tiap mode adalah penting untuk menjaga agar setiap proses yang berkomunikasi tidak mengalami deadlock, yaitu saling tunggu yang tidak berkesudahan. MPI telah memiliki mekanisme agar deadlock tidak terjadi, tetapi dalam kondisi tertentu ini tidak terhindarkan, misalnya ketika buffer tujuan penuh atau tidak tersedia.

2.2. Algoritma Bitonic Sort

Bitonic Sort adalah suatu algoritma pengurutan paralel menggunakan sorting network [4]. Suatu bitonic sequence adalah suatu rangkaian (sequence) yang terurut menaik kemudian terurut menurun atau terurut menurun kemudian menaik. Contoh rangkaian bitonic misalnya <1,4,6,8,3,2> dan <9,8,3,2,4,6>. Bitonic Sort bergantung pada penyusunan rangkaian bitonic menjadi sebuah rangkaian terurut. Kompleksitas waktu dari Bitonic Sort sesuai dengan kedalaman jaringannnya, mengingat berjalan secara paralel, yaitu Θ(log2(n)).

Berikut tahap-tahap sorting atau pengurutan dalam Bitonic Sort seperti ilustrasi pada Gambar 1:

  • s = áa0,a1,…,an-1ñ adalah rangkaian bitonic sehingga : a0 ≤ a1 ≤ ··· ≤ an/2-1 dan an/2 ≥ an/2+1 ≥ ··· ≥ an-1.
  • Dengan demikian sub rangkaian 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
  • Lakukan pemecahan pada rangkaian bitonic menjadi dua sub rangkaian 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 bitonic merge.

clip_image002

Gambar 1. Skema proses dari Bitonic Sort.

Program Bitonic Sort yang digunakan sebagai uji coba memiliki tujuan pokok menyusun array lokal dari tiap-tiap proses menjadi sederetan array global yang berurutan. Array global ini terpecah-pecah di setiap proses dengan urutan yang sudah teratur. Pengurutan untuk array lokal menggunakan fungsi standar quicksort. Pengurutan secara global menggunakan mekanisme sorting network.

Sebagai contoh, terdapat 2 proses yaitu A dan B, masing-masing telah mempunyai local array (n/p) yang berisi angka terurut. A berisi angka ganjil, [ 1 3 5 7 ], dan B angka genap, [ 2 4 6 8 ]. Bitonic Sort di sini bertujuan agar array secara global terurut dari A s/d B, yaitu A berisi [ 1 2 3 4] dan B berisi [ 5 6 7 8 ].

Proses penggabungan dan pemecahan ini terdapat dalam fungsi Merge_split, untuk contoh array A dan array B dengan algoritma berikut:

  • Menyiapkan array C untuk penempatan hasil, dengan ukuran sebanding A atau B.
  • Membandingkan tiap-tiap elemen dari dari A dan B, keduanya sudah dalam keadaan terurut, dan menyimpannya di C.
  • Penentuan rangkaian bitonic, yaitu LOW atau HIGH, untuk A dan B yang berjalan paralel. Sehingga A akan mendapat hasil LOW, yaitu [ 1 2 3 4 ] dan B mendapat hasil HIGH, yaitu [ 5 6 7 8 ].

Bila proses yg terlibat lebih banyak, algoritma di atas ditambah dengan pengaturan agar antara 2 proses saling bertukar data dengan urutan yang tepat. Pertu-karan data berlangsung secara menyeluruh sesuai me-kanisme sorting network. Data dalam Bitonic Sort bersifat independen sehingga tidak dikenal istilah worst case atau best case, semua langkah tetap dijalankan secara lengkap meskipun array sudah terurut sejak awal.

clip_image004

Gambar 3. Kedalaman dan komparator untuk n = 8.

Proses A vs B

Rangkaian A vs B

Posisi A vs B

0 – 1

naik – naik

bawah – atas

2 – 3

turun – turun

atas – bawah

0 – 2

naik – naik

bawah – atas

1 – 3

naik – naik

bawah – atas

0 – 1

naik – naik

bawah – atas

2 – 3

naik – naik

bawah – atas

Tabel 1. Susunan Bitonic Sort untuk 4 Proses

Contoh Bitonic Sort untuk 4 proses diilustrasikan seperti pada Tabel 1. Di sini Proses A dan B saling bertukar data (menggunakan 1 komparator). Rangkaian bitonic bisa secara menarik atau menurun. Posisi array setiap pasang adalah atas atau bawah. Banyaknya pertukaran data (perbandingan) untuk 4 proses adalah 6 kali, dengan kedalaman (tahap) adalah 2. Perbandingan jumlah n, kedalaman, dan komparator dapat dilihat di Tabel 2 berikut.

Pada tabel di atas jumlah komparator yang digunakan sebanding dengan jumlah proses (n), menyebabkan biaya komunikasi meningkat sejalan besarnya array. Untuk meminimalkan biaya komunikasi pada jumlah data yang besar, beberapa penelitian berkembang, seperti Mihai Florin Ionescu [1], yang melakukan optimasi pada komparator. Optimasi tersebut dilakukan pada penyusunan data, secara adaptif, yang dapat menimalkan biaya komuni-kasi. Teknik ini diperkenalkan sebagai Adaptif Bitonic Sort. Program pada makalah ini tidak menggunakan teknik-teknik tersebut, tetapi berdasarkan ide awal Bitonic Sort yang dikemukakan oleh Butcher [7].

Banyak

n

Kedalaman

d = log2(n)

Komparator

c = (n * d * (d + 1)) / 4

2

1

2 * 1 * 2 / 4 = 1

4

2

4 * 2 * 3 / 4 = 6

8

3

8 * 3 * 4 / 4 = 24

16

4

16 * 4 * 5 / 4 = 80

32

5

32 * 5 * 6 / 4 = 240

Tabel 2. Banyak komparator untuk n = 2 s/d 32

2.3. Mekanisme Penghitungan Waktu

Pertukaran data antar 2 proses dalam program menggunakan fungsi MPI_Sendrecv, terdapat di fungsi Merge_split. Dengan demikian pencatatan statistik penggunaan waktu dapat dilakukan di sini. Fungsi MPI_Sendrecv adalah fungsi untuk mengirim dan menerima sekaligus. Fungsi ini bersifat blocking, yaitu menunggu pertukaran data selesai sebelum melanjutkan tahap berikutnya.

void Merge_split( … ) {

// hitung waktu run —

s_time[R_TIME] += Get_Delta();

MPI_Sendrecv(

local_list, list_size, mpi_t, partner, 0,

temp_list, list_size, key_mpi_t, partner, 0,

MPI_COMM_WORLD, &status);

// hitung waktu exchange —

s_time[X_TIME] += Get_Delta();

} /* Merge_split */

Besar pertukaran data yang terjadi pada setiap tahap atau kedalaman Bitonic Sort sebanding dengan besar elemen. Pada array dengan 64 elemen (n) diurutkan oleh 4 proses (p), maka setiap elemen mendapat 16 elemen (n/p). Setiap terjadi Exchange antar 2 proses melalui MPI_Sendrecv akan terjadi 2 * n/p, atau 32 elemen (kirim dan terima data). Dengan demikian total seluruh Exchange adalah n * log2(n).

Dalam pencatatan dibagi menjadi 2 waktu, yaitu saat eksekusi program secara lokal (Run) dan saat pertukaran data (Exchange). Waktu Run dihitung sejak awal program dijalankan hingga sesaat sebelum pertukaran data dilakukan. Waktu Exchange dihitung saat fungsi MPI_Sendrecv dijalankan. Pengambilan waktu secara presisi menggunakan fungsi MPI_Wtime yang berguna untuk mendapatkan waktu proses yang berjalan. Keluaran dari fungsi adalah angka pecahan (double) dengan satuan detik.

Pemecahan waktu eksekusi program dengan Run dan Exchange dianggap mencukupi sebagai sumber analisa penghitungan waktu. Waktu Run di sini merupakan waktu eksekusi program secara lokal, digunakan untuk mengukur seberapa efektif pemakaian sumber daya lokal (memori dan CPU) dalam suatu komputer. Waktu Exchange adalah waktu pertukaran data, yang menyatakan waktu untuk berkomunikasi antar proses. Bagian 3 akan menerangkan hasil-hasil eksperimen yang dilakukan untuk algoritma ini.

3. DATA DAN ANALISA

Percobaaan dilakukan pada mesin Hastinapura melalui console (shell). Beberapa kali percobaan dilakukan untuk melihat konsistensi data, karena hasil percobaan pada portal inGrid pada makalah sebelumnya berbeda. Disebabkan oleh portal inGrid sedang mengalami kesalahan, dan eksekusi yang dijalankan selalu memunculkan pesan error, maka data-data yang disajikan pada Tabel 3 – 7 berikut diperoleh dari eksekusi program pada console Unix saja.

Untuk melihat performa Bitonic Sort pada Hastinapura, dilakukan beberapa percobaan dengan menggunakan 1, 2, 4, 8 dan 16 prosesor, dengan ukuran elemen n dimulai dari 2000, dan bertambah dengan kelipatan 10 sampai 20.000.000 untuk setiap prosesor. Waktu eksekusi (Run) dan waktu pertukaran data (Exchange) diukur untuk setiap percobaan, yaitu waktu minimal, maksimal, dan rata-rata dari semua prosesor yang terlibat. Asumsi yang diambil adalah bahwa waktu maksimal menentukan waktu total seluruh program, sedangkan waktu rata-rata adalah waktu proses komputasi (Run dan Exchange) pada masing-masing prosesor yang diambil nilai rata-ratanya. Tabel 3 di bawah mengilustrasikan waktu eksekusi atau komputasi program secara keseluruhan.

Berdasarkan Table III, dibentuk beberapa tabel perbandingan sesuai dengan kriteria yang akan diukur, yaitu perbandingan antara waktu RUN jumlah pro-sesor, terhadap jumlah data, dan perbandingan antara data-data maksimum dengan rata-ratanya. Hal ini ditunjukkan pada tabel 4 sampai 7.

Data

Jumlah Proses

Kedala

man

Kompa

rator

Waktu RUN

Waktu EXCHANGE

min

max

rata-rata

min

max

rata-rata

2k

1

0

0

0.000571

0.000571

0.000571

0

0

0

20k

1

0

0

0.005774

0.005774

0.005774

0

0

0

200k

1

0

0

0.068182

0.068182

0.068182

0

0

0

2M

1

0

0

0.804055

0.804055

0.804055

0

0

0

20M

1

0

0

9.378709

9.378709

9.378709

0

0

0

2k

2

1

1

0.000346

0.000360

0.000353

0.000090

0.000398

0.000244

20k

2

1

1

0.002956

0.003036

0.002996

0.000271

0.001320

0.000796

200k

2

1

1

0.033847

0.034310

0.034078

0.003720

0.008161

0.005941

2M

2

1

1

0.412533

0.418587

0.415560

0.035348

0.043188

0.039268

20M

2

1

1

4.772902

4.801135

4.787019

0.351884

0.372898

0.362391

2k

4

2

6

0.000249

0.000290

0.000274

0.000372

0.001038

0.000620

20k

4

2

6

0.001633

0.001705

0.001660

0.00054

0.003777

0.001840

200k

4

2

6

0.018053

0.020005

0.018920

0.009552

0.029374

0.016628

2M

4

2

6

0.209747

0.222463

0.217702

0.108223

0.325055

0.183742

20M

4

2

6

4.271148

4.481539

4.413589

0.742426

1.151330

0.921586

2k

8

3

24

0.000185

0.000215

0.000192

0.000921

0.002232

0.001701

20k

8

3

24

0.001041

0.001650

0.001387

0.001819

0.005326

0.002867

200k

8

3

24

0.009982

0.019121

0.012387

0.017645

0.142965

0.126048

2M

8

3

24

0.114114

0.217066

0.144628

0.440352

0.752550

0.551298

20M

8

3

24

3.466228

4.523442

3.724951

2.286570

3.075677

2.568431

2k

16

4

80

0.000193

0.000258

0.000202

0.003074

0.103909

0.026162

20k

16

4

80

0.000685

0.001586

0.000785

0.004269

0.031509

0.007022

200k

16

4

80

0.005710

0.016375

0.005958

0.130500

0.307665

0.251660

2M

16

4

80

0.115733

0.331833

0.231037

1.607513

2.012869

1.776489

20M

16

4

80

1.825017

5.093939

3.701838

3.157474

5.550319

4.997287

Tabel 3. Data Hasil Percobaan Bitonic Sort

3.1. Analisa waktu rata-rata

Tabel 4 memperlihatkan kepada kita mengenai perbandingan waktu komparasi (RUN) untuk masing-masing ukuran data dan prosesor. Sedangkan Tabel 5 memperlihatkan perbandingan waktu pertukaran data (Exchange) di antara prosesor. Dari kedua tabel tersebut, dapat kita lihat bahwa untuk semua ukuran data, waktu eksekusi komparasi lebih kecil adalah pada jumlah prosesor 8 atau 16, sedangkan waktu komunikasi atau pertukaran data lebih cepat meng-gunakan 2 prosesor. Hal ini sebanding dengan jumlah pekerjaan yang harus dilakukan oleh tiap prosesor, yaitu bila menggunakan 2 prosesor, maka proses komparasi hanya terjadi 1 kali, dan kedalaman komparasi hanya 1 langkah. Semakin banyak jumlah prosesor, kedalaman semakin bertambah dan proses komparasi semakin membutuhkan banyak langkah (komparator). Hubungan antara kedalaman, langkah komparasi dan jumlah prosesor dapat dilihat pada Tabel 2. Waktu tercepat tercetak tebal dan berwarna merah. Untuk prosesor tunggal, tidak terjadi waktu pertukaran data antara prosesor, oleh karena itu pada Tabel 5 waktunya adalah nol.

data

Jumlah prosesor

1

2

4

8

16

2k

0.00057

0.00035

0.00027

0.00019

0.00020

20k

0.00577

0.00300

0.00166

0.00139

0.00079

200k

0.06818

0.03408

0.01892

0.01239

0.00596

2M

0.80406

0.41556

0.21770

0.14463

0.23104

20M

9.37871

4.78702

4.41359

3.72495

3.70184

Tabel 4. Perbandingan waktu komparasi rata-rata

data

Jumlah prosesor

1

2

4

8

16

2k

0.00000

0.00024

0.00062

0.00170

0.02616

20k

0.00000

0.00080

0.00184

0.00287

0.00702

200k

0.00000

0.00594

0.01663

0.12605

0.25166

2M

0.00000

0.03927

0.18374

0.55130

1.77649

20M

0.00000

0.36239

0.92159

2.56843

4.99729

Tabel 5. Perbandingan waktu pertukaran rata-rata

Gambar 4 mengilustrasikan representasi data-data pada Tabel 4. Dari grafik dapat disimpulkan, semakin banyak jumlah prosesor, maka waktu eksekusi kom-parasi semakin kecil. Dari data-data tersebut, dapat dihitung percepatan proses komparasi, yaitu,

(1)

clip_image006

Dengan t1 dan tn masing-masing adalah waktu komparasi untuk 1 prosesor dan n prosesor. Sedangkan efisiensi dapat dihitung dari,

(2)

clip_image008

data

Jumlah prosesor

1

2

4

8

16

2k

1.00

1.62

2.08

2.97

2.83

20k

1.00

1.93

3.48

4.16

7.36

200k

1.00

2.00

3.60

5.50

11.44

2M

1.00

1.93

3.69

5.56

3.48

20M

1.00

1.96

2.12

2.52

2.53

Tabel 6. Percepatan waktu komparasi rata-rata

data

Jumlah prosesor

1

2

4

8

16

2k

80.88%

52.10%

37.17%

17.67%

20k

96.36%

86.96%

52.04%

45.97%

200k

100.04%

90.09%

68.80%

71.52%

2M

96.74%

92.33%

69.49%

21.75%

20M

97.96%

53.12%

31.47%

15.83%

Tabel 7. Efisiensi komparasi rata-rata

Dari persamaan (1) dan (2), dapat dihitung percepatan (speed up) dan efisiensi waktu komparasi dengan menggunakan n prosesor seperti disajikan pada Tabel 6 dan 7 berikut ini.

Data tabel 7 jelas memperlihatkan bahwa efisiensi tertinggi dicapai oleh jumlah prosesor dua. Hal ini disebabkan karena dengan menggunakan dua prosesor, maka waktu pertukaran data antar prosesor tidak banyak mempengaruhi waktu komparasi, karena kedalaman bitonic-nya adalah 1. Sehingga begitu selesai melakukan exchange (pertukaran), maka prosesor segera melakukan komparasi data berikutnya. Sehingga efisiensi waktu rata-rata keseluruhan kompa-rasi menjadi lebih cepat.

image

Gambar 4. Grafik waktu komparasi rata-rata terhadap jumlah prosesor

Berbeda dengan menggunakan 8 atau 16 prosesor, percepatan proses komparasi memang lebih tinggi, karena jumlah data array bitonic yang dikomparasikan pada masing-masing prosesor lebih kecil, sehingga proses komparasi menjadi lebih cepat. Namun karena banyaknya proses exchange yang terjadi, maka waktu pertukaran menjadi lebih tinggi. Oleh karena itu grafik pada Gambar 5 menunjukkan garis yang monoton naik seiring dengan bertambahnya jumlah prosesor, yang berarti semakin banyak jumlah prosesor yang digunakan, semakin tinggi waktu pertukaran yang dibutuhkan, karena semakin dalam tingkat kedalaman proses pengurutan data.

Gambar 7 menunjukkan total waktu eksekusi keseluruhan dari data waktu rata-rata pertukaran dan komparasi. Untuk data yang besar, maka total waktu eksekusi terlihat paling cepat dilakukan dengan menggunakan 2 prosesor. Pengaruh terbesar dari tidak sesuainya harapan bahwa semakin banyak jumlah prosesor, maka waktu eksekusi semestinya semakin cepat tidak terjadi, adalah karena besarnya waktu pertukaran yang dibutuhkan oleh banyak prosesor, karena semakin banyak prosesor, semakin tinggi tingkat kedalaman proses sorting paralel Bitonic Sort. Sehingga semakin banyak pula waktu pertukaran yang dibutuhkan. Total waktu eksekusi ini akan dibahas kembali pada analisa data waktu maksimum di bagian berikut.

image

Gambar 5. Grafik waktu pertukaran rata-rata terhadap jumlah prosesor

clip_image014

Gambar 6. Efisiensi waktu komparasi untuk masing-masing prosesor

image

Gambar 7. Total rata-rata waktu eksekusi program secara keseluruhan

3.2. Analisa Waktu Maksimum

Di samping melihat waktu rata-rata komputasi keseluruhan, dilakukan pula analisa terhadap waktu maksimum dari suatu prosesor, yang mencerminkan elapsed time (konsumsi waktu) yang dihabiskan oleh program pada saat menjalankan tugas. Asumsi ini diambil karena waktu komputasi keseluruhan adalah saat di mana program mulai dijalankan, sampai kepada program memberikan suatu hasil. Karena program Bitonic Sort berjalan secara paralel, maka total elapsed time-nya adalah total waktu run dan exchange yang masing-masing maksimum di antara prosesor. Bisa saja waktu maksimum untuk run dan exchange tidak berada pada satu prosesor yang sama. Data mengenai hal ini disajikan pada Tabel 8 sampai 10.

data

Jumlah prosesor

1

2

4

8

16

2k

0.00057

0.00036

0.00029

0.00022

0.00026

20k

0.00577

0.00304

0.00171

0.00165

0.00159

200k

0.06818

0.03431

0.02001

0.01912

0.01638

2M

0.80406

0.41859

0.22246

0.21707

0.33183

20M

9.37871

4.80114

4.48154

4.52344

5.09394

Tabel 8. Perbandingan waktu komparasi maksimum

data

Jumlah prosesor

1

2

4

8

16

2k

0

0.00040

0.00104

0.00223

0.10391

20k

0

0.00132

0.00378

0.00533

0.03151

200k

0

0.00816

0.02937

0.14297

0.30767

2M

0

0.04319

0.32506

0.75255

2.01287

20M

0

0.37290

1.15133

3.07568

5.55032

Tabel 9. Perbandingan waktu pertukaran maksimum

data

Jumlah prosesor

1

2

4

8

16

2k

1

1.59

1.97

2.66

2.21

20k

1

1.90

3.39

3.50

3.64

200k

1

1.99

3.41

3.57

4.16

2M

1

1.92

3.61

3.70

2.42

20M

1

1.95

2.09

2.07

1.84

Tabel 10. Percepatan proses komparasi

Efisiensi proses komparasi untuk waktu komparasi maksimum tetap masih dicapai oleh jumlah prosesor 2, sehingga dapat disimpulkan bahwa kedalaman proses pengurutan data sangat berpengaruh terhadap waktu komparasi yang berjalan di masing-masing prosesor. Karena dengan semakin dalamnya proses sorting paralel bitonic, maka waktu komparasi secara keseluruhan menjadi tidak efisien, walaupun dari segi percepatan proses komparasi menggunakan prosesor lebih banyak lebih cepat.

3.3. Analisa Waktu Komputasi Keseluruhan

Walaupun secara rata-rata maupun maksimum, waktu komparasi tercepat ditunjukkan oleh jumlah prosesor yang banyak (8 atau 16 prosesor), namun pengukuran performa bitonic secara keseluruhan adalah waktu komparasi dan waktu pertukaran yang dihabiskan selama proses. Waktu pertukaran yang besar untuk jumlah prosesor yang besar dapat memperbesar total waktu komputasi, sehingga menurunkan kecepatan program secara keseluruhan. Hal ini diilustrasikan pada Tabel 12 dan 13 berikut ini.

data

Jumlah prosesor

1

2

4

8

16

2k

0.0006

0.0006

0.0009

0.0019

0.0264

20k

0.0058

0.0038

0.0035

0.0043

0.0078

200k

0.0682

0.0400

0.0355

0.1384

0.2576

2M

0.8041

0.4548

0.4014

0.6959

2.0075

20M

9.3787

5.1494

5.3352

6.2934

8.6991

Tabel 12. Elapsed Time rata-rata

data

Jumlah prosesor

1

2

4

8

16

2k

0.0006

0.0008

0.0013

0.0024

0.1042

20k

0.0058

0.0044

0.0055

0.0070

0.0331

200k

0.0682

0.0425

0.0494

0.1621

0.3240

2M

0.8041

0.4618

0.5475

0.9696

2.3447

20M

9.3787

5.1740

5.6329

7.5991

10.6443

Tabel 13. Elapsed Time maksimum.

Pengaruh waktu pertukaran yang sangat signifikan telah menurunkan performa Bitonic Sort pada jumlah prosesor yang besar, sehingga performa program tidak sebanding dengan bertambahnya jumlah prosesor. Menurut waktu rata-rata, total waktu yang dibutuhkan untuk pengurutan data berjumlah besar dicapai oleh jumlah prosesor 2 (20M) dan pengurutan data sedang (20k – 2M) dicapai oleh jumlah prosesor 4. Sedangkan untuk jumlah data kecil, maka menggunakan prosesor tunggal lebih baik. Sedangkan menurut perhitungan waktu maksimum, mulai jumlah data 20k, maka waktu pengurutan data keseluruhan lebih cepat dengan menggunakan 2 prosesor saja.

image

Gambar 8. Elapsed time keseluruhan Bitonic Sort diukur dengan waktu maksimum prosesor.

4. KESIMPULAN

Program pengurutan Bitonic Sort yang dirancang secara paralel, tidak menjamin semakin cepatnya waktu komputasi secara keseluruhan bila menggunakan semakin banyak prosesor. Hal ini disebabkan karena semakin besar pula waktu yang dibutuhkan untuk pertukaran. Program Bitonic Sort memiliki waktu komputasi keseluruhan paling cepat dengan menggunakan 2 prosesor, karena waktu eksekusi (komparasi) dan waktu pertukaran (koordinasi/ komuni-kasi) dari 2 prosesor lebih kecil, yang berkorelasi dengan tingkat kedalaman proses sorting paralel.

Secara umum, Bitonic Sort memiliki waktu komunikasi (overhead) yang besar dengan semakin banyaknya prosesor yang digunakan. Kesimpulan ini diperoleh dari serangkaian eksperimen dan simulasi program pada mesin Hastinapura dalam infrastruktur inGrid.

Saran

Meskipun demikian, kebenaran dari simpulan ini masih perlu divalidasi kembali dengan menjalankan program pada portal inGrid, mengingat dari hasil simulasi pertama [8], waktu eksekusi secara keseluruhan lebih cepat jika menggunakan jumlah prosesor yang besar. Namun karena waktu yang terbatas dan sistem yang tidak stabil, maka validasi tersebut belum dapat dijalankan.


REFERENSI

  1. Mihai Florin Ionescu, Klaus E. Schauser. “Optimizing Parallel Bitonic Sort”, 1997.
  2. Michael J. Quinn, “Parallel Programming in C with MPI and OpenMP”, Oregon State University, 2001.
  3. Message Passing Interface Forum, “A Message-Passing Interface Standard Version 2.1”, June 2008.
  4. T. H. Cormen, C.E. Leiserson, et. al., “Introduction to Algorithms” 2nd edition, The MIT Press, 2003.
  5. Ananth Grama, Anshul Gupta, et. al. “Introduction to Parallel Computing”, second edition. Pearson Education, 2003.
  6. Harry Jordan and Gita Alaghband, “Fundamentals of Parallel Processing: Algorithms Architectures, Languages”, Prentice Hall, 2003.
  7. K.E. Batcher. “Sorting Networks and their Applications”, AFIPS Spring Joint Computing Conference, Vol. 32, 1968.
  8. Maykada H.K., Surya Agustian, “Implementasi Algoritma Sieve of Eratosthenes dan Bitonic Sort Berbasis MPI pada Sistem inGrid”, Topik dalam Komputasi Grid, 2008

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