고성능 마이크로프로세서 설계하여 보자

고성능 마이크로프로세서 설계 기법 주요내용 1. 프로세서 성능 결정 요인 2. 파이프라인 3. 파이프라인 해저드 4. 명령어 수준 병렬성 (ILP) 5. 코드이동 6. 다중이슈 7. 모험적 실행 프로세서 성능 결정 요인 CPU time = Seconds = Instructions x Cycles x Seconds Program Program Instruction Cycle Program Compiler Inst. Set. Organization Technology Inst Count CPI Clock Rate X X (X) X X X X X 파이프라인 이란 ? . 세탁 예 . A, B, C, D 각기옷을 세탁 , 말림, 접기 . 세탁에 30분 소요 . 말림에 30분 소요 . 접기에 30분 소요 . 옷을 서랍에 정리하는데 30분 소요 A B C D 순차 세탁 6 PM 7 8 9 10 1112 12 AM 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 T Time a s k O r d e r . 순차세탁은 4개의 세탁을 위해 8시간 소요 . 파이프라인을 적용했을 경우 얼마나 소요될 것인가 ? C D B A 파이프라인 세탁 6 PM 7 8 9 10 1112 12 AM Time 3030 3030303030 T a s k O r d e r . 파이프 라인 세탁은 4개 세탁에 대해 3.5 시간 소요 ! B C A D 파이프라인 교훈 . 파이프라인은 단일 태스크의 처리시간 (latency) 을 줄이지 6 PM 7 89 않지만 전체작업의 시간을 줄임(throughput) Time . 다수의 태스크가 다른 자원을 T 3030 3030303030 이용하여 동시에 수행 a . Potential speedup = s Number pipe stages k . 파이프라인 처리속도는 가장 늦은 파이프 스테이지에 의해 B A O r d e r C D 제한 . 파이프 스테이지의 길이가 다른경우 성능 저하 . 시작 시 파이프라인 채우는 시간과종료 시 끝나는시간 동안에는 모두 중첩 실행되지 않음 . Stall for Dependences 명령어 파이프라인 스테이지 예 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 . 연산결과 및 메모리참조내용의레지스터저장 파이프라인 중첩실행 Time IF ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB Program Flow IF ID EX MEM WB 5 스테이지 수행 경로 Single Cycle, Multiple Cycle, vs. Pipeline Clk Cycle 1 Multiple Cycle Implementation: IF ID EX MEM WB Cycle 2 Cycle 3 Cycle 4 Cycle 5 Cycle 6 Cycle 7 Cycle 8 Cycle 9 Cycle 10 Load IF ID EX MEM WB IF ID EX MEM Load Store Pipeline Implementation: Clk Single Cycle Implementation: Load Store Waste IF R-type Cycle 1 Cycle 2 IF ID EX MEM WBStore 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: . 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: . 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 n s t r. O r d e r Time (clock cycles) add r1,r2,r3 sub r4,r1,r3 and r6,r1,r7 or r8,r1,r9 xor r10,r1,r11 IF ID/RF EX MEM WB 세가지 유형의 데이터 해저드 -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) n s t r. O r d e r Time (clock cycles) add r1,r2,r3 sub r4,r1,r3 and r6,r1,r7 or r8,r1,r9 xor r10,r1,r11 포워딩을 위한 하드웨어 변경 포워딩을 해결할 수 없는 데이터 해저드 n s t r. O r d e r Time (clock cycles) lw r1, 0(r2) sub r4,r1,r6 and r6,r1,r7 or r8,r1,r9 포워딩을 해결할 수 없는 데이터 해저드 n s t r. O r d e r Time (clock cycles) 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: Fast code: LW Rb,b LW Rb,b LW Rc,c LW Rc,c ADD Ra,Rb,Rc LW Re,e SW a,Ra ADD Ra,Rb,Rc LW Re,e LW Rf,f LW Rf,f SW a,Ra SUB Rd,Re,Rf SUB Rd,Re,Rf SW d,Rd SW d,Rd 분기명령에 의한 제어 해저드 (Control Hazard) Time Branch IF ID EX MEM WB IF ID EX MEM WB IF stall stall IF ID EX MEM WB IF ID EX MEM 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 클럭 손실 제어 해저드 Time Branch IF ID EX MEM WB IF ID EX MEM WB stall IF ID EX MEM WB IF ID EX MEM WB Program Flow 파이프라인 수행 경로 분기 해저드 해소 방법들 #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) . 분기손실되는 클럭 동안에 다른 명령 수행 branch instruction sequential successor1 sequential successor2 ........ sequential successorn Branch delay of length n branch target if taken #4: 분기예측 (branch prediction) 지연분기 . 지연슬롯 위치 명령어 수준 병렬성 . 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) . 하드웨어 해저드인 경우는 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 PipeStages Int. instruction FP instruction Int. instruction FP instruction Int. instruction FP instruction IF IF ID ID IF IF EX EX ID ID IF IF MEM MEM EX EX ID ID WB WB MEM MEM EX EX WB WB MEM MEM WB 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 개의 마이크로연산으로 분리