[컴퓨터구조#7-1] ILP (Instruction-Level Parallelism) - dependence, Out-of-Order execution, 동적 스케줄링

참고: Computer Architecture: A Quantitative Approach (5th edition) - 3. Instruction-Level Parallelism and its Exploitation

이번 글과 다음 글에서는 ILP에 대해 다룰 것이다. 이번 글에서는 여러 가지 의존성(data/name/control/memory dependence)와 out-of-order execution, 그리고 동적 스케줄링에 대해 소개하고 다음 글에서는 Tomasulo 알고리즘에 대해 논의할 것이다.

목차

1. Dependence
2. Out-of-Order Execution
3. Dynamic Scheduling
4. Tomasulo Algorithm

---

0. ILP

본격적인 내용에 들어가기 앞서, ILP 란, 여러 명령어를 병렬적으로 실행하는 것을 의미한다. 하드웨어적 관점에서는 하드웨어가 parallelism을 발견하고 동적으로 hazard를 피하는 것(superscalar out-of-order 프로세서 등), 소프트웨어적 관점에서는 소프트웨어(컴파일러)가 parallelism을 발견하고 명령어를 정적으로 스케줄링하는 것(VLIW, EPIC)을 의미한다. 하드웨어 접근법에서는 명령어 실행이 re-order될 수 있다. 하지만 결국에는 in-order 프로그램 순서를 유지해야 한다.

Basic block은 단일 entry point와 exit point을 가지는 코드 시퀀스를 의미한다. exit point를 제외하고는 브랜치를 포함하고 있지 않다. 평균 동적 브랜치 비율은 15~25%이므로 이 basic block 크기는 4~7개의 명령어로 이뤄진다. basic block 내부에서는 ILP를 제한적으로밖에 활용할 수 없다.

→ 실행 경로를 추측(speculation)하려면, 여러 basic block 간의 parallelism을 찾아야 한다. 물론 잘못된 경로를 예측하여 실행할 수도 있다. 이 경우 현재 state를 버리고 올바른 state에서 다시 시작해야 한다.

 

1. Dependence

Data Dependence

: 다른 명령어의 결과르 사용하는 true dependence 혹은 RAW를 의미한다.

(예시) sub의 operand로 add의 결과 r2를 사용한다.

add r2, r3, r4
sub r5, r2, r6

Data dependent한 명령어는 완벽하게 오버랩될 수 없다. Bypassing, 동적 스케줄링 등 data dependence의 비용을 줄이려는 아키텍처 기술들이 있다.

Data dependence는 hazard의 가능성, 결과들이 계산되어야 하는 순서, 그리고 최대로 활용될 수 있는 병렬성에 대한 상한을 시사(set theoretical upper bound on ILP)한다. 정확한 결과를 위해서는 데이터 간 순서가 보장되어야 하기 때문에, 최대로 빠른 경로는 data dependence graph의 critical path가 되는 것이다. 

이런 ILP의 한계를 극복하기 위해, dependence는 유지하되 hazard를 피하거나, 코드를 변경함으로써 dependence를 제거하는 방법이 있을 수 있다. 전자의 경우 컴파일러나 하드웨어에 의한 코드 스케줄링을 통해 실현될 수 있다.

 

Name Dependence

두 명령어가 같은 레지스터나 메모리 위치(name)을 사용하지만 두 명령어 간 해당 이름과 관련된 데이터 흐름이 없는 경우 Name Dependence라고 한다. 다음 두 종류의 name dependence가 있다.

• Anti-dependence (WAR Hazard) : add에서 r2의 값을 읽고 그 이후 sub에서 r2에 값을 쓴다. add가 올바른 값을 가지려면 add와 sub의 순서가 유지되어야 한다. (만약 sub와 add의 순서를 바꾸면 add도 원치 않은 r2값을 읽게 되며 두 명령어 간 RAW hazard가 된다.)

add r1, r2, r4
sub r2, r5, r6

• Output-dependence (WAW Hazard) : add에서 r2에 값을 쓰고 이후 sub에서도 r2에 값을 쓴다. r2가 최신 값을 유지하도록 하려면 마찬가지로 두 명령어 간 순서가 보장되어야 한다. 그래야 그 이후에 xor이 정확한 r2의 최신 값(sub의 결과)을 유지할 수 있다.

add r2, r3, r4
sub r2, r5, r6
xor r7, r2, r8

 이런 name dependence는 제한된 name (=레지스터 혹은 메모리 위치) 때문에 발생한다. 만약 아키텍처 레지스터가 무제한으로 욌다면 이런 dependence는 발생하지 않을 것이다. 하드웨어적으로 register renaming을 통해 이를 해결할 수 있다. (컴파일러에서 레지스터 이름을 지정해도 프로세서 내에서 자체적으로 레지스터를 renaming하여 특정 instr. window 내에서는 ISA에서 정해진 개수 이상의 레지스터 이름을 사용할 수 있게 한다.)

 

Control Dependence

(dynamic한 순서인 경우) 모든 명령어는 어떤 older conditional branch에 dependent하다.

예를 들어 다음과 같은 예시에서 S1은 p1에 control dependent하며 S2는 p2에 control dependent하다. 하지만 S2가 p1에 control dependent하지는 않다.

if p1 {
	S1
}
if p2 {
	S2
}

만약 프로그램이 정해진 순서대로(in-order) 실행된다면 control dependence는 당연히 보장된다. 하지만 (프로그램 정확도를 위반하지 않는다면) 실행되어서는 안 되는 명령어가 실행되어 control dependence를 위반하게 될 수도 있다. 따라서, control dependence는 반드시 보존되어야 하는 critical 특징은 아니다. 대신, 프로그램 정확도에 주요한 역할을 하는, 그리고 보통 data와 control dependence를 통해서 모두 유지될 수 있는) exception behavior와 data flow가 유지되어야 한다. 

Exception behavior

예외 행동을 보존한다는 것은 명령어 실행 순서를 바꾸더라도 프로그램에서 발생하는 exception에는 영향을 주어서는 안 된다는 것을 의미한다. (→ 명령어를 재배치해도 프로그램에 새로운 exception을 일으키면 안 된다. 로 relax되기도 함)

예를 들어, 다음 예시에서 ld와 add 간 dependnece가 없기 때문에 add는 ld 전에 실행될 수 있다.

ld r1, 0(r9)
add r2, r3, r4

명령어가 exception-free한 상태가 되기 전까지는 system state를 업데이트하면 안 되기 때문에 레지스터와 메모리에 대한 쓰기를 hold하고 있어야 한다. 이를 위한 아키텍처적 해결방법으로는 out-of-order로 실행하지만 in-order로 커밋하는 Reorder buffer가 있다.

 

Memory Dependence

메모리 위치를 통한 data dependence를 의미한다. (*이전까지의 dependence는 레지스터 name 기반의 dependence였다.) 이 memory dependence는 주소를 계산한 이후에만 식별될 수 있다.

예를 들어, r8+100 = r9 = r10-10 이라고 해보자.

/* RAW */
sw r6, 100(r8)
ld r1, 0(r9)

/* WAR */
ld r1, 100(r8)
sw r6, 0(r9)

/* WAW */
sw r1, 100(r8)
sw r6, 0(r9)
ld r7, -10(r10)

• RAW: sw에서 r6의 값을 r8+100(=r9)에 저장하는데 다음 ld에서 r9 값을 r1에 저장하는 상황 → store에서 load로 bypassing하여 해결할 수 있음
• WAR: RAW와 동일한 반대의 경우
• WAW: sw로 같은 주소에 연속적으로 write 후 ld에서 값을 읽어오는 상황

메모리 주소는 실행 전까지는 알 수 없기 때문에 하드웨어에서는 이를 register 기반의 dependence보다 더 알아차리기 어렵다.

 

2. Out-of-Order Execution

다음과 같은 여러 가지 multi-issue 프로세서가 있다.

In-order Superscalar	- in-order로 시행 - Alpha 21164, SPARC
Out-of-Order Superscalar	- out-of-order execution, in-order commit - 하드웨어가 dependence를 확인하고 명령어를 스케줄링한다. - out-of-order load는 허용할 수도 있고 안 할 수도 있다.
VLIW (Very Long Instruction Word)	- 컴파일러를 통해 명령어 그룹을 생성한다. 그룹 내에서는 dependence가 존재하지 않는다. - 그룹 내의 명령어는 병렬적으로 실행된다. - 컴파일러가 dependence 없는 그룹을 보장하기 때문에 하드웨어가 간단하다. - 그룹들 간에는 in-order execution
EPIC (Explicitly Parallel Instruction Computing)	- VLIW를 지원하는 더 많은 하드웨어가 있다. (유동성 ↑) - 인텔 Itanium

이 중, Superscalar OoO Execuion에 대해 알아보자.

역할에 따라 크게 세 종류의 unit으로 구분된다.

	Fetch & Decode Units	Issue logics & Execution Units	Instruction Retire (commit)
해당 unit	branch predictor branch target buffer (BTB) Instruction cache register file	reservationi station w/ bypassing functional units (execution 단위) load-store unit data cache register file	reorder buffer
특징	- in-order이지만 speculative함 - 여러 명령어를 fetch함 - 브랜치 방향과 타겟을 예측	- out-of-order -동적 스케줄링 - load/store ordering - bypassing / register renaming	- in-order, non-speculative - RF 업데이트 - 메모리 업데이트 - exception 처리

Instruction Fetch

각 사이클마다 basic block 내 여러 개의 명령어를 fetch할 필요가 있다. 단순한 브랜치 스케줄링이나 브랜치 지연 슬롯은 공격적인 ILP 프로세서에는 충분치 않다. 다음과 같은 추가적인 유닛이 필요하다.

• 브랜치 방향 예측: branch predictor
• 브랜치 타겟 예측: branch target buffer
• 리턴 주소 예측: return address stack

 

3. Dynamic Scheduling

동적으로 스케줄링할 때도, data dependence를 만족하도록 명령어를 스케줄링해야 한다. 이에 맞춰 (int adder, int multiplier, fp adder, fp mult/div .. 등) 여러 Functional Unit을 스케줄링해야 하고, 피연산자들이 준비가 되면 명령어를 실행해야 한다. 또한, 여러 명령어가 ready라면 그 중 어느 것을 실행할지도 고려해야 한다.

하드웨어 renaming을 통해 name dependence를 줄이고, out-of-order 코어이더라도 in-order semantic을 반드시 준수해야 한다. 즉, 레지스터나 메모리는 in-order로 업데이트되어야 한다.

하드웨어는 dependence chain을 추출하고 stall을 최소화하도록 명령어들을 재배열한다. 이 과정에서 캐시를 통한 load 명령어의 지연시간, 메모리 주소에서의 dependence 등 예측 불가한 의존성이나 지연을 효과적으로 처리할 수 있다. 또한, 동적 스케줄링은 하나의 파이프라인에 최적화된 코드를 다른 파이프라인에서도 효율적으로 돌릴 수 있으며 speculation을 더 효과적으로 만든다.

 

Out-of-order Execution / Register Renaming

다음과 같은 명령어들이 있다고 생각해보자.

I1: LW R1, 10(R9)
I2: SUB R3, R1, R2
I3: ADD R2, R4, R5
I4: XOR R3, R4, R5
I5: LW R6, 20(R1)
I6: AND R7, R2, R3
I7: OR R8, R6, R7

I2와 I3 사이에 WAR, I2와 I4 사이에 WAW, 그리고 I6와 I6 사이에 RAW hazard가 존재한다.

하드웨어에서 Register renaming을 통해 이런 dependence를 없앨 수 있다.

I1: LW P1, 10(R9)
I2: SUB P3, P1, P2
I3: ADD P2x, P4, P5
I4: XOR P3x, P4, P5
I5: LW P6, 20(P1)
I6: AND P7, P2x, P3x
I7: OR P8, P6, P7

만약 물리적 레지스터의 개수가 아키텍처적 레지스터(ISA에 정의된 것)보다 많다면 새로운 임시 이름을 더 생성할 수 있고, 더 이상 사용 가능한 물리적 레지스터가 없다면 WAR/WAW를 structural hazard로 바꿀 수 있다.