CSAPP 4.5 Pipelnied Y86-64 Implementations

📝 상세 정리

#

4.5.0 Intro

#

• 이제 설계를 시작할 준비가 되었다.
• SEQ를 소폭 수정하여 PC계산을 fetch 단계로 옮기자.
• 파이프라인 레지스터를 추가하자.
• 아직 종속성을 제대로 처리하지 못하지만, 일단 효율적인 파이프라인을 만들어보자.

4.5.1 SEQ+: Rearranging the computation Stages

#

• SEQ의 5단계를 약간 재배열해서 PC업데이트 단계가 클록 주기의 끝이 아닌 시작에 오도록 하자.
  • 이 설계를 SEQ+라고 한다.
• PC를 클록 주기의 시작에 오게 하기 위해선, 이전의 icode, Cnd, valC, valM, valP등이 필요하다.
  • 이젠 이 다섯개를 하드웨어 레지스터를 따로 둬서 저장하면 되겠다.
• 이걸 회로 리타이밍이라고 한다.

4.5.2 Inserting Pipeline Registers

#

• 중간에 stat, icode, ifun, rA, rB, valC, valA, valP, dstE… 등 여러가지를 저장하는 층을 만들자.
• SEQ의 단계와 같지만, 단계 사이를 파이프라인 레지스터가 분리하고 있는것이다.
• 그 층의 이름은 다음과 같다.
  • F: PC의 예측값 보유
  • D: Fetch와 Decode 사이에서, 최근에 인출된 명령어에 대한 정보 보유
  • E: Decode와 Execute 사이에서, 가장 최근에 디코드된 명령어에 대한 정보와 레지스터파일에서 읽은 값 보유
  • M: Execute와 Memory 사이에서, 메모리단계에서 처리할 가장 최근에 실행된 명령어의 결과 보유
    • 조건부 점프 처리를 위한 분기조건 / 대상에 대한 정보도 보유
  • W: Memory와 Write back 단계 사이에서, 계산된 결과를 레지스터 파일에 쓰기 위한 정보 보유
    • ret 명령어 완료시 PC 선택 로직에 반환 주소 공급

4.5.3 Rearranging ans Relabeling Signals

#

• SEQ와 SEQ+는 한번에 하나의 명령어만 처리하므로 valC, rscA, valE와 같은 신호에 고유한 값 존재
  • 하지만 파이프라인 설계에서는 서로 다른 명령어와 연관된 여러 버전 존재
  • 올바른 버전의 신호를 사용하도록 주의하지 않으면, 오류가 발생할 수 있다.
    • 따라서 D_stat, E_stat.. 처럼 명명하자.
  • 하드웨어 레지스터가 아닌 그 안에서 계산되는 stat과 같은 부분도 있다!
    • 이는 소문자로 f_stat, m_stat과 같이 쓰자.
  • 전체 프로세서의 실제 상태는 W_stat을 기반으로 Write Back 단계에서 계산된다.
• SEQ+, PIPE- 의 디코드단계는 모두 valE, valM용 dstE, dstM 신호를 생성한다.
  • SEQ+에서는 이 신호를 레지스터 파일 쓰기 포트에 직접 꽂았지만
  • PIPE-에서는 이 신호가 파이프라인을 통해 전달되어, Write Back 단계에서 신호가 전달되면 그때 수행한다.
• PIPE에서 SEQ+에 없는게 하나 있다.
  • Select A 블럭
  • 이 블럭은 파이프라인 레지스터 D의 valP 혹은 레지스터파일의 A포트에서 값을 선택하여 valA를 결정한다.
  • 이는 파이프라인 레지스터 E와 M으로 전달되어야 하는 상태 양을 줄이기 위해서이다.
    • call 명령어만이 메모리단계에서 valP를 필요로 한다.
    • 조건부 점프만이 Execute 단계에서 valP를 필요로 한다. (안뛸떄)
    • 두 경우 모두 레지스터파일을 읽은 값을 쓰지 않는다.
    • 따라서 이 신호를 병합하여 valA를 통해 전달하면서, 파이프라인 레지스터의 상태 양을 줄일 수 있다.

4.5.4 Next PC Prediction

#

• 파이프라인 설계의 목표는 매 클럭 사이클마다 새로운 명령어를 발행하는 것
  • 이를 달성하기 위해선, 현재 명령을 가져온 직후 다음 명령어의 위치를 결정해야함
    • 하지만 가져온 명령어가 조건부 분기라면, 명령어가 실행 단계를 통과한 후에나 알 수 있다.
    • 가져온 명령어가 ret라면 메모리 단계를 통과한 후에나 알 수 있따.
  • 나머지는 모두 Fetch 단계에서 계산된 정보를 기반으로 다음 명령어의 주소를 결정할 수 있다.
    • call과 jmp의 경우에는 valC, 그 외의 경우에는 valP가 된다.
  • 따라서 PC의 다음 값을 예측하면서, 클럭마다 새로운 명령어를 발행시키자.
    • 조건부는 무조건 뛴다 or 무조건 안뛴다 등으로 결정해버리면 된다.
    • 예측이 틀렸을때 어떻게 하는지는 4.5.8장에서 다루겠다.
  • 이 방법을 분기 예측 (branch prediction) 이라고 한다.
    • 우리는 뭄조건 뛴다고 예측하고 해보자. 따라서 PC를 valC로 예측하자.
    • ret는.. 이슈가 깊다. 여기에서는 거의 모든 값이 올 수 있으니까.
      • 따라서, 우리 설계에서는 ret에 대해서는 예측하지 않고, Write back이 끝날때까지 명령어 처리를 보류하겠다.
      • 이것도 4.5.8에서 다루자.
  • Fetch 단계를 보면 Predict PC에 valP, valC가 꽂혀있는걸 볼 수 있다.
    • 이걸 F_predPC에 저장한다.
    • F_predPC와 M_valA, W_valM, M_cnd를 이용해서 Select PC를 진행한다.
    • ret일때는 W_valM, jump할때는 M_valA로 가던가 하겠다.

4.5.5 Pipeline Hazards

#

• 아직 우리는 종속성 문제를 해결하지 못했다.
• 종속성은 두가지 형태로 나타난다.
  • 데이터 종속성
    • 한 명령어에 의해 계산된 결과가 후속 명령어의 데이터로 사용되는 경우
  • 제어 종속성
    • 한 명령어가 후속 명령어의 위치를 결정하는 경우
    • jump, call, ret일때
• 이 위험성들을 우리는 hazard라고 한다.
  • 이도 똑같이 데이터 hazard, 제어 hazard라고 한다.
• Data hazard

  irmovq $10, %rdx
  irmovq $3, %rax
  (여러개의 nop)
  addq %rdx, %rax
  halt

  • 와 같은 코드가 있었다고 할 때, nop의 개수에 따라 오류가 발생할 수도 안발생할 수도 있다.
  • 예를들어 nop가 세개 이상이라면 문제가 없지만, 없다면? addq가 rdx, rax를 읽을때 위의 명령어들의 Write back 단계에 가지 못했기 때문
  • Avoid Data Hazards by Stalling
    • 위험조건이 더이상 성립하지 않을 때까지 파이프라인 내 하나 이상의 명령어를 대기시키는 것
    • 소스 연산자를 생성하는 명령어가 쓰기 Write back 단계를 통과할 때 까지 Decode 단계의 명령어를 대기시키면 된다.
    • addq 명령어가 Decode 단계에 있을 때, Execute, Memory, Write back 단계에 있는 명령어중 하나가 %rdx나 %rax를 업데이트 할 것을 감지하면, 명령어를 스테일링해서 Decode 단계에서 대기시킨다.
      • 물론 이때 뒤의 Fetch단계에 있는 명령어도 보류된다.
    • 이는 실행단계에 버블을 주입해서 처리한다.
      • 이는 동적으로 생긴 nop와 같다.
      • 상세 메커니즘은 4.5.8에서 살펴보자.
    • 그러나 이러한 방법은 구현은 쉽지만 아무래도 결과적인 성능이 좋진 않다.
      • 3사이클이나 쉬게 되니까
  • Avoiding Data Hazards by Forwarding
    • PIPE는 기본적으로 소스 연산자를 Decode 단계에서 레지스터 파일에서 읽지만, 해당 소스 레지스터중 하나에 대한 쓰기 작업이 Wrtie back 단계에서 대기중일 수도 있다!
      • 써질때까지 기다리는 대신, 곧 쓰일 값을 거기서 Decode 단계에 훔쳐와서 써버리자.
    • 이런 방법을 Data Forwarding / Forwarding / Bypassing 이라고 한다.
    • 데이터 포워딩을 구현하기 위해선 기본적인 하드웨어 구조에 추가적인 데이터 연결 및 제어 로직이 있어야 한다.
    • 이렇게 데이터 해저드를 포워딩으로 처리할 수 있는 PIPE를 PIPE+라고 한다.
  • Load/Use Data Hazards
    • Memory 작업이 파이프라인 후반부에 있기에, 포워딩만으로 처리할 수 없는 한 해저드 클래스가 존재한다.

    mrmovq 0(%rdx), %rax
    addq %ebx, %eax

    • 위와 같이 메모리에서 읽어온 값을 그대로 써야한다고 해보자.
    • 이건 데이터 포워딩으로 불가능할 것 같다. 어떻게 해야하지?
      • 이건 어쩔수없이 Stalling 해야한다.
      • Stall 한번 후 Memory 단계에서 Forward로 데려오면 되겠다!
    • 이런 load/use Hazard를 피하기 위한 stall + Forward를 load interlock이라고 한다.
      • 이것만이 파이프라인 처리량을감소시키므로, 매 클럭 사이클마다 새로운 명령어를 발행한다는 목표는 거의 도달했다고 볼 수 있다.
• Control Hazards
  • 이는 위에서 말한것과 같이 Fetch단계의 현재 명령어를 기반으로 다음 명령어의 주소를 신뢰할 수 없을때
    • ret / jump 에 대해서만 이슈
      • 특히 jump는 예측을 실패했을때만 이슈
  • ret는 fetch 후 write back 단계에 돌입할때까지 (Memory가 끝날때까지) bubble을 주입해서 다음 PC를 계산할 수 있도록 기다린다.
    • bubble 3개!
  • jump가 이슈인데, 이는 일단 분기 예측을 했다고 가정하자. 분기 예측을 실패하면, 몇개의 잘못된 명령어들이 Fetch, Decode에 들어가있는 상태이다.
    • 그러면 이 잘못된 명령어 / 계산값들을 버려야한다.
    • 따라서 디코드 및 실행 단계에 버블을 주입해서, 이 명령어들을 취소 (instruction squashing) 할 수 있다.
    • 우리가 관찰 가능한 상태에는 문제가 안생기고, 두 클럭이 낭비된다는 단점만 있다.
• 구체적인 방법은 4.5.8장에서 보자. (왤케 미루냐)

4.5.6 Exception Handling

#

• 프로세서 내의 다양한 활동이 예외 상황으로 갈 수도 있다.
  • 이건 프로그램에 의해 내부적으로 / 혹은 외부 신호에 의해 외부적으로 생성될 수 있다.
  • 우리 ISA에는 다음과 같은 내부 생성 예외가 있다.
    • 정지 명령어 (halt)
    • 명령어와 함수 코드의 유효하지 않은 조합
    • 명령어 페치 또는 데이터 읽기/쓰기에서 유효하지 않은 주소에 대한접근
  • 보다 완전한 프로세서라면, 네트워크 인터페이스가 새 패킷을 수신하거나 / 사용자가 클릭을 했다는 외부 예외도 처리해야 한다.
• 예외를 발생시킨 명령어를 예외 발생 명령어 (excepting instruction) 이라고 부르자.
  • 실제 이런 명령어는 존재하지 않지만, 유효하지 않은 주소에 가상 명령어가 존재한다고 생각하면 쉽다.
  • 예외에 도달하면 정지하고, 적절한 상태 코드를 설정해야한다.
• 파이프라인 시스템에서 예외처리는 몇가지 미묘한 세부 사항을 수반한다
  • 여러 명령어에 의해 동시에 예외가 발생할 수 있다.
    • Fetch / Memory 단계에서 동시에 발생할 수 있지
    • 그러면 어떤걸 먼저 보고할지 결정해야 한다.
      • 기본 규칙은 가장 먼저 진행된 명령어에 의해 트리거된 예외에 우선 순위를부여하는 것
      • 그러면 Memory겠네
  • 명령어가 처음 Fetch되어 시작되고 예외를 발생시킨 후, 잘못된 분기예측으로 인해 취소된 경우
    • 이 명령어를 취소하지만, 예외도 발생시키지 않도록 해야한다.
    • fetch조차 되면 안되는 명령어였기 때문
  • 예외를 발생시키는 명령어 다음에 오는 명령어가 해당 예외 명령어가 완료되기 전에 시스템 상태의 일부에 영향을 줄 수 있다.
    • Memory 단계에서 예외를 발견했지만, 이때 Execute에서 조건코드같은걸 수정한 경우
    • 예외 발생 이후에는 어떤 명령어도 시스템 상태에 영향을 미치면 안되니까

4.5.7 PIPE Stage Implementations

#

• 이제 포워딩을 갖춘 Y86-64 PIPE의 전체 구조를 완성했다.
• PC_Relection and fetch Stage
  • PC에 대한 현재 값을 선택하고 다음 PC값을 예측
  • Select PC에서 될 수 있는 값은
    • F_predPC (웬만한 경우)
    • M_valA (예측 실패한 분기가 메모리단계에 진입할떄 / ret가 아닌 valP)
    • W_valM (ret 명령어가 워크백 단계에 진입할 때)
• Decode and Write-Back Stages
  • dstE, dstM, srcA, srcB 를 잘 관리하기
  • 포워딩을 신경써야한다.
  • 포워딩 소스는 총 5개가 존재한다.
    • e_valE -> e_dstE
    • m_valM -> M_dstM
    • M_valE -> M_dstE
    • W_valM -> W_dstM
    • W_valE -> W_dstE
  • 이 5개중에 해당하지 않으면 블럭은 레지스터 포트 A에서 읽은 d_rvalA를 출력하면 된다.
  • 위의 순서대로 우선순위가 잡혀있는데, 이는 상당히 중요하다.
• Execute Stage
  • SEQ때랑 비슷하다.
  • 조건 코드를 업데이트하는 set CC가 m_stat과 W_stat 신호를 입력으로 받는것만 차이
    • 파이프라인 앞단계에 예외 상태인 명령어가 있으면 조건코드 업데이트를 막기 위해!
• Memory Stage
  • SEQ때랑 거의 동일하다.

4.5.8 Pipeline Control logic

#

• 이제 데이터 포워딩 / 분기예측과 같은 메커니즘으로 처리할 수 없는 네가지 제어 사례를 처리하고, PIPE의 설계를 완료하자.
  • Load/use Hazard
    • 한사이클 정지해야함
  • ret
    • ret이 write-back에 도달할때까지 파이프라인이 정지해야함
  • 잘못된 예측 분기
    • 명령어들을 취소하고, 점프명령어 다음 명령어에서 명령어 추출이 시작되어야함
  • Exception
    • 예외가 발생해씅랟, 관찰 가능한 상태의 업데이트를 비활성화해야함
• Desired Handling of Special Control Cases
  • load/use
    • 4.5.5에서 배운것과 같이, mrmovq, popq만이 데이터를 읽는데
    • 이들 중 하나가 execute 스테이지에 있고
    • 목적지 레지스터를 필요로하는 명령어가 decode에 있을때
    • 대기시키고 다음 사이클의 실행단계에 bubble을 주입해야 한다.
    • 파이프라인 레지스터 D, F를 고정해야 한다.
  • ret
    • 3사이클 대기시키면 된다.
  • 잘못된 예측 분기
    • D, E단계에 버블을 주입한다.
    • 올바른 명령어를 fetch한다.
  • 예외 발생
    • 파이프라인 구현이 원하는 ISA동작과 일치하도록 한다.
    • 이게 좀 어렵다.
      • 예외가 프로그램 실행중 Fetch / Memory 두단계에서 발생할 수 있고
      • 프로그램 상태가 Execute / Memory / write-back 세곳에서 업데이트되기 때문
    • 각 단계에는 stat이 포함되어있어서, 명령어마다 그 상태를 추적한다.
    • 예외가 발생하면 해당 정보를 상태 일부로 기록하고, 메모리 단계에 도달하면, 후속 명령어가 관찰 가능한상태를 수정하지 못하도록
      • Execute 단계의 명령어가 조건 코드를 설정하지 못하도록 비활성화
      • Memory 단계에 버블을 주입하여 데이터 메모리로의 쓰기 비활성화
      • Write back 단계에 예외를 유발하는 명령어가 있을 경우 정지
        • write-back이 레지스터 파일을 갱신하는 유일한 단계이기 때문!
• Detecting Special Control Conditions
  • 이런 특수 상황이 발생하는 조건
  • load/use
    • E_icode ∊ {IMRMOVQ, IPOPQ} && E_dstM ∊ {d_srcA, d_srcB}
  • ret
    • IRET ∊ {D_icode, E_icode, M_icode}
  • 잘못된 예측 분기
    • E_icode = IJXX&& !e_Cnd
  • 예외
    • m_stat ∊ {SADR, SINS, SHLT} || W_stat ∊ {SADR, SINS, SHLT}
• Pipeline Control Mechanisms
  • 클럭이 튈때, stall과 bubble에 따라 갱신 / 고정 / nop화를 할 수 있겠다
  • stall과 bubble을 동시에 1로 설정하는것은 오류로 간주한다.
• Combinations of Control Conditions
  • 현실에서는 여러 특수조건이 동시에발생할 수도 있다.
  • 하지만 우리가 상호배타적으로 세팅을 잘 해놔서, 뜰만한 중첩이 많이 없다.
  • 해봤자 예측실패와 ret1, load/use와 ret1정도.
    • 앞을 조합 A, 뒤를 조합 B라고 하자.
  • 조합 A에서는 분기가 잘못 예측되었음을 감지하고 ret를 취소한다.
  • 조합 B에서, ret때문에 버블을 넣으면 좀 곤란해진다.
    • load/use에서는 Decode를 stall하려고하고
    • ret때문에는 Decode 단계에 버블이 들어가니까
    • ret를 위해 한 사이클 지연되어야한다.
• Control logic implementation
  • 이를 모두 관리하는 Pipeline control Logic이라는게 있어야한다.
  • 여기서 F_stall, D_bubble, D_stall, E_bubble…등을 관리하고
  • D_icode, d_srcA, d_srcB, e_Cnt..등을 받아서 처리해야한다.

4.5.9 Performance Analysis

#

• 파이프라인 제어 로직때문에 우리 목적이었던 매 클럭마다 명령어 하나 처리하기를 못하게 되긴한다.
  • 이건 버블의 주입 빈도를 측정함으로써 정량화할 수 있다.
    • 이 측정을 CPI (Cycle Per Instruction)이라고 한다.
    • 이 측정은 파이프라인의 평균 처리 속도의 역수이지만, 시간은 피코초가 아닌 클럭 사이클 단위로 측정된다.
  • $C_i$를 명령어 개수, $C_b$를 버블 개수라고 하면
    • $CPI = \frac{C_i + C_b}{c_i} = 1.0 + \frac{C_b}{C_i}$
    • 따라서 명령어당 버블 비율로 나타낼 수 있는데, 버블이 들어가는 예이ㅗ는 세가지가 있으므로
    • $CPI = 1.0 + lp + mp + rp$
      • load penelty / mispredicted branch penalty / return penalty
    • 이때 비율들로 계산할 수 있겠다.

4.5.10 Unfinished Business

#

• 아직도 누락된 사항들이 존재한다.
• Multicycle Instructions
  • 정수 곱셈 / 나눗셈이나 부동소수점 연산을 수행하는 명령어도 구현해야 한다.
  • ALU를 사용해서 실행단계 로직의 기능을 확장하면 되겠지만, 성능이 너무 낮아진다.
    • 나눗셈의 경우 64사이클이나 걸릴수도 있다..
  • 그래서 독립적으로 작동하는 특수 하드웨어 기능 유닛을 사용한다.
    • 물론 파이프라이닝도 되어있다
• Interfacing with the Memory System
  • 명령어 인출과 데이터메모리 모두 한 메모리 위에 있고
  • 가상주소를 참조하기전에 실제주소를 가야하고…
  • 메모리값이 디스크에 있어서 수백만 클럭 사이클이 필요할수도
  • 이건 6, 9장에서 나중에 더 자세히 배울 것이다.
  • 운영체제, 가상메모리, 캐시 등등등

❔질문 사항

#

valA = MUX(
  srcA == e_dstE ? e_valE :   // Execute 단계에서 forwarding
  srcA == m_dstM ? m_valM :   // Memory 단계에서 forwarding
  srcA == W_dstE ? W_valE :   // Write-back 단계에서 forwarding
  ...
  RegisterFile[srcA]           // 정상 경로
)

🔗 참고 자료

#