BAB I PENDAHULUAN 1.1 Latar Belakang Peningkatan jumlah data yang digunakan dalam sistem komputer tidak lagi mampu diikuti penambahan jumlah prosesor komputer karena masalah biaya yang tumbuh sangat cepat, serta jika dilakukan secara sekuansial waktu yang dibutuhkan sangat tinggi[1], dari fakta inilah mulai bermunculan ide untuk melakukan proses secara paralel dengan memecah proses dan data menjadi beberapa bagian dan diproses dalam komputer yang berbeda dan teknik ini kemudian dikenal dengan nama Komputasi Paralel. Komputasi paralel dibicarakan pertama kali oleh S. Gill ( Ferranti ) membahas mengenai cara pemrograman paralel untuk kebutuhan percabangan proses pada April 1958, serta pada tahun yang sama dua orang peneliti dari IBM yaitu John Cocked an Daniel Stotnick yang membahas proses perhitungan numeric secara paralel untuk pertama kalinya. Perkembangan komputasi paralel ini merupakan dasar pembentukan sebuah komputasi klaster yang kita kenal saat ini, dimana sebuah sistem klaster terdiri dari beberapa komputer yang dapat saling berkomunikasi untuk mengerjakan suatu tugas yang sama, saat ini komputasi klaster ini telah banyak digunakan untuk membantu proses yang pada umumnya memerlukan kapasistas besar, baik karena harus mengolah data dalam ukuran yang sangat besar atau melakukan proses perhitungan yang sangat banyak. Komputasi klaster secara fisik terdiri dari sebuah server sebagai induk, dan beberapa komputer lain sebagai tempat untuk melakukan pengolahan data, dimana setiap komputer tersebut akan terhubung menggunakan jaringan lokal yang memiliki kecepatan relatif tinggi. Komputer induk (master) pada komputasi klaster ini akan bertugas untuk memecah dan membagi pekerjaan yang akan dikirimkan kepada komputer pekerja ( slave ) [8]. Hingga saat ini pembagian pekerjaan dalam sebuah mesin paralel dilakukan dengan membagi secara merata kepada setiap komputer pekerja yang dikenalinya tanpa mempertimbangkan kemampuan komputer tersebut dalam menyelesaikan masalah, sehingga terdapat kemungkinan penggunaan waktu yang lebih tinggi selain itu tingkat efisiensi penggunaan mesin paralel juga memiliki nilai yang relatif rendah, masalah ini terjadi karena antrian
1
proses yang bersifat tunggal sehingga semua sumber daya akan dialokasikan untuk proses pada antrian paling atas. Berikut merupakan topologi pembagian kerja mesin paralel yang banyak digunakan saat ini.
Gambar 1. 1 Topologi Bintang
Untuk menghindari beberapa hal tersebut dalam tugas akhir ini akan dilakukan pengembangan terhadap topologi pembagian kerja pada mesin paralel. Pembagian pekerjaan dalam perluasan topologi ini dapat memanfaatkan teknik pewarnaan-f pada graf, teknik ini juga memungkinkan adanya perbedaan kemampuan setiap komputer pada mesin paralel untuk memproses data pada waktu yang sama, kemampuan setiap komputer ini akan direpresentasikan dengan fungsi-f setiap simpul pada graf yang berarti banyaknya warna sama yang boleh terkait pada simpul tersebut. Analisis ini diharapkan mampu memberikan hasil alokasi sumber daya yang berimbang sehingga efisiensi dan kecepatan mesin paralel akan meningkat.
2
1.2 Tujuan Tujuan penelitian ini adalah : a) Membentuk sebuah topologi alokasi sumber daya mesin paralel yang merepresentasikan pengalokasian sumber daya yang dimodelkan melalui hasil kali kartesius pada graf sederhana. b) Mengetahui jumlah antrian sumber daya dan alokasi sumber daya pada suatu topologi mesin paralel berdasarkan kemampuan setiap komputer dalam melakukan penyelesaian suatu tugas tertentu. c) Menentukan topologi optimum yang memiliki kesesuaian terhadap sumber daya serta tingkat efisiensi penggunaan sumber daya sehingga diperoleh kinerja yang optimal.
1.3 Rumusan Masalah Pada Tugas Akhir ini akan dirumuskan masalah sebagai berikut : a) Bagaimanakah bentuk dari topologi yang dapat dimodelkan oleh hasil kali kartesius antara graf sederhana ? b) Bagaimanakah cara untuk menentukan jumlah antrian eksekusi yang dapat dihasilkan oleh sebuah topologi dengan melihat kemampuan proses setiap komputer pada mesin paralel? c) Bagaimanakah cara untuk mendapatkan topologi optimum dari model hasil kali graf sederhana tersebut ? d) Bagaimanakah tingkat efisiensi dan kecepatan topologi pembagian kerja tersebut untuk memecahkan kasus tertentu ?
1.4 Batasan Masalah Ruang lingkup dalam pembahasan Tugas Akhir ini adalah sebagai berikut : a) Topologi yang dihasilkan hanya merupakan gambaran dari hasil kali kartesius antara graf sederhana dan tidak berarah yaitu Kn, Cn, Sn, Wn, Pn. b) Waktu pemrosesan untuk setiap tugas dalam mesin paralel diasumsikan sama yang akan dinyatakan dalam satu satuan waktu.
3
c) Biaya perancangan topologi pembagian kerja mesin paralel diabaikan. d) Setiap komputer dalam mesin paralel dapat bertindak sebagai master node dan slave node.
1.5 Metodologi Penelitian 1. Studi Literatur Literatur dalam hal ini berupa buku, hasil penelitian, dan sumber lain dari internet untuk memberikan referensi yang jelas mengenai sistem yang akan diteliti. 2. Simulasi dan Implementasi Pada tahap ini dilakukan simulasi terhadap graf hasil kali kartesius untuk mendapatkan pola yang dapat direpresentasikan dalam bentuk matriks ketetanggaan serta melakukan implementasi dalam program pembantu proses analisis. 3. Evaluasi Sistem Pada
tahap
ini
dilakukan
evaluasi
terhadap
pola
yang
telah
diimplementasikan dalam sistem dengan percobaan terhadap beberapa graf hasil kali kertesius yang merepresentasikan topologi mesin parallel. 4. Analisis Pada tahap ini dilakukan analisis terhadap kinerja suatu topologi mesin paralel dengan menggunakan program pembantu yang telah dirancang sebelumnya. 5. Kesimpulan Pada tahap ini akan ditarik kesimpulan berdasarkan pada hasil analisis sehingga diperoleh kinerja topologi mesin parallel yang optimum.
4
1.6 Sistematika Penulisan Sistematika penulisan Tugas Akhir ini adalah : BAB I : PENDAHULUAN Bagian ini berisikan latar belakang masalah, tujuan penelitian, rumusan masalah, batasan masalah, metodologi penelitian, dan sistematika penulisan. BAB II : DASAR TEORI Bagian ini menjelaskan secara teori tentang graf, operasi hasil kali kartesius, indeks f kromatik, pewarnaan graf, komputasi parallel. BAB III : ANALISIS PERANCANGAN SISTEM Bagian ini menjelaskan sistem komputasi parallel, kebutuhan sistem, parameter yang digunakan dan penggunaan DAG ( directed acyclic graph ) untuk menggambarkan ketergantungan proses eksekusi. BAB IV : ANALISIS SISTEM DAN EVALUASI Bagian ini berisikan analisis bentuk topologi pembagian kerja suatu mesin paralel dan kesesuaiannya terhadap sumber daya yang dimliki sehingga dapat meningkatkan efisiensi dan kecepatan mesin paralel dengan memanfaatkan model graf hasil kali kartesius. BAB V : KESIMPULAN DAN SARAN Bagian ini berisikan kesimpulan dan saran dari hasil penelitian.
5
