Code Reordering(Instruction Scheduling)
Code Reordering (명령어 스케줄링, Instruction Scheduling)은 하드웨어가 어쩔 수 없이 발생시키는 파이프라인의 거품(Stall)을 소프트웨어(컴파일러)가 똑똑하게 재배치하여 없애버리는 마법입니다.
앞서 우리는 하드웨어에 아무리 훌륭한 Forwarding 회로를 달아도, Load-Use Hazard 앞에서는 타임머신이 없어서 무조건 1사이클을 쉬어야(Stall) 한다는 것을 확인했습니다. 컴파일러는 이 1사이클을 그냥 놀리면서 버리는 것을 참지 못합니다.
그래서 컴파일러는 코드를 훑어보고 "어차피 1클럭 쉴 바에, 결과에 아무런 영향을 안 주면서 당장 실행할 수 있는 다른 명령어를 저 빈칸(Stall 위치)에 땡겨와서 실행하자!"라고 결정합니다. 마치 테트리스 빈칸을 채우는 것과 같습니다.
- Before Scheduling (스케줄링 전: 원래 코드)
LD R2, 0(R1) // Load B into R2
LD R3, 4(R1) // Load E into R3
ADD R4, R2, R3 // Stall! (Needs R3 from previous LD)
ST R4, 12(R1) // Store A
LD R5, 8(R1) // Load F into R5
ADD R6, R2, R5 // Stall! (Needs R5 from previous LD)
ST R6, 16(R1) // Store C- After Scheduling (스케줄링 후: 최적화된 코드)
컴파일러가 코드의 의존성을 분석합니다.
"가만 보자... 밑에 있는 LD R5, 8(R1)은 앞의 명령어들과 겹치는 레지스터가 하나도 없네? 그럼 순서를 위로 확 끌어올려도 프로그램 결과는 똑같잖아!"
LD R2, 0(R1) // Load B into R2
LD R3, 4(R1) // Load E into R3
LD R5, 8(R1) // Load F into R5 (Moved up!)
ADD R4, R2, R3 // No stall! (R3 was loaded 2 cycles ago)
ST R4, 12(R1) // Store A
ADD R6, R2, R5 // No stall! (R5 was loaded 2 cycles ago)
ST R6, 16(R1) // Store C[해결된 원리 (왜 스톨이 사라졌을까?)]
- 이제 ADD R4, R2, R3는 LD R3가 끝나자마자 바로 실행되지 않습니다. 중간에 LD R5라는 엉뚱한(?) 명령어가 1사이클을 소모해 주며 방패막이 역할을 합니다.
- 하드웨어 입장에서는 그 1사이클 동안 이미 LD R3의 메모리 접근(MEM 단계)이 끝났기 때문에, ADD가 실행(EX 단계)될 때 스톨 없이 바로 포워딩을 받을 수 있습니다.
- 뒤에 있는 ADD R6 역시 LD R5와 멀리 떨어지게 되어 스톨이 완전히 사라집니다!
그래서 다음과 같이 순서를 재배치(Reordering)합니다.
Control Hazard
앞서 우리가 BNEZ (Branch if Not Equal to Zero) 명령어를 풀면서 겪었던 '점프 페널티'나 '플러시(Flush)'의 근본적인 원인이 바로 이 녀석입니다
1. Conditional branches
"If the branch is taken (condition is true) next instruction should be fetched from the target address"
일반적인 명령어들은 바로 다음 줄(PC + 4)을 순서대로 실행하면 됩니다. 하지만 if문이나 for, while 루프를 만드는 조건부 분기 명령어(Branch)는 다릅니다.
- 조건이 참일 때 (Taken): 순서를 건너뛰고 엉뚱한 목적지 주소(Target Address)로 점프해서 다음 명령어를 가져와야 합니다.
- 조건이 거짓일 때 (Not Taken): 점프하지 않고 그냥 바로 밑에 있는 다음 줄의 명령어를 가져오면 됩니다.
2. 정보가 만들어지는 시점 (너무 늦음)
"We have necessary data at the end of ID stage or EX stage (depending on where the target address is calculated)"
우리가 다음 명령어를 제대로 가져오려면 두 가지 정보가 필요합니다.
- 조건 평가: "그래서 진짜 점프를 해, 말아?" (조건식 계산)
- 주소 계산: "점프한다면, 정확히 메모리 몇 번지로 가야 해?" (목적지 주소 계산)
문제는 이 정보들이 너무 늦게 계산된다는 것입니다.
- 초기/기본 파이프라인 구조: 이 두 가지 계산을 모두 EX (실행) 단계가 끝나야 알 수 있습니다.
- 최적화된 파이프라인 구조: (우리가 앞서 풀었던 하드웨어처럼) 비교기와 덧셈기를 앞당겨서 ID (해독) 단계 끝부분에서 간신히 알아냅니다.
3. 정보가 필요한 시점 (너무 빠름)
"The next instruction needs the data at the beginning of IF stage"
이것이 파이프라인의 치명적인 모순입니다.
분기 명령어의 바로 다음에 실행될 명령어는, 자신의 첫 번째 단계인 IF (Instruction Fetch) 단계를 시작하자마자 "내가 어느 주소에서 명령어를 가져와야 하는지(PC 값)"를 알아야 합니다.
Control Hazard의 발생 (시간 역설)
자동차 운전(내비게이션)에 비유해 보겠습니다.
- IF 단계 (명령어 가져오기): 운전자가 교차로에 진입하면서 핸들을 꺾어야 하는 순간입니다. (당장 목적지를 알아야 함)
- ID / EX 단계 (주소 및 조건 계산): 조수석에 앉은 친구가 지도를 보고 "아! 왼쪽으로 꺾어야 해!"라고 계산을 끝내는 순간입니다.
분기 명령어가 ID나 EX 단계에서 "어디로 갈지" 열심히 계산하고 있는 동안, 바로 뒤따라오는 다음 명령어는 이미 파이프라인의 IF 단계로 진입하려고 대기 중입니다. 하지만 앞 명령어가 아직 계산을 안 끝냈으니, 다음 명령어는 도대체 메모리의 어디(어떤 주소)로 가서 명령어를 가져와야 할지 알 수가 없습니다.
이 엇박자로 인해 파이프라인이 멍을 때리거나 엉뚱한 길로 들어서게 되는 현상을 Control Hazard라고 부릅니다.
1. Branch Condition (분기 조건)
"그래서 이번에 시험 볼 과목(테스트 기준)이 뭐야?"
- 개념: 점프를 할지 말지 결정하기 위해 CPU가 확인해야 하는 '조건식' 그 자체입니다.
- 예시: BNEZ (Branch if Not Equal to Zero) 명령어에서는 "R4 레지스터 안의 값이 0이 아닌가?"라는 질문이 바로 Condition입니다.
- 하드웨어 동작: ID 단계나 EX 단계에서 비교기(Comparator) 회로를 통해 두 값을 빼보거나 0인지 확인하는 연산을 수행합니다.
2. Branch Outcome (분기 결과 / 분기 방향)
"테스트 채점 결과, 합격(O)이야 불합격(X)이야?"
- 개념: Condition(조건)을 테스트해 본 결과, 최종적으로 내려진 O/X 결론입니다. 이 Outcome은 무조건 다음 두 가지 상태 중 하나로만 나옵니다.
- Taken (테이큰, 분기 발생): 조건이 '참(True)'이어서, 엉뚱한 목적지로 점프를 해야 하는 상태.
- Not Taken (낫 테이큰, 분기 미발생): 조건이 '거짓(False)'이어서, 점프를 취소하고 그냥 바로 아래 줄(PC+4)에 있는 명령어를 계속 실행하는 상태.
- 연결 고리: 우리가 앞서 계산 문제에서 "Predict Taken(점프할 거라고 예측)", "Predict Not Taken(점프 안 할 거라고 예측)"이라고 불렀던 것이 바로 이 Outcome을 하드웨어가 맘대로 찍어버리는 기술입니다!
3. Target Address (목적지 주소 / 타겟 주소)
"합격(Taken)했으면, 이제 어디로 가야 해? 정확한 주소 줘!"
- 개념: Outcome이 'Taken'으로 나와서 점프를 해야 할 때, 실제로 날아갈 도착지(메모리 번지수)입니다.
- 예시: 명령어에 적혀 있던 Loop라는 글자가 실제로 가리키는 메모리의 번지수(예: 메모리 2000번지)입니다.
- 하드웨어 동작: 현재 명령어의 주소(PC)에다가, 명령어에 적힌 점프 거리(Offset)를 덧셈기(Adder)로 더해서 최종 Target Address를 계산해 냅니다.
다음 명령어는 파이프라인의 IF 단계를 당장 시작해야 하는데, CPU는 저 세 가지 정보가 하나도 없습니다.
어디로 갈지(Target Address) 덧셈도 해봐야 하고,
점프할지 말지(Condition) 비교도 해봐야 하고,
최종 결정(Outcome)을 내려야만 비로소 다음 명령어를 올바르게 가져올 수 있습니다.
이 계산들이 끝날 때까지 걸리는 시간이 바로 우리가 표에 그렸던 스톨(Stall) 1칸의 정체입니다.
