ALGORITMA SIEVE OF ERATOSTHENES PARALEL BERBASIS MPI PADA SISTEM KOMPUTASI PARALEL IN-GRID

ALGORITMA SIEVE OF ERATOSTHENES PARALEL BERBASIS MPI PADA SISTEM KOMPUTASI PARALEL IN-GRID Maykada Harjono K1, Surya Agustian2 1

Kementerian Komunikasi dan Informatika Jl. Medan Merdeka Barat 9, Jakarta Pusat 2 Teknik Informatika, FST UIN Suska Riau Jl. HR Soeberantas km 11,5 Panam, Pekanbaru, Riau 1 [email protected], [email protected]

Abstrak Komputer memiliki keterbatasan dalam menentukan bilangan prima mulai dari yang pertama, sampai besaran tertentu saja. Salah satu algoritma untuk menentukan urutan bilangan prima adalah Sieve of Eratosthenes (SoE), yang dapat mempersingkat pekerjaan mencari bilangan prima dari urutan bilangan integer. Namun, kemampuan komputasi yang terbatas pada satu komputer tunggal menyebabkan memori stack pada angka tertentu yang cukup besar. Di samping itu, prosesnya pun akan semakin lambat. Pemrograman secara paralel dapat meningkatkan ketersediaan sumber daya komputasi, terutama sumber daya memori dan prosesor, sehingga dapat mengatasi masalah di atas. Salah satu mekanisme paralelisme ini dengan menggunakan Message Passing Interface (MPI). Penelitian ini dilakukan untuk mengetahui kemampuan dan performa dari komputasi parallel dalam menentukan bilangan prima dengan menggunakan algoritma Sieve of Eratosthenes secara paralel dengan MPI. Pengujian dan analisa dilakukan pada mesin Hastinapura di lingkungan cluster inGRID (Indonesia GRID). Hasil yang diperoleh, menunjukkan bahwa sampai 16 prosesor, performa sebanding dengan jumlah prosesor yang terlibat, dan sebanding dengan limit bilangan prima yang akan ditemukan. Kata kunci : sieve of eratosthenes, MPI, message passing interface, komputasi paralel

1.

Pendahuluan

Bilangan prima banyak digunakan dalam berbagai algoritma, sebagai basis bilangan untuk dasar kalkulasi bermacam-macam formula matematika. Antara lain sebagai base bilangan pada algoritma winnowing [1], algoritma berbagai macam sistem enkripsi seperti RSA [2], dan lain-lain. Algoritma Sieve of Eratosthenes adalah suatu algoritma untuk menentukan deretan bilangan prima dari sekelompok urutan bilangan asli yang ditentukan. Semakin besar rentang batas bilangan asli (integer) tersebut, maka algoritma akan semakin berat dijalankan oleh komputer. Dengan berkembangnya teknologi pemrograman parallel, membagi tugas komputasi metode sieve of Eratosthenes ke dalam beberapa sumber daya komputasi menjadi hal yang dapat meningkatkan performa komputasi dan waktu eksekusinya. Hasil pengolahan dari proses-proses yang tersebar kemudian dikumpulkan sebagai hasil akhir. Tujuan dari penelitian ini adalah melakukan uji coba komputasi tersebar, yang dimulai dari program

yang dirancang secara sekuensial menjadi paralel. Pada bagian 2 akan dijelaskan algoritma Sieve of Eratosthenes untuk mencari bilangan prima, 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 terakhir. 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, MD5, dan sebagainya. 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 [4]. Diperkenalkan pertama kali oleh Eratosthenes of Cyrene (276 BC - 194 BC). Cara kerjanya sebagai berikut: 1) Inisialisasi suatu array sejumlah N dengan 0. 2) Ambil bilangan prima pembagi awal, yaitu 2, tandai setiap elemen array kelipatan 2 dengan 1. Sehingga elemen yang ditandai: {2} {4} {6} {8} ... {N}. 3) Lanjutkan dengan bilangan prima berikutnya, yaitu 3, tandai setiap elemen array kelipatan 3 dengan 1. Sehingga elemen yang ditandai: {3} {6} {9} {12} ... {N}. 4) 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. 5) Elemen array yang tidak ditandai merupakan bilangan prima. Bentuk pseudocode dari tahap-tahap di atas yaitu [4]: a. Create list of unmarked natural numbers 2, 3, …, n b. k ← 2 c. Repeat i. Mark all multiples of k between k2 and n ii. k ← smallest unmarked number > k Until k2 > n d. 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 Message Passing Interface Message Passing Interface (MPI) adalah suatu spesifikasi library pemrograman untuk messagepassing, yang diajukan sebagai standar oleh berbagai komite dari vendor, pelaksana dan pemakai.[3] MPI digunakan secara luas mengingat: a) telah memiliki standar; b) dirancang berkinerja tinggi pada mesinmesin paralel; c) tersedia secara bebas maupun komersial; d) dikembangkan banyak pihak; e) informasi penerapan dan pengujian tersedia. Dalam pemodelan menggunakan messagepassing, suatu proses (process) adalah sebuah pencacah program dan ruang alamat [5]. 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 [6], 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.

Gambar 1. Operasi penjumlahan pada MPI reduce Proses komputasi utama pada MPI dilakukan oleh processor 0, termasuk pembagian tugas dan pengumpulan kembali hasil-hasil operasi dari komputasi yang dilakukan oleh prosesor paralel lainnya, seperti yang dapat dilihat pada Gambar 1. 2.3 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’.

prima yang disebarkan ke seluruh proses adalah 2, 3, dan 5. 0. [2] [3] [4] [5] [6] [7] 1. [8] [9] [10] [11] [12] [13] 2. [14] [15] [16] [17] [18] [19] 3. [20] [21] [22] [23] [24] [25]

Gambar 2. Perbandingan array global dan array lokal Setelah array global dibagi-bagi menjadi arrayarray lokal dari masing-masing proses seperti Gambar 2, 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, seperti diperlihatkan prosesnya pada Gambar 3. Berikut penyesuaian pseudocode dari tahaptahap di atas: a. Create list of unmarked natural numbers 2, 3, …, n b. k ← 2 c. Repeat i. Mark all multiples of k between k2 and n ii. k ← smallest unmarked number > k { hanya root } iii. Process 0 broadcasts k to rest of processes { hanya root } Until k2 > n d. The unmarked numbers are primes e. 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

Gambar 3. Komunikasi data antar proses [7] 3.

Eksperimen pada Infrastruktr inGRID

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. 3.1

Data Pengujian

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 5 dan 6. 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.

3.2

Analisa

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 prosesor 1, waktu eksekusi meningkat dengan bertambahnya jumlah data, seperti terlihat pada Gambar 4 di bawah ini. Menggunakan lebih dari 1 prosesor, waktu eksekusinya berubah (lebih cepat) tetapi tidak signifikan

Tabel 1. Perbandingan waktu eksekusi algoritma SoE untuk berbagai jumlah prosesor dan data Rentang data N (juta)

Jumlah Processor 4

1

2

1 10 20 40 80 100 120 150 200 400

0.030 0.675 1.444 2.954 6.145 7.792 9.543 11.900 15.784 32.878

0.210 0.675 1.028 2.064 3.882 4.802 5.607 6.881 9.121 18.093

0.210 0.476 0.853 1.504 2.514 2.990 3.603 4.057 5.417 9.767

8

16

0.284 0.476 0.802 1.320 2.080 2.432 2.560 3.066 3.917

0.328 0.765 0.809 1.449 1.793 2.034 2.386

Jml bil prima ditemukan 78,498 664,579 1,270,607 2,433,654 4,669,382 5,761,455 6,841,648 8,444,396 11,078,937 21,336,326

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

Jumlah Processor

N (juta)

2

4

8

16

1 10 20 40 80 100 120 150 200 400

0.141 1.000 1.404 1.432 1.583 1.623 1.702 1.729 1.730 1.817

0.141 1.416 1.692 1.965 2.444 2.607 2.649 2.933 2.914 3.366

0.104 1.416 1.801 2.237 2.954 3.204 3.728 3.881 4.030

0.090 0.882 1.784 2.039 3.428 3.831 3.999

Sedangkan pada 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 4-6, 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).

Gambar 4. Peningkatan waktu eksekusi dengan bertambahnya data

Percepatan komputasi dapat dilihat pada Tabel 2 dan gambar 5-6. 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.

Gambar 5. Grafik waktu eksekusi untuk beberapa jumlah data N

Gambar 6. Grafik percepatan waktu eksekusi untuk beberapa jumlah data N Faktor-faktor eksternal juga dicurigai menjadi penyebab kurang presisinya bentuk grafik percepatan maupun waktu eksekusi seperti telah disajikan pada gambar 4-6. 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.

Kesimpulan

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. 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. Saran 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.

DAFTAR PUSTAKA [1] Schleimer, Saul, Daniel S. Wilkerson, dan Alex Aiken. Winnowing: Local Algorithms for Document Fingerprinting. San Diego: In Proceedings of the ACM SIGMOD International Conference On Management Of Data. 2003 [2] Rivest, R.; A. Shamir; L. Adleman (1978). A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM 21 (2): 120–126 [3] Quinn, Michael J., 2001, Parallel Programming in C with MPI and OpenMP. Oregon State University Press.

[4] http://www.nist.gov/dads/HTML/sieve.html. (diakses tanggal 23/10/2008). [5] Grama et. all. 2003, Introduction to Parallel Computing, second edition, Pearson Education. [6] ___,Internet: http://www-unix.mcs.anl.gov/mpi/. diakses: 23/10/2008. [7] Harry Jordan and Gita Alaghband, 2003, Fundamentals of Parallel Processing: Algorithms Architectures, Languages, Prentice Hall.