이 실습은 루프 교환에 관한 것으로, 이전 실습보다 난도가 높습니다.
이 실습 과제에서는 그레이스케일 이미지에 적용되는 가우시안 블러 알고리즘을 최적화합니다. 현대 카메라는 성능 좋은 이미지 센서를 갖추고 있어 큰 파일을 만들어 냅니다. 현대 CPU는 카메라로 찍은 사진 한 장을 얼마나 빠르게 필터링할 수 있습니까? 단순한 2D 합성곱 대신 1차원 디지털 필터를 두 번 적용하는 방식으로 이미 상당한 속도 향상을 얻었습니다.
힌트
힌트 1:
코드에는 메모리 접근 패턴이 최적이 아닌(캐시 미스를 많이 일으키는) 루프가 하나 있습니다. 그 루프를 찾아내고, 이상적인 루프 반복 패턴이 어떤 모습이어야 하는지 파악한 다음, 그에 맞게 리팩터링하십시오.
힌트 2:
문제가 되는 루프는 다음과 같습니다:
for (int i = 0; i < radius + 1 + radius; i++) {
dot += input[(r - radius + i) * width + c] * kernel[i];
}이 루프는 실제로 다른 두 루프 안에 중첩되어 있습니다:
for (int c = 0; c < width; c++) {
...
for (int r = 0; r < std::min(radius, height); r++) {
...
for (int i = 0; i < radius + 1 + radius; i++) {
dot += input[(r - radius + i) * width + c] * kernel[i];
}
...
}
...
}이상적인 메모리 접근 패턴이 어떠해야 하는지 생각해 보십시오. 여기서부터 그 목표를 달성하려면 이 루프 레이아웃에서 무엇을 바꿔야 하는지 알아낼 수 있습니다.
힌트 3:
이 코드는 c, r, i 순서로
루프를 돕니다. 그러나 이상적인 루프 중첩 계층은 r ->
i -> c입니다:
for (int r = 0; r < std::min(radius, height); r++) {
...
for (int i = 0; i < radius + 1 + radius; i++) {
...
for (int c = 0; c < width; c++) {
...
}
...
}
...
}순서를 재배치할 수 있으려면 중첩 루프 안의 기존 변수를 어떻게 바꿔야
합니까? 일반적으로 이러한 리팩터링을 하려면 누산기의 차원을 늘려야
합니다. 이 경우에는 dot에 주목하십시오.
풀이:
배경:
이 실습은 주어진 입력 이미지에 가우시안 블러를 적용하는 알고리즘을 다룹니다. 이 알고리즘의 성능은 다시 작성해야 하는 핫스팟 때문에 저하됩니다.
Intel CPU에서 성능 분석을 수행하기 위해 Linux perf를
기반으로 만든 도구 모음인 pmu-tools를 사용하여
코드의 하향식(top-down) 분석을 수행할 수 있습니다.
(Python이 설치되어 있다면) pmu-tools의
toplev.py 스크립트를 다음과 같이 이 실습에 실행할 수
있습니다:
toplev.py --core S0-C0 --run-sample -l2 -v --no-desc taskset -c 0 ./lab ARG1 ARG2여기서 ARG1과 ARG2는 각각 입력 및 출력
.pgm 파일의 경로입니다.
(저장소에 있는 예제를 사용하려면 ARG1은
${CMAKE_CURRENT_SOURCE_DIR}/pexels-pixabay-434334.pbm이고
ARG2는 output.pgm입니다.
output.pgm은 lab을 실행한 후
build 디렉터리에 lab과 함께 생성됩니다.)
출력의 일부는 다음과 같습니다:
--------------------------------------------------------------
Benchmark Time CPU Iterations
--------------------------------------------------------------
bench1/iterations:5 290 ms 290 ms 5
...
C0 FE Frontend_Bound % Slots 3.5 < [ 8.0%]
C0 BAD Bad_Speculation % Slots 0.3 < [ 8.0%]
C0 BE Backend_Bound % Slots 74.5 [ 8.0%]
C0 RET Retiring % Slots 21.6 < [ 8.0%]
C0 FE Frontend_Bound.Fetch_Latency % Slots 1.9 < [ 8.0%]
C0 FE Frontend_Bound.Fetch_Bandwidth % Slots 1.1 < [ 8.0%]
C0 BAD Bad_Speculation.Branch_Mispredicts % Slots 0.2 < [ 8.0%]
C0 BAD Bad_Speculation.Machine_Clears % Slots 0.1 < [ 8.0%]
C0 BE/Mem Backend_Bound.Memory_Bound % Slots 49.7 [ 8.0%]<==
C0 BE/Core Backend_Bound.Core_Bound % Slots 24.8 [ 8.0%]
C0 RET Retiring.Light_Operations % Slots 20.9 < [ 8.0%]
C0 RET Retiring.Heavy_Operations % Slots 0.4 < [ 8.0%]
C0-T0 MUX % 8.00
C0-T1 MUX % 8.00
Run toplev --describe Memory_Bound^ to get more information on bottleneck```이 출력은 코드가 주로 Memory Bound 상태이며, 자원의 거의 50%가 단지 데이터가 준비되기를 기다리느라 묶여 있음을 보여 줍니다.
perf report를 실행하면 문제가 되는 코드 줄을 찾을 수
있습니다:
dot += input[(r - radius + i) * width + c] * kernel[i];이는 solution.cpp의 37번째 줄입니다. 전체 루프는 다음과
같습니다:
for (int c = 0; c < width; c++) {
...
// Middle part of computations with full kernel
for (int r = radius; r < height - radius; r++) {
// Accumulation
int dot = 0;
for (int i = 0; i < radius + 1 + radius; i++) {
dot += input[(r - radius + i) * width + c] * kernel[i];
}
// Fast shift instead of division
int value = (dot + rounding) >> shift;
output[r * width + c] = static_cast<uint8_t>(value);
}
}보시다시피 i에 대한 내부 루프가 진행될 때마다 다음
input 조회에서 width개 요소만큼 건너뜁니다.
이는 전혀 캐시 친화적이지 않습니다. 이런 식으로 메모리를 건너뛰며
접근하면 캐시 라인에 함께 적재되는(또는 L1 캐시에 이미 있을 수도 있는)
주변 요소를 제대로 활용하지 못합니다. 이처럼 큰 스트라이드는 비용이 큰
캐시 미스를 다수 유발하고 성능을 떨어뜨립니다.
해결책
i 루프 안에서 c를 순회하도록 루프
순서를 재배치해야 합니다. 현재 작성된 방식으로는 루프 반복 사이에
의존성이 있으므로 이것이 간단하지 않습니다. K번째 반복에서
dot이 증가한 값은 K-1번째 반복에서의 값에
의존하며, 그 이전 반복도 마찬가지입니다.
따라서 이 의존성을 끊으려면 dot을 길이가
width인 int 배열로 확장해야 합니다.
먼저 이 함수에서 c에 대한 최상위 루프로부터 다음 코드
부분을 추출합니다:
for (int c = 0; c < width; c++) {
// Top part of line, partial kernel
...
int value = static_cast<int>(dot / static_cast<float>(sum) + 0.5f);
output[r * width + c] = static_cast<uint8_t>(value);
}
} // *** <--- STOP `c` HERE ***
// Middle part of computations with full kernel
...
for (int c = 0; c < width; c++) { // <--- *** RESTART `c` HERE ***
// Bottom part of line, partial kernel그런 다음 dot을 길이가 width인 배열로
바꾸어, (이전 코드처럼) 주어진 c에 대해 값을 누적하면서도
메모리 접근 패턴을 개선하기 위해 c 루프를 i
루프 안에서 수행합니다:
for (int r = radius; r < height - radius; r++) {
int dot[width];
for (int c = 0; c < width; c++) {
dot[c] = 0; // <- INITIALISATION
}
// Accumulation
for (int i = 0; i < radius + 1 + radius; i++) {
for (int c = 0; c < width; c++) {
// <- LOOP OVER `c` INSIDE `i`; sequential accesses are cache-friendly
dot[c] += input[(r - radius + i) * width + c] * kernel[i];
}
}
// <- PUT `c`th loop value into `output` as before
for (int c = 0; c < width; c++) {
// Fast shift instead of division
int value = (dot[c] + rounding) >> shift;
output[r * width + c] = static_cast<uint8_t>(value);
}
}이렇게 변경한 후 벤치마크를 다시 실행하면 놀라운 속도 향상(290ms에서 71.4ms로)을 보이며, Memory Bound 접근은 리소스 사용량의 5.4%에 불과한 수준으로 줄어듭니다. 이제 코드는 주로 알고리즘이 반드시 수행해야 하는 연산에 의해 제한됩니다.
--------------------------------------------------------------
Benchmark Time CPU Iterations
--------------------------------------------------------------
bench1/iterations:5 71.4 ms 71.0 ms 5
...
C0 FE Frontend_Bound % Slots 5.4 < [ 8.0%]
C0 BAD Bad_Speculation % Slots 0.7 < [ 8.0%]
C0 BE Backend_Bound % Slots 27.4 [ 8.0%]
C0 RET Retiring % Slots 66.6 < [ 8.0%]
C0 FE Frontend_Bound.Fetch_Latency % Slots 2.8 < [ 8.0%]
C0 FE Frontend_Bound.Fetch_Bandwidth % Slots 2.1 < [ 8.0%]
C0 BAD Bad_Speculation.Branch_Mispredicts % Slots 0.5 < [ 8.0%]
C0 BAD Bad_Speculation.Machine_Clears % Slots 0.2 < [ 8.0%]
C0 BE/Mem Backend_Bound.Memory_Bound % Slots 5.4 < [ 8.0%]
C0 BE/Core Backend_Bound.Core_Bound % Slots 22.0 [ 8.0%]<==
C0 RET Retiring.Light_Operations % Slots 64.5 [ 8.0%]
C0 RET Retiring.Heavy_Operations % Slots 3.3 < [ 8.0%]
C0-T0 MUX % 8.00
C0-T1 MUX % 8.00