데이터 의존성 체인 가속하기 #1.

범용 애플리케이션의 성능에서는 핵심 데이터 의존성 체인이 점점 더 유일하게 중요한 요소가 되어 가고 있습니다. 그렇기 때문에 이러한 체인을 식별하고 더 빠르게 실행할 수 있는 방법을 알아 두는 것이 매우 중요합니다. 소프트웨어 수준에서는 애초에 존재하지 말았어야 할 인위적인 데이터 의존성을 가끔 만들어 넣는 경우가 있습니다. 이러한 경우는 대개 쉽게 찾을 수 있습니다. 반면에 일부 데이터 의존성 체인은 특정 유형의 자료 구조에 본질적으로 내재되어 있습니다.

아아, 정겨운 연결 리스트여... 연결 리스트를 순회하는 것은 본질적으로 기이이이이이이일고 긴 데이터 의존성 체인입니다. 노드 N+1을 얻으려면 먼저 노드 N을 가져와야 합니다. 메모리 지역성 문제를 제쳐 두더라도 의존성 체인은 사라지지 않습니다. 데이터 의존성은 사실상 실행을 직렬화하여 ILP(Instruction-Level Parallelism, 명령어 수준 병렬성)를 매우 낮게 만듭니다.

이 실습 과제의 과제는 연결 리스트 A의 모든 값을 연결 리스트 B에서 찾는 것입니다. 이는 O(N^2) 알고리즘이며 포인터 추적(pointer chasing)이 많이 발생합니다. 두 연결 리스트 모두 아레나 할당자를 사용하여 개별 노드를 서로 바로 옆에 배치하므로 메모리 지역성이 향상됩니다. 이 실습 과제에서 벤치마크의 성능을 더욱 향상시키려면 여러 의존성 체인의 실행을 겹쳐야 합니다.

이 실습의 아이디어는 @ibogosavljevic이 제안했습니다.

힌트

힌트 1:

연결 리스트의 n번째 노드는 n-1번째 원소보다 먼저 접근할 수 없으며, 그 원소는 다시 n-2번째 원소를 필요로 하는 식으로 이어집니다. 이 의존성 체인은 끊을 수 없지만, 이를 더 잘 처리할 수 있는 방법을 생각해 볼 수 있겠습니까?


힌트 2:

알고리즘에서 List A의 모든 노드를 List B의 모든 노드와 비교한다는 점에 주목하십시오. 이러한 비교를 더 효율적으로 수행하는 방법을 찾을 수 있겠습니까?


힌트 3:

List A의 여러 노드를 묶고 각 배치를 list B의 각 노드와 비교해 보십시오. 어떤 배치 크기에서 성능이 가장 크게 향상되며, 이론적으로 왜 그런지 생각해 볼 수 있겠습니까?


풀이:

배경:

코드의 의존성 체인은 성능 병목으로 이어질 수 있습니다. 의존성 체인이란 새로운 작업을 완료하기 전에 반드시 먼저 수행되어야 하는 코드 부분을 말합니다. 즉, 새로운 작업은 이전 체인에 의존성을 가집니다. 이는 작업 흐름을 병렬화할 수 없게 만들기 때문에 문제가 될 수 있습니다.

실습의 문제를 살펴봅시다. 연결 리스트의 모든 노드를 하나씩 꺼내 다른 리스트에서 같은 값을 가진 노드를 찾는 이차 시간 알고리즘이 있습니다.

이 문제의 의존성 체인은 꽤 분명합니다. 연결 리스트의 n번째 노드는 n-1번째 요소보다 먼저 접근할 수 없고, n-1번째 요소는 다시 n-2번째 요소를 필요로 하며, 이런 식으로 계속 이어집니다.

다음은 원본 코드를 실행한 성능 보고서의 예시입니다.

-----------------------------------------------------
Benchmark           Time             CPU   Iterations
-----------------------------------------------------
bench1           85.5 ms         85.4 ms           33

해결책

여기서는 의존성 체인을 끊을 방법이 없으므로 더 효율적인 전략을 생각해야 합니다. 리스트 A의 모든 노드를 리스트 B의 노드들과 비교한다는 점을 고려하면, B의 각 노드를 방문할 때마다 A의 노드 묶음을 비교하는 편이 더 나은 접근법입니다. 이렇게 하면 A에서 노드 집합을 가져와 B의 모든 노드에서 그 항목들을 루프로 순회합니다. 이런 방식으로 리스트 A의 노드 N과 N+1을 연결 리스트 B와 비교하는 시점 사이의 시간 간격을 줄여 의존성 체인의 영향을 줄일 수 있습니다.

루프 반복마다 처리할 A의 노드 수를 매개변수로 받는 템플릿 버전의 해답 함수를 만들 수 있습니다.

template<int N>
unsigned solution(List *l1, List *l2) {
    ...
}

먼저 리스트 l1의 길이를 셉니다.

List* head1 = l1;
int length1 = 0;
while (head1 != nullptr) {
    length1++;
    head1 = head1->next;
}

그다음 크기가 N인 청크를 l2의 각 노드와 비교하고, l2에서 N개의 값을 모두 찾으면 크기가 N인 다음 청크로 일찍 넘어갑니다.

  unsigned retVal = 0;
  List* head2 = l2;

  // Process in chunks
  for (int i = 0; i < length1 / N; i++) {
    std::array<unsigned, N> arr{};
    for (int j = 0; j < N; j++) {
      arr[j] = l1->value;
      l1 = l1->next;
    }
    int seen = 0;
    l2 = head2;
    while (l2) {
      int v = l2->value;
      for (int j = 0; j < N; j++) {
        if (arr[j] == v) {
          retVal += getSumOfDigits(v);
          if (++seen == N) {
            break;
          }
        }
      }
      l2 = l2->next;
    }
  }

빠짐없이 처리하려면 앞선 N 크기 블록에서 처리되지 않은 l1의 나머지 요소도 처리해야 합니다.

  // process any remaining elements in l1 (<N elements)
  while (l1) {
    unsigned v = l1->value;
    l2 = head2;
    while (l2) {
      if (l2->value == v) {
        retVal += getSumOfDigits(v);
        break;
      }
      l2 = l2->next;
    }
    l1 = l1->next;
  }

탐색할 노드 블록의 크기는 어느 정도가 적절하겠습니까? 이는 여러분의 컴퓨터에서 직접 시험해 보아야 하지만, 연결 리스트가 아레나 할당자를 통해 메모리에 할당된다는 점에 주목하십시오. 즉, 요소들이 연속된 메모리에 서로 인접해 있습니다. CPU는 한 번에 캐시 라인 하나씩 불러오므로, 메모리에서 첫 번째 노드를 불러오면 인접한 노드 여러 개도 함께 불러오게 됩니다. 구조체 List의 크기는 16입니다(크기가 8인 포인터와 크기가 8인 unsigned int).

struct List {
  List *next;
  unsigned value;
};

x86 시스템에서 캐시 라인의 너비는 64바이트입니다. 따라서 한 번에 List 포인터 4개씩 블록으로 처리하는 것에서 시작하는 것이 합리적입니다. 이 포인터들이 가리키는 메모리 영역이 캐시 라인 하나와 같기 때문입니다.

N = 4를 사용하면 벤치마크에서 뚜렷한 개선이 나타납니다. 절반의 시간에 두 배의 반복을 수행합니다!

-----------------------------------------------------
Benchmark           Time             CPU   Iterations
-----------------------------------------------------
bench1           34.7 ms         34.7 ms           78

해결책 코드(링크):

해답 링크