Design, Implementation and Evaluation of a New Variable Latency Integer Division Scheme
Open Access
- 8 April 2024
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 73 (7) , 1767-1779
Abstract
Integer division is key for various applications and often represents the performance bottleneck due to its inherent mathematical properties that limit its parallelization. This paper presents a new data-dependent variable latency division algorithm derived from the classic non-performing restoring method. The proposed technique exploits the relationship between the number of leading zeros in the divisor and in the partial remainder to dynamically detect and skip those iterations that result in a simple left shift. While a similar principle has been exploited in previous works, the proposed approach outperforms existing variable latency divider schemes in average latency and power consumption. We detail the algorithm and its implementation in four variants, offering versatility for the specific application requirements. For each variant, we report the average latency evaluated with different benchmarks, and we analyze the synthesis results for both FPGA and ASIC deployment, reporting clock speed, average execution time, hardware resources, and energy consumption, compared with existing fixed and variable latency dividers.Keywords
All Related Versions
This publication has 22 references indexed in Scilit:
- Design and Evaluation of Buffered Triple Modular Redundancy in Interleaved-Multi-Threading ProcessorsIEEE Access, 2022
- Review of Basic Classes of Dividers Based on Division AlgorithmIEEE Access, 2021
- A 32-bit Integer Division Algorithm Based on Priority Encoder2020
- Unsupervised K-Means Clustering AlgorithmIEEE Access, 2020
- Rethinking Integer Divider Design for FPGA-Based Soft-Processors2019
- An improvement in the restoring division algorithm (Needy Restoring Division Algorithm)2009
- LU-decomposition and numerical structure for solving large sparse nonsymmetric linear systemsComputers & Mathematics with Applications, 2002
- Design of synchronous and asynchronous variable-latency pipelined multipliersIEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2001
- Completion-detecting carry select additionIEE Proceedings - Computers and Digital Techniques, 2000
- Division algorithms and implementationsIEEE Transactions on Computers, 1997