Matrix multiplication와 index에 따른 속도차이
Matrix Multiplication (매트릭스 행렬 곱연산)은 사실 어려운 개념은 아닙니다.
중학교? 쯤에 배웠던것 같은데, 이 개념을 바로 프로그래밍에 써먹기도 그다지 어렵진 않은 내용인것 같습니다.
2 by 2 matrix라고 생각했을 때 예를 들어보면 다음과 같습니다.
- A matrix
|
a1 |
a2 |
|
a3 |
a4 |
- B matrix
|
b1 |
b2 |
|
b3 |
b4 |
A와 B의 matrix multiplication 결과를 C matrix (A**B)라고 할 때,
C matrix를 구하는 방법은 다음과 같다.
- C matrix
|
a1*b1 +a2*b3 |
a1*b2 + a2*b4 |
|
a3*b1 + a4*b3 |
a3*b2 + a4*b4 |
A matrix와 B matrix의 column, row의 수를 n*n 이라고 할 때,
C matrix에 각각 들어갈 데이터 (예를들면 c[1][1])는 A의 column(=B row) 수만큼 연산이 필요합니다.
(c[0][0]을 예로 (a1*b1) + (a2*b3) 이렇게 2번의 연산이 필요하다.)
따라서 C의 matrix의 column과 row의 수는 n^2이라고 나타낼 수 있기 때문에,
matrix multiplication의 계산에 필요한 연산 횟수는 O(n^3) 이라고 할 수 있습니다.
이처럼 matrix multiplication을 직접 프로그래밍 하는것은 O(n^3) 연산이기에 3중 for loop를 이용하면
쉽게 구현할 수 있지만, n^3 연산이란것은 굉장히 오래 걸리는 것으로 NP problem으로 구분됩니다.
매우 오래걸리는 연산인데도 불구하고 만약 컴퓨터 Cache를 제대로 이해하지 못한 채
matrix 곱연산을 구현한다면 정말 최악의 running time이 걸리는 프로그램이 될 수 있습니다.
: 결론, Cache의 구조를 이해하지 못한 채 Matrix multiplication (행렬의 곱연산)을 구현할 경우 문제가 발생할 수 있다!
(시간이 O(n^3) 보다 더욱더 많이 걸림!)
이것을 방지하기 위해 아래 3by4 matrix (이하 Mat)의 구조를 예로 들어보겠습니다.
column과 row로 구분되어 있는건 당연한 이야기지만, 실제로 우리가 사용하는 main memory는 1차원이기 때문에
위의 matrix 행렬 Mat은 아래 그림에 나와있는 배열과 같이 1차원으로 저장됩니다.
기본적으로 memory cache는 '근처에 있는것을 자주 사용할 것이다' 라는 가정이 있기 때문에
Row0, Row1, Row2를 따로 저장할 확률이 굉장히 높습니다.
따라서 Mat[0][0]을 사용한 후에, Mat[0][1]을 사용하게 된다면 연산 효율이 좋을 것이며
Mat[0][0]을 사용한 후에, Mat[1][0]을 사용하게 된다면 Cache mismatch로 인해 속도 효율이 굉장히 느릴것입니다.
(결론: row를 움직이면서 matrix에 접근하게 되면 매우 느리다.)
실제로도 그런지 확인해보겠습니다.
단순히 1000 by 1000 matrix A와 B를 random하게 생성하여
A**B 두행렬의 곱연산인 C matrix를 만드는데까지 걸리는 indexing 순서를 달리하여 시간을 출력해보았습니다.
C의 Col, Row를 i,j라고 할 때 i, j에 따라서 k=1 to Size∑(A[i][k]+B[k][j]) 를 연산하게 되는데
여기서 i와 j, k에 의한 3중 loop의 순서를 바꾸면서 구현해보았습니다.
Index를 어떻게 먼저 loop에 넣느냐에 따라 결과는 다음과 같습니다.
KIJ, IKJ > IJK, JIK > JKI, KJI
KIJ, IKJ의 순서가 가장 빨랐는데, KIJ를 기준으로 설명을 해보면 다음과 같습니다.
for (k=0; k<n; k++) {
for (i=0; i<n; i++) {
r = a[i][k];
for (j=0; j<n; j++)
c[i][j] += r * b[k][j];
}
}
가장 많이 실행되는 3번쨰 for loop를 보시면 가장 큰 특징을 찾을 수 있습니다.
for (j=0; j<n; j++)
c[i][j] += r * b[k][j];
C matrix와 B matrix 모두 j변수로 인해 column이 움직이는것을 확인할 수 있습니다.
따라서 가장 빠른 KIJ, IKJ 순서의 indexing을 이용한 3중 for loop는 'row를 움직이면서 연산하는식이 없기 때문에 빠르다'
라는 결론을 낼 수 있겠네요.
하지만 가장 느린 JKI, KJI중에 JKI를 예로 들면 다음과 같습니다.
for (j=0; j<n; j++) {
for (k=0; k<n; k++) {
r = b[k][j];
for (i=0; i<n; i++)
c[i][j] += a[i][k] * r;
}
}
가장 많이 실행되는 3번째 for loop를 보시면 다음과 같습니다.
for (i=0; i<n; i++)
c[i][j] += a[i][k] * r;
C matrix와 Amatrix 모두 i 변수로 인해 row가 움직이는 것을 확인할 수 있습니다.
KIJ, IKJ: 가장 빠름: 모두 column으로 움직이면서 연산
IJK, JIK: 두번째로 빠름: 하나의 matrix에 대해서는 row, 다른 하나의 matrix에 대해서는 column으로 움직이면서 연산
JKI, KJI: 가장 느림: 모두 row로 index 변수를 움직이면서 연산.
- 결론
matrix 연산을 할 때, column으로 index를 옮기면서 연산해야 빠르다.
row로 index를 옮기며 연산하면 느리다.