BAB II TINJAUAN PUSTAKA
II.1
Arsitektur Komputer dengan Memori Terdistribusi Cluster yang dibangun di dalam penelitian ini termasuk dalam sistem
komputer dengan arsitektur memori terdistribusi. Komputer-komputer yang diintegrasikan ke dalam cluster memiliki memori dan prosesor masing-masing yang terhubung satu sama lain dengan sebuah jaringan interkoneksi.
II.1.1 Taksonomi Flynn Untuk Arsitektur Komputer Taksonomi arsitektur komputer yang paling popular didefinisikan oleh Michael J. Flynn pada tahun 1966. Skema klasifikasi Flynn berdasarkan pada aliran informasi pada prosesor. Dua aliran informasi yang mengalir pada prosesor adalah instruksi dan data. Aliran instruksi didefinisikan sebagai urutan instruksiinstruksi yang diolah oleh unit pemroses. Aliran data didefinisikan sebagai lalu lintas pertukaran data antara memori dengan unit pemroses. Menurut klasifikasi Flynn, aliran instruksi dan aliran data dapat berupa tunggal maupun jamak. Arsitektur komputer menurut Flynn dapat diklasifikasikan sebagai berikut: 1.
SISD
: Single Instruction Stream Single Data Stream
2.
MISD: Multiple Instruction Stream Single Data Stream
3.
SIMD: Single Instruction Stream Multiple Data Stream
4.
MIMD: Multiple Instruction Stream Multiple Data Stream
13
14
Komputer konvensional dengan prosesor tunggal diklasifikasikan ke dalam sistem SISD. Komputer SISD hanya memiliki satu unit pemroses yang menerima sebuah aliran
instruksi yang mengoperasikan sebuah aliran data.
Diagram blok komputer dengan klasifikasi SISD ditunjukkan oleh Gambar II.1.
Gambar II.1 Diagram Blok SISD Komputer paralel yaitu komputer yang memiliki lebih dari satu unit pemroses dapat dikalasifikasikan sebagai SIMD atau MIMD. Perbedaan antara sistem SIMD dengan MIMD terletak pada unit kontrol yang memberikan instruksi pada unit pemroses. Di dalam sistem SIMD terdapat sebuah unit kontrol yang memberikan sebuah instruksi yang akan dieksekusi oleh semua prosesor secara sinkron. Gambar II.2 menunjukkan diagram klasifikasi SIMD.
Gambar II.2 Diagram Blok SIMD
15
Di dalam sistem MIMD, masing-masing prosesor memiliki unit kontrol yang mengeksekusi instruksi-instruksi yang berbeda pada data yang berbeda pula. Gambar II.3 menunjukkan diagram blok MIMD.
Gambar II.3 Diagram Blok MIMD Di dalam kategori MISD, terdapat beberapa unit pemroses yang saling berbagi sebuah memori. Sebuah aliran data akan diproses sacara simultan oleh masing-masing prosesor dengan masing-masing prosesor tersebut memperlakukan sebuah aliran data dengan perlakuan yang berbeda. Komputer cluster yang akan dibahas di dalam tugas akhir ini menggunakan klasifikasi MIMD karena menggunakan beberapa komputer yang saling independen dan terhubung dengan sebuah jaringan. Masing-masing komputer independen tersebut memiliki unit kontrol masing-masing dan mengeksekusi instruksi-instruksi yang berbeda pada data yang berbeda pula.
16
II.1.2 Arsitektur MIMD Arsitektur paralel MIMD terdiri dari modul prosesor dan memori yang jamak dan terhubung dengan sebuah jaringan. MIMD dibagi menjadi dua kategori yaitu shared memory dan message passing. Gambar II.4 menunjukkan dua kategori sistem komputer dengan arsitektur MIMD
Gambar II.4 Shared Memory dan Message Passing dalam Arsitektur MIMD ( Sumber : S. Morrison, Richad , 2003 ) Di dalam sistem shared memory prosesor berkomunikasi melalui shared variable yang dapat diakses oleh semua prosesor. Sedangkan di dalam sistem Message Passing pertukaran informasi antar prosesor dilakukan melalui jaringan interkoneksi.
17
II.1.3 Organisasi Memori Arsitektur MIMD Klasifikasi arsitektur MIMD dapat diklasifikasikan lagi menurut struktur memorinya. Struktur memori di dalam arsitektur MIMD dapat berupa shared memory atau distributed memory. 1.
GMSV - Global Memory Shared Variable.
2.
GMMP - Global Memory Message Passing.
3.
DMSV - Distributed Memory Shared Variable.
4.
DMMP - Distributed Memory Message Passing. GMSV dan GMMP merupakan shared memory sedangkan DMSV dan
DMMP merupakan message passing. Komputer cluster termasuk dalam klasifikasi DMMP karena mengunakan mekanisme message passing dalam melakukan komunikasi antar proses. Gambar II.5 menunjukkan klasifikasi memori menurut Flynn.
Gambar II.5 Klasifikasi Sistem Komputer Menurut Flynn ( Sumber : S. Morrison, Richad , 2003 )
18
Arsitektur MIMD dengan struktur memori DMMP memiliki mekanisme pertukaran informasi antar prosesor yang dilakukan dengan menggunakan Message Transfer System (MTS). MTS sangat tergantung pada kecepatan jaringan interkoneksi antar prosesor.
II.2
Komputer Cluster Komputer Cluster adalah rakitan dari beberapa komputer yang saling
independen yang terintegrasi oleh sebuah jaringan interkoneksi dan mendukung akses terhadap perangkat lunak untuk pengorganisasian dan pengontrolan tugas komputasi sehingga komputer cluster dapat dipandang sebagai sebuah sistem komputer dengan banyak unit pemroses dan memiliki memori yang terdistribusi. Di dalam sebuah cluster terdapat beberapa komputer yang disebut sebagai node. Masing-masing node tersebut merupakan mesin komputasi yang saling terintegrasi satu sama lain dengan sebuah jaringan. Node-node di dalam cluster tersebut dapat memiliki sistem operasi dan sistem input dan output masingmasing. Jika semua node di dalam cluster memiliki arsitektur dan sistem operasi yang sama, maka cluster tersebut dikatakan sebagai cluster yang homogen. Jaringan interkoneksi yang menghubungkan node-node di dalam cluster sebisa mungkin memiliki bandwidth yang tinggi dan lantensi yang serendah mungkin karena kecepatan dan latensi di dalam jaringan cluster sangat menentukan performa komputasi yang dilakukan oleh cluster. Untuk membangun sebuah cluster dibutuhkan empat buah komponen, yaitu dua buah komponen hardware dan dua buah komponen software.
19
Komponen hardware yang pertama adalah node atau mesin komputasi dan yang kedua adalah jaringan interkoneksi, sedangkan komponen software yang pertama adalah software yang dapat digunakan oleh pengguna untuk mengembangkan aplikasi paralel dan yang kedua adalah software yang digunakan untuk memonitor dan mengatur aplikasi yang berjalan di dalam cluster.(S.Morisson, Richard, 2003) Gambar II.6 menunjukkan layer-layer yang membangun sebuah komputer cluster. Layer yang paling atas adalah aplikasi paralel yang akan dijalankan di dalam cluster. Layer Cluster Middleware sampai dengan Layer High Speed Network Switch dibangun oleh komponen-komponen perangkat keras dan perangkat lunak yang merupakan integrator sistem cluster.
Gambar II.6 Layer Komputer Cluster Komputer cluster digunakan untuk melakukan komputasi dengan performa yang tinggi. Komputasi dengan performa tinggi tersebut dicapai dengan melakukan komputasi secara paralel yaitu menyelesaikan sebuah permasalahan komputasi dengan membagi permasalahan untuk diselesaikan secara simultan oleh masing-masing node di dalam cluster.
20
Setiap node di dalam komputer cluster yang dibangun di dalam penelitian ini adalah komputer cluster yang menggunakan sistem operasi Linux dan perangkat-perangkat input dan output yang mirip.
II.3
Parallel Processing Parallel processing adalah sebuah metode untuk memecahkan sebuah
permasalahan yang besar dengan cara memecah permasalahan tersebut menjadi komponen-komponen yang lebih kecil dengan proses kalkulasi atau komputasi dilakukan secara paralel. Untuk membuat sebuah algoritma paralel diperlukan sebuah langkah yaitu dekomposisi permasalahan, sehingga permasalahan yang lebih kecil dapat ditugaskan ke prosesor-prosesor untuk diproses secara simultan. Terdapat dua cara dalam dekomposisi permasalahan yaitu, dekomposisi domain dan dekomposisi fungsional. 1.
Dekomposisi domain. Di dalam dekomposisi domain atau paralelisasi data, data dibagi ke dalam ukuran yang hampir sama dan kemudian dikirimkan ke prosesor yang berbeda untuk diproses. Masing-masing prosesor hanya memroses bagian data yang diterima saja. Masing-masing proses harus berkomunikasi secara periodik untuk pertukaran data.
2.
Dekomposisi fungsional. Di dalam dekomposisi fungsional atau dekomposisi tugas (task), sebuah permasalahan didekomposisikan menjadi tugas-tugas
21
(tasks) yang lebih kecil. Tugas kemudian diberikan kepada komputerkomputer untuk diproses. ( Rusadi, Fajran Iman, 2006 )
II.4
Message Passing Message passing merupakan salah satu model pemrograman aplikasi
paralel yang banyak digunakan. Setiap proses yang bekerja bersama secara paralel dapat berkomunikasi satu sama lain dengan cara mengirim pesan. Proses-proses ini dapat berdiri sendiri dan tidak perlu berbagi apa-apa, termasuk sumber daya prosesor dan memori. Dalam message passing, setidaknya ada dua operasi dasar yang dimiliki oleh program untuk berkirim pesan, yaitu operasi pengiriman pesan (send ) dan operasi untuk menerima pesan (receive). Dengan dua perintah ini, satu proses sudah dapat mengirim pesan ke satu proses yang lain lalu proses penerima pesan akan memanggil fungsi untuk mengambil pesan yang dikirimkan kepadanya. Model komunikasi mengirim (send) dan menerima (receive) disebut sebagai komunikasi point-to-point. Melalui dua perintah dasar tersebut dapat dikembangkan model komunikasi yang lebih lanjut yang melibatkan lebih dari satu proses sekaligus.
22
Gambar II.7 Komunikasi Point-to-Point ( Sumber : Rusadi, Fajran Iman, 2006 ) Pengiriman pesan kepada sekelompok proses dapat digunakan untuk melakukan sinkronisasi, pengiriman data dari satu prosesor ke semua prosesor yang lain (broadcast ), mendapatkan data dari semua prosesor ke sebuah prosesor dan menyimpan data tersebut (gather), maupun membagi data yang disimpan pada memori sebuah prosesor ke memori prosesesor lainnya. Model komunikasi seperti ini disebut sebagai komunikasi kolektif. Gambar II.8 menunjukkan gambaran mengenai model komunikasi antar node-node yang dapat dilakukan dengan MPI.
Gambar II.8 Komunikasi Kolektif ( Sumber : Rusadi, Fajran Iman, 2006 )
23
II.4.1 Message Passing Interface Model message passing telah dikenal luas sebagai salah satu model pemrograman aplikasi paralel. Dengan message passing, setiap proses yang terlibat dalam penyelesaian masalah secara paralel dapat berkomunikasi dengan cara mengirim pesan. Konsep message passing kemudian dijadikan sebuah standar agar ada suatu cara yang sama dalam penulisan program. Standar ini dapat digunakan oleh berbagai macam pengguna dan dapat diimplementasikan secara efisien dalam berbagai macam komputer. Standar ini kemudian dikenal sebagai Message Passing Interface (MPI). ( Rusadi, Fajran Iman, 2006 ) MPI berisi sekumpulan application programming interface (API ) yang dapat digunakan oleh pengembang aplikasi. API ini dirancang untuk dapat diterapkan pada bahasa pemrograman apa saja (language independent ). MPI juga menetapkan protokol dan spesifikasi bagaimana setiap fitur dari MPI diimplementasikan. MPI menggunakan objek yang disebut komunikator dan grup untuk mendefinisikan
sekumpulan
proses-proses
yang
ada
untuk
melakukan
komunikasi. Gambar
II.9
menunjukkan
sebuah
himpunan
komunikator
MPI_COMM_WORLD dengan anggota node-node komputasi didalamnya. Hampir semua fungsi-fungsi atau routine menggunakan komunikator sebagai argumen. Salah satu komunikator yang paling sering digunakan adalah MPI_COMM_WORLD.
24
Error! Gambar II.9 Komunikator MPI_COMM_WORLD ( Sumber : Rusadi, Fajran Iman, 2006 ) Di dalam program MPI, harus terdapat pemanggilan fungsi MPI_Init sebagai inisialisasi program dan MPI_Finalize untuk terminasi program. Deklarasi variabel
dan
algoritma-algoritma
yang
berada
diantara
MPI_Init
dan
MPI_Finalize akan dijalankan secara paralel atau akan dibaca oleh semua proses yang berada di dalam komunikator. Gambar II.10 menunjukkan sebuah struktur program MPI. Penulisan program MPI untuk bahasa pemrograman seperti C, C++, dan Fortran selalu diawali dengan pemanggilan pustaka MPI (MPI include file). Setelah melakukan pemanggilan pustaka MPI, selanjutnya fungsi-fungsi MPI dapat dipanggil di dalam program. Fungsi yang harus dipanggil untuk menjalankan program MPI adalah fungsi yang digunakan untuk inisialisasi program MPI dan terminasi program MPI, yaitu MPI_Init dan MPI_Finalize. Program yang dituliskan diantara pemanggilan fungsi MPI_Init dan MPI_Finalize akan dieksekusi oleh semua
node
yang
MPI_COMM_WORLD.
termasuk
dalam
himpunan
komunikator
25
Gambar II.10 Struktur Program MPI ( Sumber : Rusasdi, Fajran Iman, 2006 )
II.4.2 Local Area Multicomputer/Message Passing Interface (LAM/MPI) LAM/MPI adalah aplikasi open source yang mengimplementasikan standard MPI. Di dalam cluster LAM/MPI berfungsi sebagai midleware yang memberikan fungsionalitas parallel processing dengan MPI. LAM/MPI sendiri terdiri dari beberapa layer, yaitu : User Application, MPI layer, LAM layer, dan Operating System.
Gambar II.11 Layer LAM/MPI ( Sumber : Rusasdi, Fajran Iman, 2006 )
26
Layer LAM pada Gambar II.11 memuat LAM Runtime Environment dan Application Programming Interface MPI. LAM RTE adalah user daemon yang servis-servis message passing, pengontrolan proses, akses file jarak jauh, dan I/O forwarding. Pengguna menjalankan LAM RTE dengan perintah lamboot. Lamboot akan menjalankan daemon lamd pada setiap node di dalam cluster. Setelah LAM RTE berjalan, pengguna dapat menjalankan program MPI. Ketika pengguna telah selesai menjalankan LAM RTE, perintah lamhalt digunakan untuk melakukan terminasi lamd di setiap node.
II.5
Network File System (NFS) NFS adalah sistem file yang terdistribusi di dalam sebuah jaringan
komputer. Komputer-komputer di dalam jaringan yang mengimplementasikan NFS dapat mengakses NFS server dengan cara mounting NFS tersebut. NFS yang telah di-mount oleh NFS client dapat dianggap seolah-olah sebagai sistem file lokal. Di dalam cluster yang didedikasikan untuk komputasi paralel disyaratkan adanya berkas aplikasi pada setiap komputer yang digunakan untuk eksekusi. Dengan mengimplementasikan NFS di dalam cluster, hal ini tidak akan menjadi masalah karena berkas aplikasi dapat diakses oleh semua node. Perancangan NFS untuk cluster sangat diperlukan. Komputer head node harus menyediakan sejumlah ruang di dalam hard disk untuk dijadikan sebagai
27
NFS. Hard disk tersebut harus dipartisi sesuai dengan kebutuhan head node maupun compute node.
II.6 Network Information System (NIS) NIS adalah basis data terdistribusi yang menggantikan salinan-salinan file konfigurasi dengan sebuah sistem pengaturan yang terpusat. NIS di dalam cluster digunakan untuk mengintegrasikan administrasi sistem di masing-masing node. Dengan menggunakan NIS, cluster hanya membutuhkan sebuah NIS server untuk menjalankan administrasi sistem di setiap node. Dalam hal ini head node bertindak sebagai nis server, dan compute node bertindak sebagai nis client.
II.7 Secure Shell (SSH) SSH didalam cluster digunakan untuk melakukan komunikasi antar node. LAM/MPI mengharuskan head node untuk mengeksekusi aplikasi-aplikasi paralel di setiap node. Dengan SSH hal tersebut dapat dilakukan karena SSH adalah aplikasi yang digunakan di dalam sistem UNIX untuk melakukan pengaksesan ke sebuah mesin secara remote. Head node harus dapat mengakses compute node dengan menggunakan SSH tanpa harus melakukan otentikasi terlebih dahulu. Untuk melakukan pengaksesan compute node dengan SSH, komputer head node harus membangkitkan kunci privat dan publik untuk diberikan kepada compute node. Ketika head node akan melakukan komunikasi dengan compute node kunci publik diberikan kepada compute node. Compute node kemudian akan memberikan
28
angka acak ke head node. Angka acak tersebut hanya dapat diterjemahkan oleh kunci privat yang dimiliki oleh head node. Jika kunci privat dapat menterjemahkan angka acak yang diberikan oleh compute node maka head node akan diberikan izin untuk mengakses compute node tanpa otentikasi.
II.8 Ganglia Ganglia adalah aplikasi yang digunakan oleh grid maupun cluster untuk memantau proses dan beban kerja di masing-masing node. Ganglia sangat mudah untuk digunakan karena aplikasi ini berbasis web. Ganglia dapat digunakan untuk memantau beban proses sebuah cluster maupun beban proses untuk masingmasing node di dalam cluster. Aplikasi ganglia dapat diunduh dari situs http://www.ganglia.info. Instalasi ganglia di dalam cluster sedikit berbeda dengan instalai aplikasi-aplikasi lain. Ganglia harus diinstal di tiap-tiap node di directory sistem masing-masing. Hal tersebut harus dilakukan karena ganglia harus memiliki file konfigurasi yang spesifik untuk tiap-tiap node.
II.9
OCTAVE MPITB GNU Octave adalah sebuah program yang digunakan untuk memecahkan
masalah komputasi numeris baik yang bersifat linear maupun non linear. Octave memiliki kompatibilitas dengan MATLAB yang sudah terlebih dahulu dikenal baik dikalangan matematika maupun teknik. Karena kemiripannya dengan MATLAB maka Octave cukup mudah untuk digunakan.
29
Walaupun Octave kompatibel dengan MATLAB, Octave parser berbeda dengan MATLAB. Maka, terdapat beberapa perbedaan dalam hal syntax maupun beberapa fungsi. Tabel II.1 menunjukkan perbedaan antara OCTAVE dengan MATLAB. Tabel II.1 Perbedaan OCTAVE dengan MATLAB Perbedaan
OCTAVE
MATLAB
Fungsi bersarang
Tidak mendukung
Mendukung
Just-In-time compiler (JIT)
Tidak mendukung
Mendukung
Kompilasi ke biner
Tidak mendukung
Mendukung
Penanganan grafik
Masih sangat tergantung pada gnuplot
Memiliki fungsi sendiri
Simulink
Tidak mendukung
Mendukung
Komentar
Menggunakan karakter ‘#’ atau ‘%’
Hanya karakter ‘%’
Profiler
Tidak mendukung
Mendukung
Toolboxes
Octave memiliki beberapa toolboxes yang memberikan fungsi – fungsi tambahan
Tidak memiliki toolbox
Kode blok.
if
if … end function … end for … end
… endif function … endfunction for … Endfor Startup script.
Supaya
.octaverc
Octave
dapat
melakukan
startup.m
parallel
processing,
Octave
membutuhkan sebuah modul tambahan yaitu MPITB (MPI Tool Box) untuk
30
memanggil fungsi-fungsi MPI. MPITB adalah sebuah toolbox atau modul yang digunakan Octave untuk melakukan pemanggilan fungsi-fungsi MPI. MPITB mengimplementasikan pustaka-pustaka MPI menjadi fungsifungsi yang dapat dipanggil melalui OCTAVE. Dengan MPITB, program yang dibuat dengan OCTAVE dapat diimplementasikan secara paralel. (Eaton, John W, 2007)
