Oleh : Andrizal ABSTRACT

ISSN:2085-6989

ANALISIS KEHANDALAN ALGORITMA PERKALIAN PARALLEL BRAUN ARRAY MULTIPLIER UNTUK OPERASI PERKALIAN WAKTU NYATA (Analysis Mainstay Algorithm Multiplication Of Parallel Braun Array of Multiplier For The Operation Of Multiplication of Real Time) Oleh : Andrizal Jurusan Teknik Elektro Politeknik Negeri Padang Kampus Limau Manis Padang 25163 Telp 0751-72590 Fax 0752-72576 E-mail : [email protected]

ABSTRACT Real-time system (RTS) accurately entails the speedy accuracy process. To comply with the performance of the real time of the spedd process, a processor or refiner used to require a strategy of algorithm in executing the process. A problem will arise when the data processed are not yet settled whereas the deadline provided to processing is restricted. Consequently, the data, which are generated, cannot be made use of the system to process after wards and cause automatically the system fail or the performance deceases. This research investigated the ability of the parallel processing multiplication of the Braun Array Multiplier in conforming to the speed process toward the multiplication of theunlabelled numbers in a restricted deadline. To recognize the ability of the algorithm, it is carried out a ratio with series of mathematical steps or multiplication algorithm by means of applying the simulation of VHDL programming language. This simulation indicates the result of timing diagram which can be analyzed through algorithm process speed respectively. The result, found through the algorithm of Braun Array Multiplier, acquired the process speed which was much better then compared with serial algorithm. This research is expected to prove and authenticate that the Braun Array Multiplier can be made use of Real Time System Application. Keywords: Multiplier, Real-Time System, Deadline.

PENDAHULUAN

memproses data. Banyak usaha yang dilakukan dalam memenuhi kriteria

Sistem waktu-nyata merupakan sistem komputer yang berkaitan erat dengan peryaratan waktu-tenggat (deadline). Sistem ini memerlukan proses yang cepat, respons tepat waktu dan akurasi hasil yang sebaik-baiknya [Alan 2002, Bruce 1999]. Sistem dikatakan berhasil jika respon yang dihasilkan masih dalam batas nilai toleransi yang diterima dan dalam waktu tidak melampaui deadline walaupun waktu yang tersedia untuk sistem tidak cukup lagi untuk

proses sistem waktu-nyata antara lain menggunakan teknik: scheduling, parallelism, data reduction, data compression, dan preprocessing. Usaha-usaha diatas mengacu kepada tersedianya hasil dari proses saat dibutuhkan sesuai dengan deadline dan dengan pencapaian nilai akurasi yang masih berada dalam nilai yang bisa ditoleransi.

Elektron: Vol 2 No. 1, Edisi: Juni 2010 |

77

ISSN:2085-6989 Terdapat beberapa prilaku parameter Task dalam memproses seperti gambar 1 [Andrizal, tesis 2005] : ta

td

Tp

t

ta + Tp ≤ td

(a) Proses ideal dan memenuhi kriteria waktu nyata ta

ta’

dly y

td

Tp

t

Tp

ta + Tp >td

’

(b) Proses yang tidak ideal akibat keterlambatan ta kriteria sistem waktu nyata tidak terpenuhi

ta

td’

Tp Tp’

ta + Tp >td

td t

TPercepatan

(c) Proses yang tidak ideal akibat waktu td dipercepat kriteria sistem waktu nyata tidak terpenuhi

ta’ ta dly

td’

Tp Tp’

td t

TPercepatan

ta + Tp >td (d) Proses yang tidak ideal akibat waktu kedatangan ta terlambat dan td dipercepat kriteria sistem waktu nyata tidak terpenuhi

Gambar 1. Prilaku parameter proses. Metoda pemrosesan perkalian meliputi : sistem bit-serial, sistem serial-parallel dan sistem parallel [Smit 1999]. Sistem perkalian bit-serial telah diterapkan dalam beberapa algoritma yang ada seperti :Shift-and-add multiplier sedangkan untuk algoritma perkalian 78

parallel juga terdapat beberapa algoritma salah satunya adalah Braun Array multiplier. Unit perkalian shift-and-add, proses perkalian dimulai dari Least Significant Bit (LSB) dilanjutkan sampai Most Significant Bit (MSB) pada bit multiplier. Secara umum laju perubahan nilai akurasi terlihat pada contoh perkalian seperti pada tabel 1, karena proses perkalian dimulai dari LSB sehingga laju akurasi mulai dengan nilai akurasi yang rendah diawal dan maksimum berada pada iterasi terakhir. Untuk mendapatkan akurasi maksimum dibutuhkan 4 iterasi untuk proses perkalian 4 bit dan seterusnya akan membutuhkan N kali iterasi untuk perkalian N bit. Dengan demikian apabila algoritma ini digunakan untuk aplikasi perkalian waktu nyata jika waktu proses yang tersedia tidak cukup atau terpaksa dihentikan karena waktu kedatangan (ta), dan atau waktu-tenggat Td tidak sesuai lagi dengan karakteristik ideal, akan menyebabkan waktu sistem tidak cukup memproses data sampai selesai sehingga sistem bisa gagal. Hal ini disebabkan nilai akurasi hasil proses yang didapat belum terpenuhi pada iterasi yang terbatas. Jadi apabila algoritma ini digunakan untuk aplikasi waktu nyata, tentu tidak dapat memuhi kriteria kinerja yang diiginkan apabila terjadi sistem terpaksa memberikan respon pada saat nilai akurasi yang belum cukup. Cara yang paling tepat digunakan adalah dengan cara mengolah data secara parallel atau serentak, walaupun proses terpaksa dihentikan atau waktu proses sudah habis, maka iterasi yang ada sudah mencukupi untuk mendapatkan hasil maksimum. Penelitian ini bertujuan untuk menganalisa kemampuan pencapaian | Elektron: Vol 2 No. 1, Edisi: Juni 2010

ISSN:2085-6989 hasil operasi dalam 1 kali iterasi untuk proses perkalian secara parallel. Rancangan ini masih memiliki batasan yaitu hanya digunakan maksimum untuk perkalian 8 bit bilangan tidak bertanda. Hasil yang diharapkan adalah dengan adanya penggunaan metoda perkalian parallel, didapatkan hasil akurasi yang sesuai dengan kebutuhan perkalian waktu nyata walaupun waktu iterasi yang terbatas.

(LSB First). Arsitektur rangkaian terlihat pada Gambar 2. Keluaran bit dari multiplexer (MUX) akan di AND dengan bit-bit multiplicand, hasilnya disimpan diregister dan digeser (shift) sebanyak iterasi proses.

Unit perkalian shift-and-add, melakukan proses perkalian dimulai dari bit LSB dilanjutkan sampai MSB multiplier Tabel 1. Proses perkalian 4 bit (10102 x 10102) algoritma Shift And Add Iterasi Bit Multiplier Bit multiplicand Hasil 0 0 1010 00002 1 1 1010 10100 2 0 1010 101000 3 1 1010 1100100

Akurasi (%) 0 20 40 100

Gambar 2. Arsitektur unit perkalian Serial shift-and-add. Hasil operasi ini dijumlahkan dengan isi akumulator dan di simpan kembali di akumulator. Proses ini di ulangi untuk setiap bit multiplier sampai bit MSB, dan hasil akhir perkalian terdapat di akumulator. Algoritma dapat digambarkan dalam bentuk pseudo-code berikut ini : Elektron: Vol 2 No. 1, Edisi: Juni 2010 |

Register B Multiplier, Register A multiplicand, jumlah bit data n bit, Semua data terdapat diregister for (i=0; i<=n; i++) {

Bufer[0…k]←B[i] AND A[0…k]; Y[0…j] ← Bufer [0…k] Sll [i]; 79

ISSN:2085-6989 Acc[0...j] ←Acc[0...j] + Y[0...j]; } Pada algoritma ini nilai hasil ditentukan pada pengolahan data di register B yang diatur melalui sebuah multiplexer dimana pengaturan bit-bit multiplexer dimulai dari LSB, maka komputasi akan mulai dari bit-bit yang tidak berpengaruh significant terhadap hasil. METODOLOGI PENELITIAN Waktu proses (Tp) dalam sistem komputer dapat dibuat fleksibel (diperkecil) melalui penggunaan unit aritmatika yang dapat dihentikan prosesnya setiap saat dan hasilnya dapat digunakan. Hasil yang didapat haruslah memiliki nilai akurasi yang terbaik. Hal ini dapat dilakukan dengan cara pengolahan data secepat mungkin dangan hasil proses maksimal. Dengan demikian rancangan sistem perkalian waktu nyata harus memiliki sifat-sifat : a. Hasil proses maksimal walaupun waktu proses terbatas. b. Untuk mendapatkan hasil maksimal dilakukan secepat mungkin maksimal 1 siklus iterasi dengan cara parallel. Konsep dengan cara melakukan proses secara parallel dan hanya membutuhkan maksimal 1 siklus iterasi untuk meyelelesaikan proses walaupun jumlah bit data yang diproses semakin banyak. Hal ini sangat dibutuhkan ketika terjadi perubahan lingkungan yang menyebabkan proses terpaksa dihentikan karena deadline sudah datang atau waktu proses menjadi lebih singkat. Sistem semacam ini tentu bermanfaat digunakan dalam proses real- time yang mengalami perubahan waktu proses.

80

HASIL PENELITIAN Konsep dasar perkalian parallel algoritma Braun Array terlatak pada iterasi yang dibutuhkan, Hasil proses didapat hanaya dengan 1 kali siklus iterasi. Hasil proses yang didapat sesuai dengan kebutuhan system waktu nyata yang dibatasi dengan deadline. Untuk Uji coba dan simulasi rancangan sistem digunakan perangkat lunak Altera MaxPluss II Baseline 10.2, sehingga dapat dianalisis kemampuan algoritma ini. Arsitektur ini diperlihatkan pada Gambar 3. Kombinasi full adder dirangkai membentuk fungsi perkalian dengan algoritma Braun array multiplier. Secara sederhana Gambar 3 memperlihatkan rangkaian Braun array multiplier. Dari gambar 3 terlihat, input adalah a(0) … a(3) dan b(0)…b(3), sedangkan output adalah P(0)…P(7). Persamaan output P adalah ;  m−1 n −1  m −1   n −1 P = AxB =  ∑ ai 2 i  x ∑ b j 2 j  = ∑∑ (ai xb j )2 i 2 j  i =0   j =0  i = 0 j =0

Maka, p0 = a0 .b0 P1 = a1 .b0 + a0 .b1 + c P2 = a 2 .b0 + a1 .b1 + a0 .b2 + c P3 = a3 .b0 + a 2 .b1 + a1 .b2 + a0 .b3 + c P4 = a 4 .b0 + a3 .b1 + a 2 .b2 + a1 .b3 + a0 .b4 + c P5 = a5 .b0 + a 4 .b1 + a3 .b2 + a 2 .b3 + a1 .b4 + a0 .b5 + c P6 = a6 .b0 + a5 .b1 + a 4 .b2 + a3 .b3 + a 2 .b4 + a1 .b5 + a0 .b6 + c P7 = a7 .b0 + a 6 .b1 + a5 .b2 + a 4 .b3 + a3 .b4 + a 2 .b6 + a1 .b5 + a0 .b7 + c

Untuk mendapatkan perkalian dengan jumlah input 8 bit, rangkaian diatas dikembangkan menjadi rangkaian dengan jumlah input 8 bit dengan autput 16 atau lebih bit. | Elektron: Vol 2 No. 1, Edisi: Juni 2010

ISSN:2085-6989

Gambar 3. Arsitektur perkalian 4 bit parallel Braun Array multiplier. Secara keseluruhan rangkain menggabungkan fungsi gerbang AND di setiap input full adder, dan dengan kombinasi carry save adder didapat fungsi perkalian secara parallel. Persamaan output dari rangkaian perkalian 8 bit Braun Array multiplier yang dirancang adalah sebagai berikut :

p 0 = a 0 .b0 P1 = a1 .b0 + a 0 .b1 + c P2 = a 2 .b0 + a1 .b1 + a 0 .b2 + c P3 = a3 .b0 + a 2 .b1 + a1 .b2 + a 0 .b3 + c P4 = a 4 .b0 + a3 .b1 + a 2 .b2 + a1 .b3 + a0 .b4 + c P5 = a5 .b0 + a 4 .b1 + a3 .b2 + a 2 .b3 + a1.b4 + a 0 .b5 + c P6 = a 6 .b0 + a5 .b1 + a 4 .b2 + a3 .b3 + a 2 .b4 + a1.b5 + a0 .b6 + c P7 = a7 .b0 + a6 .b1 + a5 .b2 + a 4 .b3 + a3 .b4 + a 2 .b6 + a1 .b5 + a 0 .b7 + c P8 = a 7 .b1 + a6 .b2 + a5 .b3 + a 4 .b4 + a3 .b6 + a 2 .b5 + a1 .b7 + c P9 = a7 .b2 + a 6 .b3 + a5 .b4 + a 4 .b5 + a3 .b6 + a 2 .b7 + c P10 = a7 .b3 + a 6 .b4 + a5 .b5 + a 4 .b6 + a3 .b7 + c P11 = a7 .b4 + a6 .b5 + a5 .b6 + a 4 .b7 + c P12 = a7 .b5 + a6 .b6 + a5 .b7 + c P13 = a7 .b6 + a6 .b7 + c P14 = a7 .b7 + c P15 = c

P0 – P15 merupakan sum dari hasil sum of product masing-masing bit dan hasil dari perkalian. Hasil ini didapat hanya dalam 1 siklus proses dan tidak tergantung kepada jumlah bit multipiler yang diproses. Dengan demikian hasil proses maksimal didapat jauh lebih cepat dibandingkan dengan sistem perkalian serial. Hasil simulasi proses perkalian parallel algoritma Braun Array dapat dilihat pada gambar 4-8.

Elektron: Vol 2 No. 1, Edisi: Juni 2010 |

81

ISSN:2085-6989

Gambar .Diagram waktu terburuk proses perkalian serial 250 x 250, hasil selesai pada 8 siklus iterasi dengan waktu proses 1,846 us.

Gambar 5.Diagram waktu terbaik proses perkalian serial 1 x 250, hasil selesai pada 1 siklus iterasi dengan waktu proses 77,7 ns.

Gambar 6. Diagram waktu perkalian parallel Braun Array 5x4 diselesaikan 50 ns kurang 1 siklus iterasi (200 ns). 82

| Elektron: Vol 2 No. 1, Edisi: Juni 2010

ISSN:2085-6989

Gambar 7. Diagram waktu perkalian parallel Braun Array 9x20 diselesaikan 64 ns kurang 1 siklus iterasi (200 ns).

Gambar 8. Diagram waktu perkalian parallel Braun Array 12x20 diselesaikan 63 ns kurang 1 siklus iterasi (200 ns).

Gambar 9. Diagram waktu perkalian parallel Braun Array 15x12 diselesaikan 60,6 ns kurang 1 siklus iterasi (200 ns). Elektron: Vol 2 No. 1, Edisi: Juni 2010 |

83

ISSN:2085-6989

Gambar 10. Diagram waktu perkalian parallel Braun Array 18x11 diselesaikan 74,4 ns kurang 1 siklus iterasi (200 ns).

Gambar 11. Diagram waktu perkalian parallel Braun Array 4x20 diselesaikan 59 ns kurang 1 siklus iterasi (200 ns). PEMBAHASAN Bilangan multiplier dan multiplicand yang diuji adalah bilangan desimal 8 bit tidak bertanda. Hasil simulasi berbentuk grafik dan kinerja ditinjau dari percepatan waktu proses. Dalam pengujian ini dilakukan perbandingan kedua algoritma metoda serial dan algoritma metoda parallel. Setiap algoritma akan diberi kasus perhitungan terbaik dan terburuk, serta sejumlah perkalian terhadap sejumlah data acak.

84

Metoda Parallel

Metoda Serial

Gambar 12. Perbandingan laju akurasi hasil proses kedua metoda. | Elektron: Vol 2 No. 1, Edisi: Juni 2010

ISSN:2085-6989 Pada Gambar 12 memperlihatkan laju akurasi hasil proses untuk kedua algoritma yang didapat dari beberapa simulasi terhadap sejumlah perkalian bit yang dilakukan terhadap kedua algoritma. Hasil yang didapat terlihat hasil akurasi nilai proses yang dihasilkan oleh masing-masing proses. Nilai akurasi metoda serial 100% jika iterasi sudah maksimal 8 siklus. Sementara algoritma perkalian metoda parallel Braun Array Multiplier menghasilkan akurasi proses 100% kurang dari 1 siklus iterasi. Jadi nilai akurasi algoritma perkalian parallel Braun Array lebih baik dibandingkan dengan algoritma perkalian serial shift-and-add. Dimana data yang dihasilkan dapat memenuhi kriteria untuk penggunaan perkalian waktu nyata dalam menghadapi kasus dimana waktu proses yang tersedia tidak mencukupi untuk sejumlah siklus yang dibutuhkan atau waktu proses yang diperpendek.

SIMPULAN Berdasarkan data dan analisis yang diperoleh pada penelitian ini, dapat diambil kesimpulan sebagai berikut : 1. Algoritma perkalian parallel Braun Array mampu mendapatkan nilai akurasi proses 100% maksimal hanya 1 siklus iterasi, walaupun jumlah bit multiplier yang digunakan maksimal dan tidak tergantung jumlah bit multiplier. 2. Kompleksitas rangkaian algoritma parallel Braun Array Multiplier lebih kompleks dibandingkan dengan algoritma serial Shift AndADD. 3. Hasil penelitian ini sangat menguntungkan dalam meningkatkan kinerja sistem waktu-nyata, yaitu tersedianya Elektron: Vol 2 No. 1, Edisi: Juni 2010 |

hasil proses yang dapat diakses setiap saat dengan akurasi yang terbaik jika waktu proses terpaksa diperpendek atau dihentikan.

DAFTAR PUSTAKA Andrizal. 2005, Perancangan unit aritmatika perkalian waktu nyata algoritma Shift-And-ADD metoda MSB-P1, tesis, ITB. Andrizal.2009, Kehandalan metoda MSB-P1 algiritma Shift-And-ADD Pada Operasi Perkalian waktu nyata, Poli Rekayasa,Volume 4. Alan C. Shaw.2002,Real-Time Systems and Software, John Wiley & Sons. Bruce powel Douglass 1999, Doing Hard Time: Developing Real-Time Systems with UML, Objects, Frameworks, and Patterns, Addison Wesley Hassan Gomna, 2000, Designing Concurren, Distributed, and Real time Applications With UML, Addison_Wesley Pub Co, Kuspriyanto, Kerlooza, Y.Y.2004. Toward New Real-Time Processor : The Multioperand MSB-First RealTime Adder, Proceedings of DSD’2004 Euromicro Symposium on Digital System Design, RennesFrance, IEEE Computer Society. Kuspriyanto,Kerlooza,Y.Y.2004 Keandalan Unit Multioperand MSBFirst Realtime Adder Pada Operasi Penjumlahan Data Acak, Proceeding SITIA 2004, Seminar on Inteligent Technology and Its Applications, Surabaya, May 18th. Levi, S.T., Agrawala, A.K.1990. RealTime System Design, McGraw-Hill. Russ Miller and Laurence Boxer, 2000 Algorithms Seduential and parallel: A Unified Approach, I/e, Prentice_Hall, 85

ISSN:2085-6989 Skahill K. 1996. VHDL for Programmable Logic, Addison Wesley. Smith, D.J. 1999. HDL Chip Design, Done Publication.

86

| Elektron: Vol 2 No. 1, Edisi: Juni 2010