조건부 이동이 분기 예측 실패에 취약하지 않은 이유는 무엇입니까?

조건부 이동이 분기 예측 실패에 취약하지 않은 이유는 무엇입니까?

---

이 게시물 (StackOverflow에 대한 답변) (최적화 섹션)을 읽은 후 조건부 이동이 분기 예측 실패에 취약하지 않은 이유가 궁금합니다. cond move 에 대한 기사를 찾았습니다 (AMD의 PDF) . 또한 그들은 cond의 성능 이점을 주장합니다. 이동합니다. 그런데 왜 그렇습니까? 나는 그것을 보지 않는다. 해당 ASM 명령어가 평가되는 순간 이전 CMP 명령어의 결과는 아직 알려지지 않았습니다.

---

잘못 예측 된 분기는 비싸다

최신 프로세서는 일반적으로 문제가 해결되면 매 사이클마다 1 ~ 3 개의 명령어를 실행합니다 (이 명령어가 이전 명령어 또는 메모리에서 도착하기 위해 데이터 종속성을 기다리는 동안 지연되지 않는 경우).

위의 문장은 타이트한 루프에 대해 놀랍게도 잘 유지되지만, 이것은 사이클이 올 때 명령이 실행되는 것을 막을 수있는 하나의 추가 종속성에 눈을 멀게하지 않아야합니다. 명령이 실행 되려면 프로세서가 페치 및 디코딩을 시작해야합니다. 그것은 15-20주기 전에.

프로세서가 분기를 만나면 어떻게해야합니까? 두 대상을 모두 가져오고 디코딩하는 것은 확장되지 않습니다 (더 많은 분기가 뒤 따르면 기하 급수적 인 경로 수를 병렬로 가져와야합니다). 따라서 프로세서는 추측 적으로 두 가지 중 하나만 가져오고 디코딩합니다.

이것이 잘못 예측 된 분기가 비용이 많이 드는 이유입니다. 효율적인 명령 파이프 라인으로 인해 일반적으로 보이지 않는 15-20 사이클의 비용이 듭니다.

조건부 이동은 결코 비싸지 않습니다.

조건부 이동은 예측이 필요하지 않으므로이 패널티를 가질 수 없습니다. 일반 명령어와 마찬가지로 데이터 종속성이 있습니다. 사실, 조건부 이동은 데이터 종속성이 "조건 참"및 "조건 거짓"케이스를 모두 포함하기 때문에 일반 명령보다 더 많은 데이터 종속성을 갖습니다. 조건부로 r1로 이동하는 명령 이후 r2의 내용은 r2의 이전 값 r2과에 모두 의존하는 것 같습니다 r1. 잘 예측 된 조건부 분기를 사용하면 프로세서가 더 정확한 종속성을 추론 할 수 있습니다. 그러나 데이터 종속성이 도착하는 데 시간이 필요한 경우 일반적으로 도착하는 데 1-2주기가 걸립니다.

메모리에서 레지스터로 조건부 이동은 때때로 위험한 내기 일 수 있습니다. 메모리에서 읽은 값이 레지스터에 할당되지 않는 조건이면 메모리에서 아무것도 기다린 것입니다. 그러나 명령어 세트에서 제공되는 조건부 이동 명령어는 일반적으로 레지스터에 등록되어 프로그래머가 이러한 실수를 방지합니다.

---

그것은 모두 명령 파이프 라인 에 관한 것 입니다. 최신 CPU는 파이프 라인에서 명령어를 실행하므로 CPU가 실행 흐름을 예측할 수있을 때 성능이 크게 향상됩니다.

cmov

    add     eax, ebx
    cmp     eax, 0x10
    cmovne  ebx, ecx
    add     eax, ecx

---

해당 ASM 명령이 평가되는 순간 이전 CMP 명령의 결과는 아직 알려지지 않았습니다.

아마도 CPU cmov는 cmp및 cmov명령 의 결과에 관계없이 다음 명령 이 바로 실행될 것임을 여전히 알고 있습니다 . 따라서 다음 명령어는 분기의 경우가 아닌 미리 안전하게 가져 오거나 디코딩 할 수 있습니다.

다음 명령은 실행하기 전에 실행할 수도 있습니다 cmov(제 예에서는 안전합니다)

분기

    add     eax, ebx
    cmp     eax, 0x10
    je      .skip
    mov     ebx, ecx
.skip:
    add     eax, ecx

이 경우 CPU의 디코더가 인식 je .skip하면 1) 다음 명령에서 명령을 프리 페치 / 디코딩 할 것인지 또는 2) 점프 대상에서 계속할지 여부를 선택해야합니다. CPU는이 순방향 조건 분기가 발생하지 않을 것이라고 추측하므로 다음 명령 mov ebx, ecx이 파이프 라인으로 이동합니다.

몇 사이클 후에 je .skip가 실행되고 분기가 수행됩니다. 젠장! 이제 우리의 파이프 라인은 실행해서는 안되는 임의의 정크를 보유합니다. CPU는 캐시 된 모든 명령어를 플러시하고에서 새로 시작해야 .skip:합니다.

이는 cmov실행 흐름을 변경하지 않기 때문에 발생 하지 않는 잘못 예측 된 분기의 성능 저하 입니다.

---

실제로 결과는 아직 알려지지 않았지만 다른 상황이 허용하는 경우 (특히 종속성 체인) cpu는 cmov. 관련된 분기가 없기 때문에 이러한 명령은 어떤 경우에도 평가되어야합니다.

이 예를 고려하십시오.

cmoveq edx, eax
add ecx, ebx
mov eax, [ecx]

다음의 두 명령어 cmov는의 결과에 의존하지 않으므로 자체가 보류 중일 cmov때도 실행할 수 있습니다 cmov(이를 순서에 맞지 않는 실행 이라고 함 ). 실행할 수 없더라도 가져오고 디코딩 할 수 있습니다.

분기 버전은 다음과 같습니다.

    jne skip
    mov edx, eax
skip:
    add ecx, ebx
    mov eax, [ecx]

여기서 문제는 제어 흐름이 변경되고 mov분기가 잘못 예측 된 경우 건너 뛴 명령을 "삽입"할 수 있다는 것을 CPU가 볼만큼 영리하지 않다는 것입니다. 대신 분기 이후에 수행 한 모든 작업을 버리고 다시 시작합니다. 기스로부터. 이것이 벌칙이 발생하는 곳입니다.

---

이것들을 읽어야합니다. Fog + Intel을 사용하면 CMOV 만 검색하면됩니다.

Linus Torvald의 2007 년경 CMOV 비판
Agner Fog의 마이크로 아키텍처 비교
인텔 ® 64 및 IA-32 아키텍처 최적화 참조 설명서

짧은 대답, 올바른 예측은 '무료'이며 조건부 분기 오 예측은 Haswell에서 14-20 사이클의 비용이들 수 있습니다. 그러나 CMOV는 결코 무료가 아닙니다. 여전히 나는 CMOV가 Torvalds가 뛰었을 때보 다 훨씬 낫다고 생각합니다. 모든 프로세서에 대해 모든 시간에 대한 정답은 하나도 없습니다.

---

이 그림은 [Peter Puschner et al.] 슬라이드에서 단일 경로 코드로 변환하고 실행 속도를 높이는 방법을 설명합니다.

참고 URL : https://stackoverflow.com/questions/14131096/why-is-a-conditional-move-not-vulnerable-for-branch-prediction-failure