Instruction-Level Parallelism (ILP) and Its Exploitation

ILP: concepts and Challenges

ILP -> hardware, software 두가지 방법으로 끌어낸다.

CPI < 1

branch 와 다음 branch 사이의 instruction 들을 basic block 이라고 함.
한 basic block 안에서 ILP를 끌어내는 것은 한계가 있기 때문에 여러개의 basic block 에서 ILP를 이끌어내야함.
가장 간단한 방법은 loop iteration 에서 찾는 것. -> loop-level parallelism

• 이 경우 vector processing이 효율적이다.

Compiler technique

loop unrolling , scheduling
여러개의 loop를 합쳐서 loop 조건 연산을 줄이거나, 순서를 바꿔서 stall 를 줄임.
limitation -> code size 가 커짐, register pressure 가 쎄짐.

Branch prediction

static - compile time 에
dynamic - hardware 가 실제 연산 도중에.

dynamic 중에 two-level, correlation, tournament predictor 들이 있음.
(local) (global) (둘 다)

Dynamic scheduling

Compile time(static)에 해결 못하는 것들을 해결(ex. cache miss 로 인한 delay)

Tomasulo의 방법이 대표적.

• reservation station, renaming 등을 이용.
• 장점으로는 distribution of hazard detection logic, elimination of stalls for WAW, WAR 이 있음.

Tomasulo 알고리즘은 2.5절에서 잘 설명되어있음. 찾아볼 것.
이 scheme 은 개발된 이후 몇년동안 잘 안쓰이다가 90년대 이후에 널리 쓰이게 되었는데
그 이유는 다음과 같다.

1. 특정코드, 특정 하드웨어, 컴파일러의 지원없이 성능향상이 가능
2. 캐시가 고안되기 전에 생긴 방법이지만, 캐시로 인한 예측불가능 delay 때문에 더욱 널리 쓰이게 됨. Out-of-order 는 캐시 미스로 이한 delay 시간동안 연산을 계속 수행가능하도록 해줌.
3. issue capability 에 더욱 집중, schedule 이 어려운 코드에 더 신경을 쓰면서 중요해짐.
4. dynamic scheduling 이 speculation 에 중요한 요소이고, speculation 이 90년대 중반에 적용되기 시작함.

Hardware-Based Speculation

speculation 을 통해 control dependence 를 극복하자.
speculation 으로 미리 연산후 맞을 경우 commit한다.

multiple issue static scheduling

in-order / out-of-order superscalar & VLIW

Advanced technique

1. fetch bandwidth 를 늘리는데, 문제는 branch. -> Branch Target Buffer 를 사용
2. return address predictors -> procedure return 주소를 예측.
3. prefetch, branch prediction, memory access 등의 정보를 저장하는 trace cache.

Limits on ILP

1. window size
2. branch / jump prediction
3. finite registers
4. imperfect alias analysis

Reference

John Hennessy and David Patterson, Computer Architecture