On the implementation of QR-decomposition on a three-dimensional systolic array

Cover Page

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

  1. Елфимова Л. Д. «Быстрые алгоритмы для базовой операции клеточных методов линейной алгебры», Кибернетика и системный анализ, 51:6 (2015), с. 35–45.
  2. Горюшкина А. Е., Семенов С. Г. «Применение систолической системы на основе метода моментов для усовершенствования дискретного преобразования Хартли», Збірник наукових праць Харківського університету Повітряних Сил, 2016, №1(46), с. 89–91.
  3. 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.
  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.
  5. 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.
  6. Abdollahi M. M., Tehrani M. „Designing a novel reversible systolic array using QCA“, Italian Journal of Science & Engineering, 1:3 (2017), pp. 158–166.
  7. Воеводин В. В. Математические модели и методы в параллельных процессах, Наука, М., 1986, 296 с.
  8. Бабенко В. Н., Ивановский О. Я., Тимонов Д. А. «Систолическая структура обратного хода метода Гаусса и ее основные свойства», Экологический вестник научных центров Черноморского экономического сотрудничества, 15:1 (2018), с. 8–14.
  9. С. Гун, Х. Уайтхаус, Т. Кайлат (ред.). Сверхбольшие интегральные схемы и современная обработка сигналов, Радио и связь, М., 1989, ISBN 5-256-00179-5, 472 с.
  10. Бабенко В. Н. Устройство вращения вектора, 11 с.
  11. Бабенко В. Н. Устройство нормировки вектора, 7 с.
  12. Бабенко В. Н. «Алгоритм инверсии делителя», Экологический вестник научных центров Черноморского экономического сотрудничества, 10:4-1 (2013), с. 19–25.
  13. Бабенко В. Н. Аспекты машинного решения систем линейных уравнений, Экоинвест, Краснодар, 2020, ISBN 978-5-94215-531-5, 307 с.
  14. Мальцев А. А., Пестрецов В. А., Хоряев А. В., Масленников Р. О. «Метод QR-разложения комплексной матрицы с помощью треугольного систолического массива», Сборник научных трудов „Проблемы разработки перспективных микроэлектронных систем‟ (9–12 октября 2006 г.), ред. А. Л. Стемпковский, ИППМ РАН, М., 2006, с. 91–96.
  15. Тыртышников Е. Е. «Параллельные методы для обобщенно-тёплицевых систем», Журнал вычислительной математики и математической физики, 36:6 (1996), с. 5–19.
  16. 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.
  17. 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.
  18. 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.
  19. 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.
  20. Григорьев В. Р. Методы параллельной цифровой обработки информации в трехмерных оптических интегральных схемах, М., 2005, 231 с.
  21. 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.
  22. 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

Supplementary Files
Action
1. JATS XML
Download


Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

Согласие на обработку персональных данных

 

Используя сайт https://journals.rcsi.science, я (далее – «Пользователь» или «Субъект персональных данных») даю согласие на обработку персональных данных на этом сайте (текст Согласия) и на обработку персональных данных с помощью сервиса «Яндекс.Метрика» (текст Согласия).