Email this article On the implementation of QR-decomposition on a three-dimensional systolic array
- Authors: Babenko V.N.1, Nevecherya A.P.2
-
Affiliations:
- Kuban State Technological University
- Kuban State University
- Issue: Vol 16, No 1 (2025)
- Pages: 45-59
- Section: Articles
- URL: https://bakhtiniada.ru/2079-3316/article/view/299218
- DOI: https://doi.org/10.25209/2079-3316-2025-16-1-45-59
- ID: 299218
Cite item
Full Text
Abstract
Intensive data flows, formed systems of linear equations in real time, as well as systems of linear equations of large dimensionality cause the involvement of systolic arrays for their machine solution. In the presented systolic array, designed to reduce matrices to triangular form, the realization of orthogonal rotation transformations can be carried out both by two-dimensional vector rotation devices CORDIC, and its modifications. For the proposed systolic array, descriptions of its configuration, operation and technical characteristics, as well as the structure of input and output data flow are given.
About the authors
Viktor Nikolaevich Babenko
Kuban State Technological University
Email: rnibvd@mail.ru
PhD, Associate Professor, Department of General Mathematics, Kuban State Technological University. Research interests: numerical methods.
Artyom Pavlovich Nevecherya
Kuban State University
Email: artiom1989@mail.ru
Senior Lecturer at the Department of Mathematical and Computer Methods, Kuban State University. Research interests: mathematical modeling of dynamics of non-closed complex systems, extreme problems, artificial intelligence systems.
References
- Елфимова Л. Д. «Быстрые алгоритмы для базовой операции клеточных методов линейной алгебры», Кибернетика и системный анализ, 51:6 (2015), с. 35–45.
- Горюшкина А. Е., Семенов С. Г. «Применение систолической системы на основе метода моментов для усовершенствования дискретного преобразования Хартли», Збірник наукових праць Харківського університету Повітряних Сил, 2016, №1(46), с. 89–91.
- Azimian A., Dehkordi A. K., Tehrani M. „A novel systolic array architecture for matrix multiplication circuit design using carbon nanotube technology“, International Journal of Computer Applications, 172:6 (2017), pp. 1–4.
- Causapruno G., Riente F., Turvani G., Vacca M., Massimo R. R., Zamboni M., Graziano M. „Reconfigurable systolic array: from architecture to physical design for NML“, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 24:11 (2016), pp. 3208–3217.
- Randjelovic B. M., Milovanovic E. I., Milovanovic I. Z. „Systolic algorithms for matrix multiplication on space optimal one-dimensional systolic arrays“, Facta Universitatis (Nis). Series: Mathematics and Informatics, 29:3 (2014), pp. 243–259.
- Abdollahi M. M., Tehrani M. „Designing a novel reversible systolic array using QCA“, Italian Journal of Science & Engineering, 1:3 (2017), pp. 158–166.
- Воеводин В. В. Математические модели и методы в параллельных процессах, Наука, М., 1986, 296 с.
- Бабенко В. Н., Ивановский О. Я., Тимонов Д. А. «Систолическая структура обратного хода метода Гаусса и ее основные свойства», Экологический вестник научных центров Черноморского экономического сотрудничества, 15:1 (2018), с. 8–14.
- С. Гун, Х. Уайтхаус, Т. Кайлат (ред.). Сверхбольшие интегральные схемы и современная обработка сигналов, Радио и связь, М., 1989, ISBN 5-256-00179-5, 472 с.
- Бабенко В. Н. Устройство вращения вектора, 11 с.
- Бабенко В. Н. Устройство нормировки вектора, 7 с.
- Бабенко В. Н. «Алгоритм инверсии делителя», Экологический вестник научных центров Черноморского экономического сотрудничества, 10:4-1 (2013), с. 19–25.
- Бабенко В. Н. Аспекты машинного решения систем линейных уравнений, Экоинвест, Краснодар, 2020, ISBN 978-5-94215-531-5, 307 с.
- Мальцев А. А., Пестрецов В. А., Хоряев А. В., Масленников Р. О. «Метод QR-разложения комплексной матрицы с помощью треугольного систолического массива», Сборник научных трудов „Проблемы разработки перспективных микроэлектронных систем‟ (9–12 октября 2006 г.), ред. А. Л. Стемпковский, ИППМ РАН, М., 2006, с. 91–96.
- Тыртышников Е. Е. «Параллельные методы для обобщенно-тёплицевых систем», Журнал вычислительной математики и математической физики, 36:6 (1996), с. 5–19.
- Xiaojun W., Miriam L. „A truly two-dimensional systolic array FPGA implementation of QR decomposition“, ACM Transactions on Embedded Computing Systems, 9:1 (2009), 3, 17 pp.
- Jianfeng Z., Paul C., Hengzhu L. „CORDIC-based enhanced systolic array architecture for QR decomposition“, ACM Transactions on Embedded Computing Systems, 9:2 (2015), 9, 22 pp.
- Semih A., Sufeng N., Jafar S. „FPGA implementation of fast QR decomposition based on givens rotation“, 2012 IEEE 55th International Midwest Symposium on Circuits and Systems (MWSCAS) (05–08 August 2012, Boise, ID, USA), IEEE, 2012, ISBN 9781467325264, pp. 470–473.
- Dongdong C., Mihai S. „Fixed-point CORDIC-based QR decomposition by givens rotations on FPGA“, 2011 International Conference on Reconfigurable Computing and FPGAs (30 November 2011 – 02 December 2011, Cancun, Mexico), IEEE, 2012, ISBN 978-0-7695-4551-6, pp. 327-332.
- Григорьев В. Р. Методы параллельной цифровой обработки информации в трехмерных оптических интегральных схемах, М., 2005, 231 с.
- Yamazaki I., Kurzak J., Luszczek P., Dongarra J. „Design and implementation of a large scale tree-based QR decomposition using a 3D virtual systolic array and a lightweight runtime“, Parallel Processing Letters, 24:04 (2014), 1442004.
- Paolo G., Christian P. High level synthesis implementation of a three-dimensional systolic array architecture for matrix multiplications on Intel Stratix 10 FPGAs, 2021, 9 pp.
Supplementary files
