Speculative execution 대 branchless code

추측 실행과 브랜치리스 코드: 숨겨진 성능 트레이드오프

현대 프로세서는 초당 수십억 개의 연산을 수행하지만, 메모리 접근 속도는 더 느리게 증가하고 있습니다. 이 격차는 데이터를 기다리는 시간이 주요 성능 손실 원인이 됨을 의미합니다. 프로세서는 수동적인 실행기에서 능동적인 데이터 흐름 관리자로 진화했습니다: 비순차 실행, 의존성 재정렬, 그리고 추측 실행이 그 예입니다.

분기 예측은 메모리 지연 시간을 숨기기 위해 로드를 일찍 시작할 수 있게 합니다. 잘못된 예측은 10~20 사이클의 비용이 들지만, L3 또는 DRAM을 기다리는 데는 수백 사이클이 소요됩니다. 브랜치리스 코드는 잘못된 예측을 제거하지만, 프로세서의 추측 능력을 없앱니다.

순차 실행에서 추측 실행으로의 진화

초기 시스템은 명령어를 엄격하게 순차적으로 실행했습니다. IBM System/360 Model 91는 비순차 실행을 위한 토마술로 알고리즘을 도입했습니다: 피연산자가 준비되면 명령어가 시작됩니다.

추측 실행은 나중에 인텔 펜티엄 프로(1995)와 같은 슈퍼스칼라 프로세서에서 등장했습니다. 40개의 마이크로-옵 파이프라인은 수십 개의 명령어를 동시에 처리하며, 이력을 기반으로 분기를 예측합니다.

for (size_t i = 0; i < n; i++) {
    if (arr[i] >= 0) {
          ... code_true ...;
    } else {
        ... code_false ...;
    }
}

여기서, arr[i]를 로드할 때 데이터가 L1에 없으면 10~100+ 사이클의 지연이 발생할 수 있습니다. 프로세서는 분기를 예측하고, code_true를 시작하며, 프리페치를 시작합니다. 잘못된 예측 시—플러시하고 재시작합니다.

브랜치리스 vs 브랜치풀: 캐시 의존성

분기를 사용한 단순화:

if (arr[i] > 0) {
    result++;
}

다음과 같이 변환:

result += (arr[i] > 0);

• 데이터가 L1에 있을 때: 브랜치리스가 승리—잘못된 예측 없음, 최소 지연.
• L2: 중립, 잘못된 예측 비용이 낮음.
• L3/DRAM: 브랜치풀이 더 빠름—추측이 프리페치를 일찍 트리거하여 지연 시간을 숨김.

브랜치리스는 지연을 임계 경로로 이동시킵니다: 프로세서는 계산을 겹치지 않고 비교 전에 데이터를 기다립니다.

값 검색: 무조건 로드의 비용

원본:

Value result = default_value;
for (size_t i = 0; i < n; ++i) {
    if (keys[i] == target) {
        result = values[i];
    }
}
return result;

브랜치리스:

Value result = default_value;
for (size_t i = 0; i < n; ++i) {
    result = (keys[i] == target) ? values[i] : result;
}
return result;

브랜치리스에서는 values[i]가 모든 반복에서 로드되어 전체 배열에 대한 대역폭을 낭비합니다. 원본은 일치할 때까지만 읽습니다.

이진 검색: 의존성 체인

브랜치풀:

while (low < high) {
    size_t mid = low + (high - low) / 2;
    if (keys[mid] < target)
        low = mid + 1;
    else
        high = mid;
}

프로세서는 다음 mid를 추측적으로 계산하고 keys[mid]를 프리페치합니다.

브랜치리스:

while (low < high) {
    size_t mid = low + (high - low) / 2;
    size_t step = (high - low) / 2;
    low  = (keys[mid] < target) ? mid + 1 : low;
    high = (keys[mid] < target) ? high    : mid;
}

비교 결과에 대한 의존성이 추측을 차단합니다: 다음 mid는 low/high 쓰기를 기다립니다.

• 예측의 절반이 틀리지만, 초기 프리페치가 플러시와 겹칩니다.
• 브랜치리스: 더 많은 명령어, 늦은 로드, 명시적인 메모리 지연.

핵심 요약

• 추측은 예측된 분기에서 프리페치를 트리거하여 메모리 지연 시간을 숨깁니다.
• 브랜치리스는 잘못된 예측을 제거하지만 L3/DRAM 접근 시 성능을 악화시킵니다.
• 대상 하드웨어에서 프로파일링: L1—브랜치리스, 큰 배열—브랜치풀.
• 콘솔 게임 포트는 종종 이러한 효과를 무시하여 문제를 겪습니다.
• 브랜치리스 체인의 의존성이 비순차 최적화를 차단합니다.

L1에 무작위 데이터가 있을 때, 브랜치리스가 우세합니다. 패턴이나 대용량 데이터에서는 추측 로드로 인해 브랜치풀이 승리합니다.

— Editorial Team