4. Pipelining

Pipeline

여러 instruction들의 실행을 overlap시켜서 CPI를 1로 만들고, 성능을 향상시킨다.

더 많은 하드웨어를 써서 더 많은 stage로 나눈다면 더 빠른 속도를 얻을 수 있다.

 

Pipeline을 overlapped execution, instruction-level parallelism이라 한다.

 

MIPS는 5개의 stage로 나눠서 pipelining을 한다.

1. IF
   • instruction fetch
2. ID
   • instruction decode, register read
   • control signal을 만들면서, 동시에 register을 읽어서 속도를 향상시킨다.
3. EX
   • execute operation or calculate address
4. MEM
   • memory access
5. WB
   • write result back to register

 

각 stage에서는 다른 instruction들이 실행된다.

 

Performance

Pipelining은 throughput을 통해서 speedup을 얻는다.

Latency(instruction 하나를 실행하는데 걸리는 시간)이 줄어드는 것은 아니다.

 

모든 stage가 같은 시간이 걸리게 하면 가장 이상적이고, 가장 좋은 성능 개선을 얻는다.

이를 모든 stage가 balanced 되어있다고 한다.

 

예를 들어, lw의 실행이 총 800ps가 걸리므로, 5단계로 나누면 각 단계별 160ps가 된다.

이렇게 되면 5배의 성능 향상을 얻을 수 있다. (stage 하나 당 한 instruction이 종료되기 때문)

 

그러나, 각 stage 별로 걸리는 시간이 다르기 때문에 공평하게 나누지 못한다.

그렇기에 critical path인 stage를 기준으로 cct를 잡아야 하고 각 stage별 시간은 200ps가 된다.

따라서 5배의 성능 향상을 얻지는 못한다.

 

---

Pipeline Diagram

Traditional form

 

Resource usage form

 

---

MIPS Pipelining

Pipelining을 만들기 쉬운 이유

MIPS는 pipelining을 하기 쉽다.

MIPS는 RISC architecture로, pipeline을 고려해서 만들어진 것이기 때문이다.

 

따라서 다음과 같은 특징을 갖는다.

• 모든 instruction들의 길이가 같다.
  • 하드웨어의 구현과 pipeline의 적용이 쉽다.
  • 한 cycle에 fetch, decode 하기가 쉽다.
• Instruction format이 적고 규정(regular)되어 있다.
  • R, I, J format
  • decode하는 것과 register read를 동시에 수행할 수 있다.
• Memory operand가 load와 store에서만 나타난다.
  • load/store을 통해서만 memory access를 한다.
  • base addressing mode를 사용하기 때문에 memory access보다 ALU operation이 먼저 수행되어야 한다.
  • 즉, calculate address는 3번째 stage에서, access memory는 4번째 stage에서 수행된다.
• Memory가 align 되어있다.
  • memory access를 한번 함으로써 데이터를 읽을 수 있다.
  • 만약 unaligned 되어 있다면 memory access를 2번 해야 하는 상황이 발생한다.

 

Hazard

이상적인 pipelining은 매 cycle마다 instruction이 시작하고, 종료되는 것이다.

이를 방해하는 요인들을 Hazard라고 한다.

• Structural hazard
• Data hazard
• Control hazard

 

---

Pipelined Datapath

각 stage 별로 다른 instruction들이 수행된다.

따라서 각 stage의 신호들이 앞/뒤의 stage에 영향을 주지 않게 해야 한다.

 

이러한 insulation 기능을 위해서 register을 사용한다.

각 stage 사이마다 pipeline register를 두는 것이다.

 

값이 올라가는 순간에 결과를 pipeline register에 저장한다.

이를 통해 clock이 다시 올라가기 전에는 이전/이후 stage의 영향을 받지 않을 수 있다.

 

각 stage 별로 pipeline register에 저장하는 정보는 다음과 같다.

• IF/ID register
  • instruction
  • PC + 4
• ID/EX register
  • PC+4
  • registers
  • immediate : sign extended
  • control signals
• EX/MEM register
  • memory address
  • control signals
  • data to write
• MEM/WB register
  • data read
  • control signals

 

IF/ID, ID/EX register에 저장할 때에는 아직 어떤 instruction인지 모르기 때문에 모든 instruction에서 공통으로 진행된다.

반면, EX/MEM, MEM/WB register에 저장하는 것은 instruction의 종류마다 다르다.

 

각 instruction 별 EX/MEM, MEM/WB register

• load
  • EX/MEM : memory address, control signal
  • MEM/WB : data read(읽은 data), control signal
• store
  • EX/MEM : memory address, data to write(쓸 data), control signals
  • MEM/WB : none(store is finished)
• ALU
  • EX/MEM : ALU result, write register number, control signals
  • MEM/WB : ALU result, write register number, control signals
  • MEM stage에서 수행할 연산이 없으므로 EX/MEM register의 값을 MEM/WB register에 그대로 옮긴다.
• Branch
  • EX/MEM : branch target, zero or not, control signals
  • MEM/WB : none(store is finished in MEM stage)

 

---

Pipelined Control

IF, ID stage는 수행할 instruction이 어떤 것인지 모르기 때문에 모든 instruction들이 공통으로 수행된다.

그러나 IF에서는 PCSrc, ID에서는 RegWrite라는 control signal이 필요하다.

 

이들의 위치는 IF, ID이지만, 실제 그 신호를 주는 것은 MEM과 WB stage에서이다.

즉, 아직 decode되지 않은 단계에서 control signal들이 결정되지 않아서 오류나는 것이 아니라, MEM과 WB stage에서 결정된 것을 받아오는 것이다.

 

Datapath와 마찬가지로 single cycle implementation과 다른 것이 아니라 동일한 것이다.

단지 stage 별로 구분되었을 뿐이다.

 

 

Control signal들도 pipeline register을 통해서 움직인다.

• EX
  • 4개의 control signal
  • ALUSrc : ALU에 input으로 들어갈 source를 결정한다.
  • RegDst : 저장할 register number를 결정한다.
  • ALUOp(2) : ALU operation을 결정한다.(2bit)
• MEM
  • 3개의 control signal
  • Branch : branch인지 아닌지 결정한다.(PCSrc)
  • MemRead : data memory에 read 할 것인지 결정한다.
  • MemWrite : data memory에 write 할 것인지 결정한다.
• WB
  • 2개의 contorl signal
  • RegWrite : register file에 write 할 것인지 결정한다.
  • MemToReg : register file에 write할 것이 memory에서 읽은 data인지, ALU에서 계산된 결과인지 결정한다.

 

Truth table 또한 signle cycle에서와 동일하다.

단지 stage 별로 구분되었을 뿐이다.