안녕하세요, 지난 시간에 이어서 Control Hazard에 대해서 알아보도록 하겠습니다.
Control Hazard는 파이프라인 구조에서 분기 명령어나 조건부 명령어의 결과가 결정되기 전까지
다음에 실행할 명령어를 예측할 수 없는 상황에 발생하는 문제를 의미합니다.
쉽게 말해서, CBZ와 같은 분기 명령어를 만났을 때, CBZ가 가르키는 주소로 분기를 하게 되고 파이프라인은
잘못된 명령어를 fetch하게 되면서 파이프라인의 성능을 저하시킬 수 있습니다.
파이프라인의 성능 저하의 예를 들자면, pipeline stall이나 Mispredicted Branch(잘못된 분기 예측)으로 인해서
분기 명령어의 결과가 결정되기 전까지 파이프라인을 대기시키거나, 이미 가져온 명령어들을 Flush하기 때문에
사이클을 낭비하는 문제가 발생해 성능을 저하시킬 수 있습니다.
그렇다면 해당 문제를 해결할 수 있는 방법은 무엇이 있을까요?
첫 번째 방법으로, ID Stage에서 분기를 실행하지 말지 결정하는 것 입니다.
ID Stage에서 분기를 실행할지 말지 결정하는 방법에는 Target address adder와 Register comparator를 이용하는 것 입니다.
Target address adder는 분기 명령어가 발생할 경우, 분기할 목표 주소를 계산하는 하드웨어입니다.
PC와 offset을 더해 분기할 주소를 계산해서 분기 여부가 빠르게 결정될 수 있습니다.
보통 EX단계까지 가야 CBZ의 목표 주소가 계산되기 때문에 미리 계산할 수 있다면,
pipeline stall을 예방하고 pipeline의 성능을 저하시키는 요인을 예방할 수 있게 됩니다.
Register Comparator의 경우 분기 명령어가 조건에 따라 분기할지 말지 결정될 때 사용되는 방법입니다.
이전에 Instruction에 대해서 배울 때, Conditional Branch에 대해서 배웠던 것을 기억하실겁니다.
Conditional Branch의 경우 N,Z,C,V의 조건 플래그를 가지고 있는 Register의 값을 가지고
분기할지 말지 결정하기 때문에 미리 레지스터 비교기를 가지고 분기할지 말지 결정하게 되는 것 입니다.
예를 들어서, CBZ 명령어의 경우, 특정 레지스터 값이 0인지 여부만 확인하면 되기 때문에
단순 비교기가 필요합니다. B.EQ의 경우에는 NZCV 조건플래그 레지스터에서 Z 플래그가
1인지 확인해 두 레지스터가 같은지 판단한 후, 분기 할지 말를 결정합니다.
만약 위의 예시로 보자면, branch를 ID단계에서 찾아내고, AND명령어를 Flush해야 합니다.
Flush는 잘못된 명령어를 제거하고, 파이프라인을 정리하여 올바른 명령어로 재시작할 수 있도록 도와줍니다.
Flush는 기존의 명령어를 NOP명령어로 대체하여 플러시가 이루어질 수 있도록 해주는 것 입니다.
Dynamic Branch Prediction
Dynamic Branch Prediction은 파이프라인의 성능 최적화를 위해 분기 명령어의 결과를 동적으로 예측하는 방법입니다.
Deeper pipeline과 superscalar pipeline을 사용한 경우, CPU의 성능을 향상할 수 있지만,
복잡해짐에 따라서 Control Hazard의 영향을 더 많이 받게 됩니다.
Deeper pipeline은 파이프라인 단계의 수를 늘려 각 단계에서 수행되는 작업을 더 세밀하게 나누게 됩니다.
예를 들어서, fetch, decode, execute, memory, write back을 더 세밀하게 나누는 방식입니다.
Deeper pipeline의 경우 세부하게 나뉘어서 각 단계를 더 빠르게 실행할 수 있어서 clock speed를 높일 수 있습니다.
Superscalar pipeline의 경우 한 번에 여러 개의 명령어를 동시에 실행할 수 있도록 파이프라인 내부에
여러 개의 ALU등을 두는 방식입니다. 이는 Instruction Level Parallelism(ILP)을 극대화해 성능을 높일 수 있습니다.
두 pipeline의 차이점으로 deeper pipeline은 명령어를 더 세밀하게 나눠 더 높은 클록속도를 추구하는 것이고,
superscalar pipeline은 동일한 클록 사이클에 여러 명령어를 동시에 실행해 명령어 처리량(Throughput)을 증가시키는 것 입니다.
결론적으로, Deeper pipeline과 Superscalar pipeline의 경우에는 분기예측에 따라 성능이 달라지기 때문에
Dynamic Branch Prediction을 통해 static prediction보다 dynamic branch prediction을 사용하게 됩니다.
이제 dynamic branch prediction에 대해서 더 자세히 살펴보도록 하겠습니다.
우선 분기 명령어 실행 과정에서의 Dynamic Prediction은 분기 명령어가 파이프라인에 들어오면,
Branch Prediction Buffer를 참조해 해당 분기 명령어가 과거에 동작했는지를 기반으로 예측합니다.
예측 결과가 taken이라면 target address에서 명령어를 가져오기 시작합니다.
만약에 not taken이라면 다음 명령어를 fall-through 주소에서 가져오게 됩니다.
만약에 예측이 실패했다면, 파이프라인을 Flush하여 잘못 가져온 명령어들을 제거하게 됩니다.
그리고 Brnach Prediction Buffer의 예측 결과를 반대(Flip)로 바꾸고, 다음에 동일한 분기 명령어가
실행될 때 더 나은 예측을 할 수 있게 하며, 1bit predictor와 2bit predictor를 사용하게 됩니다.
1bit predictor
1-bit predictor는 바로 이전 결과를 통해서 예측하는 predictor입니다.
예를 들어서, 이전에 했던 branch 예측이 Not Taken으로 예측했다면 다음 branch 또한 Not Taken으로 예측하는 것 입니다.
즉, $for(int i = 1; i <= 10; i++) {...}$를 생각해보자면, 처음에 Taken인지 Not Taken인지 결정하고 난 이후에,
T(Taken), T, T, T, T, T, T, T, T, T, N(Not Taken), N, ....
위와 같은 방식으로 예측하게 됩니다. 해당 예측에서는 loop이 시작되는 첫 번째에서 Taken인지 Not Taken인지
결정하는 것과 마지막에 loop을 벗어나기 직전에 예측하는 것에서 틀린 예측을 수행하게 됩니다.
1bit predictor는 이중loop과 같은 곳에서는 현저히 낮은 예측률을 갖게 됩니다.
그 이유는 각 for문에서 서로 다른 예측을 기록하게 된다면, NTNTNTNT와 같은 방식으로 엇갈리면서 최악의 경우,
예측률은 0%가 되게 됩니다.
위의 예측에 대해서 state diagram을 그려서 직관적으로 이해해보자면 아래와 같습니다.
원래 Moore Machine으로 표현하지만, Mealy Machine으로 설계된 것 또한 표현해본 것 입니다.
2bit predictor
1bit predictor의 경우, 하나의 지난 예측을 기준으로 예측하게 되기 때문에 오류가 발생할 가능성이 높습니다.
실제로 일상에서도 이전 하나의 경우만 가지고 예측을 하는 경우는 없다고 생각합니다.
그래서 좀 더 정확한 예측을 위해서 2bit predictor를 이용하는데, 이는 이전 2번의 예측 결과를 이용하는 것 입니다.
2bit predictor이기 때문에, 총 4개의 state가 존재합니다.
11은 strongly taken, 10 weakly taken, 00 strongly not taken, 01 weakly not taken
위의 내용으로 State diagram을 그려 직관적으로 알아보면 다음과 같습니다.
마지막으로, predictor가 있더라도 taget address를 계산이 필요하고, 계산을 위한 1 cycle penalty가 존재하게 됩니다.
여기서 1 cycle penalty를 해결하기 위한 방법으로 BTB(Branch Target Buffer)를 사용하면,
분기 예측이 성공했을 때 해당 목표 주소를 즉시 제공할 수 있어 지연 시관을 최소화할 수 있습니다.
BTB는 branch prediction이 taken으로 예측될 경우, 파이프라인은 BTB에서 미리 cache된 목표 주소를
가져와 해당 주소에서 명령어를 fetch하게 됩니다.
BTB index는 보통 현재 명령어의 PC값을 사용해 목표 주소를 빠르게 찾습니다.
BTB에는 Hit와 Miass라는 개념이 있습니다.
Hit는 BTB에 해당 분기 명령어의 목표 주소가 BTB에 존재하며, 그 주소에서 명령어를 즉시 가져와 실행합니다.
Miss는 BTB에 해당 분기 명령어가 없다면, 파이프라인은 목표 주소를 직접 계산해야 하고, 이 과정에서 지연이 발생합니다.
만약 분기 예측 실패하게 된다면 파이프라인은 Flush를 수행해 명령어를 제거하고 BTB의 기록을 업데이트 합니다.
지금까지 Control hazard에 대해서 살펴봤습니다.
다음 시간에는 memory(cache)에 대해서 알아보도록 하겠습니다.
감사합니다.
출처
Instruction pipelining - Wikipedia
From Wikipedia, the free encyclopedia Method of improving instruction-level parallelism Basic five-stage pipeline Clock cycleInstr. No. 1 2 3 4 5 6 7 1 IF ID EX MEM WB 2 IF ID EX MEM WB 3 IF ID EX MEM WB 4 IF ID EX MEM 5 IF ID EX (IF = Instruction Fetch, I
en.wikipedia.org
- superscalar pipeline: https://en.wikipedia.org/wiki/Superscalar_processor
Superscalar processor - Wikipedia
From Wikipedia, the free encyclopedia CPU that implements instruction-level parallelism within a single processor "Superscaler" redirects here. For the Sega arcade system board, see Sega Super Scaler. Simple superscalar pipeline. By fetching and dispatchin
en.wikipedia.org
'전자전기공학 > 컴퓨터구조' 카테고리의 다른 글
| [컴퓨터구조][cache#2] (0) | 2024.10.25 |
|---|---|
| [컴퓨터구조][Cache] (0) | 2024.10.16 |
| [컴퓨터구조][Hazards #1 Data Hazard] (0) | 2024.10.11 |
| [컴퓨터구조][CPU#3 Pipelining기본] (1) | 2024.10.02 |
| [컴퓨터구조][CPU#2 Single Cycle CPU, Dual Port SRAM] (4) | 2024.10.01 |