KINERJA KOMUNIKASI DATA KOLEKTIF BROADCAST PADA PC CLUSTER. Ade Jamal *, Pandriya Sistha **

Kembali kembali

Risalah Lokakarya Komputasi dalam Sains dan Teknologi Nuklir XVII, Agustus 2006 (435-444)

KINERJA KOMUNIKASI DATA KOLEKTIF BROADCAST PADA PC CLUSTER Ade Jamal *, Pandriya Sistha** ABSTRAK KINERJA KOMUNIKASI DATA KOLEKTIF BROADCAST PADA PC CLUSTER. sejumlah pc yang dihubungkan melalui jaringan dan perangkat lunaknya menjadi sebuah kesatuan sistem yang dikenal sebagai PC Cluster sering digunakan untuk mendapatkan kemampuan dan kinerja komputasi yang lebih tinggi dibanding sebuah pc tunggal [1]. Kemampuan komputasi kinerja tinggi dari PC Cluster yang telah ada bahkan telah sudah bisa mengalahkan kinerja dari mesin komersial kelas supercomputer yang harganya jauh lebih mahal, sehingga dalam satu dekade terakhir jumlah mesin komputasi kinerja tinggi (high performance computing - hpc) yang masuk 500 tercepat didunia dari kelas arsitektur ini bertambah banyak. Faktor biaya yang murah yang manjadi unggulan harus dilihat imbang dengan faktor kesulitan dan faktor kinerjanya. Hasil pengkajian dan percobaan memperlihatkan bahwa seringkali komunikasi data menjadi hal yang penting dan menentukan faktor kesulitan dan kinerja tadi. Kajian ini akan memperlihatkan hasil penelitian sebelumnya[2,3,4] untuk meningkatkan kinerja komunikasi data dalam rangka meningkatkan kinerja komputasi berbasis PC Cluster ini dengan memperhatikan faktor-faktor tersebut diatas. Komunikasi data yang dipilih adalah komunikasi data kolektif broadcast, dimana data dari satu buah pc, yang dalam dunia cluster disebut node, dikirim ke semua node lainnya. Kata-kata Kunci: Komputasi Kinerja Tinggi, PC Cluster, Algoritma Komputasi

ABSTRACT PERFORMANCE OF COLLECTIVE DATA COMMUNICATION – BROADCAST- ON PC CLUSTER A Number of PC (Personal Computer) connected through networking and related software is combined into a unified system, well known as PC Cluster, which is frequently built to provide greater computational power than a single PC. Existing PC Cluster around the world, nowadays can perform better than much more expensive supercomputer. In TOP 500 the fastest computer in the world, High Performance Computing (HPC) machines in category Cluster put a side supercomputer in the last decade. Low cost factor is the most important advantage of PC Cluster, however, we must consider too two coupled factor, i.e., difficulty- and performance factor of building PC Cluster. Previous experiments and assessments have shown that data communication between PC in cluster is often a significant effect on difficulty and overall performance factors. This article will show the results of some effort to increase the performance of data communication in PC Cluster. We limited ourselves in collective data communication, more specific in broacast data communication where data form one PC node sends to all other node in PC Cluster. Keywords: High Performance Computing (HPC), PC Cluster, Computational Algorithms

*

P3TIE, BPP Teknologi Gd.II. Lt. 4, Jl. MH Thamrin 8 Jakarta 10340, e-mail: [email protected] Teknik Informatika, Fakultas Teknik, Universitas Al-Azhar Indonesia

**

435


LATAR BELAKANG Sistem Komputasi Kinerja Tinggi (HPC systems) menjadi semakin mudah terjangkau untuk dunia riset maupun industri karena dua alasan. Yang pertama karena semakin banyak diterimanya konsep Open Source untuk piranti lunak. Alasan kedua adalah diperkenalnya teknologi cluster di awal tahun 90-an, dan cepatnya perkembangan teknologi ini dalam dua dekade ini. Dua alasan ini menyebabkan HPC yang sebelumnya hanya didominasi oleh produsen supercomputer, dapat dibuat dengan teknologi clustering dan open source software dengan harga yang jauh lebih murah dari supercomputer[5]. Teknologi tersebut di artikel ini disebut sebagai PC Cluster. PC Cluster termasuk dalam kategori arsitektur Massively Paralel Processor (MPP), yaitu tipe mesin HPC yang terdiri dari sejumlah besar bahkan sangat besar (bisa mecapai 1000-an processor) dimana setiap processor, yang biasanya disebut computing node, memiliki sendiri CPU, memory, sistem operasi dan Input/Output system, dan bisa berkomunikasi antar node melalui sebuah sistem message passing. Yang membedakan PC Cluster dengan mesin supercomputer tipe MPP adalah node yang digunakan PC Cluster harus dari barang komputer yang tersedia mudah dipasaran atau barang komoditas atau istilah yang sering dipakai COTS system (Commodity Off The Shelf) dan menggunakan open source software seperti Linux[1]. Definisi Cluster dalam dunia Teknologi Informasi dapat memiliki beberapa pengertian. Secara umum definisi Cluster adalah sejumlah komputer (PC ataupun workstation) yang digabungkan sebagai satu kesatuan dengan bantuan piranti lunak dan jaringan computer. Kegunaan dari PC Cluster dapat dibedakan dalam tiga jenis. Pertama digunakan untuk meningkatkan ketersediaan dari sistem yang handal (reliable) atau dikenal dengan High Availability (HA). Hal ini diperlukan untuk sistem yang menjalankan mission-critical dimana kontinuitas dari fungsi sangat kritis. Yang kedua adalah Load Balancing Clusters, yang umumnya digunakan pada web-server yang sangat sibuk seperti search engine Google. Disini beberapa computer node menjadi host dari website yang sama, dan jika ada permintaan untuk mengkakses ke halaman web ini, maka akan diarahkan ke computer node yang bebannya lebih rendah. Yang ketiga adalah untuk komputasi kinerja tinggi atau High Performance Cluster (HPC), yang merupakan tujuan dari pengguna tradional dari PC Cluster, seperti peneliti, industri riset dan pengembangan. Dalam hal ini Cluster digunakan dengan cara menjalankan program secara paralel untuk aplikasi yang sangat banyak memakan waktu (time consuming). Sebuah project bernama Beowolf [1] pada tahun1993 diakui sebagai HPC Cluster pertama yang berhasil membuat sebuah alternatif murah dari supercomputer besar yang dibangun dari COTS (commodity of the self) computer. Beowolf cluster

436


pada waktu itu terdiri dari 16 buah PC-DX4 digabungkan dengan channel bonded Ethernet. Dewasa ini istilah Beowolf Cluster digunakan untuk PC Cluster berbasis computer komoditas yaitu yang mudah didapat dipasaran setempat, menggunakan open source software seperti Linux, dan memiliki kemampuan skalabilitas yang tinggi untuk mendapatkan komputasi kinerja tinggi. HPC Cluster dibutuhkan oleh hampir semua industri yang memerlukan sistem komputer dengan kemampuan kinerja tinggi. Beberapa contoh pengguna intensif dari HPC Cluster adalah Life science research untuk simulasi molekul protein untuk penelitian penyakit Alzheimer; Eksplorasi Minyak dan Gas untuk analisa data seismogram yang sangat besar jumlah datanya (terabytes) untuk menentukan lokasi sumber minyak; simulasi untuk predikisi gempa bumi; Graphical rendering untuk pekerjaan rekayasa untuk memanipulasi grafik beresolusi tinggi; simulasi astrofisis, simulasi cuaca dan iklim, analisa model financial, special effects dalam dunia film; dan juga di bidang teknologi nuklir sperti untuk simulasi reaktor fusi nuklir.

PEGOLAHAN DATA PARALEL HPC Cluster untuk komputasi kinerja tinggi menggunakan prinsip dasar pengolahaan data secara paralel dimana sebuah tugas dipecah menjadi beberapa tugas atau proses yang lebih kecil yang kemudian dijalankan secara paralel[6]. Hasil dari proses yang lebih kecil ini digabungkan kembali sehingga menjadi hasil tugas besar yang aslinya. Dengan diolahnya data secara paralel, maka sebuah pekerjaan secara teoretis dapat diselesaikan dengan kecepatan diharapkan sebanding dengan jumlah mesin (node) dalam mesin paralelnya. Tidak semua permasalahan dapat dipecah dan dijalankan secara paralel karena adanya ketergantungan hasil antara tugas-tugas kecil tersebut. Dalam hal ini, permasalahan tidak mudah dijalankan secara optimal pada HPC Cluster karena selain sebuah proses yang memerlukan data dari proses lainnya, sehingga harus menunggu proses asal data tersebut selesai, juga data hasil antara tugas-tugas kecil tersebut harus ditransfer antara proses dengan menggunakan jalur komunikasi data. Komunikasi data ini adalah salah satu biaya yang harus dibayar oleh pengolahan data secara paralel, sehingga kelipatan percepatan (dikenal dalam teknologi komputasi paralel dengan speed-up) tidak dapat berbanding lurus dengan jumlah node. Untuk permasalahan yang dapat diolah secara paralel dengan mudah, seperti pengolahan grafik (rendering) dan permasalahan probabilitas, biasanya tidak banyak membutuhkan komunikasi data. Karena itu masalah ini sering dikategorikan sebagai embrassingly parallel problem. Pada kenyataanya kebanyakan permasalahan fisis, yang mencari penyelesaian persamaan diferensial[10] dan integral, tidak masuk dalam kategori yang disebut di atas. Sistem ini disebut coupled problem, mulai dari loosely coupled problem sampai

437


ke kategory tightly coupled problem yang tidak bisa diparalelkan. Untuk coupled problem yang diparalelkan, komunikasi data menjadi sangat penting dan dapat menurunkan kinerja komputasi dari PC Cluster. Jalur komunikasi data ini terdiri sistem jaringan interkoneksi antara node dan sistem pengiriman data (message passing). Dua buah sistem pengiriman data yang populer adalah MPI (Message Passing Interface) [8] dan PVM (Parallel Virtual Machine)[9]. Baik MPI maupun PVM, pengiriman data yang paling dasar dan primitif adalah komunikasi data antara dua buah node tertentu, dimana sebuah node mengirim sejumlah data ke node tertentu lainnya, sementara node penerima siap menunggu data yang sedang dikirim oleh node pengirim tersebut. Contohnya dalam MPI proses pengirim memanggil fungsi MPI_Send sementara proses penerima memanggil MPI_Receive seperti terlihat digambar bawah ini.

KOMUNIKASI DATA KOLEKTIF Komunikasi data tersebut di atas disebut Point-to-Point Communication. Selain jenis komunikasi ini sistem seperti MPI menyediakan juga fungsi komunikasi data koleketif dimana semua proses terlibat dalam proses komunikasi data ini. Fungsi komunikasi data kolektif ini dapat dibedakan menjadi tiga kelas sebagai berikut: Synchronization – dimana semua proses menunggu sampai semua proses sampai ke titik sinkronisasi. Transfer data kolektif- diantaranya broadcast (data yang sama dikirim oleh sebuah proses pengirim ke semua proses lainnya sebagi penerima), scatter (data yang berbeda dikirim oleh sebuah proses pengirim kemasing-masing proses lainnya sebagi penerima data ), gather (sebuah proses mengumpulkan data yang berbeda dari semua proses lainnya sebagi pengirim data) Komputasi kolektif (reduce): sebuah proses mengumpulkan data dari semua proses lainnya dan melakukan proses komputasi pada data yang sedang dikumpulkan seperti pencarian nilai maksimum/minimum, pejumlahan, perkalian dan sebagainya.

438


Kajian yang dilakuan pada artikel ini adalah kinerja dari transfer data kolektif jenis kedua khususnya broadcast. Artikel [2, 3] memperlihatkan bahwa tiga transfer data kolektif ini (broadcast, scatter dan gather) diperlukan untuk algoritma perkalian secara paralel, dan fungsi broadcast yang digunakan untuk mentransfer (copy) data salah satu matriks dari proses utama ke semua proses lainnya memerlukan waktu yang paling banyak dibanding dua transfer data kolektif lainnya.

ARSITEKTUR JARINGAN INTERKONEKSI PADA PC CLUSTER Dalam dunia teknologi jaringan dikenal beberapa jenis arsitektur jaringan seperti koneksi garis/linear, ring, 2D dan 3 D mesh, cube, torus dan koneksi bintang[2]. Jaringan interkoneksi ini bisa statis, yaitu koneksi antara dua node dihubungkan langsung secara fisis oleh kabel komunikasi, dan bisa juga dinamis, yaitu diantara node-node terdapat switch yang mengatur koneksi secara otomastis dan dinamis seperti terlihat digambar ini.

Proses implementasi PC Cluster menggunakan switch lebih sederhana dibandingkan implementasi interkoneksi statis yang paling mudah sekalipun misalnya koneksi linear. Kesederhanaan ini sayangnya terkadang diikuti oleh beban komunikasi yang berat, karena jalur komunikasi dalam switch, walaupun dirancang seolah-olah setiap port dihubungkan kesetiap port lainnya secara kontinu, kapasitas bandwith switch tidak bisa tidak ada batasan karena pemakaian jalur secara bersama-sama oleh node-node yang terhubungkan. Interkoneksi statis seperti ring dan torus memberikan alternatif jalur komunikasi yang lebih banyak untuk menghindari pemakaian kapasitas penuh jalur komunikasi secara bersamaan, khususnya untuk fungsi komunikasi data kolektif.

439


ALGORITMA BROADCAST PARALEL RING Algoritma broadcast yang paling sederhana adalah dengan cara serial yaitu data dikirim dari proses sumber ke masing-masing proses lainnya secara bergantian.seperti terlihat digambar bawah ini untuk arsitektur interkoneksi ring. Algortima ini kita sebut algortima naif[3], dan terbukti sangat tidak efisien dalam hal waktu pengiriman. Kelemahan dari algoritma ini adalah kemungkinan terjadinya komunikasi bottleneck dan congestion sangat tinggi dan juga jalur komunikasi tidak digunakan optimal karena pada saat bersamaan hanya satu jalur yang digunakan.

7

0

6

5

4

1

2

3

1 2 3 4 5 6 7

Lingkaran dengan nomor pada gambar di atas merepresentasikan proses dengan nomor urutnya, dan tanda panah putus-putus merepresentasikan langkah komunikasi point-to-point dengan nomor urutnya. Perbaikan algoritma naif ini adalah dengan membuat komunikasi berjalan secara paralel, dalam hal ini kami namakan double ring seperti terlihat digambar di bawah ini. 4 3 7

6

5

4

2

4 0

1

2

3

1 2

3

440


Algoritma ini dapat diimplementasikan dengan mekanisme sederhana “storeand-forward” yaitu data akan disimpan atau diterima sepenuhnya dulu oleh proses antara sebelum diteruskan ke proses lainnya. Mekanisme ini akan berkurang efisiensinya jika data yang harus dikirim besar jumlahnya dan/atau jika jumlah prosesnya banyak. Perbaikan dari mekanisme tadi adalah mekanisme “cut-and-through” dimana data dipecah menjadi paket lebih kecil, sehingga ketika paket lebih kecil sudah diterima, dapat langsung diteruskan ke proses lain walaupun belum keseluruhan data sudah diterima proses penerima. Dengan mekanisme ini jalur komunikasi lebih merata digunakan secara paralel.

PEMBAHASAN HASIL Algoritma double ring ini tidak harus diimplementasikan pada PC Cluster berbasis interkoneksi Ring. Pada [4] memperlihatkan algoritma ini dapat secara efisien diterapkan pada interkoneksi torus dengan catatan pemilihan urutan ring yang optimum. Pada kajian kali ini kita implementasikan algoritma broadcast ini pada PC Cluster sederhana yang menggunakan sebuah switch dan dibandingkan dengan algoritma standar MPI_Bcast yang diberikan oleh paket pustaka MPICH. Grafik berikut memperlihatkan waktu yang dibutuhkan oleh 8 node PC Cluster dengan switch dan dibandingkan dengan menggunakan interkoneksi Tourus 3x3[4].

Broadcast time (seconds)

12

MPICH on Torus[4]

10 8

DOUBLE RING on Torus [4] MPICH (using Switch)

6 4 2 0 0

2000000

4000000

DOUBLE RING (using Switch)

Number of Element

Dari grafik tampak algoritma broadcast menggunakan teknik double ring lebih baik kinerjanya dibandingkan dengan standar MPICH. Yang menarik disini adalah standar MPI_Bcast dari MPICH kinerjanya hampir tidak tergantung pada arsitektur menggunakan switch maupun interkoneksi statik torus. 441


Di bawah ini hasil kajian diperlihatkan kembali dalam tabel. Broadcast time in seconds Parallel Algorithm Machine Switch MPICH Torus[4] Switch Double RING Torus[4]

Total number broadcasted (Double precision) 160000 640000 1440000 2560000 4000000 0.42 1.70 4.01 7.02 10.98 0.43 1.62 3.69 6.72 10.93 0.53 1.44 3.18 5.27 8.18 0.41 1.23 2.59 4.37 6.73

KESIMPULAN Kesimpulan utama dari kajian ini adalah kinerja broadcast pada PC Cluster dapat ditingkatkan dengan cara memperbaiki sistem interkoneksi nodenya dari sistem interkoneksi sederhana menggunakan switch diubah dengan statis koneksi torus bersaamaan dengan perbaikan algoritma komunikasi datanya.

DAFTAR PUSTAKA 1. ANONYMOUS, Beowolf overview/index.htm

Project

Overview,

http://www.beowolf.org/

2. JAMAL ADE, SISTHA PANDRIYA, “Interkoneksi Statis pada “PC Jaringan” serta Aplikasi Komputasi Paralel Matriks”, Proceeding of Semiloka Simulasi dan Komputasi serta Aplikasi 2005 (In Indonesian), November, BPPT, Jakarta, Indonesia, (2005) p.B-1 3. JAMAL ADE, SISTHA PANDRIYA, “Tuning of One-To-All Broadcast on Ring Based PC Cluster for Simple Block Matrix Multiplication”, in Proc. The 7th Seminar on Intelligent Technology and Its Applications, 3rd Conf. Information Technology Applications in Biomedicine, SITIA, ITS, Surabaya, (2006) pp. I-F-18 4. JAMAL ADE, SISTHA PANDRIYA , “Evaluation of One-To-All Broadcast Ring Based Algorithm on Torus PC Cluster”, akan dipresentasikan pada The 2nd Indonesia Japan Joint Scientific Symposium 2006 (IJJSS), UI, Depok, 2006.

442


5. G. C. MAI, C.A.F. DE ROSE, ”Low Cost Cluster Architectures for Parallel and Distributed Processing”, CLEI Electronic Journal (3) 1 (2000). 6. GRAMA A., A.L GUPTA, G. KARYPIS, V. KUMAR, Introduction to Parallel Computing, Addison Wesley, 2003. 7. GROPP W., DOSS N., MPICH Model MPI Implementation Reference Manual, Argonne National Laboratory ,ANL-00, August 2004. 8. GROPP W., et.al., MPI-The Complete Reference, Vol. 1, The MPI Core,The MIT Press , 1998. 9. ANONYMOUS , http://www.csm.ornl.gov/pvm/pvm_home.html PVM Parallel Virtual Machine. 10. JAMAL ADE, SAINJATI A., SUWARJONO A., “Parallel Algorithm for Solving a block-tridiagonal system”, Jurnal Ilmu Pengetahuan, Teknologi dan Budaya AlAzhar Indonesia, (2) 1 (2003).

DISKUSI

RULIYANTI PARDEWI 1. Apakah program aplikasi maupun OS Yang dipergunakan di PC Cluster bisa menggunakan sistem lain selain OSS ? 2. Baik computer code maupun data yang dapat disetor di masing-masing PC atau hanya datanya saja, atau computer codenya saja yang disimpan disalah satu PC yang difungsikan sebagai server ?

ADE JAMAL 1. Ya, ada versi MSWindows untuk message passing system 2. Dua-duanya (Program dan data) bisa disebar tergantung tujuannya. Misal untuk: Cluster, bertujuan reliabilitas maka data yang disebar dan program client server Komputasi Kinerja Tinggi, program dan data disebar ke masing-masing mode.

443


DAFTAR RIWAYAT HIDUP

1. Nama

: Ade Jamal

2. Tempat/Tanggal Lahir

: Jakarta, 15 Desember 1965

3. Instansi

: BPPT/ Univ. Al Azhar

4. Pekerjaan / Jabatan

: Peneliti/Kajur. T.Informatika

5. Riwayat Pendidikan

: (setelah SMA sampai sekarang)

• S1 Fac Of Aerospace Engineering, Delft University of Technology, Belanda, 1992 • S3 Computational Mechanics, Delft University of Technology, Belanda, 1998 6. Pengalaman Kerja

:

• Asisten Peneliti/Dosen, Fac Of Aerospace Engineering, Delft University of Technology, Belanda, 1992-1997 • Pusat Rekayasa Rancang Bangun, BPPT, (1997-1999) • Pusat Pengkajian & Penerapan Teknologi Informasi dan Elektronik, BPPT, 1999 • Peneliti di Pusat Teknologi Informasi dan Komunikasi, BPPT • Ka. Jurusan Univ. Al Azhar, Indonesia • Consultant PT. Tijara Pratama 7. Publikasi(Makalah)

:

• IJJSS 2006, • SITIA 2006, ITS Surabaya

444

KINERJA KOMUNIKASI DATA KOLEKTIF BROADCAST PADA PC CLUSTER. Ade Jamal *, Pandriya Sistha **

Recommend Documents