Method of Fast Matrix Multiplication Under ARM Architecture Using SIMD Instructions

Скорочена інформація про документ
dc.contributor.authorDychka, I. A.
dc.contributor.authorVinnyk, D. A.
dc.contributor.authorBukhtiyarov, Yu. V.
dc.contributor.authorYurchyshyn, V. Ya.
dc.date.accessioned2021-04-01T11:41:20Z
dc.date.available2021-04-01T11:41:20Z
dc.date.issued2020
dc.description.abstractenBackground. Matrix multiplication is a rather complicated algorithm with a large number of operations. An additional problem is the nonlinear memory traversal of matrices. Matrix multiplication is widely used in various fields, such as neural networks, solutions of linear equation systems, matrix transformations, and so on. Therefore, it is important to develop a method of matrix multiplication, which will take into account the problems of the location of the matrices in memory, and will effectively manage the data when reused. Objective. The purpose of the paper is to develop a method of fast matrix multiplication of two matrices, as well as multiplying the matrix by the transposed matrix and by a list of vectors (including special case for only one vector), as well as to implement it as a function with optimization for ARM architecture processors. The function must be able to handle different types of data and submatrices. The integer result can be scaled. Methods. The main ideas of the developed method are simultaneous work with several rows/columns of input matrices and their splitting into blocks, which will allow the algorithm to run on the same memory for a while. The C programming language was chosen for implementation. SIMD instructions were used to increase productivity. We also need to properly organize the memory preloading for effective implementation under the ARM architecture. Results. A function that performs matrix multiplication by the developed method with the necessary parameters was implemented as a result of the study. Tests on various sizes and types have shown that the implemented function is faster than analogues from the OpenCV2 and Eigen 3 libraries. Testing was done using the vipmed utility for running and measuring features developed for enterprise use at VIT. Conclusions. The proposed matrix multiplication method gives the expected acceleration of matrix multiplication operations, has passed evaluation test for use and meets the target requirements. For further work, it is necessary to study in more detail the influence of the cache at different levels and compare with other existing libraries.uk
dc.description.abstractruПроблематика. Матричное умножение является достаточно сложным алгоритмом с большим количеством операций. Дополнительной проблемой также является нелинейный обход матриц по памяти. Операция матричного умножения широко используется в различных сферах, таких как нейронные сети, решения систем линейных уравнений, матричные преобразования и т.п. Поэтому важно разработать метод матричного умножения, который будет учитывать проблемы расположения матриц в памяти, а также эффективно будет распоряжаться данными при их повторном использовании. Цель исследования. Разработать метод быстрого матричного умножения двух матриц, умножения матрицы на транспонированную и на список векторов (в т.ч. частный случай для одного вектора); реализовать его в виде функции с оптимизацией для процессоров архитектуры ARM. Функция должна уметь работать с различными типами данных и с подматрицамы. Целочисленный результат может быть отмасштабирован. Методика реализации. Главными идеями разработанного метода является одновременный проход несколькими строками/столбцами входных матриц и их разбиение на блоки, что позволит алгоритму некоторое время работать на одной и той же памяти. Для реализации был выбран язык программирования С. Для увеличения производительности использованы SIMD-инструкции. Для эффективной реализации под архитектуру ARM также необходимо правильно организовать работу с предварительной загрузкой памяти. Результаты исследования. Реализована функция, которая выполняет матричное умножение по разработанному методу с необходимыми параметрами. Проверки на разных размерах и типах показали, что реализованная функция быстрее аналогов из библиотек OpenCV2 и Eigen 3. Тестирование проходило с помощью утилиты vipmed для запусков и замеров характеристик, разработанной для корпоративного пользования в компании VIT. Выводы. Предложенный метод умножения матриц дает ожидаемое ускорение операции умножения матриц, прошел оценочный тест на использование и соответствует заданным в цели требованиям. Для дальнейшей работы необходимо подробнее исследовать влияние кэша разного уровня и сравнить с другими существующими библиотеками.uk
dc.description.abstractukПроблематика. Матричне множення є досить складним алгоритмом із великою кількістю операцій. Додатковою проблемою також є нелінійний обхід матриць по пам’яті. Операція матричного множення широко використовується в різних сферах, таких як нейронні мережі, розв’язки систем лінійних рівнянь, матричні перетворення тощо. Тож важливо розробити метод матричного множення, що враховуватиме проблеми з розташуванням матриць у пам’яті, а також ефективно розпоряджатиметься даними при їх повторному використанні. Мета дослідження. Розробити метод швидкого матричного множення двох матриць, множення матриці на транспоновану та на список векторів (у т.ч. окремий випадок для одного вектора); реалізувати його у вигляді функції з оптимізацією для про­цесорів архітектури ARM. Функція має вміти працювати з різними типами даних та з підматрицями. Цілочисловий результат може бути масштабований. Методика реалізації. Головними ідеями розробленого методу є одночасних прохід декількома рядками/стовпчиками вхідних матриць та їх розбиття на блоки, що дасть алгоритму змогу деякий час працювати на одній і тій самій пам’яті. Для реалізації було вибрано мову програмування С. Для збільшення продуктивності використано SIMD-інструкції. Для ефективної реалізації під архітектуру ARM також необхідно правильно організувати роботу з попереднім завантаженням пам’яті. Результати дослідження. Реалізовано функцію, що виконує матричне множення за розробленим методом із необхідними параметрами. Перевірки на різних розмірах і типах показали, що реалізована функція є швидшою за аналоги з бібліотек OpenCV2 та Eigen 3. Тестування відбувалося за допомогою утиліти vipmed для запусків і замірів характеристик, розробленої для корпоративного користування у компанії VIT. Висновки. Запропонований метод множення матриць дає очікуване прискорення операції множення матриць, пройшов оціночний тест на використання та відповідає заданим у меті вимогам. Для подальшої роботи необхідно детальніше дослідити вплив кеша різного рівня та порівняти з іншими існуючими бібліотеками.uk
dc.format.pagerangePp. 35-43uk
dc.identifier.citationMethod of Fast Matrix Multiplication Under ARM Architecture Using SIMD Instructions / I. A. Dychka, D. A. Vinnyk, Yu. V. Bukhtiyarov, V. Ya. Yurchyshyn // Наукові вісті КПІ : міжнародний науково-технічний журнал. – 2020. – № 2(129). – С. 35–43. – Бібліогр.: 9 назв.uk
dc.identifier.doihttps://doi.org/10.20535/kpi-sn.2020.2.205115
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/40380
dc.language.isoenuk
dc.publisherКПІ ім. Ігоря Сікорськогоuk
dc.publisher.placeКиївuk
dc.relation.ispartofНаукові вісті КПІ : міжнародний науково-технічний журнал, 2020, № 2(129)uk
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/en
dc.subjectmatrix multiplicationuk
dc.subjectARM architectureuk
dc.subjectvector operationsuk
dc.subjectmatrix transpositionuk
dc.subjectматричне множенняuk
dc.subjectархітектура ARMuk
dc.subjectвекторні операціїuk
dc.subjectтранспонування матриціuk
dc.subjectматричное умножениеuk
dc.subjectархитектура ARMuk
dc.subjectвекторные операцииuk
dc.subjectтранспонирование матрицыuk
dc.subject.udc004.231.2(045)uk
dc.titleMethod of Fast Matrix Multiplication Under ARM Architecture Using SIMD Instructionsuk
dc.title.alternativeМетод реалізації швидкого матричного множення під архітектуру ARM із використанням SIMD-інструкціїuk
dc.title.alternativeМетод реализации быстрого матричного умножения под архитектуру ARM с использованием SIMD-инструкцииuk
dc.typeArticleuk

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Ескіз
Назва:
NVKPI2020-2_04.pdf
Розмір:
333.66 KB
Формат:
Adobe Portable Document Format
Опис:
Завантажити
Ліцензійна угода
Зараз показуємо 1 - 1 з 1
Ескіз недоступний
Назва:
license.txt
Розмір:
9.01 KB
Формат:
Item-specific license agreed upon to submission
Опис:
Завантажити

Зібрання

Наукові вісті КПІ: міжнародний науково-технічний журнал, № 2(129)