이 실습에서는 그레이스케일1 이미지를 이진2 이미지로 변환하는, 오래되었지만 여전히 훌륭한 오츠 이진화(Otsu's thresholding)3 기법을 다룹니다. 이 알고리즘의 핵심 부분 중 하나는 그레이스케일 이미지의 히스토그램을 계산하는 것, 즉 이미지에서 특정 색상이 몇 번 나타나는지 계산하는 것입니다. 입력 이미지가 8비트 그레이스케일이므로 서로 다른 색상은 256가지뿐입니다.

std::array<uint32_t, 256> hist;
hist.fill(0);
for (int i = 0; i < image.width * image.height; ++i)
  hist[image.data[i]]++;

히스토그램 알고리즘의 구현은 매우 간단하지만 한 가지 골치 아픈 특성이 있습니다. 이미지의 각 픽셀마다 1) 해당 픽셀 색상의 현재 값을 읽고, 2) 그 값을 증가시킨 다음, 3) 다시 저장해야 합니다.

히스토그램에서 같은 색상에 대한 갱신이 비교적 높은 빈도로 발생하면, 프로세서가 픽셀 i+1의 처리를 시작하기 전에 픽셀 i의 갱신을 완료하지 못했을 수 있습니다. 이런 경우 프로세서는 i+1 갱신을 위해 로드되는 값이 메모리에서 올지, 아니면 i의 저장에서 올지를 예측합니다. 메모리에서 온다면 두 갱신을 병렬로 수행할 수 있지만, 그렇지 않다면 프로세서는 갱신을 직렬화해야 합니다.

간단한 예시: 이미지에 다음과 같은 픽셀이 있다면,

0xFF 0xFF 0xFF 0xFF 0xFF 0xFF ...

hist[0xFF]에 대한 모든 갱신이 직렬화됩니다.

이 문제를 어떻게 우회할 수 있을지 생각해 보십시오. 힌트: 추가 메모리를 사용할 수 있습니다.

보너스 연습 문제 1: 원래 구현과 여러분의 해법에서 최악의 경우와 최선의 경우는 각각 무엇입니까?

입력 이미지는 다음에서 가져왔습니다: https://people.sc.fsu.edu/~jburkardt/data/pgmb/pgmb.html

힌트

힌트 1:

분석해야 할 배열 채우기 패턴은 다음 코드 조각입니다.

for (int i = 0; i < image.width * image.height; ++i)
    hist[image.data[i]]++;

image.data의 원소가 동일한 긴 연속 구간을 만나면 문제가 발생한다는 점을 알 수 있습니다. 예를 들어, image.data 배열에 서로 인접한 원소 열 개로 이루어진 블록이 있고, 이들이 모두 100과 같다고 가정해 봅시다. CPU가 hist에 필요한 수정을 비순차적으로 수행할 수 있습니까?


힌트 2:

image.data의 원소가 동일한 긴 연속 구간이 있으면, 증가 연산에는 이전 값을 알아야 하므로(즉, 앞선 모든 증가 연산이 완료되어야 하므로) CPU는 hist에 대한 이 명령어들을 순서대로 처리할 수밖에 없습니다.


힌트 3:

긴 파이프라인을 더 작은 청크로 나누어, image.data의 연속된 동일 원소 때문에 순차 실행이 강제될 가능성을 줄여 보십시오.


풀이:

배경:

벤치마크 대상 함수는 다음과 같습니다.

std::array<uint32_t, 256> computeHistogram(const GrayscaleImage& image) {
  std::array<uint32_t, 256> hist;
  hist.fill(0);
  for (int i = 0; i < image.width * image.height; ++i)
    hist[image.data[i]]++;
  return hist;
}

여기서 발생할 수 있는 성능 문제를 이해하려면 CPU 파이프라인이 어떻게 동작하는지, 그리고 현재 코드가 어떻게 문제를 일으킬 수 있는지 이해해야 합니다.

최신 CPU에서 명령어가 파이프라인에서 처리되는 방식을 단순화하여 보면 다음과 같습니다.

  1. Instruction Fetch - CPU가 다음에 실행할 명령어를 가져옵니다
  2. Instruction Decode - 이어서 CPU가 이 명령어를 자신이 이해할 수 있는 형태로 디코딩합니다
  3. Execute - 명령어가 실행됩니다
  4. Memory Access(메모리 접근) - 메모리에 접근합니다
  5. Write Back - 명령어의 결과가 확정되고 커밋(retired)됩니다

현대 CPU는 순차(In-Order) 실행과 비순차(Out-of-Order, OOO) 실행을 모두 지원합니다. 전자에서는 명령어가 엄격하게 프로그램 순서대로 실행되는 반면, 비순차 실행에서는 CPU가 (프로그램 순서상) 앞선 명령어가 완료되기 전에 후속 명령어의 파이프라이닝과 실행을 시작할 수 있습니다. OOO 실행은 뒤에 오는 연산을 미리 시작해 먼저 끝냄으로써 눈에 띄는 성능 향상을 가져올 수 있습니다.

그러나 OOO 실행에는 제약이 있습니다. CPU는 OOO로 실행하는 동안에도 그렇지 않았을 때와 정확히 같은 결과를 내야 합니다. 따라서 어떤 명령어의 실행이 앞선 명령어의 결과에 대한 의존성으로 제약을 받는다면, 그 명령어는 진행되어서는 안 됩니다. 이는 또한 CPU가 언제 실행했는지와 관계없이 모든 연산이 프로그램 순서대로 retire되어야 한다는 뜻이기도 합니다.

이러한 제약을 파이프라인 해저드(pipeline hazards)라고 합니다. 여기서 풀고 있는 이 실습과 관련된 해저드는 데이터 해저드(data hazards)라고 합니다. 이는 명령어 사이에 읽기 및 쓰기 의존성이 있는 경우를 말합니다.

위 코드 조각의 배열 채우기 패턴으로 돌아가 보면 다음과 같습니다.

for (int i = 0; i < image.width * image.height; ++i)
    hist[image.data[i]]++;

image.data의 요소들이 동일한 값으로 길게 연속되는 구간을 만나면 문제가 생긴다는 것을 알 수 있습니다. 예를 들어, image.data 배열에 서로 인접한 열 개의 요소로 이루어진 블록이 있고 그 값이 모두 100이라고 가정해 봅시다. CPU가 hist에 필요한 수정을 비순차적으로 수행할 수 있겠습니까?

답은 '아니요, 할 수 없습니다'입니다. "hist[100]의 메모리 값을 증가시키는" 명령어가 여러 개 있습니다. 루프의 한 반복에서 hist[100]에 수행되는 쓰기 연산은 hist[100]의 어떤 값을 증가시켜야 하는지 알아야 하는데, 이전 반복이 retire된 이후에야 그 값을 알 수 있습니다. 결국 이는 순차 CPU 명령어 파이프라인에 가까운 형태로 퇴화하며, 후속 반복의 명령어들은 앞선 명령어들이 retire될 때까지 기다려야 합니다.

이론을 정리했으니 이제 성능 분석으로 돌아갈 수 있습니다. 다음은 원래 코드에 대한 perf 출력의 예입니다.

-----------------------------------------------------
Benchmark           Time             CPU   Iterations
-----------------------------------------------------
bird/0           85.5 us         85.5 us        32819
coins/1          39.1 us         39.1 us        72406
pepper/2         32.4 us         32.4 us        86228
pixabay/3        14.6 ms         14.6 ms          193

해결책

hist[x]의 증가 연산을 더 작고 독립적인 하위 배열로 나누고, 그 중간값들을 마지막에 단순히 합산하는 방식으로 이 파이프라인 해저드의 영향을 줄일 수 있습니다. 코드는 다음과 같습니다.

std::array<uint32_t, 256> computeHistogram(const GrayscaleImage& image) {
  std::array<uint32_t, 256> hist1{};
  std::array<uint32_t, 256> hist2{};
  std::array<uint32_t, 256> hist3{};
  std::array<uint32_t, 256> hist4{};

  int i = 0;
  for (; i + 3 < image.width * image.height; i+=4) {
    hist1[image.data[i]]++;
    hist2[image.data[i+1]]++;
    hist3[image.data[i+2]]++;
    hist4[image.data[i+3]]++;
  }

  for (; i < image.width * image.height; i++) {
    hist1[image.data[i]]++;
  }

  for (int j = 0; j < hist1.size(); ++j) {
    hist1[j] += hist2[j] + hist3[j] + hist4[j];
  }
  return hist1;
}

루프를 네 개 단위의 청크로 나누고, 네 개의 히스토그램에서 각각 해당하는 인덱스를 증가시킵니다. 이 배열들은 스택 기반 배열이므로 메모리가 매우 가깝고 그만큼 빠르기 때문에, hist 요소에 무작위로 접근해도 괜찮다는 점에 유의하십시오.

앞의 네 개 단위 블록에서 처리되지 않고 남은 요소가 있다면, hist1에 대해 최대 세 번의 증가 연산을 추가로 수행하면 됩니다.

마지막으로 결과를 합산합니다.

생성된 어셈블리 코드를 분석해 보면(-O3 최적화로 컴파일), 마지막 루프에서 매우 좋은 점을 발견할 수 있습니다.

루프:

  for (int j = 0; j < hist1.size(); ++j) {
    hist1[j] += hist2[j] + hist3[j] + hist4[j];
  }

어셈블리:

.L8:
    vmovdqu (%rax,%rbx), %ymm0
    vpaddd  (%rcx,%rax), %ymm0, %ymm0
    vpaddd  (%r12,%rax), %ymm0, %ymm0
    vpaddd  0(%r13,%rax), %ymm0, %ymm0
    addq    $32, %rax
    vmovdqu %ymm0, -32(%rax,%rbx)
    cmpq    $1024, %rax
    jne .L8

컴파일러가 우리의 루프를 자동 벡터화했습니다! YMM 레지스터(256비트)를 사용하여 hist[i] 배열에 저장하는 uint32_t 객체에 대해 256 / 32 = 8개의 덧셈을 동시에 수행할 수 있으므로, SIMD를 통해 큰 성능 이점을 얻을 수 있습니다.

벤치마크 결과, (반복 횟수가 더 많은 경우에도) 실행 시간이 줄어들어 성능이 개선되었음을 확인할 수 있습니다:

-----------------------------------------------------
Benchmark           Time             CPU   Iterations
-----------------------------------------------------
bird/0           67.2 us         67.2 us        41713
coins/1          32.2 us         32.2 us        86758
pepper/2         28.3 us         28.3 us        98598
pixabay/3        12.9 ms         12.9 ms          218

해결책 코드(링크):

해결책 링크

  1. https://en.wikipedia.org/wiki/Grayscale↩︎

  2. https://en.wikipedia.org/wiki/Binary_image↩︎

  3. https://en.wikipedia.org/wiki/Otsu%27s_method↩︎