ANALISIS DAN IMPLEMENTASI SISTEM PENGOLAHAN DATA MATRIKS PADA SISTEM KOMPUTASI PARALEL MENGGUNAKAN MPI DAN METODE STRASSEN
I
Sinta Kartika Maharani, 'Muhammad Nasrun, J Andrew Brian Osmond 1,2"Jurusan Sistem Komputer± Institut Teknologi Telkom Ikartika sinta@yahoo,com, 2mnr@ittelkom,ac.id, 'abo@ittelkom,ac.id
ABSTRAK Seiring dengan kemajuan teknologi kebutuhan akan komputer sebagai solusi dari sebuah masalah yang dihadapi semaIdn meningkat karena asumsi bahwa komputasi dianggap lebih cepat dalam menyelesaikan suatu permasalahan dibandingkan dengan cara manuaL Maka dari itu dibutuhkan proses komputasi yang cepat, salah satu solusinya adalah dengan komputasi paralel dimana komputasi dilakukan secara bersamaan dengan memanfaatkan beberapa komputer independen secara bersamaan yang umumnya digunakan saat kapasitas yang dibutuhkan sangat besar untuk mengolah data dalam jumlah yang besar juga. Solusi ini menjadi sebuah pili han . karena komputasi berbagai secara sekuensial mengalami keterbatasan. Perkalian matriks merupakan sebuah masalah yang kompleks jika ordenya sudah mencapai ribuan dan penyelesaian menggunakan sekuensial akan membutuhkan waktu yang lama. Metode penyelesaian matriks yang digunakan adalah metode konvensional dan Strassen. Metode konvensional yang dibuat, diimplementasikan menggunakan MPI (Message Passing Interface) pada sebuah komputer dengan jumlah proses yang berbeda untuk setiap percobaan orde matriks. Metode Strassen dibuat dengan melakukan partisi pada setiap matriks menjadi submatriks berukuran 2x2. Dari hasil percobaan, untuk perkalian matriks orde 1024xl024, metode Strassen lebih lambat 88,32%, dan penggunaan memorinya 35% lebih banyak dlbandingkan metode konvensional. Untuk perkalian matriks orde 2048x2048, metode Strassen lebih lambat 84,8% dan penggunaan memorinya 49,13% lebih banyak dibandingkan metode konvensional. Hasil perkalian kedua matriks orde 1024xl024 dan 2048x2048 metode lambat karena tidak Strassen lebih mengunakan metode komputasi paralel Kata kunci: matriks, konvensional, metode Strassen, MPI
metode
ABSTRACT Along with advances in computer technology as a solution to the need of a growing problem faced due to the assumption that computing is considered to be faster in solving a 'Problem than the manual way. Therefore needed a fast computational process, one solution is to parallel computing in which computing is done simultaneously by utilizing multiple independent computers simultaneously which is commonly used when a very large capacity required to process large amounts of data as well; This solution becomes an option for sequential computing has many limitations. Matrix multiplication is a complex problem if ordenya has reached thousands and using the sequential completion will take a long time. Matrix solution method used is the and Strassen. conventional method Conventional methods are created, implemented using MPI (Message Passing Interface) on a computer with a number of different processes for each trial- order matrix. Strassen method is created by partitioning the matrix into suhmatrices each ofsize 2x2. From the experimental results, for the order of IOUxIOU matrix multiplication, Strassen method is slower 88.32% and use 35% more memory than conventional methods. For the order of 2048x2048 matrix multiplication, Strassen method is slower 84.8% and use 49.13% more memory than conventional methods. Results of second order matrix multiplication I024xI024 and 2048x2048 Strassen's method is slower because it does not use parallel computing method Key words: matrix, conventional method, Strassen method, MP
I.
PENDAHULUAN
Saat 101, komputer banyak digunakan sebagai solusi sebuah masalah yaog dihadapi. Hal ini disebabkan oleh asumsi bahwa komputasi dianggap lebih cepat dalam menyelesaikan suatu pennasalahan dibandingkan dengan cara manual. Oleh karena itu semakin dituntut proses komputasi yang cepat. Salah satu solusi yang
Analisis dan Implementasi Sistem pengolahan Data Matriks Pada Komputasi Paralel Menggunakan MPI dan Metode Strassen [Sinta Kartika Maharani]
163
dapat digunakan adalah dengan komputasi parale!. Komputasi paralel adalah suatu teknik melakukan komputasi secara bersamaan dengan memanfaatkan beberapa komputer independen secara bersamaan yang umumnya digunakan saat kapasitas yang dibutuhkan sangat besar untuk mengolah data dalam jumlah yang besar juga. Solusi ini menjadi sebuah pilihan karena komputasi secara sekuensial mengalami berbagai keterbatasan. Beberapa bidang terapan yang memerlukan program paralel : Kimia dan molekul, Fisika Terapan, Biosains, Bioteknologi, Sains Komputer dan Maternatika. Matriks merupakan suatu representasi data dalarn bentuk baris dan kolom. Matriks adalah struktur data yang 'statik' , yaitu ukuran maksirnal memorinya sudab ditentukan dari awa!. Batas indeks baris dan kolom harus terdefinisi dengan pasti saat dideklarasi dan tidak dapat diubah-ubah. Matriks digunakan dalam memecahkan banyak persoalan dan memudahkan di dalarn pembuatan analisis-analisis yang mencakup hubungan antar variabe!. Orde matriks adalah representasi dari jumlah baris dan kolom yang memuat data-data dalam rnatriks tersebut. Orde matriks dapat mencapai ratusan bahkan ribuan. Jika pada matriks yang berorde ribuan dilakukan suatu operasi perkalian atau pemangkatan dan diselesaikan secara sekuensial akan membutuhkan waktu yang lama. Oleh karena itu dibutuhkan suatu teknik komputasi yang efektif untuk menyelesaikan persoalan tersebut. Untuk menyelesaikannya akan digunakan metode komputasi parale! yang nantinya akan menggunakan perangkat lunak MPI (Message Passing Interface) dengan menggunakan topologi interconnection network : memori terdistribusi. Operasi matriks termasuk dalam topologi SIMO (Single Instruction Multiple Data Stream). 2. 2.1
Dasar Teori 8truktur Utama Internal Komputer
Sebuah komputer memiliki 4 struktur utama internal komputer, yaitu : I. Central Processing Unit (CPU), berfungsi mengontrol operasi komputer dan membentuk fungsi pengolahan datanya. 2. Main Memory (Memori Utama), berfungsi untuk menyimpan data dan instruksi. 1/0, berfungsi untuk memindabkan data 3. antara komputer dengan lingkungan lainnya. beberapa 4. System Interconnection, mekanisme komunikasi antara CPU, Memori utama dan 110. CPU sendiri memiliki 4 komponen utama yang memiliki fungsi masing-masing, yaitu :
164
1.
2.
3.
4.
Control Unit, berfungsi mengontrol operasi CPU dan pada akhirnya mengontrol komputer Aritmetic Logic Unit (ALU), berfungsi membentuk fungsi-fungsi pengolahan data komputer. Register, berfungsi sebagai penyimpanan internal bagi CPU. CPU Interconnection sejumlah mekanisme komunikasi antara CU, ALU, dan Re gister,
Register sendiri ada beberapa jenis, yaitu : a. General Purpose Register, yang dapat digunakan untuk menyimpan angka dan alamat secara sekaligus, General Purpose Register terdiri dati empat buab register 'yang mempunyai kemarnpuan 16 bit dan dapat dibagi menjadi register Low dan High Bits yang masing-masing berkemarnpuan 8 bit. Contoh dati General Purpose Register : Accumulator Register (AX), Base Register (BX), Counter Register (CX), dan Data Register (OX). b. Pointer Register, register ini menangani 16 bit yang biasanya mengakses memori operand. Register ini terdiri dati : Stack Pointer (SP), Base Pointer (BP), Source Index (81), dan Destination Index (01). Register SP dan BP digunakan untuk menunjuk ke stack. c. Flag Register, register 16-bit khusus dengan posisi bit tunggal yang diketjakan (assigned) untuk menunjukkau status CPU atau hasil-hasil operasi aritrnatik. Dari 16 bit posisi hanya 9 bit posisi yang digunakan dan diberi nama sesuai dcngan 2 jenis tipe flag dasar : I) Control Flag, terdiri dari : Direction Flag (OF), Interrupt Flag (IF), dan Trap Flag (TF) 2) Status Flag, terdiri dati : Carry Flag (CF), Overflow Flag (OF), Zero Flag (ZF), Auxilary Flag (AF), Sign Flag (SF), dan Parity Flag (PF), 4. Segment Register, bertujuan untuk mengarnbil instruksi. Register ini terdiri dati 16 bit, yaitu : a. Code Segment (CS), untuk mencatat segmen dati kode program atau instruksi. b. Data Segment (OS), untuk mwnyimpan alamat dati segmen letak data. c. Stack Segment (SS), untuk menyimpan alarnat segmen memori yang digunakan menjadi stack. d. Extra Segment (ES), untuk menyimpan alamat segmen tambaban. e. Instruction Pointer (IP), merupakan register pasangan CS yang merupakan
ITTelkom Journal on ICT. Volume 1 Nomor2 SeptemberTahun 2012
register utama unutk rnenunjukkan baris perintah program. Pada saat pertama program dijalankan, IP akan langsung menunjuk pada awal program. CS dan IP berfungsi sebagai Program Counter (PC). Pada umumnya semua kode bahasa mesin ditaruh di CS, semua data ditaruh pada data segmen sedangkan operasi PUSH dan POP disediakan tempat di SS. Ada pula empat register utama yang digunakan untuk pertukaran data antara CPU dan memori, yaitu : Program Counter (PC), Instruction Register (IR), Memory Address Register (MAR) dan Memory Buffer Register (MBR).
2.
Seluruh elemen pemrosesan menerima dan menjalankan instruksi yang sarna yang dikirimkan unit pengendali, namun melakukan operasi terhadap himpunan data yang berbeda yang berasal dari aliran data yang berbeda pula.
3.
1.2.1
I.
4.
Pengelompokan Flynn
Berdasarkan jumlah aliran instruksi dan aliran datanya, Michael J. Flyon pada tabun 1966 mengelompokkan komputer digital menjadi empat golongan besar. Aliran insttuksi (instruction stream) adalab urutan instruksi yang dieksekusi oleh sistem komputer, sedangkan alirandata (data stream) adalab urutan data yang diolab termasuk data masukan, bagian dari data, maupundata sementara yang dipanggil atau digunakan oleh aliran instruksi. Keempat kelompok komputer tersebut adalab : Komputer SISD (Single Instruction streamSingle Data stream) Pada komputer jenis ini semua insttuksi dikerjakan terurut satu demi satu, tetapi juga dimungkinkan adanya overlapping dalam eksekusi setiap bagian insttuksi (pipelining). Pada umumnya komputer SISD berupa komputer yang terdiri atas satu buab pemroses ( single processor). Namun komputer SISD juga mungkin memiliki lebih dari satu unit fungsional (modul mernori, unit pemroses, dan lain-lain), selama seluruh unit fungsional tersebut beradadalam kendali sebuah unit pengendali.
Komputer MISD (Multiple stream-Single Data stream)
Instruction
Komputer jenis ini rnerniliki n unit pemroses yang masing-masing menerima dan' mengoperasikan instruksi yang berbeda terhadap aliran data yang sama, dikarenakan setiap unit pemroses rnemiliki unit pengendali yang berbeda. Keluaran dari satu pemroses menjadi masukanbagi pemroses berikutnya. Belum ada perwujudan nyata dari komputer jenis ini kecuali dalambentuk prototipe untuk penelitian.
2.2 Komputasi Paralel Komputasi Paralel adalah salab satu teknik melakukan komputasi secara bersamaan dengan memanfaatkan beberapa komputer independen secara bersamaan. Hal ini diperlukan pada saat kapasitas yang dibutuhkan sangat besar, baik karena harus rnengolah data dalam jurnlah besar ataupun karena tuntutan proses komputasi yang banyak. Kasus kedua pada umumnya ditemukan dalam proses kalkulasi numerik untuk menyelesaikan persamaan matematis di bidang fisika, kimia dan lain-lain..
Komputer SIMD (Single Instruction streamMultiple Data stream) Pada komputer SIMD terdapat lebih dari satu elemen pemrosesan yang dikendalikan oleh sebuah unit pengendali yang sarna.
Komputer MIMD (Multiple Instruction stream-Multiple Data stream) Pada sistem komputer MIMD murni terdapat interaksi di antara n pemroses. Hal ini disebabkan seluruh aliran dari dan ke memori berasal dari space data yang sama bagi semua pernroses. Komputer MIMD bersifat tightly coupled jika tingkat interaksi antara pernroses tinggi dan disebut loosely coupled J'ika tingkat interaksi antara pernroses rendah 4]
2.2.2
Arsitektur Komputer Paralel
Komputer sekuensial berdasarkan klasifikasi Flyon adalah kelompok komputer SISD ± hanya mempunyai satu unit pengendali untuk menentukan insttuksi yang akan dieksekusi. Pada setiap satuan waktu hanya satu instruksi yang dapat dieksekusi, dimana kecepatan akses ke memori dan kecepatan piranti masukan dan keluaran dapat memperlambat proses komputasi. Beberapa metode dibangun untuk menghindari masalah tersebut, seperti penggunaan cache memory. Namun komputer sekuensial ini tetap mengalami keterbatasan j ika menangani masalah yang memerlukan kecepatan tinggi. Halhal tersebut di atas pada akhirnya melatar belakangi labirnya sistem komputer paralel. Berdasarkan klasifikasi Flynn, komputer paralel termasuk kelompok SIMD atau MIMD. Komputer paralel mempunyai lebih dari satu unit pemroses dalam sebuah komputer yang sama. Hal yang membuat suatu komputer dengan
Analisis danIrnplementasi Sistem pengolehan DataMatriks Pada Komputasi Paralel Menggunakan MPI dan Metod. Strassen[Sinta KartikaMaharani)
165
banyak prosesor disebut sebagai komputer paralel adalah bahwa seluruh prosesor tersebut dapat beroperasi secara simultan. Jika tiap-tiap prosesor dapat mengerjakan saru juta operasi tiap detik, maka sepuluh prosesor dapat mengerjakan sepuluh . juta operasi tiap detik, seratus prosesor akan dapat mengerjakan seratus juta operasi tiap detiknya. Pada dasarnya aktivitas sebuah prosesor pada komputer paralel adalah sama dengan aktivitas sebuah prosesor pada komputer sekuensial. nap prosesor membaca (read) data dari memori, memprosesnya dan menuliskannya (write) kembali ke memori. Aktivitas komputasi ini dikerjakan oleh seluruh prosesor secara parallel.l" 2.2.3
Hubungan Antar Prosesor
Sistem komputer paralel dengan banyak prosesor yang bekerja secara simultan memerlukan kemampuan untuk membagi data dan berkomunikasi antar prosesor. Berdasarkan kedua kebutuhan tersebut, terdapat dua arsitektur komputer paralel, yaitu memori bersarna dan message passing. Pada arsitektur memori
bersama, biasanya disebut multiprosesor (multiprocessor), setiap prosesor dapat mengakses memori global dan menggunakan isi data dan struktur data yang disimpan dalam memori bersarna (shared memory). Prosesor berkomunikasi dengan prosesor lain dengan menulis pesan ke memori global dimana prosesor kedua dapat membaca pesan tersebut pada lokasi memori yang sama. Skema arsitektur memori bersama dapat dilihat pada Garnbar I dibawah :
Gambar 1. Shared memory Multiprocessor''
Semua prosesor dapat melaknkan komputasi secara paralel dan masing-masing dapat mengakses memori melalui bus. Bus bertanggungjawab mengatur permintaan pemakaian memori yang berlangsung secara simultan oleh beberapa prosesor. Bus juga bertanggungjawab untuk meyakinkan bahwa semua prosesor dilayani secara adil dengan waktu tunda akses yang minimum. Salah satu kesulitan utama dari arsitektur multiprosesor dengan memori bersarna adalah kemungkinan adanya tabrakan memori (memory contention). Peristiwa ini terjadi ketika beberapa prosesor mencoba untuk mengakses memori
J66
bersama dalam periode waktu yang sangat singkat, sehingga memori tidak akan dapat menampung semua permintaan secara simultan. Akibatnya beberapa prosesor akan hams menunggu sampai prosesor lainnya dilayani. Kemungkinan terjadinya tabrakan memori ini berbanding lurus dengan bertambahnya jumlah prosesor. Beberapa teknik telah dikembangkan untuk mereduksi tabrakan memori dan membuat sistem menjadi lebih efisien. Salah satu teknik dengan adanya cache memory lokal pada masing-masing prosesor. Cache memory ini digunakan untuk menyimpan salinan isi memori yang paling barn digunakan. Hal ini menimbulkkan masalah barn, yaitu cache coherent problem, dimana akan banyak salinan isi memori pada cache yang berbeda yang menimbulkan adanya kemungkinan isi cache yang outdate setelah isi memori bersarna diperbarui (update). Teknik lain untuk mereduksi tabrakan memori adalah dengan membagi memori bersama tersebut menjadi beberapa bagian modul yang dapat diakses seeara paralel oleh prosesor yang berbeda. Data disebar ke beberapa modul memori untuk menghindari kemungkinan permintaan yang simultan ke modul memori yang sama oleh beberapa prosesor. Setiap n prosesor dapat mengakses m modul memori melalui jaringan penghubung prosesor ± memori (processor ± memory interconnection network). Skema arsitektur memori bersama dengan jaringan penghubung prosesor ± memori ditunjukkan oleh Gambar 2 berikut :
Gambar 2. Memori Bersama dengan Modulmodul 14J Jaringan penghubung un menyebabkan beberapa prosesor dapat mengakses modul-modul memori yang berbeda secara simultan. Biaya dan kinerja tipe multiprosesor ini tergantung pada raneangan internal jaringan penghubung. Beberapa eontoh jaringan penghubung ini adalah j aringan butterfly; shuffle-exchange, cross-bar dan omega. Pendekatan lain untuk mereduksi tabrakan memori adalah dengan mengeliminasi seluruh memori bersama dan menyediakan memori lokal untuk setiap prosesor. Jenis komputer paralel dengan memori yang tersebar ini disebut multikomputer.
ITTelkomJournal on leT, Volume 1 Nomor2 September Taboo2012
-
Setiap pasangan memori - prosesor ini berlaku seperti halnya komputer sekuensia!. Prosesor ± prosesor dapat membaca (read) dan menulis (write) data secara bebas dengan menggunakan memori lokalnya masing-masing, Sebuah prosesor tidak dapat mengakses lokal memori prosesor lain dengan secara langsung, tetapi prosesor tersebut dapat mengirim atau menerima data dari prosesor lain dengan mengunakan jaringan komunikasi message passing. Sehingga data dapat disebar danditukar sesuai dengan kebutuhan. [4] Skema arsitektur Message-Passing Muticomputer dapat dilihat pada Gambar 3: M
M
p
p
M
••
p
Message-Passing
_11<
• •
•
CommunicaliOlJ
•
Dari definisi speed up tersebut, lahir efisiensi, E (n), untuk sistem dengan n prosesor, Efisiensi didefinisikan sebagai berikut : E(fi)
= Sin) = ~ n
2.3
Matriks
2.3.1
Definisi Matriks
[4J
nT(n)
Dalam matematika, matriks adalah sebuah tabel dari kuantitas-kuantitas abstrak yang bisa dijumlahkan dan dikalikan. Matriks adalah sekumpulan , informasi yang setiap individu elemennya terdefinisi berdasarkan dua buah indeks (biasanya disebut baris dan kolom). Setiap elemen matriks dapat diakses secara langsung jika kedua indeks diketahui dan indeksnya harns bertipe yang mempunyai keterurutan. Struktur matriks ditunjukkan oleh Gambar 4 berikut : Malriks A(m x n)
p
p
M
M
•
•
p
ai,j
nkolom
jp
m
bans
Keterangan : P: Prosesor M: Memori
A= peroba1um
a 0.0 a 0,1 a 0,2 a 1.0 a I) au a 2.0 a 2J a 2,2
Gambar 3 Message-passing Multicomputer" 2.2.4
Pemrograman Paralel
Pemrograman paralel adalah teknik pemrograman komputer yang memungkinkan eksekusi perintah secara bersamaan, baik dalam komputer dengan satu ataupun banyak prosesor. Tujuan utama dari pemrograman paralel adalah untuk meningkatkan performa komputasi. Semakin banyak hal yang bisa dilakukan secara bersamaan, semakin banyak pekerjaan yang bisa diselesaikan. Performa dalam pemrograman paralel diukur dari berapa banyak peningkatan kecepatan (speed up) yang diperoleh dengan menggunakan teknik paralel dibanding teknik sekuensial. Parameter lain yang digunakan untuk mengukur kinerja program paralel adalah waktu eksekusi, yaitu waktu berlangsungnya program paralel yang dieksekusi oleh satu prosesor.[5]
Garnbar4 Struktur Matriks 2.3.2
Perkalian Matriks Biasa
Perkalian matriks biasa adalah perkalian matriks dengan metode standar yang biasa digunakan. Contoh penyelesaian perkalian matriks menggunakan metode biasalkonvensional (Matriks A dan B) :
[Al=[A
li
All
[C]
= [(Au' Bn ) + (An' Bn ) (A". B,,) + (A12 • B22 )J (A ZI .. 8 u ) + (A zz .. 8 ztl (A Zl • 8 1Z) + (A zz .8zz)
Speed up dapat didefmisikan sebagai berikut S/" In/
dimana:
= T(n) T(l)
[4J
S(n) = speed up TO) ~ waktu eksekusi operasi pada sistem satu prosesor, T(n) ~ waktu eksekusi pada sistem n prosesor.
2.3.3 Perkalian Matriks Strassen
dengan Metode
Pada tahun 1969, Volker Strassen mempublikasikan algoritma Strassen. Meskipun algoritma ini hanya sedikit lebih cepat daripada algoritrna standar perkalian matriks, dialah yang pertama menjelaskan bahwa eliminasi Gauss
Analisis dan Implementasi Sistem pengolahan Data Matriks Pada Komputasi Paralei Menggunakan MPI dan Metode Strassen [Sinta Kartika Maharani)
167
adalah tidak optimal. Misalkan ada 2 buah matriks persegi, dan ingin menghitung produk matriks C sebagai : .
Untuk mendapalkan matriks C dengan metode Strassen dibutuhkan 7 operasi perkalian dan 18 operasi penjumlahan/pengurangan.!" XI = (All + A,,) (B II + B,,) X, = (A'l + A,,) B II X, = All (B" - B,,) X. = A" (B" - B II) X s = (All + Ad B" X. = (A21 - All) (B II + Bd X, = (A" - A2, ) (B" + B,,)
CII = X, + X. - X, + X, C , 2 = X,+ x, C2 1 = X,+ X. C" = XI + X, - X2 + X. 3.
ANALISIS DAN PERANCANGAN
3.1
Desain Sistem Utama
Pada penelitian im, perkalian matriks dilakukan dengan 2 metode, metode konvensional dan metode Strassen dengan input matriks secara random. Desain sistem utama ditunjukkan oleh Gambar 5 berikut :
~
1m
EFJ
~ <~';;'
NO
,--i---,
i--~2-(~
Gambar 6 Flowchart algoritrna perkalian rnatriks dengan metode konvensional 3.1.2
Flowchart Metode Strassen
Algoritrna Strassen diperkenalkan oleh Volker Strassen pada tahun 1969. Algoritrna ini digunakan untuk perkalian matriks yang secara asimtot lebih cepat daripada perkalian matriks standar dan sangat berguna dalam penggunaannya untuk matriks yang berukuran besar. Flowchart algoritma Strassen ditunjukkan oleh Gambar 7 berikut:
EJ Gambar 5 Desain Sistem Utarna 3.1.1
Flowchart Metode Konvenslenal
Metode konvensional disini adalah perkalian matriks dengan cara biasa. Flowchart dari algoritrna perkalian matriks metode konvensional ditunjukkan oleh Gambar 6 berikut :
Garnbar 7 Flowchart algoritma perkalian rnatriks dengan metode Strassen
168
ITTelkomJournal on leT, Volume 1 NomOI 2 SeptemberTahun 2012
3.2 Alur Peraneangan
3.3 Skenario Pengujian
Alur peraneangan algoritma konvensional dan implementasi dalam MPI adalah : I. Matriks yang akan diuji dibuat seeara random dengan tipe bilangan integer 0-9. Matriks yang diuji juga bisa diambil dari file yang tersimpan. 2. Masuk ke program utarna, dilakukan inisialisasi mpiRank ~ 0, mpiSize = O. mpiRank adalah proses ke-n atau slave ke-n. mpiSize adalah jumlah slave yang akan mengeksekusi program, jumlah baris/vektor yang dikerjakan oleh suatu slave adalah n_order dibagi mpiSize. Juga dilakukan inisialisasi sizeSent ~ O. sizeSent adalah ukuran vektor/baris. 3. Paralelisasi yang dilakukan di algoritma konvensional ini, jumlah baris di matriks A dibagi dengan jumlah proses yang akan mengeksekusi. Sedangkan matriks B sendiri nanti dibroadeast oleh proses ke-O yang bertindak sebagai master, sehingga tiap proses dapat mengakses tanpa dikirimi dari master. Jadi setiap proses akan menerima beberapa baris matriks A dan kemudian akan melakukan perkalian dengan seliap kolom dari matriks B. 4. Matriks hasil diberi nama matriks C dan semua elemennya diinisialisasi sebagai O. 5. Master sendiri ikut melakukan perkalian beberapa baris A yang tadi sudah dibagi. Setelah master melakukan perkalian, master menunggu semua slave mengirimkan hasilnya ke master, kemudian menyusun matriks baru bemama C (yang tadi sudah diinisialisasi) yang merupakan hasil perkalian dari matriks A dan B.
Dalam kegiatan penelitian ini akan dilakukan skenario pengujian dalam I komputer dengan skenario sebagai berikut ; I. Melakukan penguj ian perkalian matriks seeara sekuensial dengan ukuran matriks 1024xl024 dan 2048x2048 dimana matriks yang dikalikan dibuat seeara aeak. 2. Melakukan pengujian perkalian matriks seeara paralel dengan jumlah proses 2, 4, 8, 16 dan 32 proses pada ukuran matriks 1024xl024 dan jumlah proses 2, 4, 8, 16 pada ukuran matriks 2048x2048. 3. Melakukan pengujian perkalian rnatriks seeara paralel metode Strassen dengan ukuran matriks 1024xlO)4 dan 2048x2048.
Alur peraneangan algoritma Strassen dan implementasi dalam MPI adalah : I. Matriks yang akan diuji dibuat seeara random dengan lipe bilangan integer 0-9. 2. Masnk ke program utarna, matriks A dan B dibagi menjadi submatriks-submatriks yang berukuran masing-masing 2x2. Seliap matriks dibagi secara vertikal dan horizontal terns menerns sampai ukurannya menjadi masing-masing 2x2. Proses divide and conquer ini merupakan proses paralelisasi yang terjadi pada metode Strassen. 3. Kemudian dilakukan proses perkalian matriks dengan metode Strassen. Matriks hasil diberi nama matriks C dan semua elemennya diinisialisasi sebagai O. 4. Setelah proses perkalian selesai, matriks C disusun yang merupakan hasil perkalian dari matriks A dan B.
4.
IMPLEMENTASI DAN PENGUJIAN
4.1
Metode Sekuensial
Dari 10 kali pereobaan perkalian matriks ukuran I024xl 024, didapatkan hasil waktu eksekusi rata-rata 74,225 detik dan penggunaan memori 100 MB. Sedangkan dari pereobaan perkalian matriks ukuran 2048x2048, didapatkan hasil waktu eksekusi rata-rata 232,6507 detik dan penggunaan memori 164 MB. Hasil pereobaan metode sekuensial ini nantinya akan digunakan untuk menghitung speed-up dan efisiensi pemroses pada pemrosesan paralel pada metode
konvensional 4.2
Metode Konvensional
Pada pereobaan perkalian matriks ukuran 1024xl024 dengan metode konvensional yang diimplementasikan menggunakan MPI, dilakukan masing-masing 10 pereobaan dengan jumlah proses 2, 4, 8, 16, dan 32 proses. Di bawah adalah tabel 4.1 yang menunjukkan hasil rata-rata dari setiap proses. Tabel I Hasil rata-rata setiap proses matriks ukuran 1024xlO24 Jumlah Waktu Eksekusi Waktu Eksekusi Proses Master (detik) Rata-rata Slave (detik) 2 56,3556855 56,4433892 4 70,0208303 43,83582 8 68,581358 40,897425 16 64,64298 39,38314 32 73,775171 50,578246 Saat eksekusi dengan 2 proses, membutuhkan memori 65 MB, 108 MB untuk 4 proses, 159 MB untuk 8 proses, 320 MB untuk 16 proses dan 640 MB untuk 32 proses.
Analisis danImplementasi Sistempengolahan DataMatriks Pada Komputasi Paralel MenggunakllnMPI dan Metod. Strassen [Sinta Kartika Maharani]
169
Berdasarkan tabel di alas terlihat bahwa saat jumlah proses 16, waktu eksekusi rata-rata slavenya adalah yang paling kecil (39,383 detik), meskipun waktu eksekusi masternya lebih besar daripada waktu eksekusi master saat jwnlah proses 2. Secara teoritis, semakin banyak proses yang melakukan pekerjaan, maka pekerjaan itu akan cepat selesai. Tapi hal ini tidak berlaku jika jumlah proses ditambah menjadi 32 proses. Saat 32 proses, justru waktu eksekusi melambat. Hal ini terjadi karena jika menggunakan 32 prosesor justru akan lebih banyak menggunakan waktu untuk membagi thread menjadi 31 dan ini membuat master harus menunggu semua slave selesai melakukan eksekusi dan mengirimnya kembali ke master kemudian menyusun kembali basil matriks. Sehingga, 16 proses merupakan jumlah prosesor ideal untuk melakukan perkalian matriks ukuran I024x 1024. Menurut Hukum Amdahl, semakin banyak prosesor dapat meningkatkan kecepatan, tetapi pada suatu titik jumlah prosesor, kecepaian akan mencapai jenuh. Sedangkan penggunaan memori untuk melakukan pekerjaan, makin banyak jumlah pekerjaan yang harus dilakukan, makin banyak source yang dibutuhkan agar pekerjaan tersebut dapat segera selesai. Peningkatan penggunaan memori mencapai rata-rata 78,66%. Pada percobaan perkalian matriks ukuran 2048x2048 dengan metode konvensional yang diimplemenlasikan menggunakan MPI, dilakukan masing-masing 10 percobaan dengan jumlah proses 2, 4, 8, dan 16 proses. Di bawah adalah tabel 2 yang menunjukkan hasil rata-rata dari setiap proses. Tabel2 Hasil rata-rata setiap proses matriks ukuran 2048x2048 Jumlah Waktu Eksekusi Waktu Eksekusi Proses Master (detik) Rata-rata Slave (detik) 2 589,46171 589,734285 4 725,845405 442,425868 16 64,64298 39,38314 16 646,667257 340,2899215 Saat eksekusi dengan 2 proses, membutuhkan memori 175 MB, 293 MB untuk 4 proses, 559 MB untuk 8 proses, dan 1052 MB untuk 16 proses. Berdasarkan tabel di alas terlihat bahwa saat jumlah proses 16, waktu eksekusi rata-rata slavenya adalah yang paling kecil (340,39 detik), meskipun waktu eksekusi masternya lebib besar daripada waktu eksekusi master saat jumlah proses 2. Secara teoritis, semakin banyak proses yang melakukan pekerjaan, maka pekerjaan itu akan cepat selesai. Terlihat bahwa saatjumlah proses 16 waktu eksekusinya lebih cepat dibanding jumlah proses 2, 4, dan 8. Saat akan dinaikkan menjadi 32
170
proses, program tidak dapat dieksekusi karena source memori yang digunakan tidak mencukupi.
4.3 Speed-up dan Elisiensi Perhitungan speed-up dan efisiensi membutuhkan data waktu eksekusi sekuensial dan waktu eksekusi paralel dengan metode konvensional. Di bawah adalah tabel 4.3 penghitungan speed-up dan eftsiensi pemroses saat perkalian matriks ukuran 1024x1024. Tabel 3 Hasil speed-up proses matriks ukuran 1024xl024 Jumlah Speed-up Eftsiensi Proses 2 1,315043 1,315043 •4 1,693243 0,564414 1,822904 0,260415 8 1,884696 0,125646 16 004734 32 1,467535 Sedangkan tabel 4 di bawah adalah tabel penghitungan speed-up dan eftsiensi pemroses saat perkalian matriks ukuran 2048x2048. Tabel 4 Hasil speed-up proses matriks ukuran 2048x2048 Jumlah Efisiensi Speed-up Proses 0,3945 0,3945 2 4 0,525851 0,175284 0,080371 8 0,562595 16 0,683682 0,045579 Pada analisis sebelumnya, jumlah proses yang ideal untuk eksekusi perkalian matriks ukuran 1024xl024 dan 2048x2048 adalah 16 proses. Dan berdasarkan 2 tabel di alas, speed-up yang baik adalah yang nilainya besar dan eftsiensi yang baik adalah yang nilainya makin kecil. Untuk eksekusi perkalian matriks ukuran 1024xl024 speed-up dan efisiensi saat 16 proses adalah 1,88 dan 0,13. Meskipun eftsiensi terkecil dirniliki saat jumlah prosesnya 32, namun speed-upnya lebih tinggi dibandingkan saat jumlah proses 16. Sedangkan untuk eksekusi matriks ukuran 2048x2048, speed-up dan efisiensi saat 16 proses adalah 0,68 dan 0,05. 4.4 Metode Strasseo Dari 10 kali percobaan perkalian matriks ukuran I 024x I024, didapatkan basil waktu eksekusi rata-rata 482,891 detik dan penggunaan memori 100 MB. Sedangkan dari percobaan perkalian matriks ukuran 2048x2048, didapatkan basil waktu eksekusi rata-rata 3878,218 detik dan penggunaan memori 344 MB.
ITTelkom Journal on leT, Volume 1 Nomor 2 September Tabun 2012
4.5
Analisa Perbandingan Konvensional dan Strassen
Metode
Metode Strassen prinsipnya mengurangi jumlah perkalian untuk mempercepat proses perkalian dua matriks dengan orde lebih besar, Tapi pengurangan ini harus diganti dengan menambah operasi penjumlahan dan pengurangan yang jumlahnya lebih banyak. Dari sisi total operasi yang diselesaikan, jumlahnya Iebih sedikit dibanding algoritma biasa ketika ukuran matriks diatas 512. sehingga A1goritma Strassen ini cocok diimplementasikan untuk ukuran matriks yang besar. Untuk perkalian matriks ukuran 1024xl024 menggunakan algoritrna Strassen total operasinya 1,971x109 sedangkan menggunakan algoritma konvensional total operasinya 2,146xI0 9. Walaupun Algoritma Strassen prinsipnya lebih cepat dalarn proses perkalian dua matriks dengan orde banyak, tapi dalam percobaan hasilnya lebih lambat daripada algoritma biasa (metode konvensional). Hal tersebut terjadi karena algoritma biasa (metode konvensionaI) menggunakan komputasi paralel, sehingga meningkatkan speed-up pemrosesannya. Sedangkan metode Strassen dibuat tidak menggunakan komputasi paralel seperti metode algoritma konvensional, Hasil untuk perkalian matriks orde 1024x1024, metode Strassen Iebih lambat 88,32%, dan penggunaan memorinya 35% lebih banyak dibandingkan metode konvensiona!. Sedangkan untuk perkalian matriks orde 2048x2048, metode Strassen lebih lambat 84,8% dan penggunaan memorinya 49,13% lebih banyak dibandingkan
metode konvensional. 5. 5.1
KESIMPULAN DAN SARAN Kesimpulan
Berdasarkan hasil percobaan yang dilakukan, dapat diambil beberapa kesimpulan : 1. Pada saat pengujian perkalian matriks dengan metode konvensional ukuran 1024x1024, jumlah prosesor ideal (untuk single computer) untuk mengeksekusi program tersebut adalah 16 proses. Dengan waktu ekseknsi rata-rata master 64,643 detik dan waktu eksekusi ratarata slave 39,383 detik. Sedangkan 2. speed-up dan efisiensinya mencapai 1,88 dan 0,13. 3. Pada saat pengujian perkaIian matriks dengan metode konvensional ukuran 2048x2048, jumlah prosesor ideal (untuk single computer) untuk mengeksekusi program tersebut adalah 16 proses. Dengan waktu eksekusi rata-rata master 646,667 detik dan waktu ekseknsi ratarata slave 340,39 detik. Sedangkan speed-up dan efisiensinya mencapai 0,68 dan 0,05.
4. Perkalian matriks rnenggunakan metode Strassen membutuhkan waktu yang lebih lama dibanding perkalian matriks menggunakan algoritma konvensional karena tidak menggunakan komputasi paralel 5. Dengan metode Strassen, eksekusi perkalian matriks ukuran 1024xlO24 membutuhkan waktu rata-rata 482,891 sekon, sedangkan eksekusi perkalian matriks ukuran 2048x2048 membutuhkan waktu 3878,218 sekon. 6. Untuk perkalian matriks orde 1024xl024, metode Strassen lebih lambat 88,32%, dan penggunaan memorinya 35% lebih banyak dibandingkan metode konvensiona!. 7. Untuk perkalian matriks orde 2048x2048, metode Strassen lebih lambat 84,8% dan penggunaan memorinya 49,13% lebih banyak dibandingkan metode konvensiona!. 5.2 Saran Saran untuk ke depan : I. Pengujian yang dilakukan dalam penelitian penelitian ini masih terbatas pada satu komputer karena adanya kesulitan mengeksekusi di dua komputer atau lebih, Semoga ke depannya ada yang melanjutkan topik ini dengan menggunakan lebih dari satu komputer. 2. Ada penelitian lainnya mengenai topik komputasi parale!. DAFTAR PUSTAKA Bersetekas, D.P. and Tsitsklis, J. N., Parallel and Distributed Computation : Numerical Methods, NJ : Prentice-Hall, 1989 [2] Blaise, Barney. 2012. Message Passing Interface (MPI). [Online]. Tersedia http://computing.lln!.gov/tutorials/mpil, [30 April 2012] [3] Freeman, T.L and Phillips, C, Parallel Numerical Algorithms, Prentice-Hall, 1992 Advanced Computer [4] Hwang, Kai., [I]
Architecture Parallelism, Scalability, Programmability, McGraw-Hill, 1993 [5] Kurniawan, Agus. 2010. Pemrograman Paralel dengan MPI & C. Yogyakarta : [6]
Penerbit Andi, Lakshmivarahan, Sand K. Dhall, Sudarshan.
1990. Analysis and Design or Parallel Algorithms. New York : McGraw-Hill [7] [8]
Publishing Company. Lester, Bruce P., The Art of Parallel Programming, NJ : Prentice-Hall, 1993 Mathews, John. H., Numerical Methods for Mathematics, Science, and Engineering, Second Edition, NJ : Prentice-Hall, 1992
Analisis dan Implementasi Sistem pengolahan DataMatriks Pada Komputasi Paralel Menggunakan MPIdan Metode Strassen [SintaKartika Maharani]
17!
[9]
Purbasari, Ayi. Teknis dan Strategi Pembangunan Algoritma Paralel. 2012.
[Online]. Tersedia: http://www.ilmukomputer.com/pengantar/ayi purbasari-teknisalgoritma.php [30 April 2012] [10] Quinn, Michael J, Designing Efficient
Algorithms
for
McGraw-Hill, 1987
Parallel
Computers,
[11] Rabdu, Konsep Pemrograman Paralel. 2012. [Online]. Tersedia: http://rabdu.blogspot.com/2010/10Ikonseppemrograman-paralel.html [30 April 2012] [12] Wilkinson, Barry and Allen, Michae1.2005.
Parallel Programming Teknik dan Aplikasi Menggunakan Jaringan Workstation dan Komputer Paralel. Yogyakarta : Penerbit Andi.
.
172
ITTelkomJournal on ICf, Volume 1 Nomor2 September Tahun 2012
