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


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

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

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