add carry 연산은 (오버플로가 발생할 수 있기 때문에) 컴파일러가 이 코드를 벡터화하기 어렵게 만듭니다. 이 문제를 해결하는 일반적인 접근 방식은 루프에서 사용하는 누산기의 폭을 넓히는 것입니다. 여기서는 acc에 uint16_t를 사용하고 있습니다. 캐리와 덧셈 사이의 의존성을 끊기 시작하려면 이를 어떻게 바꿀 수 있겠습니까?

acc에 uint32_t를 사용해 보십시오. 이렇게 하면 사실상 16비트 정수 두 묶음(즉, "기존" accs 두 개)을 한 번에 누적할 수 있습니다.

오버플로는 신중하게 처리해야 합니다. 한 번에 처리하는 blob의 원소 개수(즉, 정수 배치)를 제한하여, 이 배치 안에서 acc에 오버플로가 두 번 이상 발생하지 않도록 해 보십시오. 그렇게 하지 않으면 하위 16비트와 상위 16비트 모두에서 오버플로가 발생할 수 있으며, blob을 나누어 소비하면서 주기적으로 오버플로를 확인하지 않으면 이를 놓칠 수 있습니다.

최종 결과를 얻으려면 상위와 하위 16비트 정수를 합쳐야 한다는 점(그리고 그 연산으로 인해 생기는 오버플로도 처리해야 한다는 점!)을 잊지 마십시오.

배경:

이 실습은 데이터 집합의 체크섬을 계산하는 기본 알고리즘을 바탕으로 합니다. 체크섬은 널리 사용되며, 대표적인 예로 네트워킹을 들 수 있습니다. 체크섬은 페이로드의 데이터로부터 생성되며, 해당 데이터를 받는 쪽에서 패킷 안의 데이터를 검증하는 한 단계로 사용합니다.

코드는 매우 단순합니다.

uint16_t checksum(const Blob &blob) {
  uint16_t acc = 0;
  for (auto value : blob) {
    acc += value;
    acc += acc < value; // add carry
  }
  return acc;
}

어셈블리를 살펴보면(-O3로 컴파일함) 다음과 같습니다.

checksum(std::array<unsigned short, 1024ul> const&):
        lea     rdx, [rdi+2048]
        xor     eax, eax
.L8:
        add     ax, WORD PTR [rdi]
        adc     ax, 0
        add     rdi, 2
        cmp     rdi, rdx
        jne     .L8
        ret

컴파일러가 루프 안의 두 덧셈에 대해 두 개의 명령어를 생성했음을 알 수 있습니다. 하나는 value를 ax 레지스터에 더하는 일반적인 add이고, 다른 하나는 캐리 덧셈(add carry)인 adc 명령어입니다. 본질적으로 이 명령어는 바로 앞 줄(acc += value)에서 acc에 부호 없는 정수 오버플로가 발생했다면 acc의 값에 1을 더합니다.

다음은 원본 코드의 벤치마크 실행 결과입니다.

-----------------------------------------------------
Benchmark           Time             CPU   Iterations
-----------------------------------------------------
bench1           33.4 us         33.3 us        83412

두 번째 덧셈의 수행 여부가 첫 번째 연산의 결과에 의존하므로, 이 의존성 때문에 이 코드는 쉽게 벡터화할 수 없습니다. 이 둘을 분리할 방법을 찾아야 합니다.

해결책

벡터화와 관련된 대부분의 문제와 마찬가지로, 더 많은 연산을 수행할 수 있도록 누산기의 크기를 넓히는 방법을 찾아야 합니다. 이 경우에는 16비트 대신 32비트 부호 없는 정수를 사용할 수 있습니다. 이렇게 하면 사실상 acc를 두 개 누적하는 효과를 얻을 수 있습니다. 하나는 하위 16비트에, 다른 하나는 상위 16비트에 누적됩니다. 그런 다음 각 데이터 청크의 처리가 끝날 때마다 32비트 정수의 오버플로를 추적하고, 캐리 값을 한 번만 더합니다.

코드를 수정해 봅시다. 먼저 acc를 uint32_t로 설정해야 합니다.

uint32_t acc = 0;

다음으로, 덧셈 청크 하나당 32비트 오버플로가 최대 한 번만 발생하도록 하면서 blob의 정수를 청크 단위로 가능한 한 많이 더하려고 합니다. 이는 꽤 쉽게 달성할 수 있습니다. blob에서 만날 수 있는 가장 큰 값은 2¹⁶ - 1이므로, 한 번에 2¹⁶ - 1개를 넘는 수를 처리하지 않는다면 32비트 누산기에서 오버플로가 두 번 이상 발생하지 않습니다.

따라서 루프에 청크를 도입합니다.

constexpr size_t chunk_size = (1 << 16);
for (size_t i = 0; i < N; i += chunk_size) {
    for (size_t j = i; j < i + chunk_size && j < N; j++) {
        ...
    }
}

이제 매 루프 반복마다 덧셈 캐리 연산을 확인하는 대신, 각 청크를 처리한 후에 확인합니다. 이를 위해 매 반복이 끝난 뒤 이전 반복에서 acc의 값이 무엇이었는지 기억해 두고, 이를 acc의 새 값과 비교해야 합니다. acc가 이전 루프가 끝났을 때의 값보다 작다면 부호 없는 정수 오버플로가 발생했다는 것을 알 수 있으므로, acc를 1만큼 증가시킵니다.

constexpr size_t two_pow_16 = (1 << 16);
uint32_t acc = 0, prev = 0;
for (size_t i = 0; i < N; i += two_pow_16) {
    for (size_t j = i; j < i + two_pow_16 && j < N; j++) {
        acc += blob[j];
    }
    if (acc < prev) {
        acc++;
    }
    prev = acc;
}

누적을 마쳤으면 이제 acc의 상위 16비트와 하위 16비트를 합쳐 최종 답을 구할 차례입니다.

uint16_t top = acc >> 16;
uint16_t bottom = acc & (two_pow_16 - 1);
uint16_t ans = top + bottom;
ans += ans < top;
return ans;

이 합 자체도 오버플로가 발생할 수 있으므로, 오버플로가 발생하면 답에 1을 추가로 더합니다. ans를 top과 bottom 중 어느 것과 비교하든 상관없다는 점에 유의하십시오.

다음은 최종 코드입니다.

uint16_t checksum(const Blob& blob) {
  constexpr std::size_t two_pow_16 = 1 << 16;
  uint32_t acc = 0, prev = 0;
  for (std::size_t i = 0; i < N; i += two_pow_16) {
    for (std::size_t j = i; j < i + two_pow_16 && j < N; j++) {
      acc += blob[j];
    }
    if (acc < prev) {
      acc++;
    }
    prev = acc;
  }
  uint16_t top = acc >> 16;
  uint16_t bottom = acc & (two_pow_16 - 1);
  uint16_t ans = top + bottom;
  ans += ans < top;
  return ans;
}

성능 보고서를 보면 이 방식이 거의 10배나 빠릅니다!

------------------------------------------------------------------
Benchmark                        Time             CPU   Iterations
------------------------------------------------------------------
bench1/iterations:83000       3.61 us         3.61 us        83000