고성능 마이크로프로세서 설계 기법 순천향대학교 정보기술공학부 이 상 정 Review today, not so fast in future 순천향대학교 정보기술공학부 이 상 정

주 요 내 용 프로세서 성능 결정 요인 파이프라인 파이프라인 해저드 명령어 수준 병렬성(ILP) 코드이동 다중이슈 모험적 실행

프로세서 성능 결정 요인 Inst Count CPI Clock Rate Program X Compiler X (X) CPU time = Seconds = Instructions x Cycles x Seconds Program Program Instruction Cycle Inst Count CPI Clock Rate Program X Compiler X (X) Inst. Set. X X Organization X X Technology X

파이프라인 이란? 세탁 예 A, B, C, D 각기 옷을 세탁, 말림, 접기 세탁에 30분 소요 말림에 30분 소요 접기에 30분 소요 옷을 서랍에 정리하는데 30분 소요 A B C D

순차 세탁 6 PM 7 8 9 10 11 12 1 2 AM T a s k O r d e 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 Time A B C D 순차세탁은 4개의 세탁을 위해 8시간 소요 파이프라인을 적용했을 경우 얼마나 소요될 것인가?

파이프라인 세탁 6 PM 7 8 9 10 11 12 1 2 AM B C D A 30 Time T a s k O r d e 파이프 라인 세탁은 4개 세탁에 대해 3.5 시간 소요 !

파이프라인 교훈 6 PM 7 8 9 T a s k O r d e B C D A 30 파이프라인은 단일 태스크의 처리시간(latency)을 줄이지 않지만 전체작업의 시간을 줄임(throughput) 다수의 태스크가 다른 자원을 이용하여 동시에 수행 Potential speedup = Number pipe stages 파이프라인 처리속도는 가장 늦은 파이프 스테이지에 의해 제한 파이프 스테이지의 길이가 다른 경우 성능 저하 시작 시 파이프라인 채우는 시간과 종료 시 끝나는 시간 동안에는 모두 중첩 실행되지 않음 Stall for Dependences 6 PM 7 8 9 Time T a s k O r d e B C D A 30

명령어 파이프라인 스테이지 예 IF: 명령 페치 (Instruction Fetch) Cycle 1 Cycle 2 Cycle 3 Cycle 4 Cycle 5 IF ID EX MEM WB IF: 명령 페치 (Instruction Fetch) 명령어 캐시로 부터 다음에 수행될 명령어 페치 ID: 명령 디코드(Decode/Registers Fetch) 수행될 명령어 디코드, 레지스터 오퍼랜드 읽기 Ex: 명령 수행(EXecution/Effective Address) 명령의 수행, 메모리 연산의 유효 주소 계산 MEM: 메모리 참조 (MEMory Access/Branch completion Cycle) 메모리 참조, 분기명령 수행 Wr: Write-Back Cycle 연산 결과 및 메모리 참조 내용의 레지스터 저장

파이프라인 중첩실행 IF ID EX MEM WB Time IF ID EX MEM WB IF ID EX MEM WB IF ID Program Flow IF ID EX MEM WB

5 스테이지 수행 경로

Single Cycle, Multiple Cycle, vs. Pipeline Clk Single Cycle Implementation: Load Store Waste Cycle 1 Cycle 2 Cycle 3 Cycle 4 Cycle 5 Cycle 6 Cycle 7 Cycle 8 Cycle 9 Cycle 10 Clk Multiple Cycle Implementation: Load Store R-type IF ID EX MEM WB IF ID EX MEM IF Pipeline Implementation: Load IF ID EX MEM WB Store IF ID EX MEM WB R-type IF ID EX MEM WB

파이프라인의 성능 비교 100개 명령을 수행하는 예 가정 Single Cycle Machine 45 ns/cycle x 1 CPI x 100 inst = 4500 ns Multicycle Machine 10 ns/cycle x 4.6 CPI (due to inst mix) x 100 inst = 4600 ns Ideal pipelined machine 10 ns/cycle x (1 CPI x 100 inst + 4 cycle drain) = 1040 ns

Visualizing Pipelining

Pipelined DLX Datapath

성능 비교 예 Unpipelined CPU: Average instruction execution time 10-ns clock cycle Four cycles for ALU operations and branches Five cycles for memory operations Frequency = 40%, 20% and 40% Average instruction execution time = Clock * Average CPI = 10ns*((.4+.2)*4 + (.4*5)) = 10ns*4.4 = 44ns

성능 비교 예 Pipelined CPU: Averge instruction execution time Speedup 11-ns clock cycle (to accommodate slowest stage) No pipeline conflicts Averge instruction execution time = 11ns Speedup = Time unpipelined / Time pipelined = 44ns/11ns = 4

파이프라인 장애 요인- 파이프라인 해저드(Pipeline Hazards) 해저드 는 다음 명령이 지정된 클럭에서 계속 수행하는 것을 방해한다. 구조적 해저드(Structural hazards): 하드웨어가 여러 명령들을 수행을 지원하지 않기 때문에 발생, 자원충돌(resource conflicts) 데이터 해저드(Data hazards): 명령이 현재 파이프라인에서 수행 중인 이전명령의 결과에 종속되는 경우 발생 제어 해저드(Control hazards): 분기 명령어에 의해 발생 해저드를 해결하는 가장 단순한 방식은 해저드의 요인이 소멸될 때까지 파이프라인을 중지(stall) 하는 것이다.

1 메모리 포트 구조적 해저드

1 메모리 포트 구조적 해저드

데이터 해저드, R1 add r1,r2,r3 sub r4,r1,r3 and r6,r1,r7 or r8,r1,r9 Time (clock cycles) IF ID/RF EX MEM WB I n s t r. O r d e add r1,r2,r3 sub r4,r1,r3 and r6,r1,r7 or r8,r1,r9 xor r10,r1,r11

세가지 유형의 데이터 해저드 - RAW 명령 InstrI 다음에 명령 InstrJ 오는 예 Read After Write (RAW) 명령 InstrI 가 저장한 오퍼랜드를 명령 InstrJ 가 읽을때 발생 A = B + C; D = A + E; 명령 InstrI 가 WB 스테이지 에서 결과값을 쓰기를 할 때까지 기다려야 한다.

세가지 유형의 데이터 해저드 - WAR 명령 InstrI 다음에 명령 InstrJ 오는 예 Write After Read (WAR) 명령 InstrI 가 오퍼랜드를 읽기 전에 명령 InstrJ 가 같은 오퍼랜드를 읽는 경우 발생 A = B + C; B = D + E; 단일 파이프라인에서는 발생하지 않음: 스테이지 2에서 오퍼랜드 읽고, 스테이지 5에서 오퍼랜드 쓰기 때문 동시에 수행하는 다중이슈(multiple issue)에서는 발생

세가지 유형의 데이터 해저드 - WAW 명령 InstrI 다음에 명령 InstrJ 오는 예 Write After Write (WAW) 명령 InstrI 가 오퍼랜드를 쓰기 전에 명령 InstrJ 가 같은 오퍼랜드를 쓰는 경우 발생 A = B + C; B = D + E; 단일 파이프라인에서는 발생하지 않음: 동시에 수행하는 다중이슈(multiple issue)에서는 발생

데이터 해저드를 피하기 위한 포워딩(Forwarding) Time (clock cycles) I n s t r. O r d e add r1,r2,r3 sub r4,r1,r3 and r6,r1,r7 or r8,r1,r9 xor r10,r1,r11

포워딩을 위한 하드웨어 변경

포워딩을 해결할 수 없는 데이터 해저드 lw r1, 0(r2) sub r4,r1,r6 and r6,r1,r7 Time (clock cycles) I n s t r. O r d e lw r1, 0(r2) sub r4,r1,r6 and r6,r1,r7 or r8,r1,r9

포워딩을 해결할 수 없는 데이터 해저드 lw r1, 0(r2) sub r4,r1,r6 and r6,r1,r7 Time (clock cycles) I n s t r. O r d e lw r1, 0(r2) sub r4,r1,r6 and r6,r1,r7 or r8,r1,r9

데이터해저드를 해결하기 위한 소프트웨어 스케쥴링 데이터해저드를 해결하기 위한 소프트웨어 스케쥴링 Try producing fast code for a = b + c; d = e - f; assuming a, b, c, d ,e, and f in memory. Slow code: LW Rb,b LW Rc,c ADD Ra,Rb,Rc SW a,Ra LW Re,e LW Rf,f SUB Rd,Re,Rf SW d,Rd Fast code: LW Rb,b LW Rc,c LW Re,e ADD Ra,Rb,Rc LW Rf,f SW a,Ra SUB Rd,Re,Rf SW d,Rd

분기명령에 의한 제어 해저드(Control Hazard) IF ID EX MEM WB Time Branch IF stall ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB Program Flow

분기 중지 영향(Branch Stall Impact) If CPI = 1, 30% branch, Stall 3 cycles => new CPI = 1.9! 2가지 해결: 분기주건의 조기 결정, AND 분기주소의 조기결정 RISC 머신의 조건분기, register = 0 or  0 해결책: 0 값의 조건 테스트를 ID/RF 스테이지에서 수행 분기주소계산을 위한 덧셈기 추가 3 클럭 손실 대신 1 클럭 손실

제어 해저드 IF ID EX MEM WB Time Branch stall IF ID EX MEM WB IF ID EX MEM Program Flow

파이프라인 수행 경로 Does MIPS test affect clock (add forwarding logic too!)

분기 해저드 해소 방법들 #1: 분기 방향이 결정될 때까지 중지 #2: Predict Branch Not Taken 다음 명령을 무조건 수행 분기가 taken 된 경우 파이프라인 상의 명령을 취소(Squash) 47% DLX 분기 명령이 not taken PC+4 는 이미 계산되었기 때문에 다음 명령 페치 시 바로 사용할 수 있다. #3: Predict Branch Taken 53% DLX 분기 명령이 taken 그러나 대부분 머신에서는 타겟 주소가 계산되지 않았기 때문에 여전히 1 사이클 분기손실 필요

분기 해저드 해소 방법들 #4: 지연분기(Delayed Branch) #4: 분기예측(branch prediction) 분기손실되는 클럭 동안에 다른 명령 수행 branch instruction sequential successor1 sequential successor2 ........ sequential successorn branch target if taken #4: 분기예측(branch prediction) Branch delay of length n

지연분기 – 지연슬롯 위치

명령어 수준 병렬성 코드 예 ILP (Instruction Level Parallelism) 서로 관련 없는(데이터 종속관계가 없는) 명령들을 중첩 실행 프로그래머에게는 노출되지 않고 컴파일러나 하드웨어가 이들 명령들을 검출하여 병렬 수행 명령어 스케쥴링(instruction scheduling) 소프트웨어 스케쥴링, 하드웨어 스케쥴링 코드 예 A = B + C; => A = B + C, X = Y – Z; B = D + E; B = D + E, C = F + G; X = Y – Z; C = F + G;

코드 이동(Code Movement): Dependencies v. Hazards 주어진 파이프라인 상에서 하드웨어 해저드 유무를 프로그램 상의 종속관계를 이용하여 검출 해저드를 제거하는 방향으로 스케쥴 참 종속관계 (True Data dependencies) 하드웨어 해저드인 경우 RAW 명령 i가 종속관계가 있는 이 후 명령 j에서 사용될 결과를 생성 데이터 종속관계가 있는 경우 병렬로 수행할 없다. 레지스터 오퍼랜드인 경우 쉽게 종속관계 결정: R6=R7? 메모리 참조인 경우 종속관계 결정 어려움 0(R4) = 0(R6)? ( p* = q* ?) 다른 루프 반복, 20(R6) = 20(R6)?

코드 이동 또 다른 종류의 종속관계는 이름 종속관계(name dependence): 역 종속관계(Anti-dependence) 두 명령이 같은 이름(레지스터나 메모리)를 사용하지만 데이터를 서로 주고 받지는 않는다. 역 종속관계(Anti-dependence) 하드웨어 해저드인 경우는 WAR 명령 j 가 이전에 명령 i에서 읽은 오퍼랜드 값의 쓰기를 하는 경우 출력 종속관계(Output dependence) 하드웨어 해저드인 경우 WAW 명령 i 와 명령 j 가 같은 오퍼랜드를 쓰기 명령 간의 순서가 유지되어야 한다.

다중 이슈(Multiple Issue); Getting CPI < 1 두 가지 형태의 머신 구성 슈퍼스칼라(supersclalr), VLIW 프로세서 슈퍼스칼라 프로세서 동시에 1-8개의 명령을 페치하고 이슈하여 수행 주로 하드웨어에 의해 동시에 수행되는 명령들을 스케쥴 IBM PowerPC, Sun UltraSparc, DEC Alpha, HP 8000 (Very) Long Instruction Words (V)LIW: 컴파일러에 의해 스케쥴된 고정된 수의 명령들(1-16)을 병렬로 수행 Joint HP/Intel agreement in 1999/2000? => Itanium (Merced) Intel Architecture-64 (IA-64) 64-bit address Style: “Explicitly Parallel Instruction Computer (EPIC)”

다중이슈 파이프라인 Type Pipe Stages Int. instruction IF ID EX MEM WB FP instruction IF ID EX MEM WB Int. instruction IF ID EX MEM WB FP instruction IF ID EX MEM WB Int. instruction IF ID EX MEM WB FP instruction IF ID EX MEM WB

모험적 실행(speculation) 다중이슈 머신에서는 제어종속이나 데이터 종속관계 로 인해서 명령들이 병렬처리 되지 못하면 성능 저하가 심각 분기명령의 경우 분기조건이 나올 때까지 다음 명령들을 페치하지 않고 기다리면 성능 손실이 심각 일반 데이터 종속관계가 있는 명령의 경우도 이전의 결과값이 계산되기까지 기다리는 경우 성능이 손실 현대 고성능 프로세서에서는 위와 같은 경우 명령을 기다리지 않고 분기의 조건이나 명령의 수행결과를 기다리지 않고 이 결과값을 예측하여 계속 수행한다. 이를 모험적 실행(speculative execution)이라 한다.

모험적 실행(speculation) 예측이 맞는 경우 계속 진행하고 예측이 틀린 경우 잘못된 수행을 취소하고 올바른 수행을 해야 한다. 분기예측(branch prediction) 한 분기의 이전에 수행된 분기의 결과를 테이블에 저장하고 다시 이 분기의 수행 시에 저장된 결과값을 이용하여 예측 약 95% 이상 예측 정확도 값 예측(value prediction) 한 명령의 이전에 수행된 결과값들을 테이블에 저장하고 다시 이 명령을 수행 시에 테이블에 저장된 결과값을 참조하여 예측 약 80% 이상의 예측 정확도

다중이슈, 모험적 실행 지원을 위한 하드웨어 모험적 실행의 결과와 올바로 수행된 실제 결과를 분리 다중이슈, 모험적 실행 지원을 위한 하드웨어 모험적 실행의 결과와 올바로 수행된 실제 결과를 분리 모험적 실행의 결과 값을 바로 레지스터나 메모리에 저장하지 않고 리오더버퍼(reorder buffer)에 저장 모든 예측이 올바로 예측된 경우 버퍼의 내용을 레지스터나 메모리에 저장 => instruction comit 잘못 실행된 경우 버퍼의 내용을 지움

Pentium 동적 스케쥴링 모델 Pentium 동적 스케쥴링 모델 Dynexec-ppro.exe

Dynamic Scheduling in PowerPC 604 and Pentium Pro Both In-order Issue, Out-of-order execution, In-order Commit

Dynamic Scheduling in PowerPC 604 and Pentium Pro Parameter PPC PPro Max. instructions issued/clock 4 3 Max. instr. complete exec./clock 6 5 Max. instr. commited/clock 6 3 Window (Instrs in reorder buffer) 16 40 Number of reservations stations 12 20 Number of rename registers 8int/12FP 40 No. integer functional units (FUs) 2 2 No. floating point FUs 1 1 No. branch FUs 1 1 No. complex integer FUs 1 0 No. memory FUs 1 1 load +1 store Q: How pipeline 1 to 17 byte x86 instructions?

Dynamic Scheduling in Pentium Pro Ppro는 80x86 명령(CISC)을 파이프라인 처리하지 않는다. Ppro는 80x86 명령을 디코드하여 여러 개의 마이크로연산 (RISC)으로 분리한다. 마이크로연산을 리오더버퍼나 reservation stations에 보낸다. 80x86 명령어 크기 결정에 1 클럭 + 마이크로연산 생성에 2 클럭 전체 파이프라인 수행 시 12-14 클럭 소요 대부분의 명령이 1-4개의 마이크로연산으로 분리