[컴퓨터구조] 프로세서 5. RISC-V ILP(명령어 수준 병렬성)

CSE/컴퓨터구조

[컴퓨터구조] 프로세서 5. RISC-V ILP(명령어 수준 병렬성)

minkylee 2024. 6. 15. 19:57

ILP(instruction-level parallelism, 명령어 수준 병렬성)

파이프라이닝은 명령어 사이의 병렬성을 이용하는 기법이다. 병렬 수준을 높이기 위한 방법은 다음 두 가지가 있다.

파이프라인 깊이를 증가시켜 더 많은 명령어들을 중첩시키는 방법
매 파이프라인 단계에서 다수의 명령어를 내보내는 방법

Multiple level

다중 내보내기
다수의 명령어를 내보내어 동시에 둘 이상의 명령어를 처리한다.
매 단계마다 다수의 명령어를 내보내면 명령어 실행 속도가 클럭 속도보다 빨라질 수 있다. 즉, CPI가 1보다 작아질 수 있어 명령어 1개를 실행하는 속도가 클럭 속도보다 빨라진다.

Static multiple issue vs dynamic multiple issue

static multiple issue : 컴파일러가 프로그램을 컴파일 할 때 명령어들을 그룹으로 묶어 한 번에 여러 개의 명령어를 동시에 실행할 수 있도록 하는 방식
- 컴파일러는 여러 명령어를 한 그룹으로 묶고 명령어 그룹을 issue slot에 패키지한다.
- 컴파일러가 명령어들을 분석하여 데이터 충돌을 피한다. (두 명령어가 같은 데이터를 동시에 읽거나 쓰는 상황)
dynamic multiple issue : CPU 가 프로그램 실행 중에 명령어 스트림을 분석하여 각 사이클마다 실행할 명령어들을 선택하는 방식
- CPU는 실행 중인 명령어 스트림을 실시간으로 분석한다.
- 각 사이클마다 실행할 명령어들을 선택하고 CPU는 동시에 실행할 수 있는 명령어들을 찾아낸다.
- 명령어 순서를 재조정하더나 명령어 사이에 적절한 지연을 삽입하여 충돌을 해결한다.
- 컴파일러는 명령어를 미리 재배열하여 CPU가 명령어를 선택하기 쉽게 도와준다.

RISC-V with Static Dual Issue

한 번에 두 개의 명령어를 실행할 수 있는 issue packet을 사용한다.
하나의 패킷은 ALU/Branch를 포함한다. 다른 하나는 Load/Store 명령을 포함한다.
명령어는 64비트로 정렬된다.
ALU/Branch 명령어가 먼저 오고, 그 다음에 Load/Store 명령어가 온다.
사용하지 않는 명령어 슬롯은 NOP 명령어로 채운다.

예를 들어 다음 명령어들이 존재할 경우

add x1, x2, x3   # ALU 명령어
lw x4, 0(x5)     # 로드 명령어
beq x1, x2, loop # 분기 명령어
sw x6, 0(x7)     # 스토어 명령어

issue packet으로 재배열한다.

첫 번째 패킷: add x1, x2, x3 (ALU 명령어), lw x4, 0(x5) (로드 명령어)
두 번째 패킷: beq x1, x2, loop (분기 명령어), sw x6, 0(x7) (스토어 명령어)

Dual Issue 환경에서는 더 많은 명령어가 병렬로 실행되기 때문에 Hazard가 더 복잡해진다.

이를 해결하기 위해 더 공격적인 스케줄링이 필요하다.

EX Data Hazard:
- ALU 연산 결과를 같은 패킷 내에서 로드/스토어 명령어에서 사용할 수 없다
- 예: add x10, x0, x1과 ld x2, 0(x10)은 같은 패킷에 포함될 수 없으며, 이를 해결하기 위해 두 패킷으로 분리해야 한다. 이는 효과적으로 stall을 발생시킨다.
Load-Use Hazard:
- 로드 명령어 이후 즉시 로드된 데이터를 사용하는 명령어가 있을 때 발생하는 Hazard
- 예: 로드 명령어 이후 1 사이클의 사용 지연(latency)이 있지만, 듀얼 이슈에서는 2개의 명령어가 동시에 발행되므로 Hazard가 더 복잡해진다.

예시

Loop:
    ld x31, 0(x20)      // x31 = array element
    add x31, x31, x21  // add scalar in x21
    sd x31, 0(x20)     // store result
    addi x20, x20, 8   // increment pointer
    blt x22, x20, Loop // branch if x22 < x20

// 이 명령어들을 스케줄링 할 경우

Loop:
1 cycle:
    nop               // ALU/분기 슬롯
    ld x31, 0(x20)    // 로드/스토어 슬롯

2 cycle:
    addi x20, x20, 8  // ALU/분기 슬롯
    nop               // 로드/스토어 슬롯

3 cycle:
    add x31, x31, x21 // ALU/분기 슬롯
    nop               // 로드/스토어 슬롯

4 cycle:
    blt x22, x20, Loop // ALU/분기 슬롯
    sd x31, 0(x20)    // 로드/스토어 슬롯

이 스케줄링 방법을 통해 Dual Issue에서 명령어가 효율적으로 실행된다. NOP은 사용하지 않는 슬롯을 채우기 위해 삽입된다.

IPC는 5개의 명령어를 4번의 사이클로 실행하므로 5 / 4 = 1.25 이다. 이상적인 최대 IPC 2.0에 비해 낮지만, Dual Issue 환경에서 효율적으로 명령어를 실행한 결과이다.

Loop Unrolling

루프 본문을 복제하여 병렬성을 더욱 드러내고 루프 제어 오버헤드를 줄이는 방법을 설명한다.

이를 위해 register renaming을 사용하여 loop carried anti-dependencies(루프 반복 간에 발생하는 레지스터 이름 충돌)를 피한다. 이렇게 하면 같은 레지스터를 여러 번 사용하는 문제를 해결하고, 명령어 병렬 실행을 최적화 할 수 있다.

anti-dependency : 저장 명령어 다음에 같은 레지스터를 로드하는 명령어가 오는 경우

원래 루프는 다음과 같다.

Loop:
    ld x31, 0(x20)         // x31 = array element
    add x31, x31, x21      // add scalar in x21
    sd x31, 0(x20)         // store result
    addi x20, x20, 8       // increment pointer
    blt x22, x20, Loop     // branch if x22 < x20

보면 반복적으로 x31 레지스터를 ld 하고 연산을 한 다음 x31 레지스터에 sd 하는 것을 볼 수 있다.

루프 본문을 복제하고 레지스터 리네이밍을 완료한 결과는 다음과 같다.

Loop 4개를 복제해 x28, x29, x30, x31 네 개의 레지스터를 사용하게 하였다.

이 때 IPC = 14/8 = 1.75 로 이상적인 최대 IPC 2에 가깝다

더 많은 레지스터와 코드 크기의 증가를 대가로 성능을 향상시켰다.

Dynamic multiple issue

Dynamic multiple issue를 실행하는 프로세서는 Superscalar 라고도 한다. 제일 간단한 Superscalar 프로세서는 명령어를 순서대로 내보내고 주어진 클럭 사이클에 몇 개의 명령어를 내보낼 지 결정한다.

많은 Superscalar 프로세서는 동적 파이프라인 스케줄링(dynamic pipeline scheduling)을 포함한다.

한 사이클에 0개, 1개, 2개 또는 그 이상의 명령어를 실행 가능하며 구조적 hazard 와 데이터 hazard를 회피한다.

CPU가 자동으로 명령어를 스케줄링 하므로 컴파일러가 명령어를 최적화하여 배치할 필요가 없다. 그러나 컴파일러의 스케줄링은 여전히 성능 향상에 도움이 될 수 있다.

CPU는 매 사이클 마다 몇 개의 명령어를 실행할 지 결정하며, 명령어의 순서를 변경해도 코드의 의미가 유지되도록 한다.

요약하면 동적 스케줄링은

명령어의 순서 변경
- CPU는 명령어를 순서대로 실행하지 않고, 가능한 병렬로 실행할 수 있도록 순서를 변경한다.
- 예를 들어, 데이터가 준비되지 않은 명령어는 대기하고, 그 동안 다른 명령어를 먼저 실행한다.
순서대로 커밋
- 실행 결과는 레지스터에 순서대로 커밋한다.
- 이를 통해 프로그램의 논리적 일관성을 유지한다.

예시

다음과 같은 명령어가 있다고 하면

ld x31, 20(x1)     // 메모리에서 값을 로드하여 x31에 저장
add x1, x31, x2    // x31과 x2를 더하여 x1에 저장
sub x23, x23, x3   // x23에서 x3를 빼서 x23에 저장
andi x5, x23, 20   // x23과 20의 AND 결과를 x5에 저장

명령어 재배열을 한다.
- ld x31, 20(x1) 명령어가 실행 중일 때, CPU는 add x1, x31, x2 명령어가 x31의 값을 기다려야 하므로 대기한다.
- 그 동안 CPU는 sub x23, x23, x3 명령어를 먼저 실행한다.
동시 실행
- ld x31, 20(x1) 명령어가 메모리에서 데이터를 로드하는 동안, sub x23, x23, x3 명령어가 동시에 실행된다.
순서대로 커밋
- 모든 명령어가 실행된 후, 결과는 원래 명령어 순서에 따라 레지스터에 저장된다.

Instruction Fetch and Decode Unit (명령어 인출 및 디코드 유닛)
- 명령어를 프로그램 메모리에서 가져와 Decode 한다.
- 명령어를 각 Reservation Station으로 보낸다.
Reservation Station
- 각각의 기능 유닛에 연결된 Reservation station이 있다.
- In-order 방식으로 명령어를 받는다.
- 대기 중인 Operand를 보유한다.
- 모든 Operand가 준비되면, 명령어를 실행 유닛으로 보낸다.
Functional Unit
- Reservation에 연결된 실제 연산을 수행하는 유닛이다.
- 정수 연산, 부동 소수점 연산, Load-Store 등 다양한 유형이 있다.
- Out-of-order 방식으로 명령어를 실행한다.
Commit Unit
- 명령어 실행 결과를 순서대로 커밋한다.
- 레지스터에 결과를 쓰기 위한 Reorder Buffer를 사용한다.
  - 결과값을 버퍼에 두었다가 안전할 때 결과값을 메모리나 레지스터 파일에 쓴다.
  - 전방 전달 회로가 피연산자들을 다른 Reservation station 으로 제공해준다.
- In-order 방식으로 결과를 커밋하여 코드의 의미와 순서를 보장한다.

동작 과정

In-order Issue
- Instruction Fetch and Decode Unit에서 명령어를 가져와 Decode한 후, Reservation station으로 보낸다.
- 명령어는 프로그램의 순서대로 Reservation station에 전달된다.
Holding Pending Operand
- 모든 Operand가 준비될 때 까지 명령어를 대기시킨다.
- 필요한 Operand가 준비되면 명령어는 Functional Unit으로 이동한다.
Out-of-order Execution
- Functional Unit은 Reservation station에서 받은 명령어를 실행한다.
- 명령어는 준비된 순서대로 실행되므로, 실제 실행 순서는 프로그램 순서와 다를 수 있다.
- 실행 결과는 대기 중인 다른 Reservation station 으로도 전달된다.
In-order commit
- 실행 결과는 Commit Unit으로 보내져 순서대로 커밋된다.
- Commit Unit은 레지스터에 결과를 쓰기 위한 Reorder Buffer를 사용하여 프로그램의 의미와 순서를 보장한다.
- 발행된 명령어의 Operand를 발행된 명령어에 제공할 수 있다.

Reservation station과 out-of-order 실행을 통해 구조적 및 데이터 Hazard를 피한다.
여러 명령어를 동시에 실행하여 성능을 높인다.
프로그램의 의미와 순서를 보장한다.

Register Renaming

Reservation station 과 reorder buffer가 레지스터 이름 변경을 효과적으로 제공한다. 이게 무슨 뜻일까?

명령어가 Reservation station에 들어갈 때

필요한 데이터가 이미 레지스터나 Reorder Buffer에 있는 경우
- 데이터를 Reservation station으로 복사한다.
- 이제 이 레지스터는 다른 명령어가 사용할 수 있다.
데이터가 아직 준비되지 않은 경우
- 데이터가 준비되는 즉시 functional Unit에서 Reservation station으로 전달된다 -> 레지스터를 다시 업데이트 할 필요가 없다.

Dynamic multiple issue 에서 프로세서(CPU)는 프로그램의 데이터 흐름 순서를 바꾸지 않는 범위 내에서 명령어의 실해 순서를 바꿀 수 있다. 이러한 실행 형태를 비순차 실행(out-of-order execution) 이라고 한다.

순차적으로 실행되는 유닛들, Instruction fetch and decode unit 이 순서대로 명령어들을 내보내고 commit unit은 프로그램 인출 순서대로 결과를 레지스터나 메모리에 써야 한다. 이러한 쓰기를 순차 결과 쓰기 (inorder commit) 이라고 한다.

Predict Branch and Load Speculation

분기 명령어가 들어왔을 때 CPU는 분기명령어를 예측하고 명령어 실행을 계속한다. 그리고 분기 결과가 확실해질 때까지 실행된 명령어를 확정하지 않는다.

Load 명령어가 들어오면 지연되지 않도록 예측을 사용하는데 CPU가 메모리 주소를 미리 예측하여 그 값을 메모리에서 읽어온다. 실제 데이터가 아니더라도, 예측된 값을 사용하여 잠시동안 작업을 계속한다.

대기 중인 Store 명령이 있더라도 Load 명령어를 먼저 실행한다. 필요한 경우, 저장된 값을 직접 Load Unit으로 전달하여 데이터를 사용한다.

확정 전까지는 Load Commit 하지 않는다. 만약 예측이 틀렸다면, 올바른 데이터를 가져와서 수정한다.

이를 통해 CPU는 메모리 접근 지연으로 인한 성능 저하를 줄이고, 더 효율적으로 작업을 처리할 수 있다.

Compiler Scheduling 의 한계

왜 복잡한 Dynamic Scheduling을 할까?

예측 불가능한 Stall
- 모든 Stall을 예측할 수 없다 (Cache Miss)
분기 결과는 동적으로 결정되기 때문에 컴파일러가 미리 예측하기 어렵다.
ISA 구현의 차이로 인한 문제
- 같은 명령어 집합 아키텍처(ISA)를 사용하더라도, CPU 제조사나 모델에 따라 명령어 실행 시간과 Hazard가 다를 수 있다.
- 예를 들어, 어떤 CPU는 특정 명령어를 더 빨리 처리할 수 있고, 어떤 CPU는 같은 명령어를 처리하는데 더 오래 걸릴 수 있다.

Multiple Issue 기술의 한계

프로그램의 명령어들 간에는 순서대로 실행되어야 하는 의존성들이 있어 병렬 실행을 제한한다.
제거하기 어려운 의존성이 있다 (ex.pointer aliasing)
명령어 발행 시 창 크기 제한, 메모리 지연, 대역폭 한계 등으로 병렬 처리가 어려워 질 수 있다.
Speculation (CPU가 미래의 명령어를 예측하여 준비) 는 이러한 문제를 해결할 수 있다.

참고

https://narakit.tistory.com/125