1. ACPS
  2. Всі випуски
  3. Випуск 9, Номер 1, 2024
  4. Digital Division Algorithms for Efficient Execution on Integrated Circuits

Digital Division Algorithms for Efficient Execution on Integrated Circuits

ACPS.
2024;
Випуск 9, Номер 1
: cc. 46 - 53
https://doi.org/10.23939/acps2024.01.046
Автори:
  1. Анатолій Обшта
  2. Володимир Васильович Хома
  3. Andrii Prokopchuk
1
Національний університет “Львівська політехніка”
2
Національний університет "Львівська політехніка", м. Львів, Україна
3
Lviv Polytechnic National University, Ukraine

In this paper, we analyse division algorithms for use on chips and propose the implementation of an optimal divider for these chips. By “optimal”, we refer to an algorithm that meets the following criteria: space efficiency – which involves minimizing resource utilization on the IC’s die area; speed efficiency – the algorithm's processing time (measured in n clock cycles); power efficiency – power consumption of the divider; implementation time – time for implementation of the algorithm using HDL. The chosen algorithm should strike a balance between space efficiency and processing speed, ensuring the efficient use of hardware resources while delivering swift computational results. The ultimate goal is to create a division module that aligns seamlessly with the integrated circuit's architecture, catering to computational efficiency and resource constraints.

ПЛІС
ASIC
Digital Divider
Digit Recurrence
Functional Iteration
  1.  Matthews E., Lu A., Fang Z., Shannon L., (2019). Rethinking integer divider design for FPGA-based soft-processors. IEEE 27th Annual International Sympo- sium on Field-Programmable Custom Computing Ma- chines,      pp.           289–297.DOI:https://doi.org/10.1109/FCCM.2019.00046
  2. Sanju Vikasini M.K., Kailath B.J., (2021). 16-bit Modified vedic paravartya divider with quotient in fractions. IEEE Region 10 Symposium, pp.1–5. DOI:https://doi.org/1 0.1109/TENSYMP52854.2021.9551013
  3. Han G., Zhang W., Niu L., Zhang C., Wang Z., (2022). Hardware   implementation   of   approximate   fixed-point divider for machine learning optimization algorithm. IEEE Asia Pacific Conference on Postgraduate Research in Mi- croelectronics and Electronics, pp.22–25. DOI:https:// doi.org/10.1109/PrimeAsia56064.2022.10104001
  4. Tynymbayev   S.,   Aitkhozhayeva   E.,   Berdibayev   R., Gnatyuk  S.,  Okhrimenko  T.,  Namazbayev  T.,  (2019). Development of modular reduction based on the divider by blocking negative remainders for critical cryptographic applications. IEEE 2nd Ukraine Conference on Electrical and Computer Engineering, pp.809–812. DOI:https://doi.org/10.1109/UKRCON.2019.8879846
  5. Purohit A.A., Ahmed M.R., Reddy R.V.S., (2020). Design of   area   optimized   arithmetic   and   logical   unit   for microcontroller.  IEEE  VLSI  DEVICE  CIRCUIT  AND SYSTEM, pp.335–339. DOI:https://doi.org/10.1109/ VLSIDCS47293.2020.9179942
  6. Patankar U.S., Flores M.E., Koel A., (2020). Division algorithms - from past to present chance to improve area time and complexity for digital applications. IEEE Latin America    Electron    Devices    Conference,    pp.    1–4.DOI:https://doi.org/10.1109/LAEDC49063.2020.9073050
  7. Patankar U.S., Flores M.E., Koel A., (2021). Study of estimation based functional iteration  approximation dividers. IEEE International Conference on Consumer Electronics, pp. 1–4.  DOI: https://doi.org/10.1109/ICCE50685.2021.9427657
  8. Patankar U.S., Flores M.E., Koel A., (2021). Review of basic classes of dividers based on division algorithm. IEEE Access, pp. 23035–23069.DOI:https://doi.org/10.1109/ACCESS.2021.3055735
  9. Liu Z., Song X., Wang Z., Wang Y., Zhou J., (2023). Constructing high radix quotient digit selection tables for SRT division and square root. IEEE Transactions on Computers, pp. 2111–2119.DOI:https://doi.org/10.1109/TC.2023.3235978
  10. Chouhan M., Raghuvanshi  A.S.,  Muchahary D., (2022). FPGA implementation  of high  performance  and  energy efficient Radix-4 based FFT. Asian Conference on Innova- tion in Technology, pp. 1–5. DOI:https://doi.org/10.1109/ ASIANCON55314.2022.9908613
  11. Lang T., Nannarelli A., (2007). A radix-10 digit-recurrence division unit: algorithm and architecture. IEEE Transac- tions on Computers, pp. 727–739.DOI:https://doi.org/10.1109/TC.2007.1038
  12. Vazquez A., Antelo E., Montuschi P., (2007). A radix-10 SRT divider based on alternative BCD codings. Interna- tional  Conference  on  Computer  Design,  pp.  280–287.DOI:https://doi.org/10.1109/ICCD.2007.4601914
  13. Mehta B., Talukdar J., Gajjar S., (2017). High speed SRT divider  for  intelligent  embedded  system.  International Conference on   Soft Computing and Its Engineering Ap- plications, pp. 1–5.  DOI:https://doi.org/10.1109/ ICSOFTCOMP.2017.8280077
  14. Jun K., Swartzlander E.E., (2012). Modified non-restoring division algorithm with improved delay profile and error correction.    Circuits,    Systems    and    Computers,    pp. 1460–1464. DOI: https://doi.org/10.1109/ ACSSC.2012.6489269
  15. Dixit S., Nadeem M., (2017). FPGA accomplishment of a 16-bit divider. Imperial Journal of Interdisciplinary Re- search,     pp. 40–143. Available at: https://www.researchgate.net/publication/360588032_FPG A_Accomplishment_of_a_16-Bit_Divider   (Accessed:  07November 2023).
  16. Narendra  K.,  Ahmed S., Kumar  S.,  Asha G.H., (2015). FPGA implementation of fixed point integer divider using iterative  array  structure.  International  Journal  of  Engi- neering and Technical Research, pp. 170–179. Available at: https://www.erpublication.org/published_paper/ JETR031914.pdf (Accessed: 07 November 2023).
  17. Patankar U.S., Flores M.E., Koel A., (2023). A. Novel data dependent divider circuit block implementation for complex division and area critical applications. Sci Rep 13, pp.1–27. DOI: https://doi.org/10.1038/s41598-023-28343-3
  18. Takagi N., Kadowaki S., Takagi K., (2005). A hardware algorithm for integer division. IEEE Symposium on Com- puter Arithmetic, pp. 140–146.DOI:https://doi.org/10.1109/ARITH.2005.6
  19. Han K., Tenca A., Tran D., (2009). High-speed float- ing-point divider with reduced area. The International So- ciety for Optical Engineering, pp. 1–8. Available at: https://www.researchgate.net/publication/253273653_High-speed_floating-point_divider_with_reduced_area       (Ac- cessed: 07 November 2023).
  20. Korol I., Korol I., (2019). Logical algorithms of the accelerated   multiplication   with   minimum   quantity   of nonzero digits of the converted multipliers. Advances in Cyber-Physical Systems,  pp 25–31.DOI:https://doi.org/10.23939/acps2019.01.025
  21. Ugurdag H.F., De Dinechin F., Gener Y.S., Gören S., Didier L.S., (2017). Hardware division by small integer constants. IEEE   Transactions   on   Computers,   pp.   2097–2110.DOI:https://doi.org/10.1109/TC.2017.2707488
  22. Mannatungal  K.S.,  Perera  M.D.R.,  (2016).  Performance evaluation of division algorithms in FPGA. Proceedings of the International  Research Conference  “Medical,  Allied Health, Basic and Applied Sciences”, pp. 84–88. Available at: http://ir.kdu.ac.lk/bitstream/handle/345/1170/ FAHS017.pdf?isAllowed=y&sequence=1   (Accessed: 07November 2023).