컴퓨터 구조_pipeline

Pipeline

Pipelining Analogy

• Pipelined laundry: overlapping execution
  • Parallelism improves performance
  • Infinite loads (총 4개의 step으로 구성된 작업이라고 했을 때)
    • Speedup
      • 4n/(3+n) ≡ 4 (3은 stage - 1)
      • number of stages

        파이프라인은 여러단계로 나뉘어진 작업을 동시에 수행하여 시간을 감축시키는 것.

Datapath With Control

• Pipelining을 하려면
  • load를 여러 개의 sub-task로 나누어야 한다.
  • 각 sub-task는 1-clock cycle에 수행된다.

  → 즉 명령어 한 개는 여러 clock cycles에 수행된다.

MIPS Pipeline

• Five stages, one step per stage
  1. IF : Instruction fetch from memoey → 메모리에서 명령어를 가져온다.
  2. ID : Instruction decode & register read → 레지스터를 읽고 명령어를 해독한다.
  3. EX : Execute operation or caculate address → 연산을 실행하거나 주소를 계산한다.
  4. MEM : Access memory operand → 메모리에 접근하여 값을 쓰거나 읽는다.
  5. WB : Write result back to register : 결과를 레지스터에 작성한다.

_하나의 명령어를 수행하기 위해서는 5 단계가 필요하다_

Synchronous Digital 회로의 동작

• 클락 사이클 동안에 Combinational 회로에서 입력 신홍에 대한 출력 신호를 만든다.
• Combinational 회로의 input은 state elements의 output이다.
• Combinational 회로의 output은 state elements의 input이다.
• clock period (clock edge 간의 간격) 은 Combinational 회로의 longest delay에 의해 정해진다.

Clock cycle이 끝나면 연산된 결과가 State lelment의 저장되어야 한다.

Pipeline register

• Need registers between stages
  • To hold information produced in previous cycle

연산의 결과를 저장하기 위한 Pipelin register가 필요하며 항상 write signals 이 1이다.

Cycle Time of Pipeline Processor

• Assume time for stages is
  • 100ps for register read or write
  • 200ps for memory, ALU
• Compare pipelined datapath with single-cycle datapath 가장 긴 200ps로 통일을 하면 된다

Pipeline hazard

• 파이프라인 프로세서에서 명려엉의 수행이 끝나기 전에 다른 명령어의 수행이 시작되기 때문에 생기는 문제
  1. Structural hazards
  • A required resourece is busy
  • 한 싸이클동안 여려개의 명령어가 동시에 수행되기 때문에 생기는 문제.
    1. Data hazard
  • Need to wait for previous instrcution to complete its data read/write
    1. Control hazard (Branch Hazard)
  • Deciding on control action depends on previous instruction

1. Strucural Hazards (already solved)
   • Conflict for use of a resource
   • In MIPS pipelin with a single memory
   • Load/store requires data access
   • Instruction fetch would have to stall for that cycle
     • Would cause a pipeline “bubble”
       • Hence, pipelined datapaths require separate instruction/data memories
   • Or separate instruction/data caches

*가장간단한 해결방법은 stall을 하는 것이다 stall은 pipline 1싸이클을 쉬는것이다. 이 때 성능은 당연히 낮아진다. *

1. Data hazard Data Dependencies : 먼저 수행되는 명령어의 결과가 나중에 수행되는 명령어의 결과의 영향을 주는 것
   • 5개의 명령어 중 2번 register의 값을 모두 공유 한다면 가장 먼저 수행되는 명령어의 연산결과가 data에 써지기 전까지 나머지 명령어는 2번 register의 값을 사용할 수 없다. 이 때 이를 해결하기 위해 register file이 clock cycle 중간에 써지도록 회로를 수정한다.
   • 해결방법
   1. Stall for Data Hazard
      • 가장 간단한 방법으로 pipeline stall을 사용한다 . 하지만 성능이 떨어진다.
   2. Forwarding
      • Use result when it is computed
        • Don’t wait for it to be stored in a register
        • Requires extra connections in the datapath
          • 연산결과를 싸이클 중 마지막인 WB에서 가져오는게 아니라 그 전에 연산을 마쳤을 때 EX 단계 또는 그 다음 단계에서 필요한 Data를 가져오도록 회로를 재설계한다. 앞의 명령어의 Rd 필드와 뒤의 명령어 soruce 번호가 일치하면 Froward를 한다

• Data hazads when
  1. EX/MEM.RegisterRd = ID/EX.RegisterRs
  2. EX/MEM.RegisterRd = ID/EX.RegisterRt
  3. MEM/WB.RegisterRd = ID/EX.RegisterRs
  4. MEM/WB.RegisterRd = ID/Ex.RegisterRt
• Double Data Hazard
  • Forward from which stage?
    • the most recent value
  • EX hazard confition overrides MEM hazard condition
    • Only forward if EX hazard condition isn’t ture 만약 세 번째 명령어의 소스번호와 1,2번 명령의 Rd번호와 같다면 가장 최근 값을 사용해야 한다 따라서 이 때 최근값을 사용하려면 ForwardA= 10이 된다.
• Load-Use Data Hazard
  • Can’t always aboid stalls by forwarding
    • If value is not computed when needed 모든 경우에서 frowarding을 사용할 수 없다.(load 연산의 경우) 이 때는 pipeline stall을 사용을 할 수 밖에 없다.
• Load-Use Hazard Detection
  • Check when an instruction is decoded in ID stage
  • ALU operand register numbers in ID stage are given by
    • IF/ID.RegisterRs, IF/ID.registerRt
  • Load-use hazard when
    • ID/EX.MemRead and
      ((ID/EX.RegisterRt = IF/ID.RegisterRs)or
      (ID/EX.RegisterRt = IF/ID.RegisterRt))
  • If detected, stall and insert bubble 오직 Load 명령어에서만 MemRead 시그널이 1이다. 따라서 이 Memread 가 1이면 미리 알 수 있다.
• How to Stall the Pipeline
  • Force contrl values in ID/EX register to 0
    (MemWrite = RegWrite = 0)
    • EX, MEM and WB do nop
  • Prevent update of PC and IF/ID register
  • 또 한 번 같은 명령어를 Decode
  • 또 한 번 같은 명령어를 Fetch
  • 1-cycle stall allows MEM to read data for 1w
    • Can subsequently forward to EX stage
• Stalls and Performance
  • Stalls reduce performance
    • But are required to get correct results
  • Compiler can arrange code to avoid hazards and stalls
    • Requires knowledge of the pipeline structure

1. Control(Branch) Hazards
   • Branch 명령은 flow of control을 변경한다.
   • Fetch 할 다음 명령어의 주소는 branch 조건에 따라 달라진다. * Solution to branch hazard
   • pipeline stall
   • branch prediction
     • static
       • as taken
       • as not taken
     • dynamic
       • Branch Prediction
   • Longer pipelines can’t readily determine branch outcome early
     • stall penalty becomes unacceptable
   • Predict outcome of branch
     • Only stall if the prediction is wrong
   • In MIPS pipeline
     • predice branches as not taken 파이프라인의 (stage)길이가 걸어지면 미리 branch를 계산하기 힘들다. 따라서 미리 에상하는 과정을 거치며 만약 예상이 틀리면 미리 예상했던 값을 지운다 MIPS에서는 branch가 일어나지 않는다고 가정을 하고 시작한다

• 컴퓨터구조
• pipeline