IMPLEMENTASI FAST MULTIPLIER TRACHTENBERG METODE DUA JARI DENGAN BAHASA PEMROGRAMAN PERANGKAT KERAS VHDL Arnold Aribowo, ST., MT dan Thomas"
Abstract The processor is a very important part of the computer hardware components, which affects the whole system performance. Part of the processor's component, which performs the arithmetic and logic-related processes, is called Arithmetic/Logic Unit (ALU). One of this arithmetic processes is multiplication. The faster the processor accomplishes this process, the faster the computer system performs the data processing, especially related with arithmetic processes. To accelerate the speed of the multiplication process in the processor, the hardware implementation of fast multiplication method is needed. One of that methods, which is discussed in this paper, is Trachtenberg method. The hardware implementation of Trachtenberg method can be implemented with Very High Speed Integrated Circuit Hardware Description Language (VHDL). This paper focuses the discussion on the hardware implementation of the Trachtenberg Fast Multiplier by using VHDL. The number being multiplied and the multiplier are limited to 4 digits in size. The trachtenberg method discussed in this paper is limited to the Two Finger Method Trachtenberg. Then, the system is called as Two Finger Method Trachtenberg Fast Multiplier.
PENDAHULUAN Prosesor adalah salah satu bagian dari sistem komputer yang bertugas untuk melakukan pengolahan data. Salah satu bagian dari Prosesor yang bertugas untuk melakukan proses perhitungan, logika dan perbandingan adalah Arithmetic/Logic Unit (ALU). Salah satu proses perhitungan yang dilakukan adalah proses perkalian (multiplication). Semakin cepat prosesor melakukan multiply, maka semakin cepat proses pengolahan data pada sistem komputer yang berhubungan dengan proses aritmatika. Untuk dapat meningkatkan kecepatan proses perkalian yang dilakukan oleh prosesor, maka diperlukan metode perkalian cepat yang diimplementasikan pada prosesor. Metode perkalian cepat tersebut dapat diimplementasikan dengan melakukan pemrograman prosessor menggunakan bahasa pemrograman perangkat keras. Salah satu metode perkalian cepat yang banyak digunakan adalah metode Trachtenberg.
Jurusan Teknik Komputer, Universitas Pelita Harapan, Jakarta (
[email protected]) Jurusan Teknik Elektro, Universitas Tarumanagara, Jakarta (
[email protected]) Vol.7, No.1. April 2004
Implementasi Fast Multiplier ...
75
Metode cepat matematika dasar Trachtenberg ini sering juga disebut 'stenografi matematika". Metode ini hanya memerlukan kemampuan menghitung dari satu sampai sebelas, meniadakan pembagian panjang seperti yang dikenal, dan menghilangkan daftar perkalian. Berdasarkan sejumlah langkah yang sederhana, metode ini mudah dikuasai dan memberikan keuntungan berupa kecepatan lebih besar, kemudahan dalam menangani bilangan, dan ketepatan yang makin meningkat. Perhitungan matematika dapat diselesaikan dalam waktu kurang dari 30 persen dari biasanya, dan metode dengan sistem pengecekan cepat ini menjamin 99 persen dalam ketepatannya. Dalam kegunaannya, seperti dinyatakan pada suatu majalah pendidikan, "sistem kilat matematika dasar ini dapat membuat tiap orang dewasa biasa menjadi kalkulator yang sangat terampil, cepat, dan tepat" [8]. Untuk menghasilkan rancangan yang dapat dipakai ulang [reuse) maka pemrograman prosessor berdasarkan metode Trachtenberg dilakukan menggunakan bahasa pemrograman perangkat keras VHDL. Metode Trachtenberg yang diterapkan hanya metode dua jari saja, dan bilangan yang dikalikan maksimum terdiri dari 4 digit. Secara keseluruhan, sistem yang dibangun disebut Fast Multiplier Metode Trachtenberg Dua Jari. Paper ini diawali dengan pembahasan singkat tentang metode perkalian cepat Trachtenberg dua jari pada bagian 2. Implementasi sistem dibahas pada bagian 3. Kesimpulan paper ini akan disampaikan pada bagian 4.
METODE PERKALIAN CEPAT TRACHTENBERG DUA JARI Metode perkalian cepat Trachtenberg dikemukakan pertama kali oleh Jakow Trachtenberg, pendiri Institut Matematika di Zurich, Swiss. Metode ini tidak hanya cepat, tetapi juga sederhana. Metode ini berdasarkan prosedur yang berbeda dengan metode konvensional yang biasa dipelajari dan menghilangkan daftar perkalian panjang. Walaupun berdasarkan pada sederetan langkah yang memang hams dihafal pada awalnya, tetapi apabila sudah dikuasai, perhitungan dapat dikerjakan dengan sangat cepat [8]. Metode perkalian cepat Trachtenberg dapat dibagi kedalam 2 metode, yaitu metode langsung dan metode dua jari. Metode Trachtenberg yang dibahas pada paper ini adalah metode dua jari saja. Pada metode ini akan digunakan istilah satuan dan puluhan. Apabila bilangan yang terdiri dari satu digit dikalikan dengan bilangan lain yang terdiri dari satu digit, maka bilangan terbesar yang merupakan hasil perkalian keduanya adalah 8 1 , yang merupakan hasil dari 9 dikalikan dengan 9. Hasil perkalian tersebut terdiri dari dua angka sehingga bisa dipisahkan kedalam bagian satuan dan puluhan. Apabila perkalian keduanya menghasilkan bilangan yang terdiri dari satu digit, misalnya 6, maka hasil perkalian tersebut dapat dituliskan menjadi 06, sehingga terdiri dari bagian satuan dan 76
Implementasi Fast Multiplier ...
Vol.7, No. 1, April 2004
puluhan juga. Pada metode ini, dikenal istilah satuan dan puluhan, dimana pada suatu hasil perkalian pada proses tertentu, yang diambil hanya satuannya saja, kemudian pada hasil perkalian selanjutnya yang diambil hanya puluhannya saja. Selanjutnya, angka satuan dan puluhan yang diperoleh dari proses sebelumnya dijumlahkan. Misalnya pada perkalian 38 dengan 4, dapat dilakukan dengan beberapa langkah berikut ini :
Langkah I: Digit 8 pada bilangan pertama dikalikan dengan bilangan kedua, yaitu 4, hasilnya adalah 32. Dari hasil tersebut hanya diambil puluhannya saja, yaitu 3. Digit 3 pada bilangan pertama dikalikan dengan dengan bilangan kedua, yaitu 4, hasilnya adalah 12. Dari hasil tersebut hanya diambil satuannya saja, yaitu 2.
Langkah II: Hasil yang hanya diambil satuannya dan puluhannya, yaitu 3 dan 2 dijumlahkan sehingga menghasilkan bilangan 5. Bilangan ini akan menjadi digit kedua, dimana digit pertama adalah bagian puluhan dari bilangan yang diambil satuannya (12), yaitu 1. Sedangkan digit ketiga adalah bagian satuan dari bilangan yang diambil puluhannya (32), yaitu 2. Hasil perhitungannya adalah 152. Secara keseluruhan proses perhitungannya dapat digambarkan dengan cara berikut i n i : S
P
3
8
x
4
12 3 2 2+3 5
IPLEMENTASI FAST MULTIPLIER METODE TRACHTENBERG DUA JARI Berdasarkan metode trachtenberg dua jari yang telah diuraikan sebelumnya pada bagian 2, maka dapat dirancang arsitektur dari Fast Multiplier Trachtenberg metode dua jari. Arsitektur Fast Multiplier Trachtenberg metode dua jari yang disimbolkan seperti pada Gambar 1 mempunyai masukan bilangan a sebanyak 4 digit dikali dengan bilangan b sebanyak 4 digit yang menghasilkan keluaran bilangan q sebanyak 8 digit.
Vol.7. No.l, April 2004
Implementasi Fast Multiplier ...
11
duajari7 e l k a l [ 4 .
q±E - 1 3
4 - - 1 3
q 2 C 4 .
- 1 3
a2C
4 . - 1 3
q 3 C 4 . - 1 3
»3C
4 . - 1 3
q 4 [ 4 .
a4[
4 . -1 3
q5[
4 - -1 3
blC
4 - . 1 3
q6C
4 - - 1 3
b2[
4 . - 1 3
q 7 [ 4 .
- 1 3
b3C
4 . -1 3
qB[4.
- 1 3
b4[
4 . -1 3
-1 3
EC
SC Gambar 1. Simbol Fast Multiplier Trachtenberg metode dua jari Masing-masing digit disimbolkan dengan bilangan biner 4 bit. Jadi persamaannya adalah q8q7q6q5q4q3q2ql = b4b3b2bl x a4a3a2al. Clk merupakan masukan clock untuk sinkronisasi, masukan SC adalah masukan untuk memulai komputasi, sedangkan keluaran EC adalah keluaran yang menandakan selesainya komputasi. Penjabaran arsitektur tersebut tidak dijelaskan secara detail karena paper ini akan lebih menitikberatkan pada implementasi arsitektur. Pembuatan Fast Multiplier Trachtenberg dilakukan secara modular, yaitu dengan terlebih dahulu merancang arsitekturnya, kemudian dilanjutkan perancangan modul-modul pendukungnya, dan akhirnya setelah semua modul-modul pendukung telah dirancang dan diuji maka tahapan berikutnya adalah melakukan integrasi semua modul-modul tersebut menjadi suatu Fast Multiplier Trachtenberg yang utuh. Berikut ini akan dijelaskan pembuatan Fast Multiplier Trachtenberg metode dua jari. Fast Multiplier Trachtenberg metode dua jari ini dibuat dengan nama berkas duajari7.vhd. Berkas ini menggunakan modul-modul yang telah dibuat sebelumnya yaitu: multiply47.vhd, reg7bit.vhd, b2d7bit.vhd dan reg4bit.vhd. Multiply47.vhd dipakai untuk melakukan perkalian 1 digit, reg7bit dipakai untuk menyimpan data-data sementara, b2d7bit dipakai untuk memisahkan puluhan dan satuan, sedangkan reg4bit dipakai untuk menyimpan bilangan masukan pada waktu proses loading data. Fast Multiplier Trachtenberg metode dua jari ini merupakan rangkaian sekuensial sinkron terhadap elk dengan 8 buah state. Nama-nama state yang digunakan adalah s i , s2, s3, s4, s5, s6, s7 dan s8. 78
Implementasi fast Multiplier ...
Vol.7, No.1, April 2004
Pada state s i , chip melakukan loading data yaitu mengambil masing-masing bilangan a4, a3, a2, a l , b4, b3, b2, b l yang kemudian masing-masing disimpan di register 4 bit ra4, ra3, ra2, ra2 , rb4, rb3, rb2, rbl bila ada sinyal masukan SC( Start Computation) berlogika 1. Setelah selesai melakukan loading data, chip ini pindah ke state s2. Pada state s2, chip ini mulai melakukan komputasi untuk menghasilkan keluaran q l yaitu: 1. Melakukan perkalian ral dengan r b l , hasil perkalian satuan merupakan q l yang disimpan sementara di register r q l , sedangkan hasil perkalian puluhan disimpan sementara di register r l untuk dipakai untuk komputasi pada state berikutnya. 2. Melakukan perkalian ral dengan rb2, hasil perkalian satuan disimpan sementara di r2, sedangkan hasil perkalian puluhan disimpan sementara di register r3 untuk dipakai pada komputasi berikutnya. 3. Melakukan perkalian ra2 dengan r b l , hasil perkalian satuan disimpan sementara di r4, sedangkan hasil perkalian puluhan disimpan sementara di register r5 untuk dipakai pada komputasi berikutnya. 4. Pindah ke state s3.
Pada state s3, chip ini melakukan komputasi lanjutan untuk menghasilkan keluaran q2 yaitu: 1. Melakukan penjumlahan hasil simpanan pada register r2, r4 dan r l yang hasil satuannya merupakan q2 yang disimpan sementara di register rq2, sedangkan hasil puluhannya disimpan sementara di register pq untuk dipakai pada komputasi di state berikutnya. 2. Melakukan perkalian ral dengan rb3, perkalian ra2 dengan rb2 dan perkalian ra3 dengan rbl. 3. Bagian satuan dan puluhan hasil perkalian ral dengan rb3 masing-masing disimpan pada register r2 dan r4 untuk dipakai untuk komputasi pada state berikutnya. 4. Bagian satuan dan puluhan hasil perkalian ra2 dengan rb2 masing-masing disimpan pada register r l dan r6 untuk dipakai untuk komputasi pada state berikutnya. 5. Bagian satuan dan puluhan hasil perkalian ra3 dengan rbl masing-masing disimpan pada register r7 dan r8 untuk dipakai untuk komputasi pada state berikutnya. 6. Pindah ke state s4.
Vol.7. No.1, April 2004
Implementasi Fast Multiplier ...
79
Pada state s4, chip ini melakukan komputasi lanjutan untuk menghasilkan keluaran q3 yaitu: 1. Melakukan penjumlahan hasil simpanan pada register r2, r l , r7, pq, r3 dan r5 yang hasil satuannya merupakan q3 yang disimpan sementara di register rq3, sedangkan hasil puluhannya disimpan sementara di register pq untuk dipakai pada komputasi di state berikutnya. 2. Melakukan perkalian ral dengan rb4, perkalian ra2 dengan rb3 , perkalian ra3 dengan rb2 dan perkalian ra4 dengan r b l . 3. Bagian satuan dan puluhan hasil perkalian ral dengan rb4 masing-masing disimpan pada register r2 dan r l untuk dipakai untuk komputasi pada state berikutnya. 4. Bagian satuan dan puluhan hasil perkalian ra2 dengan rb3 masing-masing disimpan pada register xl dan r3 untuk dipakai untuk komputasi pada state berikutnya. 5. Bagian satuan dan puluhan hasil perkalian ra3 dengan rb2 masing-masing disimpan pada register r5 dan r9 untuk dipakai untuk komputasi pada state berikutnya. 6. Bagian satuan dan puluhan hasil perkalian ra4 dengan rbl masing-masing disimpan pada register rlO dan r l l untuk dipakai untuk komputasi pada state berikutnya. 7. Pindah ke state s5.
Pada state s5, chip ini melakukan komputasi lanjutan untuk menghasilkan keluaran q4 yaitu: 1. Melakukan penjumlahan hasil simpanan pada register r2, r7, r5, rlO, r4, r6, r8 dan pq yang hasil satuannya merupakan q4 yang disimpan sementara di register rq4, sedangkan hasil puluhannya disimpan sementara di register pq untuk dipakai pada komputasi di state berikutnya. 2. Melakukan perkalian ra2 dengan rb4, perkalian ra3 dengan rb3 dan perkalian ra4 dengan rb2. 3. Bagian satuan dan puluhan hasil perkalian ra2 dengan rb4 masing-masing disimpan pada register r2 dan r7 untuk dipakai untuk komputasi pada state berikutnya. 4. Bagian satuan dan puluhan hasil perkalian ra3 dengan rb3 masing-masing disimpan pada register r5 dan rlO untuk dipakai untuk komputasi pada state berikutnya.
80
Implementasi Fast Multiplier ...
Vol.7, No.1, April 2004
5. Bagian satuan dan puluhan hasil perkalian ra4 dengan rb2 masing-masing disimpan pada register r4 dan r6 untuk dipakai untuk komputasi pada state berikutnya. 6. Pindah ke state s6.
Pada state s6, chip ini melakukan komputasi lanjutan untuk menghasilkan keluaran q5 yaitu: 1. Melakukan penjumlahan hasil simpanan pada register r2, r5, r4, r l , r3, r9, r l l dan pq yang hasil satuannya merupakan q5 yang disimpan sementara di register rq5f sedangkan hasil puluhannya disimpan sementara di register pq untuk dipakai pada komputasi di state berikutnya. 2. Melakukan perkalian ra3 dengan rb4 dan perkalian ra4 dengan rb3. 3. Bagian satuan dan puluhan hasil perkalian ra3 dengan rb4 masing-masing disimpan pada register r2 dan r5 untuk dipakai untuk komputasi pada state berikutnya. 4. Bagian satuan dan puluhan hasil perkalian ra4 dengan rb3 masing-masing disimpan pada register r4 dan r l untuk dipakai untuk komputasi pada state berikutnya. 5. Pindah ke state s7.
Pada state s7, chip ini melakukan komputasi lanjutan untuk menghasilkan keluaran q6 yaitu: 1. Melakukan penjumlahan hasil simpanan pada register r2, r4, r7, rlO, r6 dan pq yang hasil satuannya merupakan q6 yang disimpan sementara di register rq6, sedangkan hasil puluhannya disimpan sementara di register pq untuk dipakai pada komputasi di state berikutnya. 2. Melakukan perkalian ra4 dengan rb4. 3. Bagian satuan dan puluhan hasil perkalian ra4 dengan rb4 masing-masing disimpan pada register r2 dan r4 untuk dipakai untuk komputasi pada state berikutnya. 4. Pindah ke state s8.
Pada state s8, chip ini melakukan komputasi lanjutan untuk menghasilkan keluaran q7 dan q8 yaitu: 1. Melakukan penjumlahan hasil simpanan pada register r2, r5, r l dan pq yang hasil satuannya merupakan q7 yang disimpan sementara di register rq7,
Vol.7, No. I.April 2004
Implementasi Fast Multiplier ...
81
sedangkan hasil puluhannya dijumlahkan dengan isi menghasilkan q8 yang disimpan sementara di register rq8.
register
r4
yang
2. Pindah ke state s i .
Setelah komputasi selesai, maka data pada register r q l sampai rq8 dikeluarkan ke keluaran q l sampai q8.
KESIMPULAN Paper ini telah membahas perancangan Fasr Multiplier Metode Trachtenberg Dua Jari dengan menggunakan Bahasa Pemrograman Perangkat Keras VHDL. Perancangan Fast Multiplier dapat meningkatkan kecepatan proses pengolahan data pada sistem komputer yang berhubungan dengan proses aritmatika. Sistem yang telah dibuat ini dapat dikembangkan dengan mengimplementasikan proses-proses aritmatika lain, diantaranya adalah pembagian berdasarkan Metode Trachtenberg, untuk melakukan pemrograman prosessor menggunakan bahasa VHDL.
PUSTAKA [1] Altera Corporation, 1998. Digital Library. Altera Corporation. [2] Ashenden Peter J., 1996. The Designer's Guide to VHDL. Morgan Kaufmann Publishers. [3] Green David, 1986. Modern Logic Design, addison Wesley. [4] Nelson V.P., Nagle H.T., Irwin D.J., Carroll B. D., 1995. Digital Logic Circuit Analysis and Design. Prentice Hall. [5] Pellerin David, Taylor Douglas, 1997. VHDL Made Easy!, Prentice Hall. 6] Salcic Zoran, Semailagic Asim, 1997. Digital Systems Design and Prototyping using Field Programmable Logic. Kluwer academic Publisher. [7] Skalhill Kevin, 1996. VHDL for Programmable Logic. Addison Wesley. [8] Soeparmo, 1990. Sistem Kilat Matematika Dasar Metode Trachtenberg. PT Rosta Jayaputra. [9] Tinder Richard F.,1991. Digital engineering Design, A Modern Approach. Prentice Hall.
82
Implementasi Fast Multiplier ...
Vol.7, No. I.April 2004
