ANALISIS DAN IMPLEMENTASI ALGORITME ADVANCED ENCRYPTION STANDARD (AES) SECARA PARALEL SAYED ZULFIKAR

ANALISIS DAN IMPLEMENTASI ALGORITME ADVANCED ENCRYPTION STANDARD (AES) SECARA PARALEL

SAYED ZULFIKAR

DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2012

ANALISIS DAN IMPLEMENTASI ALGORITME ADVANCED ENCRYPTION STANDARD (AES) SECARA PARALEL

SAYED ZULFIKAR

Skripsi sebagai salah satu syarat untuk memperoleh gelar Sarjana Komputer pada Departemen Ilmu Komputer

DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2012

ABSTRACT SAYED ZULFIKAR. Analysis and Implementation of Advanced Encryption Standard (AES) Parallel Algorithm supervised by HENDRA RAHMAWAN and ENDANG PURNAMA GIRI. AES is an algorithm for symmetric key cryptography. AES is expected to replace Data Encryption Standard (DES) as a recognized standard for various applications. The complexity of AES encryption and decryption process is O(n), it has fast computation in both encryption and decryption but its execution time will increase as the input data increase. In this research the AES algorithm would be parallelized by dividing the data to each processor (domain decomposition) and by dividing the constituent computing of AES to each processor (functional decomposition), and their performance would be analyzed. Parallel implementation of AES algorithm uses Message Passing Interface (MPI). The objectives of this research are to measure and analyze the performance of parallel AES algorithm using performance metrics. The best result of the parallel AES algorithm in this research is in the decryption process using domain decomposition method. A file with 118.525 MB size has 127.227 seconds decryption execution time using sequential AES algorithm, whereas using 16 processors, its decryption execution time is 34.896 seconds. The speedup is 3.646 and the efficiency is 0.228. This result is not good enough because the speedup is not equal to the number of processors used and the efficiency is below one. This is because the AES decryption in this research has a fast computational process, yet it has a big overhead for data communication. The worst result of the parallel AES algorithm is in the decryption process using functional decomposition method. Using the same file and three processors, the decryption execution time is 168.089 seconds. The speedup is 0.755 and the efficiency is 0.252. This is due to the fact that computing process decomposition is not equally distributed among the processes and the use of MPI blocking communication routine which cause a big overhead for data communication. Both parallel algorithms used in this research are not cost-optimal. Keywords: AES algorithm, Message Passing Interface (MPI), parallel, performance metrics, pipeline.

Judul Skripsi : Analisis dan Implementasi Algoritme Advanced Encryption Standard (AES) Secara Paralel Nama : Sayed Zulfikar NIM : G64070096

Menyetujui:

Pembimbing I

Pembimbing II

Hendra Rahmawan, S.Kom. M.T. NIP. 198205012009121004

Endang Purnama Giri, S.Kom. M.Kom. NIP. 198210102006041027

Mengetahui: Ketua Departemen Ilmu Komputer

Dr. Ir. Agus Buono, M.Si. M.Kom. NIP. 196607021993021001

Tanggal Lulus:

PRAKATA Puji dan syukur penulis panjatkan ke hadirat Allah subhanahu wa-ta’ala yang telah memberikan rahmat dan hidayah-Nya sehingga penulis dapat menyelesaikan tugas akhir ini. Selawat serta salam pada junjungan kita Nabi Muhammad shallallahu `alaihi wa sallam beserta keluarga dan sahabatnya. Penulis mengucapkan terima kasih kepada semua pihak yang telah membantu dalam penyelesaian tugas akhir ini, yaitu : 1 Kedua orang tua tercinta (Said Basri Umar dan Cut Mardiani) yang telah memberikan dukungan, bantuan, perhatian, dan doa sehingga penulis dapat menyelesaikan studi di Departemen Ilmu Komputer IPB. 2 Bapak Hendra Rahmawan, S.Kom. M.T. dan Bapak Endang Purnama Giri, S.Kom. M.Kom. selaku dosen pembimbing. 3 Ibu Ir. Sri Wahjuni, M.T. selaku dosen penguji. 4 Seluruh dosen pengajar dan civitas akademika Departemen Ilmu Komputer FMIPA IPB. 5 Keluarga besar Ilkomerz 44. 6 Semua pihak yang telah membantu pelaksanaan tugas akhir ini baik secara langsung maupun tidak langsung yang belum disebutkan di atas. Penulis menyadari dalam tugas akhir ini masih banyak kekurangan. Oleh karena itu, penulis mengharapkan kritik dan saran yang membangun. Semoga penelitian ini dapat bermanfaat bagi semua pihak yang membutuhkan. Aamiin.

Bogor, Februari 2011

Sayed Zulfikar

RIWAYAT HIDUP

Penulis lahir di Jakarta pada tanggal 26 Juni 1989. Penulis merupakan anak ketiga dari tiga bersaudara, pasangan Said Basri Umar dan Cut Mardiani. Penulis lulus dari Sekolah Menengah Atas Negeri 28 Jakarta pada tahun 2007 dan pada tahun yang sama diterima di Program Studi Ilmu Komputer, Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Pertanian Bogor (IPB) melalui jalur SPMB. Selama mengikuti perkuliahan, penulis aktif dalam berbagai kegiatan termasuk menjadi asisten praktikum Mata Kuliah Komunikasi Data dan Jaringan Komputer pada tahun 2010-2011, Organisasi Komputer pada tahun 2010-2011, dan Pemrosesan Paralel pada tahun 2011-2012. Penulis aktif di bidang non-akademis ditandai dengan menjadi panitia Masa Perkenalan Departemen pada tahun 2009 sebagai anggota divisi Logistik dan Tranportasi dan acara tahunan HIMALKOM, IT TODAY, pada tahun 2009 sebagai ketua. Penulis pernah melakukan Praktik Kerja Lapangan di PT. Pertamina RU VI Balongan, Indramayu Jawa Barat selama 35 hari kerja. Penulis membuat Sistem Informasi Online Attendance System (OASYS) PT. Pertamina RU VI Balongan (Modul Harian) selama PKL di sana.

DAFTAR ISI Halaman DAFTAR GAMBAR ...................................................................................................................... vii DAFTAR LAMPIRAN ..................................................................................................................viii PENDAHULUAN............................................................................................................................. 1 Latar Belakang .............................................................................................................................. 1 Tujuan Penelitian .......................................................................................................................... 1 Ruang Lingkup Penelitian ............................................................................................................. 1 Manfaat Penelitian ........................................................................................................................ 1 TINJAUAN PUSTAKA .................................................................................................................... 2 Kriptografi ..................................................................................................................................... 2 Kotak-S ......................................................................................................................................... 2 Inversi Kotak-S ............................................................................................................................. 2 Algoritme AES .............................................................................................................................. 2 Proses Enkripsi AES ..................................................................................................................... 2 Proses Dekripsi AES ..................................................................................................................... 4 Ekspansi Kunci.............................................................................................................................. 5 Pemrograman Paralel .................................................................................................................... 5 Metode Foster................................................................................................................................ 5 MPI (Message-Passing-Interface) ................................................................................................ 6 Performance Metrics ..................................................................................................................... 6 METODE PENELITIAN .................................................................................................................. 6 Studi Pustaka ................................................................................................................................. 7 Analisis Algoritme AES Sekuensial .............................................................................................. 7 Implementasi Algoritme AES Sekuensial ..................................................................................... 7 Penerapan Metode Foster ke Algoritme AES Domain Decomposition ......................................... 7 Analisis dan Implementasi Algoritme AES Paralel Domain Decomposition ................................ 7 Penerapan Metode Foster ke Algoritme AES Pipeline ................................................................. 7 Analisis dan Implementasi Algoritme AES Pipeline .................................................................... 7 Perancangan Percobaan ................................................................................................................. 7 Percobaan ...................................................................................................................................... 7 Analisis Kinerja ............................................................................................................................. 7 HASIL DAN PEMBAHASAN ......................................................................................................... 7 Analisis Algoritme AES Sekuensial .............................................................................................. 7 Implementasi Algoritme AES Sekuensial ..................................................................................... 8 Penerapan Metode Foster ke Algoritme AES Paralel Domain Decomposition ............................. 8 Analisis dan Implementasi Algoritme AES Paralel Domain Decomposition ................................ 9 Penerapan Metode Foster ke Algoritme AES Pipeline ............................................................... 10 Analisis dan Implementasi Algoritme AES Pipeline .................................................................. 11 Perancangan Percobaan ............................................................................................................... 13 Percobaan .................................................................................................................................... 13 Analisis Kinerja ........................................................................................................................... 14 Waktu Eksekusi Sekuensial .................................................................................................... 14 Waktu Eksekusi Paralel ........................................................................................................... 14 Speedup ................................................................................................................................... 15 Efisiensi ................................................................................................................................... 16 Cost ......................................................................................................................................... 17 Overhead ................................................................................................................................. 17 KESIMPULAN DAN SARAN ....................................................................................................... 18 Kesimpulan ................................................................................................................................. 18 Saran............................................................................................................................................ 18

v

Halaman DAFTAR PUSTAKA ..................................................................................................................... 18 LAMPIRAN .................................................................................................................................... 21

vi

DAFTAR GAMBAR Halaman 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

Kotak-S. ...................................................................................................................................... 2 Inversi kotak-S. ........................................................................................................................... 2 Proses umum enkripsi dan dekripsi AES. ................................................................................... 3 Matriks input, state, dan output. .................................................................................................. 3 Ilustrasi proses SubBytes. ........................................................................................................... 3 Ilustrasi proses ShiftRows. .......................................................................................................... 4 Matriks polimat. .......................................................................................................................... 4 Ilustrasi proses AddRoundKey. ................................................................................................... 4 Matriks inversi polimat ............................................................................................................... 4 Proses ekspansi kunci AES. ........................................................................................................ 5 Ilustrasi metode Foster. ............................................................................................................... 5 Metode penelitian. ....................................................................................................................... 6 Algoritme enkripsi AES sekuensial. ........................................................................................... 8 Ilustrasi partisi algoritme AES paralel domain decomposition. .................................................. 8 Ilustrasi komunikasi algoritme AES paralel domain decomposition ........................................... 9 Ilustrasi aglomerasi algoritme AES paralel domain decomposition ............................................ 9 Algoritme enkripsi AES paralel domain decomposition ........................................................... 10 Ilustrasi partisi algoritme AES pipeline. ................................................................................... 10 Ilustrasi komunikasi algoritme AES pipeline. ........................................................................... 11 Ilustrasi aglomerasi algoritme AES pipeline. ............................................................................ 11 Algoritme implementasi AES pipeline...................................................................................... 12 Topologi jaringan star. .............................................................................................................. 13 Perbandingan waktu eksekusi enkripsi dan dekripsi AES sekuensial. ...................................... 14 Waktu eksekusi enkripsi AES paralel domain decomposition. ................................................. 14 Waktu eksekusi dekripsi AES paralel domain decomposition. ................................................. 14 Waktu eksekusi enkripsi AES pipeline. .................................................................................... 15 Waktu eksekusi dekripsi AES pipeline. .................................................................................... 15 Speedup enkripsi AES paralel domain decomposition. ............................................................. 15 Speedup dekripsi AES paralel domain decomposition. ............................................................. 15 Speedup enkripsi dan dekripsi AES paralel domain decomposition dengan jumlah proses 8 buah. .......................................................................................................................................... 15 Speedup enkripsi dan dekripsi AES pipeline............................................................................. 16 Efisiensi enkripsi AES paralel domain decomposition.............................................................. 16 Efisiensi dekripsi AES paralel domain decomposition.............................................................. 16 Efisiensi enkripsi dan dekripsi AES pipeline. ........................................................................... 16 Cost enkripsi paralel domain decomposition. ............................................................................ 17 Cost dekripsi paralel domain decomposition ............................................................................. 17 Cost enkripsi dan dekripsi AES pipeline. .................................................................................. 17 Overhead enkripsi AES paralel domain decomposition. ........................................................... 17 Overhead dekripsi AES paralel domain decomposition. ........................................................... 17 Overhead enkripsi dan dekripsi AES pipeline. ......................................................................... 18

vii

DAFTAR LAMPIRAN Halaman 1 2 3 4 5 6 7 8 9 10 11

Variabel pendukung dan waktu eksekusi yang diharapkan ....................................................... 22 Implementasi AES sekuensial ................................................................................................... 23 Implementasi AES paralel domain decomposition .................................................................... 26 Implementasi AES pipeline ....................................................................................................... 31 Pengaturan dan instalasi MPICH2 ............................................................................................ 37 Data hasil percobaan algoritme enkripsi AES paralel domain decomposition perlakuan 1 ...... 39 Data hasil percobaan algoritme dekripsi AES paralel domain decomposition perlakuan 1 ...... 40 Data hasil percobaan algoritme enkripsi AES paralel domain decomposition perlakuan 2 ...... 41 Data hasil percobaan algoritme dekripsi AES paralel domain decomposition perlakuan 2 ...... 42 Data hasil percobaan algoritme enkripsi AES pipeline ............................................................. 43 Data hasil percobaan algoritme dekripsi AES pipeline ............................................................. 44

viii

1

PENDAHULUAN Latar Belakang Pesatnya perkembangan dunia komputer dan interaksinya melalui jaringan publik telah menjadikan keamanan data digital menjadi suatu hal yang penting. Proses pengiriman data melalui jaringan publik rawan untuk dicuri, disadap, ataupun diubah oleh pihak lain yang tidak bertanggung jawab. Untuk menjamin integritas data yang dikirim, selain bergantung kepada keamanan di dalam jaringan, perlu juga dilakukan proteksi terhadap data tersebut. Salah satu cara memproteksi data adalah menggunakan teknik kriptografi. AES merupakan teknik atau algoritme kriptografi yang telah digunakan pada berbagai aplikasi di seluruh dunia saat ini. AES diharapkan bisa menggantikan Data Encryption Standard (DES) sebagai standar yang diakui untuk keperluan berbagai aplikasi (Stallings 2003). AES memiliki proses enkripsi dan dekripsi yang diketahui memiliki kompleksitas pada lingkup O(n) (Giri 2004). Proses enkripsi dan dekripsi AES tergolong cukup cepat secara kompleksitas, namun waktu eksekusinya akan meningkat seiring dengan besarnya data yang digunakan. Berbagai upaya dapat dilakukan untuk mengurangi waktu eksekusi. Pemrosesan paralel dikenal sebagai salah satu metode untuk mengurangi waktu eksekusi, namun tidak semua jenis algoritme baik untuk diparalelkan karena terkadang beban komunikasi antar proses dapat memperburuk kinerja algoritme tersebut. Penelitian ini menerapkan pemrosesan paralel terhadap proses enkripsi dan dekripsi AES. Ada dua cara pemrosesan paralel yang digunakan yaitu dengan membagi seluruh data ke setiap proses dan dengan memecah algoritme AES ke dalam beberapa tahap untuk kemudian data diproses secara pipeline. Cara pertama dikenal dengan domain decomposition, sedangkan cara kedua dikenal dengan nama functional decomposition. Tujuan Penelitian Tujuan dari penelitian ini adalah : 1 Mengimplementasikan algoritme AES secara paralel pada komputer dengan menggunakan bahasa C dengan library MPI. 2 Menganalisis kinerja algoritme AES secara sekuensial dan paralel dengan menghitung

waktu eksekusi, speedup, efisiensi, cost, dan overhead. Ruang Lingkup Penelitian Ruang lingkup dalam penelitian ini adalah: 1 Penelitian ini menggunakan sistem operasi Windows XP Professional dan library MPICH2 pada bahasa pemrograman C. 2 Komputer yang digunakan memiliki spesifikasi processor Intel Core i5 (4 CPU) @3,2 GHz, 1.7 GB memory dan dihubungkan oleh Fast Ethernet dengan kabel UTP standar. 3 Padding dilakukan dengan cara menambahkan nilai antara 1 dan 16 sampai panjang input genap 16. Nilai tiap pad merupakan representasi dari jumlah pad yang ditambahkan. 4 Algoritme paralel yang diterapkan ada dua yaitu algoritme AES paralel domain decomposition dan algoritme AES paralel functional decomposition (pipeline). 5 Algoritme AES paralel domain decomposition diberikan dua perlakuan yaitu: a perlakuan 1 yang menggunakan empat unit komputer dengan proses yang dibangkitkan adalah 4, 8, 12, 16, 20, 24. b perlakuan 2 yang membangkitkan 4, 8, 12, dan 16 proses dengan jumlah komputer yang digunakan berturutturut sebanyak 1, 2, 3, 4 unit. 6 Jumlah proses yang dibangkitkan untuk algoritme AES pipeline dibatasi hanya 2, 3 dan 5. Pembangkitan 2 atau 3 proses hanya menggunakan 1 komputer, sedangkan pembangkitan 5 proses akan menggunakan 2 komputer,. 7 Analisis teori, analisis algoritme, analisis uji perbandingan, dan implementasi algoritme AES dibatasi untuk panjang blok pesan 128 bit dengan panjang blok kunci 128 bit. 8 Analisis performance metrics dibatasi pada waktu eksekusi, speedup, efisiensi, cost, dan overhead Manfaat Penelitian Manfaat yang dapat diperoleh dari penelitian ini adalah dapat diketahui baik atau tidaknya algoritme AES jika diparalelkan dengan cara mengukur performance metrics.

2

TINJAUAN PUSTAKA Kriptografi Kriptografi didefinisikan sebagai studi teknik matematis yang berkaitan dengan aspek keamanan informasi seperti kerahasiaan, integritas data, autentikasi entitas, dan autentikasi asal data. Adapun orang yang melakukannya disebut kriptografer (Menezes et al. 1996). Menurut Menezes et al. (1996), empat tujuan utama kriptografi yaitu: 1 Kerahasiaan. 2 Integritas data (keutuhan data). 3 Autentikasi (identifikasi entitas dan data). 4 Non-repudiasi (terjaganya kesepakatan transaksi). Menurut Menezes et al. (1996), sistem pengamanan data pada kriptografi secara umum ada dua langkah, yaitu: 1 Proses enkripsi Proses enkripsi adalah suatu proses yang mengubah plaintext (kode sesungguhnya) menjadi chipertext (kode rahasia). Pada enkripsi, proses perubahan plaintext ke chipertext dilakukan dengan cara menyandikan pesan M dengan suatu kunci K yang akan menghasilkan pesan C. 2 Proses dekripsi Proses dekripsi adalah suatu proses yang mengubah chipertext menjadi plaintext, dimana pesan yang sudah teracak dikembalikan ke pesan semula. Pada proses dekripsi, pesan C tersebut diuraikan dengan menggunakan kunci K, sehingga dihasilkan pesan M yang sama seperti pesan sebelumnya. Kotak-S Kotak-S merupakan suatu bentuk pemetaan substitusi sederhana dari m-bit input menjadi n-bit output. Suatu kotak-S dengan m bit input dan n bit output dinamakan kotak-S m*n bit (Stallings 2003).

Gambar 1 Kotak-S.

. Algoritme AES menggunakan desain kotak-S yang memetakan 4*32 bit input kepada 4*32 bit output sebagai hasilnya. Desain kotak-S yang digunakan AES dapat dilihat pada Gambar 1. Inversi Kotak-S Inversi Kotak-S merupakan bentuk kebalikan dari kotak-S yang tiap sel penyusunnya merupakan antilog (pemetaan kebalikan) dari setiap sel bersesuaian pada kotak-S. Desain inversi kotak-S yang digunakan AES dapat dilihat pada Gambar 2.

Gambar 2 Inversi kotak-S. Algoritme AES AES merupakan algoritme kriptografi yang didesain untuk beroperasi pada blok pesan 128 bit dan menggunakan tiga variasi blok kunci dengan panjang 128 bit, 192 bit, atau 256 bit. Khusus untuk penelitian ini, pengkajian akan dibatasi pada blok pesan 128 bit dengan ukuran blok kunci 128 bit. Empat proses utama algoritme terdiri atas satu proses permutasi (ShiftRows) dan tiga proses substitusi (SubBytes, MixColumns, dan AddRoundKey). Struktur algoritme secara umum cukup sederhana, dengan proses baik enkripsi maupun dekripsi diawali proses AddRoundKey, diikuti sembilan round yang masing-masing tersusun atas empat proses, dan diakhiri round kesepuluh yang terdiri atas tiga proses. Proses AddRoundKey saja yang memanfaatkan kunci, karena itu penyandian diawali dan diakhiri oleh sebuah proses AddRoundKey (Stallings 2003). Proses Enkripsi AES Secara umum, proses enkripsi dan dekripsi AES dapat digambarkan pada Gambar 3. Masukan dari algoritme enkripsi dan dekripsi AES adalah sebuah blok berukuran 128 bit. Blok ini digambarkan sebagai sebuah matriks 4x4 dengan tiap elemen berukuran satu byte dan direpresentasikan dalam dua karakter

3

heksadesimal, maka dihasilkan 16 buah input. Input tersebut direpresentasikan ke dalam matriks 4x4 yang disebut matriks input.

Gambar 4 Matriks input, state, dan output. Proses enkripsi AES diawali proses AddRoundKey diikuti sembilan round dengan arsitektur yang tersusun atas empat proses dan urutan identik yaitu SubBytes, ShiftRows, MixColumns, dan AddRoundKey. Pada akhir proses enkripsi, digunakan round kesepuluh yang tersusun atas tiga proses terurut SubBytes, ShiftRows, dan AddRoundKey yang keseluruhan proses tersebut diiringi proses penjadwalan key (oleh expand key) bagi setiap round (Stallings 2003). a

SubBytes Operasi ini merupakan suatu operasi substitusi tak linear yang beroperasi secara mandiri pada setiap byte dengan menggunakan kotak-S (Ariyus 2008). Ilustrasi proses SubBytes diberikan pada Gambar 5.

Gambar 3 Proses umum enkripsi dan dekripsi AES. Matriks input disalin kedalam matriks state yang kemudian akan dimodifikasi pada setiap tahap enkipsi atau dekripsi. Pada tahap akhir penyandian, matriks state disalin ke dalam matriks output (Stallings 2003). Ilustrasi matriks input, state, dan output tersaji pada Gambar 4. Kunci juga digambarkan sebagai matriks 4x4 yang disebut matriks key. Tiap elemennya berukuran satu byte dan direpresentasikan dalam dua karakter heksadesimal (Stallings 2003).

Gambar 5 Ilustrasi proses SubBytes. b ShiftRows ShiftRows merupakan proses permutasi sederhana dari 16 nilai matriks 4x4 kepada 16 nilai baru matriks 4x4. (Stallings 2003). Ilustrasi proses ShiftRows diberikan pada Gambar 6.

4

Gambar 6 Ilustrasi proses ShiftRows. c MixColumns MixColumns merupakan operasi terhadap setiap kolom secara terpisah. Setiap byte dari suatu kolom dipetakan terhadap suatu nilai baru dengan suatu fungsi yang melibatkan seluruh nilai (4 byte) dari kolom yang bersangkutan. Proses MixColumns mengalikan matriks polimat dengan matriks state (Stallings 2003).

Proses dekripsi diawali dengan AddRoundKey lalu dilanjutkan dengan proses sembilan buah round identik yang menggunakan key hasil ekspansi bagi round bersesuaian. Setiap round dekripsi (round pertama sampai round kesembilan) tersusun atas empat proses transformasi terurut, yaitu InvShiftRows, InvSubBytes, AddRoundKey, dan MixColumns. Proses dekripsi diakhiri oleh round kesepuluh dengan tiga proses penyusun secara berurut yaitu InvShiftRows, InvSubBytes, dan AddRounKey (Stallings 2003). a

InvShiftRows InvShiftRows merupakan transformasi kebalikan dari proses permutasi ShiftRows (Stallings 2003). Untuk kasus blok pesan 128 bit dengan 128 bit blok kunci, InvShiftRows memiliki aturan permutasi sebagai berikut: 1 Baris pertama matriks tetap. 2 Baris kedua matriks bergeser secara rotasi satu byte ke kanan. 3 Baris ketiga matriks bergeser secara rotasi dua byte ke kanan. 4 Baris keempat matriks bergeser secara rotasi tiga byte ke kanan.

b

InvSubBytes InvSubBytes memiliki kaidah pemetaan seperti proses SubBytes pada enkripsi akan tetapi kamus pemetaannya menggunakan inversi kotak-S (Stallings 2003).

c

AddRoundKey AddRoundKey pada proses dekripsi identik dengan AddRoundKey pada proses enkripsi. Hal ini dikarenakan operasi inversi dari XOR merupakan operasi XOR itu sendiri (Stallings 2003).

d

InvMixColumns InvMixColumns merupakan proses inversi dari proses MixColumns pada enkripsi (Stallings 2003). Proses InvMixColumns dapat didefinisikan sebagai proses perkalian dengan inversi dari matriks polimat pada proses enkripsi (Gambar 10).

02 03 01 01 01 02 03 01 01 01 02 03 03 01 01 02 Gambar 7 Matriks polimat. d

AddRoundKey Operasi ini merupakan suatu operasi penambahan kunci dengan operasi XOR dan setiap kunci putaran terdiri dari w[i]. Nilai w[i] merupakan kunci ekspansi yang diturunkan dari kunci primer (Ariyus 2008). Ilustrasi proses AddRoundKey diberikan pada Gambar 8.

Gambar 8 Ilustrasi proses AddRoundKey. Proses Dekripsi AES Struktur proses dekripsi AES sama dengan proses enkripsi. Akan tetapi, proses dekripsi AES memiliki urutan proses dan transformasi penyusun tiap round yang berbeda. Selain itu, transformasi yang digunakan pun merupakan transformasi kebalikan dari proses transformasi penyusun setiap round pada proses enkripsi (Stallings 2003).

0E 09 0D 0B

0B 0E 09 0D

0D 0B 0E 09

09 0D 0B 0E

Gambar 9 Matriks inversi polimat

5

Ekspansi Kunci Ekspansi kunci adalah proses untuk membangkitkan kunci bagi round pada setiap iterasi. Algoritme ekspansi kunci AES membutuhkan masukan sebuah kunci berukuran empat word dan akan menghasilkan sebuah 44 word (156 bytes) array yang linear (Stallings 2003). Proses ekspansi kunci digambarkan pada Gambar 10.

komunikasi intensif dengan bagian lain, dan memetakan kelompok tersebut ke sejumlah prosesor yang ada. Empat tahapan desain tersebut adalah partisi, komunikasi, aglomerasi, dan pemetaan (Quinn 2004). Ilustrasi metode foster dapat dilihat pada Gambar 11.

Gambar 11 Ilustrasi metode Foster. a

Partisi Partisi adalah suatu proses pembagian komputasi dan data ke dalam beberapa bagian. Ada dua cara untuk melakukan partisi, yaitu domain decompotition dan functional decompotition. Domain decompotition adalah pendekatan model algoritme paralel yang melakukan pembagian data menjadi beberapa bagian terlebih dahulu, kemudian menentukan bagaimana mengasosiasikan komputasi dengan data tersebut. sedangkan functional decompotition melakukan pembagian komputasi terlebih dahulu lalu menentukan bagaimana menghubungkan data dengan komputasi-komputasi tersebut (Quinn 2004).

b

Komunikasi Skema komunikasi antar bagian hasil partisi dibuat setelah melakukan partisi. Ada dua jenis komunikasi yang digunakan yaitu local communication dan global communication. Local communication adalah membuat saluran antar task ketika ada task yang membutuhkan nilai dari task lainnya. Global communication terjadi ketika ada primitive task dengan jumlah yang signifikan menyumbangkan data untuk menunjukkan proses komputasi (Quinn 2004).

c

Aglomerasi Aglomerasi adalah proses pengelompokkan task ke dalam task yang lebih besar guna meningkatkan kinerja

Gambar 10 Proses ekspansi kunci AES. Pemrograman Paralel Pemrograman paralel adalah pemrograman dalam bahasa yang memungkinkan secara eksplisit menunjukkan bagaimana bagian yang berbeda dari komputasi dapat dieksekusi secara bersamaan oleh prosesor yang berbeda (Quinn 2004). Algoritme paralel adalah sebuah urutan yang memberi tahu kita bagaimana cara untuk memecahkan suatu masalah menggunakan beberapa prosesor. Algoritme ini mencakup identifikasi bagian dari pekerjaan bersama ke dalam proses yang berjalan secara paralel, pengaturan akses data yang dibagi ke beberapa prosesor, pendistribusian input, output, dan data yang terkait dengan program serta koordinasi proses di berbagai tahapan pelaksanaan program paralel (Grama et al. 2003). Metode Foster Ian Foster mengemukakan empat langkah metode desain sistem paralel yang dimulai dari pembagian data ke dalam beberapa bagian, menentukan komunikasi antar bagian, mengelompokkan bagian yang memiliki

6

program maupun menyederhanakan program (Quinn 2004). d

c

Pemetaan Pemetaan adalah proses penugasan task ke prosesor. Tujuan dari pemetaan adalah memaksimalkan kemampuan prosesor dan meminimalkan komunikasi antar prosesor (Quinn 2004).

E= d

MPI (Message-Passing-Interface) MPI adalah sebuah standar library pengenalan dasar pemrograman sistem paralel (Quinn 2004). MPI dapat digunakan dengan berbagai bahasa pemrograman seperti bahasa C dan Fortran. Operasi utama yang dilakukan oleh standar MPI yaitu: a

Point-to-point Communication MPI Point-to-point Communication adalah komunikasi antar dua proses. Satu proses bertugas mengirim data atau operasi dan proses lainnya bertugas menerima data atau operasi tersebut.

b

Collective Communication MPI Collective Communication adalah komunikasi yang melibatkan sekumpulan proses yang dipanggil oleh semua proses dalam communicator.

Performance Metrics Performance metrics adalah salah satu cara untuk menganalisis kinerja algoritme paralel (Grama et al.). Beberapa persamaan performance metric yaitu: a Waktu Eksekusi Waktu eksekusi adalah waktu yang dihitung dari awal sampai akhir eksekusi. Waktu eksekusi sekuensial dilambangkan dengan Ts. Waktu eksekusi paralel adalah dilambangkan dengan Tp (Grama et al. 2003). b Speedup Speedup (S) adalah rasio dari waktu yang digunakan untuk menyelesaikan masalah dalam program sekuensial (Ts) terhadap waktu yang diperlukan untuk menyelesaikan masalah yang sama dengan program paralel (Tp) (Grama et al. 2003). Speedup dirumuskan pada Persamaaan 1 S=

Efisiensi Efisiensi (E) adalah rasio antara speedup dengan banyaknya prosesor yang digunakan (p). Suatu sistem paralel dikatakan cost-optimal jika memiliki efisiensi sebesar 1 (Grama et al. 2003). Efisiensi dirumuskan pada Persamaan 2.

e

(2)

Cost Cost (C) pada sistem paralel adalah hasil perkalian waktu eksekusi paralel dengan jumlah prosesor yang digunakan (Grama et al. 2003). Fungsi cost dirumuskan pada Persamaan 3. C = pTp (3) Overhead Overhead adalah kelebihan dari total waktu yang dibutuhkan oleh semua proses paralel dibandingkan proses sekuensial pada masalah yang sama (Grama et al. 2003). Fungsi overhead dirumuskan pada Persamaan 4. To = pTp - Ts

(4)

METODE PENELITIAN Penelitian ini akan menggunakan metode Foster dalam merancang sistem paralelnya. Pembagian komputasi akan dilakukan secara domain decomposition dan functional decomposition. Penelitian ini akan dikerjakan dalam beberapa tahap yang disesuaikan dengan metode penelitian seperti terlihat pada Gambar 12.

(1) Gambar 12 Metode penelitian.

7

Studi Pustaka Kegiatan yang dilakukan pada tahap ini adalah mengumpulkan semua informasi atau literatur yang terkait dengan penelitian. Informasi tersebut didapat dari buku, internet, dan artikel yang membahas tentang algoritme AES dan pemrosesan paralel. Analisis Algoritme AES Sekuensial Analisis algoritme yang dilakukan pada tahap ini adalah analisis kompleksitas waktu asimptotik dan penghitungan waktu eksekusi AES sekuensial yang diharapkan. Implementasi Algoritme AES Sekuensial Algoritme AES sekuensial diimplementasikan dengan menggunakan bahasa pemrograman C. Algoritme utama AES dibagi menjadi tiga bagian yaitu ekspansi kunci, enkripsi, dan dekripsi. Penerapan Metode Foster ke Algoritme AES Domain Decomposition Metode yang digunakan untuk implementasi algoritme AES secara paralel pada penelitian ini adalah metode Foster dengan tahapan partisi, komunikasi, aglomerasi, dan pemetaan. Tahapan partisi dilakukan secara domain decomposition. Analisis dan Implementasi Algoritme AES Paralel Domain Decomposition Analisis algoritme yang dilakukan pada tahap ini adalah analisis kompleksitas waktu asimptotik dan penghitungan waktu eksekusi AES paralel domain decomposition yang diharapkan. Implementasinya akan menggunakan prosedur komunikasi MPI kolektif scatter/scatterv dan gather/gatherv untuk pendistribusian data. Penerapan Metode Foster ke Algoritme AES Pipeline Metode yang digunakan untuk implementasi algoritme AES secara paralel pada penelitian ini adalah metode Foster dengan tahapan partisi, komunikasi, aglomerasi dan pemetaan. Tahapan partisi dilakukan secara functional decomposition. Fungsi yang dipecah adalah komputasikomputasi penyusun enkripsi atau dekripsi AES dan komputasi ekspansi kunci AES. Analisis dan Implementasi Algoritme AES Pipeline Analisis algoritme yang dilakukan pada tahap ini adalah analisis kompleksitas waktu asimptotik dan penghitungan waktu eksekusi

AES pipeline yang diharapkan. Implementasinya akan menggunakan prosedur komunikasi MPI point-to-point send-receive untuk aliran proses penyandian. Perancangan Percobaan Parameter-parameter yang dibutuhkan untuk percobaan ditentukan pada tahap ini. Parameter-parameter tersebut antara lain: 1 Jenis algoritme. 2 Jenis perlakuan. 3 Ukuran file masukan. 4 Jumlah prosesor dan proses. 5 Performace metrics. 6 Perangkat keras dan perangkat lunak. Percobaan Waktu enkripsi dan dekripsi dari implementasi AES secara sekuensial dan paralel akan dicatat pada tahap ini. Analisis Kinerja Waktu eksekusi algoritme AES sekuensial akan ditentukan pada tahap ini. Kedua algoritme AES paralel akan ditentukan waktu eksekusi, speedup, efisiensi, cost, dan overhead. Waktu eksekusi kedua algoritme AES paralel akan dibandingkan dengan waktu eksekusi algoritme paralel yang diharapkan dan waktu eksekusi algoritme sekuensial. HASIL DAN PEMBAHASAN Analisis Algoritme AES Sekuensial Proses enkripsi dan dekripsi AES diketahui memiliki kompleksitas pada lingkup O(n) (Giri 2004). Proses enkripsi file pada AES sekuensial diawali dengan membangkitkan 176 bytes kunci-kunci ekspansi melalui proses ekspansi kunci. Selanjutnya file dibagi-bagi ke dalam tiap blok berukuran 128 bit, kemudian setiap blok dioperasikan dengan operasi seperti pada Gambar 3. Proses ini akan terus diulangi sampai semua blok file selesai diproses. Proses dekripsi file pada AES sekuensial memiliki pola yang hampir sama dengan proses enkripsi. Perbedaannya terletak pada jenis operasinya. Waktu eksekusi enkripsi dan dekripsi AES sekuensial harapan dirumuskan pada Persamaan 5 dan 6. TSEH = x1 + x2 + A + n(B)

(5)

TSDH = x1 + x2 + A + n(C)

(6)

8

Keterangan : TSEH : waktu eksekusi enkripsi sekuensial harapan TDEH : waktu eksekusi dekripsi sekuensial harapan x1 : waktu yang dibutuhkan untuk membaca suatu data masukan x2 : waktu yang dibutuhkan untuk menulis data keluaran n : banyak blok A : waktu yang dibutuhkan untuk melakukan ekspansi kunci B : waktu yang dibutuhkan untuk melakukan enkripsi satu blok data C : waktu yang dibutuhkan untuk melakukan dekripsi satu blok data Variabel pendukung dan waktu eksekusi harapan untuk enkripsi dan dekripsi algoritme AES sekuensial disajikan dalam Lampiran 1.

Implementasi Algoritme AES Sekuensial Proses enkripsi dan dekripsi pada penelitian ini menggunakan bahasa pemrograman C, kompilator GCC, dan library MPICH2 yang digunakan untuk memakai fungsi perhitungan waktu eksekusi karena implementasi AES paralel juga menggunakan fungsi yang sama sehingga perbandingannya akan sederajat. Algoritme enkripsi AES sekuensial pada penelitian ini dijelaskan pada Gambar 13. Algoritme dekripsi AES sekuensial hampir sama dengan enkripsi AES sekuensial. Perbedaannya terletak pada jenis operasinya dan proses unpadding dilakukan di akhir sebelum hasil dekripsi disimpan ke file. Implementasi algoritme AES sekunsial dapat dilihat pada Lampiran 2. Penerapan Metode Foster ke Algoritme AES Paralel Domain Decomposition Metode yang digunakan untuk implementasi algoritme AES secara paralel adalah metode Foster. Tahapan dari metode foster yaitu: 1 Partisi Jenis partisi yang dilakukan pada algoritme ini adalah domain decomposition. File plaintext akan dipecah menjadi blok-blok data berukuran 16 byte. Setiap blok data akan ditangani oleh satu proses, sehingga untuk n blok data akan membutuhkan n proses. Ilustrasi partisi algoritme AES paralel domain decomposition ditunjukkan pada Gambar 14.

Gambar 14 Ilustrasi partisi algoritme AES paralel domain decomposition.

Gambar 13 Algoritme enkripsi AES sekuensial.

2 Komunikasi Proses master (root) akan mengirim blok-blok data kepada setiap proses untuk dienkripsi dengan menggunakan komunikasi kolektif (scatter). Hasil enkripsi tiap proses akan dikumpulkan kembali ke root juga dengan menggunakan koleksi komunikatif (gather). n blok data akan membutuhkan 2 kali komunikasi dan n buah proses. Ilustrasi komunikasi algoritme AES paralel domain

9

decomposition ditunjukkan pada Gambar 15.

Gambar 15 Ilustrasi komunikasi algoritme AES paralel domain decomposition 3 Aglomerasi Aglomerasi dilakukan untuk mengurangi komunikasi dan kebutuhan proses agar menjadi lebih efisien. Tiap proses (p) akan menangani n/p blok data. Komunikasi kolektif digunakan untuk meminimalkan komunikasi sehingga hanya membutuhkan sekali scatter untuk pendistribusian data dan sekali gather untuk pengumpulan data. Ilustrasi aglomerasi algoritme AES paralel domain decomposition ditunjukkan pada Gambar 16.

Analisis dan Implementasi Algoritme AES Paralel Domain Decomposition Algoritme ini membagi langsung semua data masukan ke setiap proses. Setiap proses akan membangkitkan kunci-kunci ekspansi dan melakukan enkripsi atau dekripsi terhadap data masukan yang telah dibagi-bagi tersebut. Terakhir, data hasil enkripsi atau dekripsi dikumpulkan di satu proses untuk kemudian dicetak. Broadcast diketahui memiliki kompleksitas Ɵ (log p), sedangkan scatter dan gather Ɵ (n + log p) (Quinn 2004). Algoritme ini dalam proses komunikasinya melakukan tiga kali broadcast, sekali scatter dan sekali gather. Ekspansi kunci memiliki kompleksitas waktu asimptotik O(1). Untuk perhitungan enkripsi atau dekripsi tiap proses akan melakukan iterasi sebanyak n/p kali. Jika diasumsikan proses pembacaan data masukan dan penulisan data keluaran diabaikan dalam analisis perhitungan kompleksitas waktu asimptotiknya, total kompleksitas waktunya adalah: Ɵ (n/p + 2n + 5log p) Keterangan: p : jumlah proses yang dibangkitkan Jika λ adalah waktu yang dibutuhkan untuk mengirim sebuah pesan dan β (bandwidth) adalah jumlah data yang dapat dikirim dalam satu waktu, maka waktu yang dibutuhkan untuk melakukan suatu broadcast adalah λ log p Scatter atau gather data berukuran 16 byte membutuhkan waktu λ log p + 16n (p-1) / (βp)

Gambar 16 Ilustrasi aglomerasi algoritme AES paralel domain decomposition 4 Pemetaan Setiap proses akan mengerjakan tugas yang sama namun dengan data masukan yang berbeda-beda. Jika n mod p != 0, jumlah blok data yang dikerjakan oleh tiap proses ada yang sebesar dan ada juga yang sebesar . Jika s = n mod p, blok data akan dipetakan ke s proses pertama sedangkan sisa proses lainnya akan dipetakan blok data.

Waktu eksekusi harapan enkripsi dan dekripsi yang diharapakan untuk algoritme AES paralel domain decomposition ini dapat dirumuskan melalui Persamaan 7 dan 8. Tp1He = x1+x2+A+

B + 5λlog p + 32n (7)

Tp1Hd = x1+x2+ A+

C+ 5λlog p + 32n (8)

10

Keterangan : Tp1He : Waktu eksekusi harapan enkripsi AES paralel domain decomposition Tp1Hd : Waktu eksekusi harapan dekripsi AES paralel domain decomposition Nilai λ diperoleh dari menghitung waktu rata-rata yang dibutuhkan untuk menyelesaikan 1000 kali proses send-receive data sebesar satu byte. Percobaan ini menggunakan Fast Ethernet sehingga nilai β adalah 12,5 x 106 byte/detik.

Variabel pendukung dan waktu eksekusi harapan untuk enkripsi dan dekripsi algoritme AES paralel domain decomposition disajikan dalam Lampiran 1. Algoritme enkripsi AES paralel domain decomposition pada penelitian ini dijelaskan pada Gambar 17. Algoritme dekripsi AES paralel hampir sama dengan enkripsi AES paralel. Perbedaannya terletak pada jenis operasinya dan proses unpadding dilakukan di akhir sebelum hasil dekripsi disimpan ke file. Implementasi algoritme AES paralel domain decomposition dapat dilihat di Lampiran 3. Penerapan Metode Foster ke Algoritme AES Pipeline Tahapan metode Foster yang digunakan dalam menyusun algoritme ini adalah: 1 Partisi Jenis partisi yang dilakukan pada algoritme ini adalah functional decomposition. Komputasi AES akan dipecah menjadi komputasi-komputasi penyusun dasarnya. Diketahui enkripsi AES terdiri atas dua komputasi utama yaitu ekspansi kunci dan enkripsi itu sendiri. Ekspansi kunci tersusun atas empat buah komputasi, yaitu: RotWord, SubWord, dan dua buah proses bitwise XOR. Secara lengkap ekspansi kunci tersusun dari 10 RotWord, 10 SubWord, dan 50 bitwise XOR. Terdapat 70 komputasi dalam ekspansi kunci. Enkripsi utama AES tersusun atas empat buah komputasi yaitu: SubBytes, ShiftRows, MixCol, AddRoundKey. Secara lengkap, enkripsi AES tersusun atas: 11 AddRoundKey, 10 SubBytes, 10 ShiftRows, dan 9 MixColumns. Terdapat 40 komputasi dalam enkripsi AES. Tiap komputasi akan ditangani satu proses sehingga untuk n blok data dibutuhkan 40 proses untuk ekspansi kunci dan 40 proses untuk enkripsi/dekripsi. Ilustrasi partisi algoritme AES pipeline ditunjukkan pada Gambar 18.

Gambar 17 Algoritme enkripsi AES paralel domain decomposition

Gambar 18 Ilustrasi partisi algoritme AES pipeline.

11

2 Komunikasi Setiap proses akan mengolah blok data masukan sesuai dengan komputasi bagiannya. Jika suatu proses telah selesai melakukan komputasi untuk suatu blok data, blok data tersebut akan dikirim ke proses selanjutnya dan proses tersebut akan menerima masukan berikutnya. Jenis komunikasi yang digunakan adalah komunikasi point-to-point. Untuk n blok data, dibutuhkan 110 proses dan komunikasi sebanyak 39n kali untuk enkripsi atau dekripsi, 69 kali untuk ekspansi kunci, dan 40 kali untuk pengiriman kunci ekspansi ke tiap proses yang menangani komputasi AddRoundKey. Ilustrasi komunikasi algoritme AES pipeline ditunjukkan pada Gambar 19.

Gambar 19 Ilustrasi komunikasi algoritme AES pipeline. 3 Aglomerasi Aglomerasi pada ekspansi kunci dilakukan karena ekspansi kunci tidak tergantung pada besarnya data masukan dan memiliki waktu komputasi yang kecil, sehingga komputasi ekspansi kunci tidak akan dipecah.

Aglomerasi pada enkripsi utama AES dilakukan tergantung pada jumlah proses yang dibangkitkan. Pada dasarnya, algoritme AES pipeline membagi enkripsi AES ke dalam tiga kelompok komputasi yang dijelaskan pada Gambar 20. Jika proses yang dibangkitkan dua, Komputasi 2 dan Komputasi 3 digabung. Jika proses yang dibangkitkan tiga, pengelompokkan komputasi tidak berubah. Jika proses yang dibangkitkan lima, Komputasi 2 akan dipecah menjadi tiga pecahan yang akan melakukan tiga iterasi yang tiap iterasinya terdiri atas empat buah komputasi yang dilaksanakan secara berturut-turut, yaitu: SubBytes, ShiftRows, MixCol, dan AddRoundKey. 4 Pemetaan Setiap proses akan melakukan komputasi yang berbeda-beda. Komputasi 1 akan dilakukan oleh proses root, Koputasi 3 akan dikerjakan oleh proses p1, sedangkan Komputasi 2 akan dikerjakan sisa proses lainnya. Analisis dan Implementasi Algoritme AES Pipeline Satu blok data membutuhkan p-1 pasang komunikasi send-receive. Maka untuk menyelesaikan seluruh komputasi bagi seluruh data dibutuhkan n(p-1) pasang komunikasi send-receive. Sepasang komunikasi send-receive membutuhkan waktu λ sehingga total kebutuhan waktu komunikasi point-to-point adalah λn(p-1) Komunikasi global yang dilakukan ada dua buah broadcast, sehingga total kebutuhan waktu komunikasi global adalah 2λ (log p) Total waktu komunikasi algoritme AES pipeline harapan dirumuskan dalam Persamaan 9. Tcpi = λn(p-1) + 2λ (log p)

(9)

Keterangan: Tcpi : waktu komunikasi AES pipeline harapan

Gambar 20 Ilustrasi aglomerasi algoritme AES pipeline.

Proses pengiriman data menggunakan komunikasi blocking. Jadi, secara otomatis, tiap proses akan saling menunggu sampai data benar-benar terkirim. Sehingga waktu

12

komputasi terbesar di suatu proses akan mempengaruhi waktu komputasi keseluruhan. Jika p = 2, waktu komputasi total enkripsi dan dekripsi AES pipeline harapannya dirumuskan dalam Persamaan 10 dan 11. Tp22He = x1 + x2 + A + d + n(9D + E) + Tcpi(10) Tp22Hd = x1 + x2 + A + d + n(9F + G) + Tcpi (11) Keterangan: Tp22He : waktu enkripsi AES pipeline harapan dengan 2 proses Tp22Hd : waktu dekripsi AES pipeline harapan dengan 2 proses d : waktu komputasi AddRoundKey D : waktu komputasi SubBytes + ShiftRows+MixCol +AddRoundKey E : waktu komputasi SubBytes + ShiftRows + AddRoundKey F : waktu komputasi InvSubBytes + InvShiftRows + InvMixCol +InvAddRoundKey G : waktu komputasi InvSubBytes + InvShiftRows + InvAddRoundKey

bahasa pemrograman C dan library MPICH2 untuk pemrosesan paralel. Algoritme disusun agar setiap proses bertanggung jawab terhadap komputasi tertentu yang seluruh rangkaian komputasi tersebut merupakan suatu komputasi AES utuh. Selanjutnya, setiap blok data dialirkan ke rangkaian komputasi tersebut untuk diolah secara bertahap. Kedatangan suatu blok data akan memicu eksekusi komputasi baru oleh suatu proses dalam pipeline, pengecualian pada proses yang menginisiasi pipeline. Implementasi AES pipeline dalam penelitian ini berbentuk linear 1D. Komunikasi antar proses untuk pengiriman aliran data menggunakan komunikasi pointto-point send-receive. Algoritme implementasi AES pipeline untuk tiap jumlah proses yang dibangkitkan digambarkan melalui Gambar 21.

Jika p = 3, maka waktu komputasi total enkripsi dan dekripsi AES pipeline harapannya dirumuskan dalam Persamaan 12 dan 13. Tp23He = x1 + x2 + A + d + n9D + E + Tcpi (12) Tp23Hd = x1 + x2 + A + d + n9F + G + Tcpi (13) Keterangan: Tp23He : waktu enkripsi AES pipeline harapan dengan 3 proses Tp23Hd : waktu dekripsi AES pipeline harapan dengan 3 proses Jika p=5, maka waktu komputasi total enkripsi dan dekripsi AES pipeline harapannya dirumuskan dalam Persamaan 14 dan 15. Tp25He = x1+ x2+A +d+9D+E+ (n-1)3D+Tcpi (14) Tp25Hd = x1+x2+A+d+9F+G+ (n-1)3F+ Tcpi (15) Keterangan: Tp25He : waktu enkripsi AES pipeline harapan dengan 5 proses Tp25Hd : waktu dekripsi AES pipeline harapan dengan 5 proses Implementasi enkripsi dan dekripsi AES pipeline dilakukan dengan menggunakan

Gambar 21 Algoritme implementasi AES pipeline. Algoritme dekripsi AES pipeline hampir sama dengan enkripsi AES pipeline. Perbedaannya terletak pada jenis operasinya

13

dan proses unpadding dilakukan di akhir sebelum hasil dekripsi disimpan ke file. Implementasi algoritme AES pipeline dapat dilihat pada Lampiran 4. Perancangan Percobaan Parameter-parameter yang digunakan dalam percobaan ini adalah: 1 Jenis algoritme Percobaan ini akan menguji tiga buah algoritme, yaitu algoritme AES sekuensial, paralel domain decomposition, dan pipeline. 2 Proses dan prosesor Jumlah komputer yang digunakan pada penelitian ini berbeda-beda, Algoritme AES paralel domain decomposition diberi dua perlakuan. Perlakuan pertama dengan membangkitkan 4, 8, 12, 16, 20, dan 24 proses pada empat buah komputer quadcore. Perlakuan kedua dengan membangkitkan 4, 8, 12, dan 16 proses pada masing-masing 1, 2, 3, 4 buah komputer quad-core, sedangkan algoritme AES pipeline dibatasi dengan membangkitkan proses sebanyak 2 dan 3 pada 1 komputer quad-core serta 5 proses pada 2 buah komputer quad-core. 3 Ukuran file Ukuran file yang digunakan ada tiga kategori yaitu kecil (berukuran sekitar 4 MB), sedang (berukuran sekitar lima kali kecil), dan besar (berukuran sekitar lima kali sedang). Detil ukuran file disajikan pada Tabel 1. Tabel 1 Nama file beseta ukurannya Nama Kategori Ukuran File File file 1 Kecil 4.762 MB file 2 Sedang 23.300 MB file 3 Besar 118.522 MB 4 Ulangan Ulangan yang dilakukan pada setiap eksekusi adalah sebanyak lima kali. 5 Performance metrics Performance metrics yang dianalisis adalah waktu eksekusi, speedup, efisiensi, dan overhead. 6 Lingkungan penelitian a Sepuluh komputer quad-core. b Tiga fast Ethernet 100 Mbps. c Sistem operasi Windows XP dan program MPICH2-1.4.1p1 32 bit. Percobaan Ketiga data yang digunakan dalam percobaan ini dijalankan dengan ketiga jenis

algoritme baik untuk komputasi enkripsi maupun dekripsinya. Perhitungan setiap perlakuan pada masing-masing file dilakukan lima kali ulangan, kemudian diambil nilai rata-ratanya. Percobaan ini dibagi ke dalam empat bagian yaitu: 1 Eksekusi enkripsi dan dekripsi algoritme AES paralel dengan perlakuan 1. 2 Eksekusi enkripsi dan dekripsi algoritme AES paralel dengan perlakuan 2. 3 Eksekusi enkripsi dan dekripsi algoritme AES pipeline. 4 Eksekusi enkripsi dan dekripsi algoritme AES sekuensial. Percobaan bagian 1 membutuhkan (2x6x3x5 = 180) kali eksekusi. Percobaan bagian 2 membutuhkan (2x4x3x5=120) kali eksekusi. Percobaan bagian 3 membutuhkan (2x3x3x5=90) kali eksekusi. Percobaan bagian 4 membutuhkan (2x3x5=30) kali eksekusi. Secara keseluruhan percobaan ini terdiri dari 210 eksekusi untuk enkripsi dan 210 eksekusi untuk dekripsi. Percobaan ini menggunakan tiga kelompok komputer yaitu: 1 Kelompok 1, terdiri atas empat buah komputer yang digunakan untuk percobaan bagian 1. 2 Kelompok 2, terdiri atas empat buah komputer yang digunakan untuk percobaan bagian 2. 3 Kelompok 3, terdiri atas dua buah komputer yang digunakan untuk percobaan bagian 3 dan 4. Percobaan ini diawali dengan melakukan pengaturan jaringan dan komputer agar bisa bekerja secara paralel. Langkah-langkah pengaturan jaringan dan komputer dapat dilihat pada Lampiran 5. Bentuk topologi jaringan yang digunakan adalah starconnected network yang dapat dilihat pada Gambar 22.

Gambar 22 Topologi jaringan star. Langkah selanjutnya adalah dengan menjalankan batch file yang berisi perintah eksekusi percobaan di masing-masing

14

kelompok komputer. Data hasil percobaan berupa waktu eksekusi tiap jenis eksekusi yang dapat dilihat pada Lampiran 6, 7, 8, 9, 10, dan 11. Khusus untuk percobaan 3, eksekusi algoritme AES pipeline, ketika proses yang dibangkitkan berjumlah 5, pada eksekusi enkripsi 4 proses pertama berada di PC1 dan 1 proses terakhir ada di PC 2, sedangkan dekripsi kebalikannya. Hal ini dilakukan untuk mencegah terjadinya eror karena overlapping aliran data. Analisis Kinerja Analisis kinerja implementasi algoritme AES sekuensial dan paralel diawali dengan menghitung waktu eksekusi untuk tiap jenis perlakuan dan data yang berbeda. Setelah diketahui waktu eksekusinya, performance metrics yang lain dapat dihitung. Penghitungan waktu eksekusi dilakukan untuk kedua proses enkripsi dan dekripsi.

Gambar 24 Waktu eksekusi enkripsi AES paralel domain decomposition.

Waktu Eksekusi Sekuensial Waktu eksekusi enkripsi dan dekripsi AES secara sekuensial untuk tiap file disajikan pada Gambar 23.

Gambar 25 Waktu eksekusi dekripsi AES paralel domain decomposition.

Gambar 23 Perbandingan waktu eksekusi enkripsi dan dekripsi AES sekuensial. Gambar tersebut menunjukkan waktu eksekusi dekripsi AES lebih lama dari enkripsi. Hal ini disebabkan tiga komputasi penyusun dekripsi AES, yaitu: InvShiftRows, InvSubstituteBytes, dan InvMixColumns membutuhkan waktu eksekusi yang lebih lama dibanding komputasi-komputasi penyusun enkripsi AES. Waktu eksekusi meningkat seiring meningkatnya ukuran file yang digunakan. Waktu Eksekusi Paralel Waktu eksekusi enkripsi dan dekripsi AES secara paralel domain decomposition untuk setiap file disajikan pada Gambar 24 dan 25.

Terlihat pada kedua gambar tersebut, waktu eksekusi aktual lebih besar dibanding waktu eksekusi yang diharapkan. Beberapa faktor dapat menyebabkan hal ini terjadi, di antaranya adalah: lantensi jaringan yang tidak konstan dan kerja prosesor yang tidak stabil. Waktu eksekusi secara paralel lebih cepat dibanding waktu eksekusi sekuensial untuk proses enkripsi maupun dekripsi. Namun, penambahan jumlah proses tidak memberikan penurunan waktu eksekusi yang berarti, bahkan ada beberapa yang waktu eksekusinya meningkat. Hal ini terjadi karena waktu komunikasi yang semakin membesar seiring meningkatnya jumlah proses yang dibangkitkan. Algoritme AES paralel domain decomposition dengan perlakuan 1 secara umum memiliki waktu eksekusi yang lebih cepat daripada dengan perlakuan 2, walaupun perbedaaan waktu eksekusinya tidak terlalu signifikan. Waktu eksekusi enkripsi dan dekripsi AES pipeline untuk setiap file disajikan pada Gambar 26 dan 27.

15

komunikasi blocking. p0 akan menunggu sampai p1 selesai mengeksekusi baru mengirim data selanjutnya. Hasilnya adalah overhead komunikasi yang tinggi. Jika proses yang dibangkitkan lima, beban fungsi cukup merata tiap proses, sehingga proses-proses tidak akan saling menunggu terlalu lama untuk mengirim atau menerima data.

Gambar 26 Waktu eksekusi enkripsi AES pipeline.

Speedup Nilai speedup enkripsi dan dekripsi AES paralel domain decomposition hasil percobaan disajikan pada Gambar 28 dan 29.

Gambar 28 Speedup enkripsi AES paralel domain decomposition. Gambar 27 Waktu eksekusi dekripsi AES pipeline. Terlihat dari kedua gambar tersebut, waktu eksekusi aktual lebih cepat dibanding waktu eksekusi harapan. Penyebab terjadinya hal ini adalah kurang akuratnya pengukuran waktu eksekusi untuk tiap komputasi. Pengukuran menunjukkan D (waktu komputasi SubBytes +ShiftRows + MixColumns + AddRoundKey) sebesar 3.742 µs, namun pengukuran lain menunjukan B (waktu komputasi enkripsi satu blok data) sebesar 10 µs. Berdasarkan struktur komputasinya, seharusnya D sepuluh kali lebih cepat dari B, namun hasil pengukuran menunjukan D tiga kali lebih cepat dari B. Hal ini dapat mengakibatkan estimasi yang berlebihan terhadap waktu eksekusi harapan secara keseluruhan. Waktu eksekusi enkripsi dan dekripsi AES pipeline lebih lambat dibandingkan dengan waktu eksekusi sekuensial pada penggunaan dua atau tiga proses. Waktu eksekusi secara pipeline baru membaik jika proses yang dibangkitkan lima. Penyebab terjadinya fenomena ini adalah penggunaan komunikasi blocking dan pendistribusian beban fungsi yang tidak merata tiap proses. Jika proses yang dibangkitkan dua, p1 memiliki beban kerja yang lebih besar dibanding p0. Akibatnya, p1 belum selesai mengeksekusi ketika p0 telah selesai karena komunikasi yang digunakan adalah

Gambar 29 Speedup dekripsi AES paralel domain decomposition. Grafik speedup untuk ukuran file meningkat dan jumlah proses tetap disajikan dalam Gambar 30.

Gambar 30 Speedup enkripsi dan dekripsi AES paralel domain decomposition dengan jumlah proses 8 buah. Berdasarkan Gambar 28 dan 29, nilai speedup cenderung naik seiring meningkatknya jumlah proses, namun hal ini

16

hanya berlaku jika jumlah proses kurang dari atau sama dengan jumlah prosesor. Jika jumlah proses lebih besar dari jumlah prosesor, speedup akan konstan dan bahkan bisa turun. Nilai speedup tidak sebanding dengan jumlah proses yang digunakan. Hal ini berkaitan dengan waktu eksekusinya yang tidak terlalu signifikan menurun seiring meningkatnya jumlah proses yang digunakan. Gambar 30 menunjukkan speedup semakin membesar seiring meningkatnya ukuran file. Fenomena ini sesuai dengan teori yang dikenal dengan nama Amdahl Effect. Speedup perlakuan 1 secara umum lebih baik dibanding perlakuan 2 karena waktu komputasi perlakuan 1 secara umum lebih baik dibanding perlakuan 2. Nilai speedup enkripsi dan dekripsi AES pipeline hasil percobaan disajikan pada Gambar 31.

Gambar 33 Efisiensi dekripsi AES paralel domain decomposition. Kedua gambar tersebut menunjukkan semakin banyak jumlah proses yang digunakan, nilai efisiensi akan semakin menurun. Nilai efisiensi yang diperoleh umumnya lebih kecil dari 0.5. Hal ini menunjukkan pemanfaatan prosesor yang rendah. Penambahan jumlah prosesor tidak dapat menurunkan waktu komputasi secara proporsional. Untuk semua jenis file, tidak ada jumlah proses yang nilai efisiensinya mendekati satu, hal ini berarti algoritme AES paralel domain decomposition yang digunakan tidak cost-optimal. Efisiensi enkripsi dan dekripsi AES pipeline untuk semua proses dan ukuran file disajikan dalam Gambar 34.

Gambar 31 Speedup enkripsi dan dekripsi AES pipeline. Speedup menggunakan dua atau tiga proses bernilai kurang dari satu menunjukkan bahwa waktu eksekusinya lebih lama dibanding dengan eksekusi secara sekuensial. Sedangkan jika menggunakan lima proses nilai speedup bernilai lebih dari satu karena waktu eksekusinya lebih cepat dibanding dengan eksekusi secara sekuensial. Efisiensi Efisiensi enkripsi dan dekripsi AES Paralel domain decomposition untuk semua proses dan ukuran file disajikan dalam Gambar 32 dan 33.

Gambar 32 Efisiensi enkripsi AES paralel domain decomposition.

Gambar 34 Efisiensi enkripsi dan dekripsi AES pipeline. Gambar 34 menunjukkan pada proses enkripsi, efisiensi semakin menurun seiring meningkatnya jumlah proses yang digunakan, sedangkan pada proses dekripsi terlihat efisiensi awalnya menurun lalu meningkat. Sekalipun waktu eksekusinya lebih buruk dari sekuensial, AES pipeline dengan menggunakan dua proses memiliki efisiensi yang cukup baik jika dibandingkan dengan AES paralel yang menggunakan proses lebih dua. Hal ini disebabkan pada dasarnya efisiensi adalah ukuran pemanfaatan prosesor dalam eksekusi program secara paralel. Untuk semua jenis file, tidak ada jumlah proses yang nilai efisiensinya mendekati satu, hal ini

17

berarti algoritme AES paralel pipeline yang digunakan tidak cost-optimal. Cost Cost enkripsi dan dekripsi AES Paralel domain decomposition untuk semua proses dan ukuran file disajikan dalam Gambar 35 dan 36.

Gambar tersebut menunjukkan bahwa pada proses enkripsi AES pipeline, nilai cost semakin besar seiring meningkatnya jumlah proses yang digunakan, sedangkan pada pada proses dekripsi nilai cost turun ketika proses yang dibangkitkan ada lima. Semakin besar ukuran file, nilai cost juga semakin besar. Overhead Overhead enkripsi dan dekripsi AES Paralel domain decomposition untuk semua proses dan ukuran file disajikan dalam Gambar 38 dan 39.

Gambar 35 Cost enkripsi paralel domain decomposition.

Gambar 38 Overhead enkripsi AES paralel domain decomposition.

Gambar 36 Cost dekripsi paralel domain decomposition Gambar 35 dan 36 menunjukkan bahwa cost semakin besar seiring dengan meningkatnya jumlah proses yang digunakan. Cost yang yang paling mendekati nilai eksekusi sekuensial adalah yang menggunakan 4 proses untuk setiap file dengan besarnya dua kali waktu eksekusi sekuensialnya. Semakin besar ukuran file, nilai cost juga semakin besar. Cost enkripsi dan dekripsi AES pipeline untuk semua proses dan ukuran file disajikan dalam Gambar 37.

Gambar 37 Cost enkripsi dan dekripsi AES pipeline.

Gambar 39 Overhead dekripsi AES paralel domain decomposition. Terlihat pada kedua gambar tersebut, nilai overhead pada proses enkripsi lebih kecil dibandingkan dengan proses dekripsi. Nilai overhead semakin meningkat seiring dengan meningkatnya jumlah proses yang digunakan, namun hal ini hanya berlaku jika jumlah proses kurang dari atau sama dengan jumlah prosesor. Nilai overhead yang tidak mendekati nol dan stabil menunjukkan sistem paralel yang digunakan tidak ideal. Overhead enkripsi dan dekripsi AES pipeline untuk semua proses dan ukuran file disajikan dalam Gambar 40. Terlihat pada gambar tersebut, nilai overhead menurun pada penggunaan lima proses. Hal ini disebabkan semata-mata karena AES pipeline dengan penggunaan lima proses dapat menurunkan waktu eksekusi sekuensialnya. Untuk semua jenis file, tidak ada jumlah proses yang nilai

18

overhead nya mendekati nol. Hal ini berarti AES pipeline juga tidak ideal.

Gambar 40 Overhead enkripsi dan dekripsi AES pipeline.

Saran Saran untuk penelitian lebih lanjut : 1 Pada penelitian selanjutnya dapat digunakan library MPI yang lain seperti Open-MP atau gabungan dari library MPI dan Open-MP. 2 Pada penelitian selanjutnya dapat dianalisis kinerja algoritme dengan parameter tambahan lain seperi Amdahl’s Law, Gustafson-Barsis’s Law, Karp-Flatt Metric, dan Isoefficiency Metric. 3 Pada penelitian selanjutnya dapat dihilangkan batasan jumlah proses yang digunakan pada algoritme AES pipeline functional decomposition.

KESIMPULAN DAN SARAN Kesimpulan Kesimpulan dari hasil penelitian ini di antaranya sebagai berikut: 1 Waktu eksekusi algoritme AES secara sekuensial akan semakin meningkat seiring dengan meningkatnya ukuran file yang digunakan. Waktu eksekusi enkripsi dan dekripsi secara sekuensial untuk file 1 (4.762 MB) adalah 3.092 dan 5.107 detik, file 2 (23.300 MB) 15.502 dan 25.475 detik, dan file 3 (118.522 MB) 76.349 dan 127.227 detik. 2 Algoritme AES paralel domain decomposition dapat menurunkan waktu komputasi AES sekuensial. Waktu eksekusi enkripsi dan dekripsi secara paralel domain decomposition terendah untuk file 1 adalah 1.372 dan 1.633 detik, file 2 6.172 dan 7.254 detik, dan file 3 29.112 dan 34.896 detik. 3 Algoritme AES pipeline dapat menurunkan waktu komputasi sekuensial pada penggunaan lima buah proses. Waktu eksekusi enkripsi dan dekripsi secara pipeline terendah untuk file 1 adalah 2.617 dan 3.408 detik, file 2 12.234 dan 16.503 detik, dan file 3 61.271 dan 83.33 detik. 4 Eksekusi AES secara paralel domain decomposition dengan perlakuan 1 memberikan hasil yang lebih baik dibandingkan dengan perlakuan 2. Selisih perlakuan 1 dengan perlakuan 2 rata-rata sebesar 0.792 detik. 5 Algoritme AES paralel domain decomposition dan algoritme AES pipeline yang digunakan dalam penelitian ini tidak cost-optimal.

DAFTAR PUSTAKA Ariyus D. 2008, Pengantar Ilmu Kriptografi Teori, Analisis, dan Implementasi. Yogyakarta: Penerbit Andi. Giri EP. 2004. Analisis Algoritme dan Waktu Enkripsi Versus Dekripsi pada Advanced Encryption Standard (AES) [skripsi]. Bogor: Fakultas Matematika dan Ilmu Pengetahuan Alam. Institut Pertanian Bogor. Grama A, Gupta A, Karypis G, Kumar V. 2003. Introduction to Parallel Computing. Ed ke-2. England: Addison-Wesley Publishing Company. Menezes A, et al. 1996, Handbook of Applied Cryptography, London: CRC Press. Quinn MJ. 2004. Parallel Programming in C with MPI and OpenMP. San Francisco: Mc Graw Hill. Stallings

W. 2003, Crypthography and Network Security Principles and Practice. Ed ke-3. London: Prentice Hall.

LAMPIRAN

22

Lampiran 1 Variabel pendukung dan waktu eksekusi yang diharapkan Variabel λ (lokal) λ (jaringan) β x1 file 1 x2 file 1 x1 file 2 x2 file 2 x1 file 3 x2 file 3 d A B C D E F G

Proses

Nilai 0.52029 µs 112.084539 µs 100 mbps 3.474 x 103 µs 151.296 x 103 µs 19.343 x 103 µs 743.531 x 103 µs 85.356 x 103 µs 3.856 x 106 µs 0.726 µs 4 µs 10 µs 17,200 µs 3.742 µs 2.960 µs 6.200 µs 3.239 µs

Waktu eksekusi AES paralel domain decomposition yang diharapkan waktu enkripsi waktu dekripsi file 1

file 2

file 3

file 1

file 3

file 3

1

3.1323

14.7181

74.2317

5.2756

25.2032

127.5666

4

1.4714

7.1998

36.6836

2.0073

9.8211

50.0173

8

1.1947

5.8456

29.7946

1.4626

7.1563

36.4615

12

1.1025

5.3943

27.4983

1.2811

6.2680

31.9429

16

1.0564

5.1686

26.3502

1.1904

5.8239

29.6836

20

1.0288

5.0332

25.6613

1.1360

5.5575

28.3281

24

1.0104

4.9430

25.2021

1.0997

5.3799

27.4244

Waktu eksekusi AES pipeline yang diharapkan waktu enkripsi waktu dekripsi

proses file 1

file 2

file 3

file 1

file 3

file 3

1

3.1323

14.7181

74.2317

5.2756

25.2032

127.5666

2

2.1474

10.5077

53.5106

3.0857

15.0980

76.8603

3

2.3281

11.3915

58.0067

3.7564

18.3787

93.5485

5

1.3959

6.8314

34.8104

1.8720

9.1604

46.6576

23

Lampiran 2 Implementasi AES sekuensial /* ****************************************************************** ** Advanced Encryption Standard implementation in C. ** By Niyaz PK ** E-mail: [email protected] ** Downloaded from Website: www.hoozi.com Modified By Sayed Zulfikar ~ [email protected] ****************************************************************** */ // Include stdio.h for standard input/output. // Used for giving output to the screen. #include<stdio.h> #include <stdlib.h> #include <mpi.h> main(int argc, char *argv[]) { int i, j, c, rank, size, alg, pad=0, sisa, Cpad = 0; unsigned long int ps, k, pk; double block; double start, finish, wp; FILE *file, *hasil, *kunci; char character; unsigned char Kunci[16]; char *file_awal, *file_akhir, *file_kunci, s; //penampung argumen file_kunci = argv[1]; file_awal = argv[2]; file_akhir = argv[3]; alg = atoi(argv[4]); //penentuan panjang kunci (128 bit) Nr = 128; // Calculate Nk and Nr from the recieved value. Nk = Nr / 32; Nr = Nk + 6; MPI_Init (&argc, &argv); MPI_Comm_rank(MPI_COMM_WORLD, &rank); MPI_Comm_size(MPI_COMM_WORLD, &size); if ((argc != 5) || (size!=1)) { MPI_Finalize(); if (rank==0) printf("\nTerjadi Kesalahan input data!\n+ Argumen Harus Berjumlah 4!\n\t1. File Eksekusi\n\t2. File Kunci\n\t3. File Input\n\t4. File output\n+ Jumlah Proses yang bisa dibangkitkan hanya 1 saja!\n+ Panjang Kunci Kurang/Lebih dari 16 Karakter!\n\nSilahkan Periksa Kembali"); exit(1); } start = MPI_Wtime();

24

Lampiran 2 (lanjutan) if (rank ==0) { pk = ambil_pchar(file_kunci); kunci = fopen(file_kunci, "rb"); fread(Kunci, pk, 1, kunci); for(i=0;i
25

Lampiran 2 (lanjutan) free(input); //mencetak hasil enkripsi hasil = fopen (file_akhir, "wb"); for (k=0;k<(((block-1)*16)+16-pad);k++) { fputc(output[k], hasil); } fclose (hasil); finish = MPI_Wtime(); wp = finish-start; //printf("%f", wp); } MPI_Finalize(); return 0; }

26

Lampiran 3 Implementasi AES paralel domain decomposition /* ****************************************************************** ** Advanced Encryption Standard Parallel Domain Decomposition implementation in C. By Sayed Zulfikar ~ [email protected] ****************************************************************** */ // Include stdio.h for standard input/output. // Used for giving output to the screen. #include<stdio.h> #include <stdlib.h> #include <mpi.h> main(int argc, char *argv[]) { int i, j, alg, pad=0, c=0, rank, size, block, ex=0, dest=1, dest2=1, d, s, cei, flo, b, tagR, sisa, Cpad=0; unsigned long int ps, pk, k; double start, finish, wp, bl; FILE *file, *hasil, *kunci; char *file_awal, *file_akhir, *file_kunci; unsigned char *tempIn, *tempOut, Kunci[16]; //penampung argumen file_kunci = argv[1]; file_awal = argv[2]; file_akhir = argv[3]; alg = atoi(argv[4]); //penentuan panjang kunci (128 bit) Nr = 128; // Calculate Nk and Nr from the recieved value. Nk = Nr / 32; Nr = Nk + 6; MPI_Init (&argc, &argv); MPI_Comm_rank(MPI_COMM_WORLD, &rank); MPI_Comm_size(MPI_COMM_WORLD, &size); MPI_Status status; int send[size]; int displs[size]; int tag[size]; start = MPI_Wtime(); start = MPI_Wtime(); //P0 melakuakan PreProcessing //P0 melakukan pengecekan inputan sesuai atau tidak //P0 melakukan pembacaan kunci, pembacaan inputan, menghitung jumlah blok yang terbentuk, dan melakukan padding if (rank == 0) { //fungsi kontrol jenis algoritma if ((alg!=1) && (alg!=2)) ex = 1;

27

Lampiran 3 (lanjutan) //fungsi kontrol jumlah argumen if (argc !=5) ex = 1; pk = ambil_pchar(file_kunci); if (pk==16) { //pembacaan kunci kunci = fopen(file_kunci, "rb"); fread(Kunci, pk, 1, kunci); for(i=0;i
28

Lampiran 3 (lanjutan) s=(block%size); b = block/size; cei = ceil (((float)block)/size); flo = floor (((float)block)/size); // The KeyExpansion routine must be called before encryption. KeyExpansion(); //jika data dapat dibagi MERATA ke setiap proses if (s == 0){ //alokasi memori untuk data input dan output yang sudah dibagi rata ke setiap proses tempIn = (unsigned char*)malloc((b*16)*sizeof(unsigned char)); tempOut = (unsigned char*)malloc((b*16)*sizeof(unsigned char)); //scatter data, setiap proses langsung mendapat banyak data MPI_Scatter (input, 16*b, MPI_UNSIGNED_CHAR, tempIn, 16*b, MPI_UNSIGNED_CHAR, 0, MPI_COMM_WORLD); //proses enkripsi atau dekripsi for (i=0;i a = c*(ceil(a/b)) + (b-c)*(floor(a/b)) else { for (i=0;i<size;i++) { //jika sisa bagi masih !=0, maka proses i akan mendapat data pembulatan ke atas if (s!=0) { send[i] = 16*cei; tag[i] = 1; s--; }

29

Lampiran 3 (lanjutan) //jika sisa bagi sudah 0, maka proses i dapat data pembulatan ke bawah else { send[i] = 16*flo; tag[i] = 0; } if (i==0) displs[i]=0; else displs[i] = displs[i-1]+send[i-1];

} if (tag[rank]==1) tagR=cei; else tagR=flo; //alokasi memori untuk data yang sudah dibagi tempIn = (unsigned char*)malloc((tagR*16)*sizeof(unsigned char)); tempOut = (unsigned char*)malloc((tagR*16)*sizeof(unsigned char)); //Scatter data berdasarkan bobotnya masing-masing MPI_Scatterv(input, send, displs, MPI_UNSIGNED_CHAR, tempIn, 16*tagR, MPI_UNSIGNED_CHAR, 0, MPI_COMM_WORLD); //proses enkripsi //jika proses termasuk yang mendapatkan data pembulatan ke atas if (tag[rank]==1) { for (i=0;i
30

Lampiran 3 (lanjutan) if (alg==2) { //unpadding if (rank==(size-1) && i==(flo-1)) { s = out[15]; for (i=16-s;i<16;i++) if (out[i]==s) Cpad++; } if (Cpad==s) pad = s; } } } MPI_Gatherv(tempOut, 16*tagR, MPI_UNSIGNED_CHAR, output, send, displs, MPI_UNSIGNED_CHAR, 0, MPI_COMM_WORLD); } //broadcast unpadding if (block<size) x=block-1; else x=size-1; MPI_Bcast(&pad, 1, MPI_INT,x, MPI_COMM_WORLD); //mencetak hasil enkripsi if (rank==0) { hasil = fopen (file_akhir, "wb"); for (k=0;k<(((block-1)*16)+16-pad);k++) { fputc(output[k], hasil); } fclose (hasil); } finish = MPI_Wtime(); wp = finish-start; if (rank==0) printf("%f", wp); free(input); MPI_Finalize(); return 0; }

31

Lampiran 4 Implementasi AES pipeline /* ****************************************************************** ** Advanced Encryption Standard Parallel Functional Decomposition implementation in C. By Sayed Zulfikar ~ [email protected] ****************************************************************** */ // Include stdio.h for standard input/output. // Used for giving output to the screen. #include<stdio.h> #include <stdlib.h> #include <mpi.h> main(int argc, char *argv[]) { int rank, size, alg, block, blockCount, proc, i, j, pad=16, ex=0; unsigned long int ps, pk, k; double start, finish, wp, bl; FILE *file, *hasil, *kunci; char *file_awal, *file_akhir, *file_kunci; unsigned char *tempIn, *tempOut, Kunci[16]; //penampung argumen file_kunci = argv[1]; file_awal = argv[2]; file_akhir = argv[3]; alg = atoi(argv[4]); //penentuan panjang kunci (128 bit) Nr = 128; // Calculate Nk and Nr from the recieved value. Nk = Nr / 32; Nr = Nk + 6; MPI_Init (&argc, &argv); MPI_Comm_rank(MPI_COMM_WORLD, &rank); MPI_Comm_size(MPI_COMM_WORLD, &size); MPI_Status status; start = MPI_Wtime(); //P0 melakuakan PreProcessing Tahap 1 //P0 melakukan pengecekan inputan sesuai atau tidak //P0 melakukan pembacaan kunci, pembacaan inputan, menghitung jumlah blok yang terbentuk, melakukan padding dan membangkitkan Upa-Kunci if (rank == 0) { //fungsi kontrol ukuran proses if ((size==2) || (size==3) || (size==5)) ex = 0; else ex = 1; //fungsi kontrol jumlah argumen if (argc !=5) ex = 1;

32

Lampiran 4 (lanjutan) pk = ambil_pchar(file_kunci); if (pk==16){ kunci = fopen(file_kunci, "rb"); fread(Kunci, pk, 1, kunci); for(i=0;i
33

Lampiran 4 (lanjutan) //PreProcessing tahap 2 dilakukan oleh P0 //P0 mengambil data tiap blok (16 byte) lalu AddRoundKey(0) dan mengirimkan data tersebut ke P1 if (rank == 0) { while (blockCount > 0) { for (i=0;i<16;i++) in[i] = input[((block-blockCount)*16)+i]; //Copy the input PlainText to state array. for(i=0;i<4;i++) for(j=0;j<4;j++) state[j][i] = in[i*4 + j]; if (alg==1) AddRoundKey(0); else AddRoundKey(10); for(i=0;i<4;i++) for(j=0;j<4;j++) out[i*4+j]=state[j][i]; MPI_Send(out, 16, MPI_UNSIGNED_CHAR, rank+1, rank+1, MPI_COMM_WORLD); blockCount--; } free(input); } //Pengecekan jika tidak ada proses antara, maka selain PreProcessing sisanya dikerjakan oleh P1 if (proc==0) { if (rank == 1) { output=(unsigned char*)malloc((block*16)*sizeof(unsigned char)); while (blockCount > 0) { MPI_Recv(in, 16, MPI_UNSIGNED_CHAR, rank-1, rank, MPI_COMM_WORLD, &status); for(i=0;i<4;i++) for(j=0;j<4;j++) state[j][i] = in[i*4 + j]; if (alg==1) { for(i=1;i<10;i++) { SubBytes(); ShiftRows(); MixColumns(); AddRoundKey(i); } SubBytes(); ShiftRows(); AddRoundKey(10); }

34

Lampiran 4 (lanjutan) else { for(i=9;i>0;i--) { InvShiftRows(); InvSubBytes(); AddRoundKey(i); InvMixColumns(); } InvShiftRows(); InvSubBytes(); AddRoundKey(0); } for(i=0;i<4;i++) for(j=0;j<4;j++) out[i*4+j]=state[j][i]; if (alg==2) { //unpadding if (blockCount == 1) { for (j=0;j<16;j++) if (out[j]==0x5) pad -=1; } } for (i=0;i<16;i++) output[((block-blockCount)*16)+i] = out[i]; blockCount--; } hasil = fopen (file_akhir, "wb"); for (k=0;k<(((block-1)*16)+pad);k++) { fputc(output[k], hasil); } fclose (hasil); finish = MPI_Wtime(); wp = finish-start; printf("%f", wp); } } //Jika ada proses antara else { if ((rank>0) && (rank<(size-1))) { while (blockCount > 0) { MPI_Recv(in, 16, MPI_UNSIGNED_CHAR, rank-1, rank, MPI_COMM_WORLD, &status); for(i=0;i<4;i++) for(j=0;j<4;j++) state[j][i] = in[i*4 + j]; if (alg==1) { for (i=((rank*proc)-(proc-1));i<=((9/proc)*rank);i++)

35

Lampiran 4 (lanjutan) { SubBytes(); ShiftRows(); MixColumns(); AddRoundKey(i); } } else { for (i=(9-((rank*proc)-proc));i>=(10-((9/proc)*rank));i--) { InvShiftRows(); InvSubBytes(); AddRoundKey(i); InvMixColumns(); } } for(i=0;i<4;i++) for(j=0;j<4;j++) out[i*4+j]=state[j][i]; MPI_Send(out, 16, MPI_UNSIGNED_CHAR, rank+1, rank+1, MPI_COMM_WORLD); blockCount--; } } //P(size-1) melakukan finishing else if (rank == size-1) { output=(unsigned char*)malloc((block*16)*sizeof(unsigned char)); while (blockCount > 0) { MPI_Recv(in, 16, MPI_UNSIGNED_CHAR, rank-1, rank, MPI_COMM_WORLD, &status); for(i=0;i<4;i++) for(j=0;j<4;j++) state[j][i] = in[i*4 + j]; if (alg==1) { SubBytes(); ShiftRows(); AddRoundKey(10); } else { InvShiftRows(); InvSubBytes(); AddRoundKey(0); } for(i=0;i<4;i++) for(j=0;j<4;j++) out[i*4+j]=state[j][i]; if (alg==2) {

36

Lampiran 4 (lanjutan) //unpadding if (blockCount == 1) { s = out[15]; for (i=16-s;i<16;i++) if (out[i]==s) Cpad++; if (Cpad==s) pad =s; } for (i=0;i<16;i++) output[((block-blockCount)*16)+i] = out[i]; blockCount--; } hasil = fopen (file_akhir, "wb"); for (k=0;k<(((block-1)*16)+16-pad);k++) { fputc(output[k], hasil); } fclose (hasil); finish = MPI_Wtime(); wp = finish-start; printf("%f", wp); } } MPI_Finalize(); return 0; }

37

Lampiran 5 Pengaturan dan instalasi MPICH2 Langkah-langkah dalam pengaturan dan istalasi MPICH2 dalam penelitian ini yaitu: 1 Hubungkan tiap komputer dengan Fast Ethernet dan kabel UTP agar membentuk topologi star. 2 Ping ke setiap komputer yang hendak digunakan, pastikan semua komputer saling terhubung agar lebih mudah buat IP menjadi statis dan matikan firewall. 3 Instal mpich2-1.4.1p1-win-ia32.msi di setiap komputer dengan menggunakan administrator priviledge. 4 Tentukan passphrase yang akan digunakan dan pastikan setiap komputer memiliki passphrase yang sama dan Pilih “Everyone” pada salah satu menu instalasi agar MPICH2 bisa digunakan untuk semua pengguna komputer.

5

Tambahkan path MPICH2 (C:\Program Files\MPICH2\bin) pada system variabel tiap komputer.

6

Buat user baru dengan nama yang seragam dan password-nya sesuai dengan passphrase di tiap komputer. Daftar user baru di tiap komputer dengan menjalankan perintah “mpiexec –register –user 1” pada jendela command prompt, masukkan nama dan passphrase sesuai dengan poin nomor 7. Jalankan contoh program C:\Program Files\MPICH2\examples\cpi.exe secara paralel dengan menggunakan user yang sudah daftarkan. Jika contoh program dapat berjalan dengan baik, cluster komputer telah siap digunakan.

7 8

38

Lampiran 5 (lanjutan) Beberapa kesalahan umum yang sering terjadi: 1 Pesan eror “Mpiexec is not recognize as internal or external command, operable program or batch file” ketika hendak menjalankan program paralel. Penyebab : instalasi MPICH2 atau penambahan path MPICH2 yang tidak sempurna. Solusi : instalasi ulang MPICH2 dan pastikan sesuai langkah di atas. 2

Pesan eror “SMPD version missmatch” ketika hendak menjalankan program paralel. Penyebab : ada program lain yang menggunakan smpd dengan versi yang berbeda dari MPICH2 yang digunakan Solusi : instalasi ulang MPICH2 dan pastikan installer-nya sama, hapus path smpd program lain jika ada.

39

Lampiran 6 Data hasil percobaan algoritme enkripsi AES paralel domain decomposition perlakuan 1 Jenis Eksekusi File

Tipe File

Sekuen 1

1

pohon.jpg (4.762.960 bytes)

Waktu Rata-Rata

Enkripsi domain decomposition perlakuan 1 4

8

12

16

20

24

3.070

1.747

1.461

1.397

1.342

1.396

1.369

3.064

1.622

1.365

1.473

1.351

1.446

1.477

3.062

1.726

1.401

1.437

1.443

1.475

1.352

3.197

1.614

1.418

1.359

1.435

1.435

1.456

3.065

1.677

1.521

1.453

1.470

1.400

1.380

3.092

1.677

1.433

1.424

1.408

1.430

1.407

SpeedUp

1.843

2.157

2.172

2.196

2.162

2.198

Efisiensi

0.461

0.270

0.181

0.137

0.135

0.137

Cost

6.709

11.466

17.085

22.530

22.884

22.509

Overhead

3.617

8.374

13.993

19.439

19.792

19.418

Jenis Eksekusi File

Tipe File

Sekuen 1

2

lagu.flac (23.300.227 bytes)

Waktu Rata-Rata

Enkripsi domain decomposition perlakuan 1 4

8

12

16

20

24

15.184

7.708

6.191

6.252

6.343

6.325

6.225

15.613

7.742

6.181

6.157

6.233

6.233

6.154

15.672

9.076

6.138

6.502

6.435

6.340

6.242

15.549

8.003

6.263

6.368

6.529

6.220

6.083

15.490

7.900

6.145

6.479

6.384

6.499

6.157

15.502

8.086

6.184

6.352

6.385

6.323

6.172

SpeedUp

1.917

2.507

2.441

2.428

2.451

2.511

Efisiensi

0.479

0.313

0.203

0.152

0.153

0.157

Cost

32.343

49.468

76.220

102.159

101.175

98.757

Overhead

16.842

33.967

60.718

86.657

85.673

83.255

Jenis Eksekusi File

3

Tipe File

Sekuen

Enkripsi domain decomposition perlakuan 1 4

8

12

16

20

24

76.177

37.213

30.780

29.028

29.197

30.184

29.294

76.229

37.107

30.813

29.331

29.272

30.301

29.834

76.751

37.701

30.979

29.027

29.176

30.322

29.197

76.238

37.302

30.661

28.972

29.300

30.338

29.902

76.351

37.428

30.861

29.201

29.323

30.286

29.557

76.349

37.350

30.819

29.112

29.254

30.286

29.557

SpeedUp

2.044

2.477

2.623

2.610

2.521

2.583

Efisiensi

video.mp4 (118.522.028 bytes)

Waktu Rata-Rata

0.511

0.310

0.219

0.163

0.158

0.161

Cost

149.400

246.550

349.341

468.056

484.580

472.910

Overhead

73.052

170.201

272.993

391.707

408.231

396.561

40

Lampiran 7 Data hasil percobaan algoritme dekripsi AES paralel domain decomposition perlakuan 1 Jenis Eksekusi File

Tipe File

Sekuen 1

1

pohon.chp (4.762.960 bytes)

Waktu Rata-Rata

Dekripsi domain decomposition perlakuan 1 4

8

12

16

20

24

5.115

2.338

1.863

1.756

1.750

1.640

1.688

5.106

2.145

1.727

1.654

1.619

1.629

1.696

5.097

2.149

1.727

1.626

1.641

1.646

1.553

5.111

2.160

1.762

1.572

1.610

1.696

1.628

5.106

2.206

1.826

1.769

1.543

1.692

1.657

5.107

2.200

1.781

1.676

1.633

1.661

1.644

SpeedUp

2.322

2.868

3.048

3.128

3.075

3.106

Efisiensi

0.580

0.358

0.254

0.196

0.192

0.194

Cost

8.799

14.248

20.107

26.122

26.573

26.306

Overhead

3.692

9.141

15.000

21.015

21.466

21.199

Jenis Eksekusi File

Tipe File

Sekuen 1

2

lagu.chp (23.300.227 bytes)

Waktu Rata-Rata

Dekripsi domain decomposition perlakuan 1 4

8

12

16

20

24

25.010

9.940

8.248

7.358

7.266

7.275

7.369

25.938

9.926

8.485

7.338

7.140

7.278

7.214

25.229

10.301

8.298

7.183

7.195

7.312

7.268

25.550

10.052

8.541

7.376

7.592

7.321

7.333

25.647

10.026

7.509

7.263

7.267

7.319

7.086

25.475

10.049

8.216

7.304

7.292

7.301

7.254

SpeedUp

2.535

3.101

3.488

3.494

3.489

3.512

Efisiensi

0.634

0.388

0.291

0.218

0.218

0.219

Cost

40.195

65.730

87.645

116.672

116.820

116.063

Overhead

14.720

40.256

62.170

91.197

91.345

90.588

Jenis Eksekusi File

3

Tipe File

Sekuen

Dekripsi domain decomposition perlakuan 1

1

4

8

12

16

20

24

127.129

50.608

39.144

35.388

35.064

36.978

35.167

127.174

49.985

39.947

36.527

35.216

36.326

35.363

127.329

50.556

39.201

35.966

35.025

36.977

36.521

127.280

49.881

38.820

36.032

36.218

37.066

36.147

127.220

50.530

38.954

35.891

35.099

36.571

35.940

127.227

50.312

39.213

35.961

35.324

36.784

35.828

SpeedUp

2.529

3.244

3.538

3.602

3.459

3.551

Efisiensi

video.chp (118.522.028 bytes)

Waktu Rata-Rata

0.632

0.406

0.295

0.225

0.216

0.222

Cost

201.248

313.706

431.532

565.190

588.539

573.241

Overhead

74.021

186.480

304.305

437.963

461.312

446.014

41

Lampiran 8 Data hasil percobaan algoritme enkripsi AES paralel domain decomposition perlakuan 2

File

Tipe File

1

pohon.jpg (4.762.960 bytes)

Waktu Rata-Rata SpeedUp Efisiensi Cost Overhead

File

Tipe File

2

lagu.flac (23.300.227 bytes)

Waktu Rata-Rata SpeedUp Efisiensi Cost Overhead

File

Tipe File

3

video.mp4 (118.522.028 bytes)

Waktu Rata-Rata SpeedUp Efisiensi Cost Overhead

Sekuen 1 3.070 3.064 3.062 3.197 3.065 3.092

Sekuensial 1 15.184 15.613 15.672 15.549 15.490 15.502

Sekuen 1 76.177 76.229 76.751 76.238 76.351 76.349

Jenis Eksekusi Enkripsi domain decomposition perlakuan 2 4 8 12 16 1.466 1.517 1.369 1.300 1.467 1.561 1.481 1.490 1.494 1.480 1.425 1.354 1.467 1.605 1.539 1.365 1.471 1.602 1.368 1.353 1.473 1.553 1.436 1.372 2.099 1.991 2.152 2.253 0.525 0.249 0.179 0.141 5.891 12.423 17.237 21.957 2.800 9.331 14.146 18.865 Jenis Eksekusi Enkripsi domain decomposition perlakuan 2 4 8 12 16 7.176 6.338 6.534 5.765 7.165 6.533 6.319 6.298 7.312 6.390 6.278 6.464 7.189 6.396 6.256 6.371 8.245 6.548 6.159 6.463 7.417 6.441 6.309 6.272 2.090 2.407 2.457 2.472 0.522 0.301 0.205 0.154 29.669 51.530 75.712 100.353 14.168 36.029 60.211 84.852 Jenis Eksekusi Enkripsi domain decomposition perlakuan 2 4 8 12 16 37.251 31.667 30.264 29.080 36.531 32.365 30.145 29.216 36.560 31.606 31.298 29.052 36.515 32.106 30.022 29.217 36.565 31.633 30.293 29.064 36.684 31.875 30.405 29.126 2.081 2.395 2.511 2.621 0.520 0.299 0.209 0.164 146.737 255.002 364.855 466.016 70.388 178.653 288.506 389.667

42

Lampiran 9 Data hasil percobaan algoritme dekripsi AES paralel domain decomposition perlakuan 2

File

Tipe File

1

pohon.chp (4.762.960 bytes)

Waktu Rata-Rata SpeedUp Efisiensi Cost Overhead

File

Tipe File

2

lagu.chp (23.300.227 bytes)

Waktu Rata-Rata SpeedUp Efisiensi Cost Overhead

File

Tipe File

3

video.chp (118.522.028 bytes)

Waktu Rata-Rata SpeedUp Efisiensi Cost Overhead

Sekuen 1 5.115 5.106 5.097 5.111 5.106 5.107

Sekuen 1 25.010 25.938 25.229 25.550 25.647 25.475

Sekuen 1 127.129 127.174 127.329 127.280 127.220 127.227

Jenis Eksekusi Dekripsi domain decomposition perlakuan 2 4 8 12 16 2.395 1.980 1.633 1.599 2.393 2.023 1.738 1.604 2.387 1.916 1.646 1.756 2.393 1.925 1.729 1.537 2.391 2.018 1.667 1.723 2.392 1.972 1.683 1.644 2.135 2.589 3.035 3.107 0.534 0.324 0.253 0.194 9.567 15.778 20.194 26.298 4.460 10.671 15.087 21.191 Jenis Eksekusi Dekripsi domain decomposition perlakuan 2 4 8 12 16 11.674 8.760 7.546 7.302 11.653 8.632 7.573 7.288 11.654 8.856 7.575 7.221 11.683 8.758 7.577 7.451 11.700 8.679 7.527 7.372 11.673 8.737 7.560 7.327 2.182 2.916 3.370 3.477 0.546 0.364 0.281 0.217 46.692 69.897 90.717 117.227 21.217 44.422 65.242 91.753 Jenis Eksekusi Dekripsi domain decomposition perlakuan 2 4 8 12 16 60.562 43.108 37.679 34.591 60.526 43.393 37.602 35.059 59.310 44.178 38.198 34.949 59.258 43.303 37.564 35.232 60.476 43.166 37.668 34.650 60.026 43.429 37.742 34.896 2.120 2.929 3.371 3.646 0.530 0.366 0.281 0.228 240.105 347.436 452.905 558.341 112.878 220.209 325.678 431.115

43

Lampiran 10 Data hasil percobaan algoritme enkripsi AES pipeline Jenis Eksekusi File

Tipe File

1

1

pohon.jpg (4.762.960 bytes)

Waktu Rata-Rata

Enkripsi Pipeline

Sekuensial 2

3

5

3.070

3.292

3.572

2.705

3.064

3.513

3.704

2.861

3.062

3.362

3.841

2.501

3.197

3.202

3.832

2.421

3.065

3.304

3.717

2.597

3.092

3.335

3.733

2.617

SpeedUp

0.927

0.828

1.181

Efisiensi

0.464

0.276

0.236

Cost

6.669

11.200

13.085

Overhead

3.577

8.108

9.993

Jenis Eksekusi File

Tipe File

1

2

lagu.flac (23.300.227 bytes)

Waktu Rata-Rata

Enkripsi Pipeline

Sekuensial 2

3

5

15.184

15.614

18.698

13.498

15.613

16.289

18.634

11.272

15.672

16.305

18.337

12.345

15.549

16.239

18.226

11.698

15.490

16.224

18.294

12.355

15.502

16.134

18.438

12.234

SpeedUp

0.961

0.841

1.267

Efisiensi

0.480

0.280

0.253

Cost

32.268

55.313

61.169

Overhead

16.766

39.811

45.667

Jenis Eksekusi File

Tipe File

1

3

Enkripsi Pipeline

Sekuensial 2

3

5

76.177

82.789

93.197

62.170

76.229

83.419

92.668

59.348

76.751

83.289

92.520

62.259

76.238

82.862

91.297

62.184

76.351

83.778

91.446

60.396

76.349

83.227

92.225

61.271

SpeedUp

0.917

0.828

1.246

Efisiensi

video.mp4 (118.522.028 bytes)

Waktu Rata-Rata

0.459

0.276

0.249

Cost

166.455

276.676

306.357

Overhead

90.106

200.327

230.008

44

Lampiran 11 Data hasil percobaan algoritme dekripsi AES pipeline Jenis Eksekusi File

Tipe File

1

1

pohon.chp (4.762.960 bytes)

Waktu Rata-Rata

Dekripsi Pipeline

Sekuensial 2

3

5

5.115

5.798

6.523

3.510

5.106

5.949

6.773

3.484

5.097

6.296

6.530

3.349

5.111

5.893

6.722

3.361

5.106

5.965

6.687

3.336

5.107

5.980

6.647

3.408

0.854

0.768

1.498

SpeedUp Efisiensi

0.427

0.256

0.300

Cost

11.960

19.941

17.041

Overhead

6.853

14.834

11.934

Jenis Eksekusi File

2

Tipe File

lagu.chp (23.300.227 bytes)

Waktu Rata-Rata

Dekripsi Pipeline

Sekuensial 1

2

3

5

25.010

30.589

33.663

16.317

25.938

30.523

32.718

17.388

25.229

30.241

34.664

16.281

25.550

29.571

34.184

16.272

25.647

30.447

33.394

16.255

25.475

30.274

33.724

16.503

SpeedUp

0.841

0.755

1.544

Efisiensi

0.421

0.252

0.309

Cost

60.548

101.173

82.513

Overhead

35.073

75.698

57.038

Jenis Eksekusi File

Tipe File

1

3

Dekripsi Pipeline

Sekuensial 2

3

5

127.129

147.072

166.296

82.992

127.174

146.597

167.077

83.703

127.329

148.462

166.662

82.770

127.280

145.313

172.100

84.027

127.220

147.131

168.309

83.160

127.227

146.915

168.089

83.330

SpeedUp

0.866

0.757

1.527

Efisiensi

video.chp (118.522.028 bytes)

Waktu Rata-Rata

0.433

0.252

0.305

Cost

293.830

504.267

416.652

Overhead

166.603

377.040

289.425