METHOD FOR INCREASING THE EFFICIENCY OF SOLVING TRIDIAGONAL SLE IN A REDUNDANT NUMBER SYSTEM ON FPGA
Keywords:
FPGA, increasing performance, online mode, reducing hardware costs, tridiagonal matricesAbstract
The article considers a new approach to the hardware implementation of the run method for tridiagonal SLEs using a non-autonomous computational mode and a redundant number system. A computing module architecture and a modified algorithm have been developed, providing acceleration of more than three times compared to the classical approach. The effectiveness of the proposed method for systems of different dimensions has been experimentally confirmed.
References
Bajard J., Kla S., Muller J. BKM: A new hardware algorithm for complex elementary functions. IEEE Transactions on Computers. 1994. Vol. 43, no. 8. P. 955–963.
Butler J. T., Sasao T. Redundant multiple-valued number systems. Japan research group on multiple-valued logic : Proceedings, Sendai, 28 July 1997. Monterey, 1997. P. 141–148.
Dychka I., Zhabin V., Zhabina V. Analysis of on-line computation effectiveness in redundant number system. 2018 IEEE first international conference on system analysis & intelligent computing (SAIC). 2018. P. 1–6. URL: https://doi.org/10.1109/SAIC.2018.8516877.
Ercegovac M. D., Muller J.-M. Arithmetic Processor for Solving Tridiagonal Systems of Linear Equations. 2006 Fortieth Asilomar Conference on Signals, Systems and Computers, Pacific Grove, CA, USA, 29 October – 1 November 2006. 2006. URL: https://doi.org/10.1109/acssc.2006.354763 (date of access: 11.05.2025).
Ercegovac M. D. On-line arithmetic: An overview. SPIE's 28th annual technical symposium. international society for optics and photonics : Proceedings, San Diego, 28 November 1984. Los Angeles, 1984. P. 86–93.
Floating-Point FPGA Gaussian Elimination in Reconfigurable Computing System / Z. Bowei et al. Chinese Journal of Electronics. 2011. Vol. 20, no. 1. P. 51–54. URL: https://cje.ejournal.org.cn/en/article/id/5546 (date of access: 01.05.2024).
Lang T., Ercegovac M. D. Digital arithmetic. Elsevier Science & Technology Books, 2003. 709 p.
Meng H., Wakabayashi K., Kuroda T. A Scalable Linear Equation Solver FPGA using High-Level Synthesis. The 24th Workshop on Synthesis And System Integration of Mixed Information Technologies (SASIMI 2022) : Proceedings, Hirosaki, 24–25 October 2022. Taipei City, 2022. P. 145–150. URL: https://sasimi.jp/new/sasimi2022/files/archive/pdf/p145_B-7.pdf (date of access: 01.05.2024).
Perera S. M., Bebiano N. A Low-cost and Numerically Stable Algorithm to Solve Tridiagonal Systems via Quasiseparable Matrices. ResearchSquare. 2023. P. 1–22. URL: https://doi.org/10.21203/rs.3.rs-3200350/v1 (date of access: 11.05.2025).
Piñeiro J., Ercegovac M. D., Bruguera J. D. Algorithm and Architecture for Logarithm, Exponential, and Powering Computation. IEEE Transactions on Computers. 2004. Vol. 53, no. 9. P. 1085–1096.
Prykladna teoriia tsyfrovykh avtomativ: Navchalnyi posibnyk / V. I. Zhabin ta in. Kyiv : Knyzhk. vyd-vo NAU, 2007. 364 s.
Strukturnyi sposib shvydkoho vyrishennia system rivnian alhebry z trydiahonalnoiu matrytseiu / V. I. Zhabin ta in. 1979. S. 1–11.
Verbovskyi I., Zhabin V. Improving the efficiency of functions computation in on-line mode on FPGA. The International Conference on Security, Fault Tolerance, Intelligence ICSFTI2022 : proceedings of the International Conference ICSFTI2022, Kyiv, 30 June 2022. Kyiv, 2022. P. 1–8. URL: https://icsfti-proc.kpi.ua/article/view/281001 (date of access: 01.06.2024).
Zhabin V. I., Korneǐchuk V. I., Tarasenko V. P. Computation of rational functions for many arguments. Automation and Remote Control. 1978. Vol. 38, no. 12. P. 1864–1871.
Zhabin V., Zhabina V., Verba O. Asynchronous on-line float-point computations in systems with direct connections between computation units. IEEE 2nd international conference on system analysis & intelligent computing : Proceedings, Kyiv, 5–9 October 2020. Kyiv, 2020. P. 1–5.
Zhabyn V. Y., Korneichuk V. Y., Tarasenko V. P. Some machine methods for computing rational functions of many arguments. Automation and Telemechanics. 1977. T. 38, № 12. S. 145–154.
