Design and Implementation of Slow and Fast Division Algorithms in Computer Architecture
Daniel Gunasekaran
Bengaluru, Karnataka
- 0 Collaborators
Computing division is more difficult than any other arithmetic operations like addition, subtraction, and multiplication. To expedite division and lower the number of clock cycles needed to complete the operation, fast division algorithms are necessary. ...learn more
Project status: Under Development
Intel Technologies
Intel FPGA
Overview / Usage
Computing division is more difficult than any other arithmetic operations like addition, subtraction, and multiplication. This is due to the complexity and ineffective parallelization of division algorithms in general. Division is an iterative algorithm where the result corresponding to the quotient must be shifted to the remainder utilizing a Euclidean measure. This makes it challenging to parallelize the process because intermediate results of one phase are used as inputs to the following step. On the contrary, multiplication can be accelerated by breaking it down into a series of bit manipulation techniques. To expedite division and lower the number of clock cycles needed to complete the operation, fast division algorithms are necessary. This is crucial since division is a frequently utilized operation in a variety of computing tasks, and cutting down on the time needed to conduct division can greatly enhance a system's overall performance.
Methodology / Approach
By subtracting the divisor from the partial remainder and restoring it if the result is negative, the slow division process known as "restoring division" provides one digit of the quotient every iteration. Although it is easy to create, it has a large latency and needs many cycles for each digit. Lookup table division is a quick division method that produces the quotient by performing two multiplication operations on a tiny lookup table. It has a Taylor series expansion foundation and has a two-cycle accuracy limit. Although it uses less hardware than restoring division, the table's memory footprint is higher.
As predicted the Fast division algorithm takes significantly less time as compared to the slow division Although the method used here is highly space consuming it requires more memory while executing in real time i.e., it will be blocking more Random-access memory for computing a division algorithm This is why we need less space consuming fast division Algorithms Combining the advantages of both restoring division and lookup table division in a hybrid approach could potentially reduce the latency and memory usage while maintaining accuracy and flexibility. By switching between the two algorithms depending on the input size and precision requirements, the hybrid approach could provide an efficient solution for a wide range of division problems.
Technologies Used
FPGA
Verilog Programming