Вопрос:

Является ли упорядочение по основным строкам более эффективным для умножения матрицы на вектор?

matrix language-agnostic linear-algebra matrix-multiplication

403 просмотра

1 ответ

321 Репутация автора

Если Mматрица nxm и vи uявляются векторами, то с точки зрения индексов умножение матрицы на вектор выглядит следующим образом u[i] = sum(M[i,j] v_j, 1 <= j <= m). Поскольку vэто вектор, его элементы предположительно хранятся в последовательных ячейках памяти для языков, ориентированных на численные вычисления. Если Mон хранится в главном порядке строк (как в C, Mathematica и Pascal), то последующие M[i,j]суммы также сохраняются в последовательных ячейках памяти по мере jувеличения, что делает итерацию очень эффективной. Если он хранится в главном порядке столбцов (как в Fortran, Matlab, R и Julia), то приращение jтребует перемещения на количество областей памяти, равное шагу внешней матрицы, которое в этом случае равноn, Это наивно кажется менее эффективным для матриц с множеством строк. (Для умножения матрицы на матрицу проблема не возникает, потому что при любом соглашении об упорядочении увеличение суммируемого индекса требует перемещения по главному шагу в памяти одной матрицы или другой.)

Является ли разница между перемещением в памяти одной единицей и многими единицами заметной или незначительной в большинстве компьютерных архитектур по сравнению с операциями умножения и сложения? (Я предполагаю «незначительное», так как на практике Fortran обычно по крайней мере так же быстр, как C, но кто-нибудь может объяснить, почему?)

Автор: tparker Источник Размещён: 08.11.2017 10:08

Ответы (1)


1 плюс

469 Репутация автора

Ожидается, что разница будет высокой в ​​большинстве компьютерных архитектур, по крайней мере, в принципе.

Матрично-векторное умножение является вычислением с привязкой к памяти, поскольку повторное использование памяти является низким. Все (N) компоненты v повторно используются для вычисления каждого элемента u, но каждый элемент матрицы (N ^ 2) используется только один раз. Если мы рассматриваем задержку типичной памяти (см., Например, https://gist.github.com/hellerbarde/2843375 ) как (менее) 100 нс по сравнению со временем, необходимым для выполнения операции с плавающей запятой (менее 1 нс), мы убедитесь, что большая часть времени тратится на загрузку и сохранение значений из / в массивы.

Мы все еще можем реализовать его в кеш-памяти, то есть иметь максимально возможную локальность данных. Поскольку память загружается в кеш в виде строк, мы должны максимально использовать загруженную строку кеша. Вот почему доступ к смежным областям памяти сокращает время, затрачиваемое на загрузку данных из памяти.

Чтобы поддержать это, давайте попробуем очень простой код:

program mv
integer, parameter :: n=10000
real, allocatable :: M(:,:), v(:), u(:)
real :: start, finish
integer :: i, j
allocate(M(n,n),v(n),u(n))
call random_number(M)
call random_number(v)
u(:)=0.
call cpu_time(start)
do i=1,n
do j=1,n
    ! non-contiguous order
    u(i)=u(i)+M(i,j)*v(j)
    ! contiguous order
    ! u(i)=u(i)+M(j,i)*v(j)
enddo
enddo
call cpu_time(finish)
print*,'elapsed time: ',finish-start
end program mv

Некоторые результаты:

               non-contiguous order   contiguous order
gfortran -O0            1.                 0.5
gfortran -O3           0.3                 0.1
ifort -O0              1.5                0.85
ifort -O3            0.037               0.035

Как видите, разница в компиляции без оптимизации значительна. Включение оптимизации gfortran все еще показывает существенные различия, тогда как с ifort есть только небольшая разница. Глядя на отчет компилятора, кажется, что компилятор поменял местами циклы, что привело к непрерывному доступу во внутреннем цикле.

Однако можем ли мы сказать, что язык с упорядочением по основным строкам более эффективен для вычисления матрицы-вектора? Нет, я не могу этого сказать. Не только потому, что компилятор может компенсировать разницу. Сам код не знает всего о строках и столбцах M: он в основном знает, что у M есть два индекса, один из которых - в зависимости от языка - непрерывен в памяти. Для матрицы-вектора наилучшим для локальности данных является «быстрый» индекс, сопоставленный с индексом строки матрицы. Вы можете добиться этого с помощью языков "row-major" и "column-major". Вы просто должны хранить значения М в соответствии с этим. В качестве примера, если у вас есть «алгебраическая» матрица

     [ M11 M12 ]
M =  [         ]
     [ M21 M22 ]

вы храните его как «вычислительную матрицу»

C       ==> M[1,1] = M11 ; M[1,2] = M12 ; M[2,1] = M21 ; M[2,2] = M22 
Fortran ==> M[1,1] = M11 ; M[2,1] = M12 ; M[1,2] = M21 ; M[2,2] = M22 

так что вы всегда будете смежны в строке «алгебраической матрицы». Компьютер ничего не знает о исходной матрице, но мы знаем, что вычислительная матрица является транспонированной версией алгебраической матрицы. В обоих случаях у меня будет внутренний цикл, повторяющийся по смежному индексу, и конечный результат будет тем же вектором.

В сложном коде, если я уже выделил и заполнил матрицу значениями, и я не могу решить сохранить транспонированную матрицу, потенциально возможно, что язык "строки-майора" даст наилучшие результаты. Но, поменять местами циклы (см. Https://en.wikipedia.org/wiki/Loop_interchange ), как это автоматически делается компиляторами Intel и как реализовано в реализациях BLAS (см. Http://www.netlib.org/lapack/explore-html. /db/d58/sgemv_8f_source.html ), уменьшите различия до очень небольших значений. Поэтому, используя Фортран, вы можете предпочесть:

do j=1,n
    do i=1,n
        u(i)=u(i)+M(i,j)*v(j)
    enddo
enddo
Автор: Franz Размещён: 08.11.2017 11:44
Вопросы из категории :
32x32