FlexKA: A Flexible Karatsuba Multiplier Hardware Architecture for Variable-Sized Large Integers
The Karatsuba algorithm is an effective way to accelerate large integer multiplications through recursive function calls. However, existing hardware implementations of Karatsuba multipliers are limited to fixed operand sizes. To enable their application in diverse domains, including homomorphic encr...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2023-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/10143627/ |
| _version_ | 1797808505660375040 |
|---|---|
| author | Byeongmin Kang Hyungmin Cho |
| author_facet | Byeongmin Kang Hyungmin Cho |
| author_sort | Byeongmin Kang |
| collection | DOAJ |
| description | The Karatsuba algorithm is an effective way to accelerate large integer multiplications through recursive function calls. However, existing hardware implementations of Karatsuba multipliers are limited to fixed operand sizes. To enable their application in diverse domains, including homomorphic encryption with varying multiplicative depths, it is necessary to support variable operand sizes. In this paper, we propose a novel Karatsuba multiplier design, named FlexKA, which supports variable operand sizes through a state machine that manages the dynamic call states of the operation. We evaluate FlexKA on the Xilinx ZynqMP FPGA and demonstrate that it supports variable operand sizes up to 256K bits, achieving a <inline-formula> <tex-math notation="LaTeX">$9.2\times$ </tex-math></inline-formula> speedup compared to a highly-optimized software library running on a CPU. Our results show that FlexKA is an efficient and effective solution for large integer multiplications with flexible operand sizes in hardware. |
| first_indexed | 2024-03-13T06:38:32Z |
| format | Article |
| id | doaj.art-dee4f005bd3b467ab713e54c16840d7d |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-03-13T06:38:32Z |
| publishDate | 2023-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-dee4f005bd3b467ab713e54c16840d7d2023-06-08T23:01:31ZengIEEEIEEE Access2169-35362023-01-0111552125522210.1109/ACCESS.2023.328264610143627FlexKA: A Flexible Karatsuba Multiplier Hardware Architecture for Variable-Sized Large IntegersByeongmin Kang0https://orcid.org/0000-0003-1106-9196Hyungmin Cho1https://orcid.org/0000-0001-8705-7066Department of Computer Science and Engineering, Sungkyunkwan University, Suwon, South KoreaDepartment of Computer Science and Engineering, Sungkyunkwan University, Suwon, South KoreaThe Karatsuba algorithm is an effective way to accelerate large integer multiplications through recursive function calls. However, existing hardware implementations of Karatsuba multipliers are limited to fixed operand sizes. To enable their application in diverse domains, including homomorphic encryption with varying multiplicative depths, it is necessary to support variable operand sizes. In this paper, we propose a novel Karatsuba multiplier design, named FlexKA, which supports variable operand sizes through a state machine that manages the dynamic call states of the operation. We evaluate FlexKA on the Xilinx ZynqMP FPGA and demonstrate that it supports variable operand sizes up to 256K bits, achieving a <inline-formula> <tex-math notation="LaTeX">$9.2\times$ </tex-math></inline-formula> speedup compared to a highly-optimized software library running on a CPU. Our results show that FlexKA is an efficient and effective solution for large integer multiplications with flexible operand sizes in hardware.https://ieeexplore.ieee.org/document/10143627/Multiplying circuitsfield programmable gate arrays |
| spellingShingle | Byeongmin Kang Hyungmin Cho FlexKA: A Flexible Karatsuba Multiplier Hardware Architecture for Variable-Sized Large Integers IEEE Access Multiplying circuits field programmable gate arrays |
| title | FlexKA: A Flexible Karatsuba Multiplier Hardware Architecture for Variable-Sized Large Integers |
| title_full | FlexKA: A Flexible Karatsuba Multiplier Hardware Architecture for Variable-Sized Large Integers |
| title_fullStr | FlexKA: A Flexible Karatsuba Multiplier Hardware Architecture for Variable-Sized Large Integers |
| title_full_unstemmed | FlexKA: A Flexible Karatsuba Multiplier Hardware Architecture for Variable-Sized Large Integers |
| title_short | FlexKA: A Flexible Karatsuba Multiplier Hardware Architecture for Variable-Sized Large Integers |
| title_sort | flexka a flexible karatsuba multiplier hardware architecture for variable sized large integers |
| topic | Multiplying circuits field programmable gate arrays |
| url | https://ieeexplore.ieee.org/document/10143627/ |
| work_keys_str_mv | AT byeongminkang flexkaaflexiblekaratsubamultiplierhardwarearchitectureforvariablesizedlargeintegers AT hyungmincho flexkaaflexiblekaratsubamultiplierhardwarearchitectureforvariablesizedlargeintegers |