MIPS Pipeline
IF: Instruction fetch from memory
ID: Instruction decode & register read
EX: Execute operation
MEM: Access memory operand
WB: Write result back to register
Hazards
구조적 해저드(Structure Hazard)
• Occurs when two or more instructions require the same hardware resource simultaneously.
• Conflict that occurs when the required resource is busy.
단일 메모리를 사용하는 MIPS 파이프라인에서 발생
- 구조적 해저드는 단일 리소스를 사용하는 과정에서 발생하는 충돌.
- 특히 로드/저장과 같은 데이터 액세스가 필요한 명령에서 자주 발생.
- Instruction Fetch가 해당 사이클 동안 지연되며, 이는 파이프라인에 Bubble(Stall)을 생성
쓰기는 앞부분에서 일어나고 ,읽기는 뒷부분에서 일어난다고 가정하면 읽기는 새로 써진 값을 읽을 수 있다.
따라서 실제 레지스터 파일의 많은 구현이 그렇듯이 이 경우에는 데이터 해저드가 발생하지 않는다.
Pipelined Datapaths는 분리된 명령어/데이터 메모리가 필요.
- 별도의 명령어/데이터 캐시
- 명령어 페치와 메모리 접근을 동시에 수행
데이터 해저드(Data Hazard)
• Need to wait for previous instruction to complete its data read/write
- 전방 전달(Forwarding, aka Bypassing)
결과가 기록(Written Back)되기를 기다리지 않고 계산되자마자 명령어가 해당 결과를 사용할 수 있게 한다.
- Load-Use Data Hazard (lw 명령어 다음에 의존성 있는 R-type 명령어 오는 경우)
전방 전달만으로 해결할 수 없다. 의존하는 명령어가 필요로 할 때 데이터가 아직 준비되지 않기 때문.
적재-사용 위험에서 필요한 데이터가 로드 명령어의 메모리 접근(MEM) 단계가 끝나야만 사용할 수 있다.
Pipeline bubbles은 lw 명령어가 MEM 단계를 완료할 때까지 R-type 명령어를 지연시키기 위해 도입된다.
Code Scheduling을 통해서 Stall을 피하 수 있다.
- lw 명령어 이후 나오는 의존성이 있는 R-type 명령어가 두 줄 이상 띄어서 나오도록 코드를 재배치하면 Stall이 발생하지 않도록 할 수 있다
제어 해저드(Control Hazard)
• Deciding on control action depends on previous instruction
분기는 제어 흐름을 결정한다
다음 명령어를 가져오는 것은 분기의 결과에 따라 달라진다
파이프라인은 항상 올바른 명령어를 가져올 수 없다.
파이프라인 초기에 레지스터를 비교하고 타겟 주소를 계산해야 합니다.
이를 ID 단계에서 처리할 수 있도록 하드웨어를 추가해야 한다.
Stall on Branch
다음 instruction을 fetching하기 전에 분기의 결과가 결정될 때까지 대기한다.
Branch Prediction : 예측이 틀릴 경우에만 스톨이 발생.
- 분기가 일어나지 않을 경우를 예측할 수 있다.
- 분기 후에는 지연 없이 명령어를 가져온다.
정적 분기 예측(Static Branch Prediction)
: either pick true or false
일반적인 분기 동작을 기반으로 한다.
예시: 반복문과 조건문 분기
뒤쪽으로 가는 분기는 예측을 취함(taken)
앞으로 가는 분기는 예측을 취하지 않음(not taken)
동적 분기 예측(Dynamic Branch Prediction)
: figure out which will be more likely between true or false
하드웨어가 실제 분기 동작을 측정.
예: 각 분기의 최근 이력을 기록합니다.
미래의 동작은 현재의 경향을 따른다고 가정.
예측이 틀릴 경우, re-fetching 하면서 Stall하고 이력을 업데이트
주기별 명령어 흐름을 통한 파이프라인 데이터 경로
- Single-clock-cycle 파이프라인 다이어그램은 한 주기 내에서 파이프라인의 사용 상태를 보여준다. 즉, 각 명령어가 한 주기 동안 파이프라인의 각 단계를 어떻게 거치는지를 나타냄
- Multi-clock-cycle 파이프라인 다이어그램은 시간이 흐르면서 각 명령어가 파이프라인의 각 단계를 어떻게 진행하는지를 그래프로 나타냄. 여러 주기에 걸쳐 명령어들이 어떻게 처리되는지를 시각적으로 보여줌
Pipelined Datapath with Control
- ALUOp + funct(6) → ALU Control
- IF → ID → EX(ALUOp, ALUSrc, RegDst) → M(MemRead, MemWrite, Branch) → WB(MemtoReg, RegWrite)
- Instruction
R-Type : op(6) + rs(5) + rt(5) + rd(5) + shmpt(5) + funct(6)
I-Type : op(6) + rs(5) + rt(5) + address / constant(16)
- lw / sw : rs + offset 계산 후 메모리의 그 주소 값에 가서 적제/저장 후 rt 레지스터로
- beq : address를 sign-extend 하고, shift-left 2한 후 (pc+4)를 더해준 값으로 rs=rt면 이동, 아니면 pc+4로
- Execution-Datapath 그릴 때 (1) ALU로 입력되는 값 , (2) EX/MEM 파이프라인 레지스터로 입력되는 값을 기준으로 생각
- 쓰기 단계에서 설정하는 제어 신호는 Mem-toReg와 RegWrite이다.
Mem-toReg는 레지스터 파일에 ALU 결과를 보낼 것인지 메모리 값을 보낼 것인지를 결정하며,
RegWrite는 선택된 값을 레지스터에 쓰게 하는 신호이다.
Forwarding Conditions (Forwarding Unit)
EX hazard
• if (EX/MEM.RegWrite &&
(EX/MEM.RegisterRd≠ 0) &&
(EX/MEM.RegisterRd=ID/EX.RegisterRs))
ForwardA= 10
• if (EX/MEM.RegWrite &&
(EX/MEM.RegisterRd≠ 0) &&
(EX/MEM.RegisterRd=ID/EX.RegisterRt))
ForwardB= 10
MEM hazard
• if (MEM/WB.RegWrite &&
(MEM/WB.RegisterRd≠ 0) &&
(MEM/WB.RegisterRd=ID/EX.RegisterRs))
: ForwardA= 01
• if (MEM/WB.RegWrite &&
(MEM/WB.RegisterRd≠ 0) &&
(MEM/WB.RegisterRd=ID/EX.RegisterRt))
: ForwardB= 01
* EX 단계와 MEM 단계에서 파이프라인 레지스터의 WB 제어 필드를 조사하면 RegWrite 신호가 인가되었는지를 알 수 있다.
ID 단계에서 명령어가 디코딩될 때 확인
ALU 연산자 레지스터 번호는 ID 단계에서 제공됨.
예: IF/ID.RegisterRs, IF/ID.RegisterRt
적재 명령어 뒤에 이 결과물을 읽는 명령어가 뒤따라 나오면 전방 전달로 해결할 수 없으므로 파이프라인을 지연시켜야 한다.
Forwarding Unit 외에 Hazard Detection Unit (HDU)도 필요하다.
ID 단계에서 동작하여 적재 명령어와 결과물 사용 사이에 지연을 추가할 수 있도록 한다.
* lw 명령어 관련 - ID/EX 파이프라인 레지스터 vs R-type 명령어 관련 - IF/ID 파이프라인 레지스터
• if (ID/EX.MemRead &&
(ID/EX.RegisterRt = IF/ID RegisterRs) ||
(ID/EX.RegisterRt = IF/ID RegisterRt))
: Stall the Pipeline(Insert bubble)
* 여기서 첫 번째 줄은 명령어가 적재 명령어인지 검사하는 것
필기한거 올리기
파이프라인을 스톨하는 방법
ID/EX 레지스터의 제어 값을 0으로 설정
EX, MEM, WB 단계에서 nop (no-operation)을 실행하여 명령어를 처리하지 않는다.
PC와 IF/ID 레지스터의 업데이트를 방지
현재 사용 중인 명령어는 다시 디코딩된다.
다음 명령어는 다시 가져온다.
Datapath with Hazard Detection
Instruction-Level Parallelism (ILP)
파이프라이닝(Pipelining): 여러 명령어를 병렬로 실행
ILP를 증가시키기 위한 방법:
더 깊은 파이프라인 : 각 단계에서의 작업량을 줄여서 더 짧은 클록 사이클
다중 명령어 발행(Multiple issue)
- 파이프라인 단계 복제: 다수의 파이프라인 사용
- 매 사이클마다 여러 명령어 시작
- CPI < 1, 따라서 사이클당 명령어 수(IPC) 사용
예시: 4GHz, 4-way 다중 명령어 발행
16BIPS, peak CPI = 0.25, peak IPC = 4
- 하지만 의존성은 실제로 이를 감소시킴
루프 언롤링(Loop unrolling)
- 루프 본문을 복제하여 더 많은 병렬성을 노출
MIPS with Static Dual Issue
정적(Static) : 명령어 쌍(pairing) 및 병렬성(parallelism)은 컴파일 타임에 컴파일러에 의해 결정됨
ALU 연산이 메모리 접근 연산과 쌍을 이루어 실행됨