행렬 순서는 행렬 벡터 곱셈에 더 효율적입니까?

Question

M이 n x m 매트릭스이고 v 및 u이 벡터 인 경우 인덱스의 측면에서 행렬 - 벡터 곱셈은 u[i] = sum(M[i,j] v_j, 1 <= j <= m)처럼 보입니다. v은 벡터이므로 그 요소는 아마도 수치 계산 지향 언어의 연속적인 메모리 위치에 저장됩니다. M이 C, Mathematica 및 Pascal에서와 같이 행 우선 순서로 저장되는 경우 j이 증가하므로 이후의 M[i,j]은 연속적인 메모리 위치에도 저장되므로 반복이 매우 효율적입니다. 열 우선 순위 (Fortran, Matlab, R 및 Julia에서와 같이)에 저장된 경우 j을 증가 시키려면 바깥 쪽 행렬 보들과 동일한 수의 메모리 위치로 이동해야합니다.이 경우에는 과 같습니다. 이것은 순진하게 많은 행을 가진 행렬에 대해 덜 효율적으로 보인다. (행렬 - 행렬 곱셈의 경우 문제가 발생하지 않습니다. 왜냐하면 순서 규칙에 따라 합계 지수를 증가 시키면 하나의 행렬의 메모리 또는 다른 행렬의 주요 보폭으로 이동해야하기 때문입니다.)

곱셈과 덧셈 연산과 비교하여, 대부분의 컴퓨터 아키텍처에서 한 단위로, 많은 단위로 메모리를 인식 할 수 있거나 무시할 수 있습니까? 실제로 Fortran은 일반적으로 C보다 빠르지 만 이유가 무엇인지 자세히 설명 할 수 있습니까?)

Answer 1

차이점은 적어도 원칙적으로 대부분의 컴퓨터 아키텍처에서 높을 것으로 예상됩니다.

매트릭스 - 벡터 곱셈은 메모리 재사용이 낮기 때문에 메모리 바인딩 계산입니다. v의 모든 (N) 구성 요소는 u의 각 요소를 계산하기 위해 재사용되지만 행렬의 각 요소 (N^2)는 한 번만 사용됩니다. 부동 소수점 연산을 수행하는 데 필요한 시간 (1ns 미만)과 비교하여 일반적인 메모리 (예 : https://gist.github.com/hellerbarde/2843375 참조)의 대기 시간이 100ns 미만이라고 생각하면 대다수의 시간이 값로드 및 저장에 소비된다는 것을 알 수 있습니다 from/to 배열.

Google은 캐시 친화적 인 방식, 즉 가능한 한 데이터 지역성을 구현할 수 있습니다. 메모리는 라인으로 캐시에로드되므로 가능한 한로드 된 캐시 라인을 사용해야합니다. 연속 메모리 영역에 액세스하는 것은 메모리에서 데이터를로드하는 데 소요되는 시간을 줄이는 이유입니다.

이를 지원하기 위해, 우리는 아주 간단한 코드를 해보자 :

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에는 두 개의 인덱스가 있으며 그 중 하나는 메모리에 따라 언어에 따라 다릅니다. 행렬 벡터의 경우 데이터 지역에 가장 적합한 행 인덱스가 행 인덱스에 매핑됩니다. "행 - 주요"및 "열 - 주요"언어로이 작업을 수행 할 수 있습니다. 이 값에 따라 M의 값을 저장하면됩니다.당신은 "계산 매트릭스"당신은 항상 "대수 매트릭스"행에 연속되도록

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 

로 저장하면 "대수"매트릭스에게

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

이있는 경우 예를 들어. 컴퓨터는 초기 행렬에 대해 아무 것도 모릅니다. 그러나 우리는 계산 행렬이 대수 행렬의 변환 된 버전이라는 것을 압니다. 두 경우 모두 연속적인 인덱스를 반복하면서 내부 루프를 만들고 최종 결과는 동일한 벡터가됩니다.

복잡한 코드의 경우 매트릭스에 값을 이미 할당하여 채우고 전치 된 매트릭스를 저장할 수 없다면 잠재적으로 "행 주요"언어가 최상의 성능을 제공 할 가능성이 있습니다. 그러나 인텔 컴파일러에 의해 자동으로 수행되고 BLAS 구현 (http://www.netlib.org/lapack/explore-html/db/d58/sgemv_8f_source.html 참조)에 의해 수행 된 것처럼 루프를 교환하면 (참조), 차이를 매우 작은 차이 값으로 줄입니다. 따라서 Fortran을 사용하면 다음을 선호 할 수 있습니다.

do j=1,n 
    do i=1,n 
     u(i)=u(i)+M(i,j)*v(j) 
    enddo 
enddo