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

• المؤلف الرئيسي: Lim, Ee Wah
• التنسيق: أطروحة
• اللغة: الإنجليزية
• منشور في: 2015
• الموضوعات: T Technology; TK7800-8360 Electronics
• الوصول للمادة أونلاين: http://eprints.usm.my/40703/

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.