[컴퓨터구조] #12. Pipeline MIPS(1)
Lec 12. Pipeline MIPS_1 (The Processor)
- Processor Performance
single-cycle processor ( 한 clk에 하나의 명령어 실행) 의 성능은
long critical path delay 에 의해 제한됨.
(critical path 가 clock frequency 를 제한함)
( *lec 11 참고
가장 오래 걸리는 경로가 critical path임.
add, sw, lw중에서는 lw가 critical path.
critical path가 짧을수록 performance 좋아짐. )
=> 더 나은 방법??
1) 반도체 기술에 의존 (small sized transistors)
2) Pipelining !!!
- Pipelining
Response time 은 그대로 (30+40+20), Throughput 은 개선됨 (전체시간 줄었으므로).
Pipelining 기법의 목적은 Throughput을 높이는 것임!! -> 여러개의 명령어를 병렬로 실행함.
5단계로 쪼갬
: IF(Instruction memory), ID(Instruction Decode), EX(ALU), MEM(data memory), WB(register file)
* Pipeline Speedup (increased throughput)
: 모든 단계가 balanced(같은 시간 걸림) 되어있다면 가장 고성능.
명령어 실행시간(pipeline) = 명령어 실행시간(sequential) / 단계(stage)의 수
- Pipelining and ISA Design
: MIPS ISA is designed with pipelining in mind
(ISA affects the complexity of the pipeline implementation)
-> 모든 명령어가 32bits (4bytes)
: RISC라서 명령어 크기 고정됨. Instruction Fetch 편함. PC가 가리키는 값으로부터 word를 읽어오면 됨.
cf) CISC 인 x86 은 명령어 길이가 1~17 bytes 로 다양해서 pipeline 구현 시 하드웨어 복잡.
-> Regular instruction formats (R, I, J -types)
: 명령어 format이 규칙적이라서 ID(decode)와 레지스터 접근(읽기)을 동시에 한 사이클 이내에 가능.
(Fetch 후에 바로 레지스터 접근)
-> Load/Store addressing
: 메모리 접근은 load/store를 통해서만 가능 (EX 단계에서 주소 계산, MEM 단계에서 메모리 접근)
-> 모든 명령어를 한 사이클 이내에 수행 가능 (명령어 1개에 ALU 최대 1개 필요)
-> Alignment of memory operands in memory
: 읽고 쓰려는 모든 data는 4의 배수 주소에 정렬되게 함으로써
한 사이클에 lw/sw 가능하게 함. (걸쳐있으면 두번에 나눠서 해야하므로)
- Basic Idea
위 그림의 datapath들이 모두 한 사이클에 동작하면 single cycle MIPS임.
-> 한계 : 모든 datapath를 거쳐야만 실행되는 명령어가 있다면, 그만큼 주기가 길어지거나 frequency가 낮아짐.
따라서 throughput 관점에서 성능을 높이기위해 pipeline 적용함.
-> single cycle MIPS를 5개의 stage로 나누고, 각각의 stage가 한 clock cycle에 동작할 수 있도록
중간중간 flip-flop 삽입.
- Graphically Representing Pipelines
Shading : unit is being used by the instruction
Right half Shading : element is being read
Left half Shading : element is being written
- Hazards
: prevents starting the next instruction in the next cycle.
Pipelining -> Hazard 발생!!
① Structure Hazards
: conflict over the use of a resource at the same time
MIPS CPU와 Memory 사이에 port가 1개라면
IF(instruction memory 읽기)와 MEM(data memory 읽기) 단계에서 같은 자원(메모리) 접근, 충돌함.
-> 잠시 stall(멈춤) 해야함. pipeline "bubble" -> 1 cycle 손해봄
* 해결책 : port를 2개로 늘리자! seperate memories for instruction and data
② Data Hazards
: data is not ready for the subsequent dependent instruction.
두개의 인접한 명령어 사이에 존재하는 data의 dependency로 인해 발생(데이터 의존성).
sub 명령어에서 사용할 $s0는 add의 WB 시점에 결과반영되므로 기다려줘야함 -> 2 cycle 손해봄
* 해결책1 : Forwarding (or Bypassing)
* 해결책2 : Code Scheduling to Avoid Stalls
lw의 경우에는 forwarding을 한다해도 1 cycle stall 필요함.
근데 scheduling 잘 하면 bubble을 숨길 수 도 있음.
lw한 값을 바로 다음 사이클 말고 그 이후에 사용하면 굳이 stall 안해도 됨.
③ Control Hazards
: Fetching the next instruction depends on the previous branch outcome
(Branch determines the flow of instructions) 조건의 참/거짓을 알아야 다음 명령어를 알 수 있음.
Branch instruction is still working on ID stage when fetching the next instruction...
조건의 참/거짓 결과 나올 때까지 기다려야함 -> 2 cycle 손해봄
* 해결책1 : Add hardware in ID stage
2 bubbles -> 1 bubbles 줄일 수 있음.
* 해결책2 : Delayed Branch
branch명령을 만났을때, branch에 대한 실질적인 실행을 한 cycle 미루겠다는 기법임.
branch 명령어 바로 다음(delay slot)에는 branch가 참이든 거짓이든 무조건 실행되는 명령어를 실행하고
branch 가 참/거짓일 때 실행되는 명령어는 branch 명령어 다다음 순서부터 실행됨.
delay slot 에 useful instruction을 담아준다. 없다면 nop(no operation).
cf) jal 에서 delay slot을 고려하여 PC+8으로 link 걸어줌.
* 해결책3 : Branch Prediction
Longer pipelines 는 branch outcome을 빠르게 결정할 수 없음.
stage 많을수록 branch의 결과를 획득하려면 bubble이 더 많아짐. (stall penalty ⬆)
-> branch 의 참/거짓 결과 미리 예측,
예측이 틀렸다면 flush (명령어 비우기/버리기)
Our MIPS 는 branch-not-taken predictor (with no delayed branch)
: delay slot 안쓰고 무조건 거짓이라고 예측 할거임.
