파이프라인 분기예측과 예측실행

I. 병렬처리를 위한 분기예측의 개요

4단계 파이프라인의 예	분기예측의 개념
	–파이프라인을 통한 명령 실행 중 조건 분기 명령의 실행이 종료될 때까지 다음 명령을 대기하지 않고 분기를 예측 실행하여 파이프라인 처리 성능 저하를 최소화하는 CPU 실행 기술 –다음 실행될 조건문이 어떤 곳으로 분기할 것인지를 확실히 알게 되기 전에 미리 추측하여 실행하여 파이프라인 효율성 확보

분기예측의 개념

–파이프라인을 통한 명령 실행 중 조건 분기 명령의 실행이 종료될 때까지 다음 명령을 대기하지 않고 분기를 예측 실행하여 파이프라인 처리 성능 저하를 최소화하는 CPU 실행 기술

–다음 실행될 조건문이 어떤 곳으로 분기할 것인지를 확실히 알게 되기 전에 미리 추측하여 실행하여 파이프라인 효율성 확보

파이프라인 제어 해저드	-파이프라인 명령어의 실행 순서를 변경하는 Branch, Jump 등 명령어 분기가 발생하면 명령이 실행이 지연되는 파이프라인 해저드가 발생하여 병렬처리 성능 저하
분기예측의 필요성	-다음 실행될 명령어의 분기방향과 분기목적지예측을 통해 명령어를 미리 실행하여 파이프라인 효율성을 확보 -파이프라인 프로세서에서 제어 해저드로 인한 Stall 발생 시 분기예측은 항상 필요

개념	-실행될 파이프라인 조건 분기문의 분기 여부(taken or not taken)를 예측하는 기법
분기 요소	taken	– 주어진 조건 분기문이 분기
분기 요소	not taken	– 주어진 조건 분기문이 분기하지 않음
예측 기법	정적 분기방향예측	-정해진 규칙에 따라 사전에 분기를 지정 ① 모든 분기문을 분기하게 함 (Always taken) ② 모든 분기문을 분기하지 않게 함 (Always not taken) ③ 뒤로 가는 분기문은 분기하고, 앞으로 가는 분기문은 분기하지 않게 함 (BTFNT)
예측 기법	동적 분기방향예측	-프로그램 실행 중 계산 이력에 따라 분기를 동적으로 예측 ① 1단계 BHT(Branch History Table) 이력 기반 예측 ② 2단계 gshare 인덱스 기반 적응적 분기예측 ③ 2가지 이상의 기법을 병행하는 하이브리드 분기예측

개념	-분기문이 어디로 분기할지 목적지(target) PC(Program Counter) 값을 예측하는 기법
분기 요소	무조건 분기	-지정된 분기 목적지 주소로 변경하여 목적지로 지정
	조건 분기	-분기 조건에 따라 직접/간접 분기문의 목적지 예측
	서브루틴 / 함수 호출	-서브루틴의 시작 주소를 PC(Program Counter)에 적재
	서브루틴 / 함수 복귀	-서브루틴 실행 종료 후 최초 호출한 주소로 되돌아감
예측 기법	직접 분기문의 분기목적지 예측	-분기목적지가 명령어에 인코딩 되어 Directed-mapped 형식의 분기목적지 예측 -BTB(Branch Target Buffer)를 통해 분기목적지를 예측
예측 기법	간접 분기문의 분기목적지 예측	-분기 목적지가 레지스터 또는 메모리에 있어 한 번 더 참조 -RAS(Return Address Stack) 이용 함수 리턴 목적지 예측 -콜백함수와 가상함수, jump table 등 다른 분기문의 실행 이력 기반 iBTB(Indirect Branch Target Buffer) 통해 예측


개념	-불확실한 예측 기반 더 나은 성능을 가져오는 방향으로 명령어를 처리하는 기법 -예측에 기반하여 확실하지 않은 명령을 미리 수행하여 결과 값이 예측 값과 다르다면 이미 처리한 명령어를 삭제
필요성	-분기문의 예측 성공 시 파이프라인 제어 해저드 발생에 따른 대기(Stall) 사이클 만큼 명령어 실행 시간을 단축하여 시스템 성능이 크게 향상 -분기예측은 미래에 벌어질 일을 예측하는 것이므로 분기문의 예측 실패에 대응 필요

예측실행에 필요한 장치	미래 예측 장치	-예측에 기반하여 확실하지 않은 명령을 미리 수행하는 장치 -동적/정적 분기예측, 이력 기반 분기예측
	ROB (Reorder Buffer)	-결과가 확실하지 않아도 실행을 계속 진행 시킬 수 있는 장치 -Issue → Execute → Write Result → (Commit) 단계로 진행
	UNDO	-예측이 틀렸을 때 원상태로 복구하는 장치
예측실행 동작원리	분기문 예측실행	-정적/동적 분기방향과, 분기목적지를 예측하여 명령어 실행 -예측 성공 또는 실패 결과에 따라 Commit 또는 UNDO 수행
	예측 성공 시	-실행된 명령어의 결과를 Commit하고 다음 명령어 수행 -분기문의 대기 사이클만큼 실행시간을 단축하여 성능 향상
	예측 실행 시	-실행된 명령어의 결과를 취소하고 원 상태로 복구(UNDO) -예측 실패한 파이프라인 개수만큼 CPU 클럭 주기 낭비

x86 및 일부 ARM 프로세서에서 예측실행으로 인해 이미 실행된 명령을 통해 메모리 참조가 가능한 Meltdown과 Spectre 취약점이 발견되어 보안 패치 등 대응 필요

도리:

김진욱 says:

2022년 6월 1일 at 12:24 오전

분기 예측 실패시 마지막 instruction은 왜 stall이 되는건가요??
- 도리 says:
  
  2022년 6월 1일 at 9:57 오전
  
  어느 부분을 말씀하시는지 확인이 조금 어렵습니다만 파이프라인 제어 해저드에 따른 분기예측의 필요성의 그림에서 Instruction i+2의 Stall이 발생한 이유를 말씀하시는 것이라면, Instruction i에서 분기 방향이 결정되지 않았으므로 분기 방향이 결정될때까지 Instruction 병렬 수행이 불가하고 분기 방향 결정 후 Instruction이 수행되어야 하므로 분기 방향 결정 전까지는 이후 Instruction의 Clock Cycle에 Stall(대기)이 발생합니다. 분기 예측 실패라고 하기는 어렵고 파이프라인 해저드 중 제어 해저드에 따른 Stall(대기) 발생이라고 이해하시면 될 것 같습니다.
  
  혹시 문의하신 의도와 답변이 다르다면 본문의 어느 부분이 궁금하신지 구체적으로 말씀 부탁드려요~