Разные задачи

Умножение матриц

Рассмотрим расспространенную задачу - умножение матриц. Например, у нас есть следующие матрицы

матрица A

матрица B

То результат перемножения матриц будет равен

То есть для получения элемента результирующей матрицы, элементы строки первой матрицы последовательно перемножаются на элементы столбцов второй матрицы, и результаты умножений складываются.

С точки зрения псевдокода это выглядело бы так:

FOR row = 1 to 3
	FOR col = 1 to 3
		acum = 0  
		FOR i = 1 to 3
			acum = acum + A[row, i]*B[i, col]
		NEXT I
		C[row, col] = acum
	NEXT col
NEXT row

Напишем программу для перемножения двух матриц размером 3x3. Для упрощения вывода результатов на консоль воспользуемся функции printf языка С.

Итак, определим файл main.s со следующим кодом:

// Умножение двух матриц 3x3
//
// Используемые регистры:
// W1 - Индекс строки
// W2 - Индекс столбца
// X4 - Адрес строки
// X5 - Адрес столбца
// X7 - накопленная сумма для элемент результирующей матрицы
// W9 - элемент матрицы A
// W10 - элемент матрицы B
// X19 - элемент матрицы C
// X20 - счетчик цикла для печати
// X12 - номер стороки в цикле dotloop
// X6 - номер столбца в цикле dotloop
.global main    // точка входа в  программу
	.equ N, 3      // Размер матрицы
	.equ WDSIZE, 4 // размер элемента в байтах
main:
    STR LR, [SP, #-16]!         // сохраняем значение регистра LR
    STP X19, X20, [SP, #-16]!   // сохраняем значения регистров X19 и X20
    MOV W1, #N                  // помещаем в W1 индекс строки
    LDR X4, =A                  // В X4 адрес текущей строки матрицы А
    LDR X19, =C                 // В X19 адрес материцы С
rowloop:
    LDR X5, =B                  // первый столбец матрицы B
    MOV W2, #N                  // индекс столбца (считаем в обратном порядке до 0)
colloop:
    MOV X7, #0                  // регистр для накопления результата - по умолчанию равен 0
    MOV W0, #N                  // счетчик цикла
    MOV X12, X4                 // в X12 помещаем адрес строки для перемножения элементов
    MOV X6, X5                  // в X6 помещаем адрес столбца для перемножения элементов
dotloop:    // Цикл для умножения элементов текущей строки матрицы A на элементы текущего столбца матрицы B
    LDR W9, [X12], #WDSIZE      // загружаем A[row, i] и увеличиваем адрес в X12 на #WDSIZE байт
    LDR W10, [X6], #(N*WDSIZE)  // загружаем в W10 данные из B[i, col]
    SMADDL X7, W9, W10, X7      // умножаем и сохраняем результат в X7
    SUBS W0, W0, #1             // уменьшаем счетчик на 1
    B.NE dotloop                // если W0 не равно 0, то переходим к dotloop для перемножения новых элементов матриц
    STR W7, [X19], #4           // сохраняем результат из W7 в X19 - C[row, col] = W7, увеличиваем адрес в X19 на 4 байта
    ADD X5, X5, #WDSIZE         // Переходим к следующему столбцу в матрице B - увеличиваем адрес в X5 на #WDSIZE байт
    SUBS W2, W2, #1             // увеличиваем счетчик столбцов
    B.NE colloop                // если не все столбцы прошли, то переходим обратно к colloop
    ADD X4, X4, #(N*WDSIZE)     // к адресу в X4 прибавляем #(N*WDSIZE) байт для перехода к адресу новой строки
    SUBS W1, W1, #1             // уменьшаем счетчик строк
    B.NE rowloop                // если еще есть строки, переходим обратно к rowloop

    MOV W20, #3                 // проходим по трем строкам
    LDR X19, =C                 // адрес результирующей матрицы C
    // выводим матрицу с помощью функции printf языка C
printloop:
    LDR X0, =prtstr             // загружаем строку форматирования для функции printf
    LDR W1, [X19], #WDSIZE      // первый элемент текущей строки матрицы
    LDR W2, [X19], #WDSIZE      // второй элемент текущей строки матрицы   
    LDR W3, [X19], #WDSIZE      // третий элемент текущей строки матрицы
    BL printf                   // Вызыв функции printf
    SUBS W20, W20, #1           // уменьшаем счетчик строк
    B.NE printloop              // если есть еще строки, переходим обратно к printloop

    MOV X0, #0                  // код возврата из функции
    LDP X19, X20, [SP], #16     // восстанавливаем значение регистров
    LDR LR, [SP], #16           // восстанавливаем регистр LR
    RET                         // выход из функции
.data
    // первая матрица
    A:  .word 1, 2, 3
        .word 4, 5, 6
        .word 7, 8, 9
    // вторая матрица
    B:  .word 9, 8, 7
        .word 6, 5, 4
        .word 3, 2, 1
// результирующая матрица
    C: .fill 9, 4, 0
    prtstr: .asciz "%3d %3d %3d\n"

Вкратце рассмотрим данный код. Прежде всего в секции .data определены три матрицы. Матрицы A и B состоят из 9 элементов типа .word, то есть чисел размером 4 байта. Матрица C определена с помощью директивы .fill, которая определяет набор из 9 элементов размеров 4 байта, каждый из которых по умолчанию равен 0.

Для упрощения работы определяем две дополнительные константы:

.equ N, 3      // Размер матрицы
.equ WDSIZE, 4 // размер элемента в байтах

Вначале определяем значения для прохода по строкам:

MOV W1, #N                  // помещаем в W1 индекс строки
LDR X4, =A                  // В X4 адрес текущей строки матрицы А
LDR X19, =C                 // В X19 адрес материцы С

В W1 помещаем счетчик строк, то есть число 3 (надо пройти по трем строкам матрицы А). В регистр X4 загружается адрес матрицы A (адрес первого ее элемента) и в X19 помещается адрес матрицы С, в которую будем сохранять результат.

Дальше начинаем цикл для прохода по строкам и определяем значения для прохода по столбцам матрицы B:

rowloop:
    LDR X5, =B                  // первый столбец матрицы B
    MOV W2, #N                  // индекс столбца (считаем в обратном порядке до 0)

В регистр X5 помещается адрес матрицы В, а в W2 - счетчик столбцов (то есть надо пройтись по 3 столбцам матрицы В).

Затем начинаем цикл по столбцам

colloop:
    MOV X7, #0                  // регистр для накопления результата - по умолчанию равен 0
    MOV W0, #N                  // счетчик цикла
    MOV X12, X4                 // в X12 помещаем адрес строки для перемножения элементов
    MOV X6, X5                  // в X6 помещаем адрес столбца для перемножения элементов

В регистр Х7 помещаем число 0 - этот регистр будет накапливать значения для одного элемента матрицы С. Кроме того, в W0 помещается счетчик цикла - надо перемножить 3 элемента из строки матрицы А и столбца марицы B. Регистр Х12 будет указывать на адрес текущего элемента строки матрицы А, а Х6 - на адрес текущего элемента столбца матрицы В.

Далее перемножаем все элементы текущей строки матрицы А и текущего столбца матрицы В:

dotloop:    // Цикл для умножения элементов текущей строки матрицы A на элементы текущего столбца матрицы B
    LDR W9, [X12], #WDSIZE      // загружаем A[row, i] и увеличиваем адрес в X12 на #WDSIZE байт
    LDR W10, [X6], #(N*WDSIZE)  // загружаем в W10 данные из B[i, col]
    SMADDL X7, W9, W10, X7      // умножаем и сохраняем результат в X7
    SUBS W0, W0, #1             // уменьшаем счетчик на 1
    B.NE dotloop                // если W0 не равно 0, то переходим к dotloop для перемножения новых элементов матриц

Для перемножения в W9 загружаем элемент по адресу X12, при этом увеличиваем данный адрес на #WDSIZE (4) байт, то есть адрес будет указываать на следующий элемент текущей строки матрицы А. Аналогично в W10 загружаем элемент по адресу X6, при этом увеличиваем данный адрес на #(N*WDSIZE) (12) байт, то есть адрес будет указываать на следующий элемент текущего столба матрицы В. Инструкция SMADDL перемножает значения W9 и W10 и прибавляет к содержимому в регистре X7. И пока не пройдем по всем 3 элементам текущих строки и столбца, продолжаем данные действия.

Таким образом, в цикле dotloop пройдем по 3 ячейкам текущих строки и столбца, получим результ и сохраним его в регистр X12.

Далее для вычисления элемента матрицы C в следующем столбце переходим к следующему столбцу матрицы B:

STR W7, [X19], #4           // сохраняем результат из W7 в X19 - C[row, col] = W7, увеличиваем адрес в X19 на 4 байта
ADD X5, X5, #WDSIZE         // Переходим к следующему столбцу в матрице B - увеличиваем адрес в X5 на #WDSIZE байт
SUBS W2, W2, #1             // увеличиваем счетчик столбцов
B.NE colloop                // если не все столбцы прошли, то переходим обратно к colloop

При этом полученный результат из X7 сохраняем в текущей элемент матрицы С, адрес которого хранится в Х19. При этом данный адрес увеличиваем на 4 байта, чтобы в следующий раз сохранить значение для следующего элемента матрицы С. Также увеличиваем адрес в X5 на #WDSIZE байт, то есть переходим к новому столбцу матрицы В и уменьшаем счетчик столбцов в регистре W2.

Если все столбцы матрицы В пройдены, то переходим к новой строке матрицы А:

ADD X4, X4, #(N*WDSIZE)     // к адресу в X4 прибавляем #(N*WDSIZE) байт для перехода к адресу новой строки
SUBS W1, W1, #1             // уменьшаем счетчик строк
B.NE rowloop                // если еще есть строки, переходим обратно к rowloop

Для этого изменяем адрес в Х4 на #(N*WDSIZE) байт (по сути на 12 байт - размер строки), уменьшаем счетчик строк в W1 и переходим к следующей строке.

Если все строки перебраны, то переходим к печати на консоль - проходим по трем строкам матрицы С и единосременно с помощью строки форматирования prtstr выводим значения трех столбцов текущей строки матрицы C.

Поскольку в данном случае используется функция языка С, скомпилируем приложение с помощью следующей команды:

aarch64-none-linux-gnu-gcc main.s -o main -static

После запуска программа отобразит нам результирующую матрицу:

 30  24  18
 84  69  54
138 114  90