Hardware Acceleration of Window Big-Digit (Wbd) Multiplication for Embedded Applications

Satu algoritma pendaraban baru yang bernama Digit Besar tetingkap (wBD) telah dicadangkan kebelakangan ini. Algoritma ini berasaskan sistem penomboran Digit Besar (BD) dan bersasarkan nombor besar yang beribu-ribu bit. Berat Hamming bagi sistem pernomboran wBD hanya n 4:6 berbanding dengan n2 bag...

Full description

Saved in:

Bibliographic Details
Main Author:	Lim, Ee Wah
Format:	Thesis
Language:	English
Published:	2015
Subjects:	T Technology TK7800-8360 Electronics
Online Access:	http://eprints.usm.my/40703/1/Hardware_Acceleration_of_Window_Big-Digit_%28Wbd%29_Multiplication_for_Embedded_Applications.pdf
Tags:	Add Tag No Tags, Be the first to tag this record!

id	my-usm-ep.40703
record_format	uketd_dc
spelling	my-usm-ep.407032018-06-06T06:48:32Z Hardware Acceleration of Window Big-Digit (Wbd) Multiplication for Embedded Applications 2015-08 Lim, Ee Wah T Technology TK7800-8360 Electronics Satu algoritma pendaraban baru yang bernama Digit Besar tetingkap (wBD) telah dicadangkan kebelakangan ini. Algoritma ini berasaskan sistem penomboran Digit Besar (BD) dan bersasarkan nombor besar yang beribu-ribu bit. Berat Hamming bagi sistem pernomboran wBD hanya n 4:6 berbanding dengan n2 bagi sistem binari, n 3 bagi nombor tanpa bersebelahan (NAF) dan n w+1 bagi NAF tetingkap (wNAF). Berat Hamming yang rendah bermaksud bilangan daraban separa yang rendah, yang mana akan mengurangkan bilangan langkah yang diperlukan dalam sesuate operasi pendaraban. Oleh itu, sistem pernomboran wBD dapat mempercepatkan proses pendaraban secara keseluruhan. Algoritma wBD telah dianalisis dan dibandingkan dengan kaedah pendaraban yang lain di tahap algoritma. Namun, belum ada karya yang mengenai pelaksanaan in peringkatan perkakasan diterbit. Untuk membolehkan penggunaan sistem penomboran wBD secara meluas dalam sistem terbenam, sesuatu rekabentuk sistem pengecutan pendarab wBD yang optimum telah diperkenalkan dalam kerja ini. Dalam kajian ini, satu sistem pengecutan pendarab wBD telah direka dengan menggunakan Verilog dan diprototaipkan dalam platform FPGA. Sistem pengecutan ini dilengkapi dengan port AXI dan disepadukan ke dalam sistem SoC yang berasaskan pemproses ARM bagi tujuan perbandingan. Pendaraban 256-bit dengan menggunakan sistem pengecut ini didapati adalah 340 kali ganda lebih cepat daripada pendaraban klasik yang dijalankan melalui teknik perisian. Ini menunjukkan bahawa sistem pendaraban wBD boleh dilaksanakan dengan optimumnya dalam peringkat perkakasan dan dapat mempercepatkan operasi pendaraban yang cuma berdasarkan perisian. ________________________________________________________________________________________________________________________ Window Big-Digit (wBD) is a recently proposed multiplication algorithm. This algorithm relies on Big-Digit (BD) numbering system and is targeting big integer with thousands bits. The hamming weight of wBD representation is only n 4:6 compared to n2 for binary, n 3 for Nonadjacent form (NAF) and to n w+1 for window-NAF (wNAF). Low hamming weight of multiplicand proportionately reduces the number of immediate partial products, which in turn will reduce the number of steps required in a multiplication function. Hence, wBD number system could be an excellent candidate to speed up overall multiplication process. The wBD algorithm has been analyzed and benchmarked against other multiplication methods in algorithmic level. However, there is no published works regarding hardware implementation of the algorithm yet. In order to enable boarder adoption of the wBD numbering system in resource constrained embedded systems, an optimized hardware accelerator design is introduced in this work. In this study, the hardware implementation of wBD multiplier is designed using Verilog and prototyped in FPGA platform. The accelerator is equipped with AXI interface and integrated into an ARM-based SoC system for benchmarking purpose. The test programs are The hardware-accelerated 256-bits multiplication is found that to be 340 fold faster than pure software implementation of classical multiplication. This shows that wBD algorithm can be optimally implemented in hardware and demonstrates excellent speed gain over pure software implementation. 2015-08 Thesis http://eprints.usm.my/40703/ http://eprints.usm.my/40703/1/Hardware_Acceleration_of_Window_Big-Digit_%28Wbd%29_Multiplication_for_Embedded_Applications.pdf application/pdf en public masters Universiti Sains Malaysia Pusat Pengajian Kejuruteraan Elektrik Dan Elektronik
institution	Universiti Sains Malaysia
collection	USM Institutional Repository
language	English
topic	T Technology TK7800-8360 Electronics
spellingShingle	T Technology TK7800-8360 Electronics Lim, Ee Wah Hardware Acceleration of Window Big-Digit (Wbd) Multiplication for Embedded Applications
description	Satu algoritma pendaraban baru yang bernama Digit Besar tetingkap (wBD) telah dicadangkan kebelakangan ini. Algoritma ini berasaskan sistem penomboran Digit Besar (BD) dan bersasarkan nombor besar yang beribu-ribu bit. Berat Hamming bagi sistem pernomboran wBD hanya n 4:6 berbanding dengan n2 bagi sistem binari, n 3 bagi nombor tanpa bersebelahan (NAF) dan n w+1 bagi NAF tetingkap (wNAF). Berat Hamming yang rendah bermaksud bilangan daraban separa yang rendah, yang mana akan mengurangkan bilangan langkah yang diperlukan dalam sesuate operasi pendaraban. Oleh itu, sistem pernomboran wBD dapat mempercepatkan proses pendaraban secara keseluruhan. Algoritma wBD telah dianalisis dan dibandingkan dengan kaedah pendaraban yang lain di tahap algoritma. Namun, belum ada karya yang mengenai pelaksanaan in peringkatan perkakasan diterbit. Untuk membolehkan penggunaan sistem penomboran wBD secara meluas dalam sistem terbenam, sesuatu rekabentuk sistem pengecutan pendarab wBD yang optimum telah diperkenalkan dalam kerja ini. Dalam kajian ini, satu sistem pengecutan pendarab wBD telah direka dengan menggunakan Verilog dan diprototaipkan dalam platform FPGA. Sistem pengecutan ini dilengkapi dengan port AXI dan disepadukan ke dalam sistem SoC yang berasaskan pemproses ARM bagi tujuan perbandingan. Pendaraban 256-bit dengan menggunakan sistem pengecut ini didapati adalah 340 kali ganda lebih cepat daripada pendaraban klasik yang dijalankan melalui teknik perisian. Ini menunjukkan bahawa sistem pendaraban wBD boleh dilaksanakan dengan optimumnya dalam peringkat perkakasan dan dapat mempercepatkan operasi pendaraban yang cuma berdasarkan perisian. ________________________________________________________________________________________________________________________ Window Big-Digit (wBD) is a recently proposed multiplication algorithm. This algorithm relies on Big-Digit (BD) numbering system and is targeting big integer with thousands bits. The hamming weight of wBD representation is only n 4:6 compared to n2 for binary, n 3 for Nonadjacent form (NAF) and to n w+1 for window-NAF (wNAF). Low hamming weight of multiplicand proportionately reduces the number of immediate partial products, which in turn will reduce the number of steps required in a multiplication function. Hence, wBD number system could be an excellent candidate to speed up overall multiplication process. The wBD algorithm has been analyzed and benchmarked against other multiplication methods in algorithmic level. However, there is no published works regarding hardware implementation of the algorithm yet. In order to enable boarder adoption of the wBD numbering system in resource constrained embedded systems, an optimized hardware accelerator design is introduced in this work. In this study, the hardware implementation of wBD multiplier is designed using Verilog and prototyped in FPGA platform. The accelerator is equipped with AXI interface and integrated into an ARM-based SoC system for benchmarking purpose. The test programs are The hardware-accelerated 256-bits multiplication is found that to be 340 fold faster than pure software implementation of classical multiplication. This shows that wBD algorithm can be optimally implemented in hardware and demonstrates excellent speed gain over pure software implementation.
format	Thesis
qualification_level	Master's degree
author	Lim, Ee Wah
author_facet	Lim, Ee Wah
author_sort	Lim, Ee Wah
title	Hardware Acceleration of Window Big-Digit (Wbd) Multiplication for Embedded Applications
title_short	Hardware Acceleration of Window Big-Digit (Wbd) Multiplication for Embedded Applications
title_full	Hardware Acceleration of Window Big-Digit (Wbd) Multiplication for Embedded Applications
title_fullStr	Hardware Acceleration of Window Big-Digit (Wbd) Multiplication for Embedded Applications
title_full_unstemmed	Hardware Acceleration of Window Big-Digit (Wbd) Multiplication for Embedded Applications
title_sort	hardware acceleration of window big-digit (wbd) multiplication for embedded applications
granting_institution	Universiti Sains Malaysia
granting_department	Pusat Pengajian Kejuruteraan Elektrik Dan Elektronik
publishDate	2015
url	http://eprints.usm.my/40703/1/Hardware_Acceleration_of_Window_Big-Digit_%28Wbd%29_Multiplication_for_Embedded_Applications.pdf
_version_	1747820806209011712

Hardware Acceleration of Window Big-Digit (Wbd) Multiplication for Embedded Applications

Similar Items