Method for On-line Acceleration of Dependent Operation Chains Using Redundant Code on FPGA with System of Linear Equations Example
DOI:
https://doi.org/10.20535/2786-8729.6.2025.333919Keywords:
FPGA, on-line computing, digit-by-digit processing, tridiagonal systems, redundant number systemsAbstract
This study examines methods for accelerating the execution of dependent operation chains in on-line mode through parallel processing of operands at the bit level in redundant code on field-programmable gate arrays (FPGA). The object of research is the hardware implementation of the Thomas algorithm for solving systems of linear equations with tridiagonal matrices on FPGA platforms. The aim is to develop a method for accelerating dependent operation chains in on-line mode using redundant code with minimization of pin count requirements. The methodology employs algorithmic analysis, hardware modeling using Active HDL, performance evaluation based on timing characteristics and resource utilization on Altera Cyclone III EP3C5E144 platform, with verification performed using Quartus.
The results reveal bottlenecks in traditional FPGA implementations of the Thomas algorithm and demonstrate that the proposed optimized method provides over threefold performance improvement while maintaining constant pin count regardless of operand bit depth. The developed computing module architecture enables bit-wise parallel data processing and supports a modified version of the Thomas algorithm adapted for on-line operation. The scientific novelty lies in combining redundant code with on-line computation techniques to simultaneously achieve computational acceleration and hardware implementation simplification. The practical value is determined by the applicability of the proposed approach to resource-constrained FPGA platforms, ensuring efficient implementation of computationally intensive algorithms with dependent operation chains.
References
V. S. Ryaben'kii and S. V. Tsynkov, "Introduction," in A Theoretical Introduction to Numerical Analysis, Chapman Hall/CRC, 2006, pp. 1–19. https://doi.org/10.1201/9781420011166-1.
J. Piñeiro, M. D. Ercegovac, and J. D. Bruguera, "Algorithm and architecture for logarithm, exponential, and powering computation," IEEE Trans. Comput., vol. 53, no. 9, pp. 1085–1096, Sep. 2004. https://doi.org/10.1109/TC.2004.53.
I. Dychka, V. Zhabin, and V. Zhabina, "Analysis of on-line computation effectiveness in redundant number system," in Proc. IEEE First Int. Conf. System Anal. & Intell. Comput. (SAIC), 2018, pp. 1–6. https://doi.org/10.1109/SAIC.2018.8516877.
J. Bajard, S. Kla, and J. Muller, "BKM: A new hardware algorithm for complex elementary functions," IEEE Trans. Comput., vol. 43, no. 8, pp. 955–963, Aug. 1994. https://doi.org/10.1109/12.295857.
S. Mousavi, D. Rahmati, S. Gorgin, and A. Lee, "Enhancing efficiency in computational intensive domains via redundant residue number systems," in Proc. 21st Int. SoC Des. Conf. (ISOCC), Sapporo, Japan, Aug. 19–22, 2024, pp. 330–331. https://doi.org/10.1109/isocc62682.2024.10762680.
S. R. Sahu, B. K. Bhoi, and M. Pradhan, "Improved redundant binary adder realization in FPGA," J. Circuits Syst. Comput., vol. 30, no. 8, pp. 2150287-1–2150287-23, Jun. 2021. https://doi.org/10.1142/s021812662150287x.
Y. Zhang, "An FPGA implementation of redundant residue number system for low-cost fast speed fault-tolerant computations," M.Eng. thesis, Nanyang Technol. Univ., Singapore, 2018. https://doi.org/10.32657/10220/47113.
H. Meng, K. Wakabayashi, and T. Kuroda, "A scalable linear equation solver FPGA using high-level synthesis," in Proc. 24th Workshop Synthesis System Integration Mixed Inf. Technol. (SASIMI), Taipei, Taiwan, 2022, pp. 145–150. [Online]. Available: https://sasimi.jp/new/sasimi2022/files/archive/pdf/p145_B-7.pdf. Accessed: May 1, 2025.
S. M. Perera and N. Bebiano, "A low-cost and numerically stable algorithm to solve tridiagonal systems via quasiseparable matrices," Research Square, pp. 1–22, Aug. 2023. https://doi.org/10.21203/rs.3.rs-3200350/v1.
M. D. Ercegovac and M. Muller, “Arithmetic processor for solving tridiagonal systems of linear equations,” in Proc. 40th Asilomar Conf. Signals Syst. Comput., Pacific Grove, CA, USA, Oct. 29–Nov. 1, 2006, pp. 337–340. https://doi.org/10.1109/acssc.2006.354763.
V. I. Zhabin, V. I. Korneǐchuk, and V. P. Tarasenko, “Computation of rational functions for many arguments,” Autom. Remote Control, vol. 38, no. 12, pp. 1864–1871, 1978.
J. T. Butler and T. Sasao, “Redundant multiple-valued number systems,” Naval Postgraduate School, Monterey, CA, USA, Tech. Rep., 1997. [Online]. Available: http://pi.314159.ru/butler1.pdf. Accessed: Aug. 1, 2025.
V. I. Zhabin, I. A. Zhukov, I. A. Klymenko, and V. V. Tkachenko, Prykladna teoriia tsyfrovykh avtomativ: Navchalnyi posibnyk, 2nd ed. Kyiv: NAU, 2009. [Online]. Available: https://comsys.kpi.ua/wp-content/uploads/2025/02/prykladna-teoriya-tsyfrovykh-avtomativ.pdf. Accessed: Aug. 1, 2025.
V. Y. Zhabyn, V. Y. Korneichuk, and V. P. Tarasenko, “Some machine methods for computing rational functions of many arguments,” Autom. Telemechanics, vol. 38, no. 12, pp. 145–154, 1977.
K. Kamalakkannan, G. R. Mudalige, I. Z. Reguly, and S. A. Fahmy, “High throughput multidimensional tridiagonal system solvers on FPGAs,” in Proc. Int. Conf. Supercomput., Virtual Event, 2022, pp. 1–13. https://doi.org/10.1145/3524059.3532371.
H. J. Macintosh, J. E. Banks, and N. A. Kelson, “Implementing and evaluating an heterogeneous, scalable, tridiagonal linear system solver with opencl to target fpgas, gpus, and cpus,” Int. J. Reconfigurable Comput., vol. 2019, pp. 1–13, Oct. 2019. https://doi.org/10.1155/2019/3679839.
T. Kuo and C. Wu, “FPGA implementation of a novel multifunction modulo (2n ± 1) multiplier using radix-4 booth encoding scheme,” Appl. Sci., vol. 13, no. 18, pp. 1–12, Sep. 2023, Art. no. 10407. Accessed: Aug. 16, 2025. [Online]. Available: https://doi.org/10.3390/app131810407.
I. Verbovskyi and V. Zhabin, “Improving the efficiency of functions computation in on-line mode on FPGA,” in Proc. Int. Conf. Secur. Fault Tolerance Intell., Kyiv, Ukraine, 2022, pp. 1–8. Accessed: Aug. 1, 2025. [Online]. Available: https://icsfti-proc.kpi.ua/article/view/281001.
V. Zhabin, V. Zhabina, and O. Verba, "Asynchronous on-line float-point computations in systems with direct connections between computation units,” in Proc. IEEE 2nd Int. Conf. System Anal. & Intell. Comput., 2019, pp. 1–5.
V. I. Zhabin, V. I. Korneichuk, V. P. Tarasenko, and A. A. Shcherbyna, “Strukturnyi sposib shvydkoho vyrishennia system rivnian alhebry z trydiahonalnoiu matrytseiu,” Tech. Rep., Feb. 1979.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 Information, Computing and Intelligent systems
This work is licensed under a Creative Commons Attribution 4.0 International License.
