이 실습은 루프 교환에 관한 실습입니다.
행렬 곱셈은 많은 수치 알고리즘에서 중요한 구성 요소입니다. 이 실습 과제에서는 주어진 실수 정사각 행렬의 정수 거듭제곱을 계산합니다. 지수를 이진수로 표현하면 행렬 연산 횟수가 크게 줄어듭니다. 그럼에도 이 코드에는 성능상 큰 결함이 있습니다. 여러분이 할 일은 그 결함을 찾아내는 것입니다.
힌트
힌트 1:
먼저 코드에서 문제가 되는 루프를 찾으십시오. 코드가 짧으므로 눈으로
직접 찾아도 되고, perf 같은 도구를 사용해 컴파일된
바이너리에 perf stat을 실행해도 됩니다.
힌트 2:
solution.cpp의 multiply에는 비효율이
있습니다. 그 이유를 알 수 있겠습니까? 현재 루프 순서에서 메모리 접근
패턴이 어떻게 되는지 생각해 보십시오.
힌트 3:
문제가 되는 코드는 다음과 같습니다:
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < N; k++) {
result[i][j] += a[i][k] * b[k][j];
}
}
}행렬 b에 대한 메모리 접근 패턴이 최적이 아닙니다. 루프
순서를 더 나은 방식으로 바꾸면 코드가 캐시 친화적으로 되어 이 문제를
해결할 수 있습니다.
풀이:
배경:
이 실습의 목표는 루프 순서 때문에 생긴 비효율적인 데이터 접근 패턴을 찾아 고치는 것입니다.
다음은 원래 코드의 성능입니다(perf stat ./lab으로 측정한
결과):
-----------------------------------------------------
Benchmark Time CPU Iterations
-----------------------------------------------------
bench1 1261 ms 1261 ms 1
Performance counter stats for './lab':
1,264,770,134 task-clock # 0.999 CPUs utilized
70 context-switches # 55.346 /sec
2 cpu-migrations # 1.581 /sec
1,369 page-faults # 1.082 K/sec
8,124,445,942 instructions # 1.73 insn per cycle
4,692,293,039 cycles # 3.710 GHz
1,160,302,252 branches # 917.402 M/sec
3,006,154 branch-misses # 0.26% of all branches
1.266066116 seconds time elapsedperf로 핫스팟을 분석하면 코드의 특정 부분이 두드러지게
나타납니다:
22 │188:┌─→vmovss xmm1,DWORD PTR [rcx] ▒
│ │for (int k = 0; k < N; k++) { ▒
│ │ add rdx,0x640 ▒
650 │ │ add rcx,0x4 ▒
│ │result[i][j] += a[i][k] * b[k][j]; ▒
1384 │ │ vfmadd231ss xmm0,xmm1,DWORD PTR [rdx-0x640] ◆
659 │ │ vmovss DWORD PTR [r8],xmm0 ▒
│ │for (int k = 0; k < N; k++) { ▒
│ ├──cmp rsi,rdx ▒
3 │ └──jne 188 ▒이 부분은 multiply 함수, 구체적으로는 가장 안쪽 루프에서
비롯된 것임을 알 수 있습니다:
// Multiply two square matrices
void multiply(Matrix &result, const Matrix &a, const Matrix &b) {
zero(result);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < N; k++) {
result[i][j] += a[i][k] * b[k][j];
}
}
}
}해결책
행렬 b에 대한 메모리 접근 패턴이 최적이 아닙니다. 가장
안쪽 루프는 k를 순회하므로 행렬에서 행과 행 사이를 건너뛰게
됩니다. 메모리 관점에서 보면 프로세서는 b[k][j]에서
b[k+1][j]로 가기 위해 메모리 여기저기를 건너뛰어야 합니다.
행을 고정한 채 a와 b의 각 열을 순회하도록 이
루프를 다시 작성하려고 합니다. 그렇게 하면 메모리를 연속적으로 순회하게
됩니다.
이를 위해 j에 대한 반복자와 k에 대한
반복자를 서로 바꾸기만 하면 됩니다:
// Multiply two square matrices
void multiply(Matrix &result, const Matrix &a, const Matrix &b) {
zero(result);
for (int i = 0; i < N; i++) {
for (int k = 0; k < N; k++) {
for (int j = 0; j < N; j++) {
result[i][j] += a[i][k] * b[k][j];
}
}
}
}다음은 수정된 코드의 벤치마크입니다. 보시다시피 약 10배 더 빠릅니다:
--------------------------------------------------------------
Benchmark Time CPU Iterations
--------------------------------------------------------------
bench1/iterations:1 126 ms 126 ms 1
Performance counter stats for './lab':
133,631,700 task-clock # 0.992 CPUs utilized
6 context-switches # 44.900 /sec
0 cpu-migrations # 0.000 /sec
1,369 page-faults # 10.245 K/sec
904,711,992 instructions # 1.91 insn per cycle
472,772,394 cycles # 3.538 GHz
150,239,295 branches # 1.124 G/sec
76,141 branch-misses # 0.05% of all branches
0.134680809 seconds time elapsed