Обобщение одного алгоритма параллельного умножения матриц в алгебре многомерных матриц
Authors: Мунерман В.И. , Мунерман Д.В. 
Published: December 2024

Многомерные матрицы – это мощный инструмент для решения различных фундаментальных научных проблем и прикладных научно-технических задач. В качестве примеров применения многомерных матриц в различных областях можно привести как работу создателя теории многомерных матриц Н.П. Соколова так и другие работы в том числе и выполненные авторами. Проблема параллельной реализации самой сложной операции алгебры многомерных матриц – (, )-свернутого произведения относится к числу наиболее важных. Не случайно проблеме параллельного умножения обычных двумерных матриц посвящено много публикаций. В этих работах рассматриваются проблемы выбора способа распределения элементов матриц между процессорами и разработки архитектур программно-аппаратных комплексов для эффективной реализации этой операции. Для параллельного умножения обычных матриц, как правило, используются два вида алгоритмов: ленточные, реализующие поэлементное умножение матриц и блочные, основанные на методе Фробениуса. Многие авторы, проводившие анализ эффективности параллельного умножения матриц, отдают предпочтение блочным алгоритмам, утверждая, что последние обладают высокой степенью масштабируемости. Учитывая тот факт, что масштабируемость – это наиболее важное свойство параллельных алгоритмов и вычислительных комплексов их реализующих, в дальнейшем будет рассматриваться параллельный алгоритм блочного умножения многомерных матриц. В работе рассматривается обобщение алгоритма Кэннонана (, )-свернутое произведение многомерных матриц.Доказано, что многомерные матрицы-операнды могут быть представлены как совокупность сечений по скоттовым индексам, произведения которых позволяют получить требуемую матрицу-результат. Для разбиения этих сечений на блоки и пересчета индексов блоков в ходе выполнения алгоритма предложен метод, основанный на использовании специфических систем счисления, и определен метод вычисления оснований этих систем счисления. Процесс выполнения обобщенного алгоритма Кэннона проиллюстрирован таблицами распределения блоков на всех этапах выполнения алгоритма. Предложенный метод обобщения может быть распространен и на другие алгоритмы блочного умножения матриц.

Multidimensional matrices are a powerful tool for solving various fundamental scientific problems and applied scientific and technical problems. As examples of the use of multidimensional matrices in various fields, one can cite the work of the creator of the theory of multidimensional matrices N.P. Sokolov and other works, including those performed by the authors. The problem of parallel implementation of the most complex operation of the algebra of multidimensional matrices, the (, )-convolution product, is one of the most important. It is no coincidence that many publications are devoted to the problem of parallel multiplication of ordinary two-dimensional matrices. In these works, the problems of choosing a method for distributing matrix elements between processors and developing architectures of software and hardware systems for the effective implementation of this operation are considered. For parallel multiplication of ordinary matrices, as a rule, two types of algorithms are used: band algorithms that implement element-wise matrix multiplication and block algorithms based on the Frobenius method. Many authors who have analyzed the efficiency of parallel matrix multiplication prefer block algorithms, arguing that the latter have a high degree of scalability. Taking into account the fact that scalability is the most important property of parallel algorithms and computing systems that implement them, in the future we will consider a parallel algorithm for block multiplication of multidimensional matrices. The paper considers a generalization of the Cannon algorithm to the (, )-convolution product of multidimensional matrices. It is proved that multidimensional matrices-operands can be represented as a set of sections by Scottish indices, the products of which allow one to obtain the required matrix-result. To split these sections into blocks and recalculate block indices during the execution of the algorithm, a method based on the use of specific number systems is proposed, and a method for calculating the bases of these number systems is determined. The process of executing the generalized Cannon algorithm is illustrated by block distribution tables at all stages of the algorithm execution. The proposed generalization method can be extended to other block matrix multiplication algorithms.