Нижегородский государственный университет им. Н.И. Лобачевского: Разработка бенчмарка для LU-разложения плотных матриц

Разработчик: Симонов Максим Вячеславович

Описание задачи:

Ключевые задачи:

  • Написание блочного алгоритма LU-разложения и его оптимизация (правильный обход памяти, подбор размера блока и т.д.);
  • Исследование эффективности алгоритма при выполнении на процессорах архитектуры x86_64;
  • Исследование эффективности алгоритма при выполнении на процессорах архитектуры RISC-V;
  • Исследование работоспособности и эффективности алгоритма на микроконтроллере К1921ВГ1Т;
  • Сравнение эффективности реализации с существующими аналогами.

Технические и иные требования:

  • Настройка UART для трансляции stdin/stdout с отладочной платы микроконтроллера на ПК с использованием программы PuTTY;
  • Настройка аппаратного генератора случайных чисел TRNG для генерации случайных матриц;
  • Максимальная экономия оперативной памяти ввиду ограниченного объема последней.

Ключевые особенности реализации:

  1. Используемый микроконтроллер:
    • К1921ВГ1Т
  2. Алгоритмы/программное обеспечение:
    • Написан блочный алгоритм LU-разложения, оптимизированный для параллельного выполнения на процессорах архитектуры RISC-V, а также однопоточная программа без ОС для использования написанного алгоритма на отладочной плате микроконтроллера К1921ВГ1Т.
    • Инструменты: Syntacore IDE; OpenOCD (прошивка и отладка); компиляторы: riscv-none-elf-gcc-15.2.0-1 для .elf файла прошивки, Intel oneAPI DPC++/C++ Compiler 2023.0.0 для тестирования алгоритма на x86_64, кросс-компилятор GNU 15.1.0; CMake; NIIET K1921VG1T SDK; PuTTY; WinSCP (для подключения к кластерам ННГУ); библиотека OpenMP для параллельных вычислений.
    • Операционная система не используется (bare-metal).
  3. Аппаратная часть:
    • Макетно-отладочная плата — КФДЛ.441461.050;
    • Программатор JLink V9 ARM USB-JTAG;
    • 2 процессора Intel Xeon Silver 4310T для тестирования на архитектуре x86_64, суммарно 2×10 физических ядер + Hyper-Threading (2×20 логических ядер);
    • Процессор Banana Pi RISC-V SpacemiT K1 (RVV 1.0) для дополнительного тестирования на RISC-V, 8 физических ядер.
  4. Образовательный или промышленный контекст:
    • Научно-исследовательская работа, выполненная в ННГУ им. Н.И. Лобачевского. Направлена на исследование возможностей высокопроизводительных вычислений на отечественных микроконтроллерах с архитектурой RISC-V.

Результаты:

  • В ходе выполнения работы был успешно разработан и протестирован бенчмарк для LU-разложения плотных квадратных матриц, запускаемый на процессорах различных архитектур, в том числе на микроконтроллерах архитектуры RISC-V;
  • Результаты тестирования:
    • Intel x86_64 (20 физических ядер): Достигнуто ускорение в 14 раз, эффективность 70%. Использование Hyper-Threading не дало прироста производительности.
    • RISC-V SpacemiT K1 (8 физических ядер): Достигнуто линейное ускорение, эффективность 100%.
    • Микроконтроллер К1921ВГ1Т: Подтверждена работоспособность для матриц размером до 250х250 элементов типа double и 350х350 элементов типа float (время вычисления не зависит от типа элементов).
    • Сравнение с аналогами: На RISC-V разработанная реализация на 22% быстрее реализации из библиотеки линейной алгебры Eigen 5.0.0. На x86_64 реализация уступила Eigen на 18% и Intel MKL на 56%. (На архитектуре RISC-V Intel MKL запустить невозможно).

Выводы:

  • Успешно разработан и протестирован кроссплатформенный бенчмарк LU-разложения. Полученная реализация конкурентоспособна с существующими аналогами, а на архитектуре RISC-V превосходит их.
  • Микроконтроллер К1921ВГ1Т (RISC-V) подтвердил принципиальную возможность реализации высокопроизводительных вычислений, однако ключевым ограничением является недостаточный объем оперативной памяти.

Перспективы:

  • Расширение объема доступной RAM создаст возможность полноценного использования микроконтроллера для высокопроизводительных вычислений;
  • Также увеличение RAM позволит использовать уже разработанный алгоритм для значительно больших матриц, что в свою очередь делает целесообразной реализацию многопоточности и параллельного выполнения в bare-metal среде, а также других оптимизаций (SIMD Intrinsics);
  •  В перспективе возможно расширение проекта до полноценной библиотеки линейной алгебры, реализующей параллельные вычисления и оптимизированной для процессоров архитектуры RISC-V.


 
Изображения:

Используемый микроконтроллер:

Рис. 1. Ускорение полученной реализации
LU-разложения на архитектуре х86_64


Рис. 2. Эффективность полученной реализации LU-разложения на архитектуре х86_64

Рис. 3. Ускорение полученной реализации
LU-разложения на процессоре Banana Pi RISC-V


Рис. 4. Эффективность полученной реализации LU-разложения на процессоре Banana Pi RISC-V

Рис. 5. График времени вычисления на К1921ВГ1Т (время в сек)