Lec7 - Speculative Execution (updated)

p.1

p.2speculative execution(추측 실행)을 통한 더 높은 ILP

• control dependence(제어 종속성)을 극복하기 위해 hardware speculation mechanism(하드웨어 추측 메커니즘)을 사용한다.
• speculative execution(추측 실행) ⇒ branch prediction(브랜치 예측)이 항상 올바르다고 가정하고 예외가 없다는 가정 하에 명령어를 fetch(페치), 이슈, execute(실행)한다.
• dynamic scheduling(동적 스케줄링) + speculative execution(추측 실행) ⇒ 본질적으로 data flow execution model(데이터 흐름 실행 모델)이다: 연산은 연산자가 모두 준비되면 즉시 실행된다.
• 그러나 speculative execution(추측 실행)은 잘못될 수 있다!
• 잘못된 브랜치 예측 (IBM 360/91은 브랜치에 대해 speculative execution(추측 실행)하지 않았음)
• IBM 360/91은 'imprecise interrupts(불정확한 인터럽트)'를 고안했다.
• 컴퓨터는 이 PC에서 멈췄으며, 이 주소 근처일 가능성이 높다.
• 디버깅이 더 어려워진다 – 특히 시스템 프로그래머에게.
• 또한 트랩(예: page fault(페이지 폴트))은 어떻게 처리할 것인가?
• 잘못된 speculative execution(추측 실행)에서 복구하고 다시 시작할 수 있는 메커니즘이 필요하다.

p.3precise exception(정확한 예외)를 위한 In-Order commit(순서 유지 커밋)

• 순서 유지 fetch(페치) 및 decode(디코딩), 그리고 reservation station(예약 스테이션)과 reorder buffer(재정렬 버퍼)로 dispatch(디스패치)한다.
• 이 강의에서는 'dispatch(디스패치)'를 '이슈'로 의미하지 않는다.
• reservation station(예약 스테이션)에서 Out-of-Order issue(비순차 이슈).
• Out-of-Order completion(비순차 완료), 결과는 reorder buffer(재정렬 버퍼)에 저장.
• In-Order commit(순서 유지 커밋) – 명령어가 더 이상 speculative execution(추측 실행)이 아니게 되면 reorder buffer(재정렬 버퍼)의 값을 architectural state(아키텍처 상태)에 업데이트한다.
• speculative execution(추측 실행)이 잘못된 경우, 복구 및 flush(플러시)하여 speculative execution(추측 실행)된 명령어를 제거한다.
• fetch(페치) → decode(디코딩) → execute(실행) → commit(커밋)
• reorder buffer(재정렬 버퍼)
• 순서 유지
• 순서 유지
• 비순차
• 예외?
• (또는 mispredicted branch(잘못된 브랜치 예측)?)
• Kill
• Kill
• Kill
• handler PC(핸들러 PC) 삽입
• (또는 정확한 PC)

p.4reorder buffer(재정렬 버퍼) 동작

• 명령어를 dispatch(디스패치)된 순서 그대로 FIFO order(FIFO 순서)로 보관한다.
• 명령어가 완료되면 결과를 ROB에 저장한다.
• execute(실행) 완료와 commit(커밋) 사이의 다른 명령어에게 연산자 제공 ⇒ RS와 유사한 더 많은 레지스터 제공.
• 결과에 reorder buffer(재정렬 버퍼) 번호로 태그를 붙임 (예약 스테이션 대신).
• 명령어가 commit(커밋)되면 ROB의 머리에 있는 값이 레지스터에 업데이트된다.
• ROB는 store buffer(스토어 버퍼)를 대체할 수 있다.
• 결과적으로, mispredicted branch(잘못된 브랜치 예측)이나 예외 발생 시 speculative execution(추측 실행)된 명령어를 쉽게 되돌릴 수 있다.
• reorder buffer(재정렬 버퍼)
• FP 연산 대기열
• FP adder(FP 가산기)
• FP multiplier(FP 곱셈기)
• reservation station(예약 스테이션)
• reservation station(예약 스테이션)
• FP 레지스터
• commit(커밋) 경로

p.5ROB를 사용한 tomasulo’s algorithm(토마술로 알고리즘)

• ROB의 각 항목은 네 개의 필드를 포함한다.
• 1. 명령어 유형
• 브랜치(결과 목적지 없음), 스토어(메모리 주소 목적지), 레지스터 연산(ALU 연산 또는 로드, 레지스터 목적지 있음)
• 2. 목적지
• 로드 및 ALU 연산의 경우 레지스터 번호, 스토어의 경우 메모리 주소
• 3. 값
• 명령어가 commit(커밋)될 때까지 명령어 결과의 값
• 4. 준비
• 명령어가 execute(실행)을 완료했고 값이 준비되었음을 나타냄

p.6speculative execution(추측 실행) tomasulo’s algorithm(토마술로 알고리즘)의 네 단계

• 1. dispatch(디스패치) – FP 연산 대기열에서 명령어를 가져온다.
• reservation station(예약 스테이션)과 reorder buffer(재정렬 버퍼) 슬롯이 비어 있으면 명령어를 dispatch(디스패치)하고 연산자 및 목적지의 재정렬 버퍼 번호를 전송한다.
• 2. 이슈 및 execute(실행) – 연산자로 작업한다.
• 두 연산자가 모두 준비되면 execute(실행); 준비되지 않으면 CDB에서 결과를 감시; reservation station(예약 스테이션)에 두 연산자가 모두 있으면 실행; RAW hazard(RAW 해저드) 확인 (때때로 '이슈'라고도 함)
• 3. 결과 쓰기 – execute(실행) 완료
• common data bus(공통 데이터 버스)에 결과를 쓰고 모든 대기 중인 functional unit(기능 유닛)과 reorder buffer(재정렬 버퍼)에 전달; reservation station(예약 스테이션)을 사용 가능 상태로 표시.
• 4. commit(커밋) – reorder buffer(재정렬 버퍼)의 결과로 architectural state(아키텍처 상태) 업데이트 (또는 'graduation(졸업)'이라고도 함)
• reorder buffer(재정렬 버퍼)의 머리에 있는 명령어가 결과를 가지고 있으면, 레지스터에 결과를 업데이트하거나 메모리에 저장하고 재정렬 버퍼에서 명령어를 제거한다. mispredicted branch(잘못된 브랜치 예측) 시 재정렬 버퍼를 flush(플러시)한다.

p.7tomasulo’s algorithm(토마술로 알고리즘)과 reorder buffer(재정렬 버퍼)

• 메모리
• FP adder(FP 가산기)
• FP multiplier(FP 곱셈기)
• reservation station(예약 스테이션)
• FP 연산 큐
• ROB7
• ROB6
• ROB5
• ROB4
• ROB3
• ROB2
• ROB1
• F0
• LD F0,10(R2)
• N
• Done?
• Dest
• Dest
• 가장 오래된
• 가장 최근의
• 메모리에서
• 1 10+R2
• Dest
• reorder buffer(재정렬 버퍼)
• 레지스터

p.8tomasulo’s algorithm(토마술로 알고리즘)과 reorder buffer(재정렬 버퍼)

• 2 ADDD R(F4),ROB1
• 메모리
• FP adder(FP 가산기)
• FP multiplier(FP 곱셈기)
• reservation station(예약 스테이션)
• FP 연산 큐
• ROB7
• ROB6
• ROB5
• ROB4
• ROB3
• ROB2
• ROB1
• F10
• F0
• ADDD F10,F4,F0
• LD F0,10(R2)
• N
• N
• Done?
• Dest
• Dest
• 가장 오래된
• 가장 최근의
• 메모리에서
• 1 10+R2
• Dest
• reorder buffer(재정렬 버퍼)
• 레지스터

p.9tomasulo’s algorithm(토마술로 알고리즘)과 reorder buffer(재정렬 버퍼)

• 3 DIVD ROB2,R(F6)
• 2 ADDD R(F4),ROB1
• 메모리
• FP adder(FP 가산기)
• FP multiplier(FP 곱셈기)
• reservation station(예약 스테이션)
• FP 연산 큐
• ROB7
• ROB6
• ROB5
• ROB4
• ROB3
• ROB2
• ROB1
• F2
• F10
• F0
• DIVD F2,F10,F6
• ADDD F10,F4,F0
• LD F0,10(R2)
• N
• N
• N
• Done?
• Dest
• Dest
• 가장 오래된
• 가장 최근의
• 메모리에서
• 1 10+R2
• Dest
• reorder buffer(재정렬 버퍼)
• 레지스터

p.10tomasulo’s algorithm(토마술로 알고리즘)과 reorder buffer(재정렬 버퍼)

• 3 DIVD ROB2,R(F6)
• 2 ADDD R(F4),ROB1
• 메모리
• FP adder(FP 가산기)
• FP multiplier(FP 곱셈기)
• reservation station(예약 스테이션)
• FP 연산 큐
• ROB7
• ROB6
• ROB5
• ROB4
• ROB3
• ROB2
• ROB1
• --
• BNE F2,<…>
• N
• F2
• F10
• F0
• DIVD F2,F10,F6
• ADDD F10,F4,F0
• LD F0,10(R2)
• N
• N
• N
• Done?
• Dest
• Dest
• 가장 오래된
• 가장 최근의
• 메모리에서
• 1 10+R2
• Dest
• reorder buffer(재정렬 버퍼)
• 레지스터

p.11tomasulo’s algorithm(토마술로 알고리즘)과 reorder buffer(재정렬 버퍼)

• 3 DIVD ROB2,R(F6)
• 2 ADDD R(F4),ROB1
• 메모리
• FP adder(FP 가산기)
• FP multiplier(FP 곱셈기)
• reservation station(예약 스테이션)
• FP 연산 큐
• ROB7
• ROB6
• ROB5
• ROB4
• ROB3
• ROB2
• ROB1
• F4
• LD F4,0(R3)
• N
• --
• BNE F2,<…>
• N
• F2
• F10
• F0
• DIVD F2,F10,F6
• ADDD F10,F4,F0
• LD F0,10(R2)
• N
• N
• N
• Done?
• Dest
• Dest
• 가장 오래된
• 가장 최근의
• 메모리에서
• 1 10+R2
• Dest
• reorder buffer(재정렬 버퍼)
• 레지스터
• 5 0+R3

p.12tomasulo’s algorithm(토마술로 알고리즘)과 reorder buffer(재정렬 버퍼)

• 3 DIVD ROB2,R(F6)
• 2 ADDD R(F4),ROB1
• 6 ADDD ROB5, R(F6)
• 메모리
• FP adder(FP 가산기)
• FP multiplier(FP 곱셈기)
• reservation station(예약 스테이션)
• FP 연산 큐
• ROB7
• ROB6
• ROB5
• ROB4
• ROB3
• ROB2
• ROB1
• F0
• ADDD F0,F4,F6
• N
• F4
• LD F4,0(R3)
• N
• --
• BNE F2,<…>
• N
• F2
• F10
• F0
• DIVD F2,F10,F6
• ADDD F10,F4,F0
• LD F0,10(R2)
• N
• N
• N
• Done?
• Dest
• Dest
• 가장 오래된
• 가장 최근의
• 메모리에서
• 1 10+R2
• Dest
• reorder buffer(재정렬 버퍼)
• 레지스터
• 5 0+R3

p.13tomasulo’s algorithm(토마술로 알고리즘)과 reorder buffer(재정렬 버퍼)

• 3 DIVD ROB2,R(F6)
• 2 ADDD R(F4),ROB1
• 6 ADDD ROB5, R(F6)
• To
• Memory
• FP adders
• FP multipliers
• Reservation Stations
• FP Op Queue
• ROB7
• ROB6
• ROB5
• ROB4
• ROB3
• ROB2
• ROB1
• --
• F0
• ROB5
• ST F4,0(R3)
• ADDD F0,F4,F6
• N
• N
• F4
• LD F4,0(R3)
• N
• --
• BNE F2,<…>
• N
• F2
• F10
• F0
• DIVD F2,F10,F6
• ADDD F10,F4,F0
• LD F0,10(R2)
• N
• N
• N
• Done?
• Dest
• Dest
• Oldest
• Newest
• From Memory
• Dest
• Reorder Buffer
• Registers
• 1 10+R2
• 5 0+R3
• Tomasulo With Reorder buffer:

p.14tomasulo’s algorithm(토마술로 알고리즘)과 reorder buffer(재정렬 버퍼)

• 3 DIVD ROB2,R(F6)
• To
• Memory
• FP adders
• FP multipliers
• Reservation Stations
• FP Op Queue
• ROB7
• ROB6
• ROB5
• ROB4
• ROB3
• ROB2
• ROB1
• --
• F0
• M[10]
• ST F4,0(R3)
• ADDD F0,F4,F6
• Y
• N
• F4
• M[10]
• LD F4,0(R3)
• Y
• --
• BNE F2,<…>
• N
• F2
• F10
• F0
• DIVD F2,F10,F6
• ADDD F10,F4,F0
• LD F0,10(R2)
• N
• N
• N
• Done?
• Dest
• Dest
• Oldest
• Newest
• From Memory
• 1 10+R2
• Dest
• Reorder Buffer
• Registers
• 2 ADDD R(F4),ROB1
• 6 ADDD M[10],R(F6)
• Tomasulo With Reorder buffer:

p.15tomasulo’s algorithm(토마술로 알고리즘)과 reorder buffer(재정렬 버퍼)

• 3 DIVD ROB2,R(F6)
• 2 ADDD R(F4),ROB1
• To
• Memory
• FP adders
• FP multipliers
• Reservation Stations
• FP Op Queue
• ROB7
• ROB6
• ROB5
• ROB4
• ROB3
• ROB2
• ROB1
• --
• F0
• M[10]
• <val2>
• ST F4,0(R3)
• ADDD F0,F4,F6
• Y
• Ex
• F4
• M[10]
• LD F4,0(R3)
• Y
• --
• BNE F2,<…>
• N
• F2
• F10
• F0
• DIVD F2,F10,F6
• ADDD F10,F4,F0
• LD F0,10(R2)
• N
• N
• N
• Done?
• Dest
• Dest
• Oldest
• Newest
• From Memory
• 1 10+R2
• Dest
• Reorder Buffer
• Registers
• Tomasulo With Reorder buffer:

p.16tomasulo’s algorithm(토마술로 알고리즘)과 reorder buffer(재정렬 버퍼)

• --
• F0
• M[10]
• <val2>
• ST F4,0(R3)
• ADDD F0,F4,F6
• Y
• Ex
• F4
• M[10]
• LD F4,0(R3)
• Y
• --
• BNE F2,<…>
• N
• 3 DIVD ROB2,R(F6)
• 2 ADDD R(F4),ROB1
• To
• Memory
• FP adders
• FP multipliers
• Reservation Stations
• FP Op Queue
• ROB7
• ROB6
• ROB5
• ROB4
• ROB3
• ROB2
• ROB1
• F2
• F10
• F0
• DIVD F2,F10,F6
• ADDD F10,F4,F0
• LD F0,10(R2)
• N
• N
• N
• Done?
• Dest
• Dest
• Oldest
• Newest
• From Memory
• 1 10+R2
• Dest
• Reorder Buffer
• Registers
• What about memory hazards???
• Tomasulo With Reorder buffer:

p.17memory hazard(메모리 해저드) 회피

• WAW hazard(WAW 해저드) 및 WAR hazard(WAR 해저드)은 메모리에서 제거된다. 실제 메모리 업데이트는 스토어가 ROB의 머리에 있을 때 순서대로 수행되므로, 더 이전의 로드나 스토어가 여전히 보류 중일 수 없다.
• RAW hazard(RAW 해저드)은 두 가지 제약 조건으로 회피된다: ̶
• 로드의 effective address(유효 주소) 계산에 대해 program order(프로그램 순서) 유지 AND̶
• ROB 내 이전 스토어의 주소 == 현재 로드의 주소인 경우, 로드가 메모리에 접근하지 못하게 함
• 이 제약 조건들은, 이전 스토어가 데이터를 쓰기 전까지는 해당 메모리 위치에 쓰여진 데이터를 접근하는 로드가 수행되지 않도록 보장한다

p.18비순차 설계 공간

• reservation station(예약 스테이션)은 어디에 있는가?̶
• reorder buffer(재정렬 버퍼)의 일부인지, 별도의 이슈 윈도우인가?̶
• functional unit(기능 유닛)에 따라 분산되어 있는가, 중앙 집중화되어 있는가?
• register renaming(레지스터 이름 변경)은 어떻게 수행되는가?̶
• 태그와 데이터가 reservation station(예약 스테이션)에 저장되며, 별도의 architectural register file(아키텍처 레지스터 파일)을 사용하는 경우̶
• 태그만 reservation station(예약 스테이션)에 저장되고, 데이터는 unified physical register file(통합 물리 레지스터 파일)에 저장되는 경우

p.19Data-in-ROB design(ROB 내 데이터 설계)

• program order(프로그램 순서)로 circular buffer(순환 버퍼)로 관리되며, 새로운 명령어는 자유 슬롯에 dispatch(디스패치)됨. oldest instruction(가장 오래된 명령어)는 완료되었을 때 commit(커밋)/reclaim(회수)됨 (결과에 p bit (Presence Bit)(P 비트) 설정)
• 태그는 ROB 내 인덱스로 지정되며, dispatch(디스패치) 시 free pointer(자유 포인터) 값이 사용됨
• dispatch(디스패치) 시, non-busy(비사용) 상태의 소스 오퍼랜드는 architectural register file(아키텍처 레지스터 파일)에서 읽어 Src1 및 Src2에 복사하고 p bit (Presence Bit)(P 비트)를 설정함. busy(사용 중) 상태의 오퍼랜드는 생산자 태그를 복사하고 P 비트를 해제함
• dispatch(디스패치) 시 valid bit(유효 비트) v 설정, 이슈 시 issued bit(이슈 비트) i 설정
• 완료 시, 소스 태그를 검색하고 일치하는 경우 데이터를 src에 복사하고 p bit set(P 비트 설정). 결과 및 예외 플래그를 ROB에 기록
• commit(커밋) 시 exception status(예외 상태)를 확인하고 트랩이 없으면 결과를 architectural register file(아키텍처 레지스터 파일)에 복사
• 트랩 발생 시, 머신과 ROB를 flush(플러시)하고 free = oldest (즉, 빈 파이프라인)로 설정, 핸들러로 점프

p.20Data-in-ROB design(ROB 내 데이터 설계)에서의 이름 변경 관리

• p bit (Presence Bit)(P 비트)가 설정되어 있으면 architectural register file(아키텍처 레지스터 파일)의 값을 사용
• 아니면 tag field(태그 필드)는 값이 생성될/생성된 ROB 내 명령어를 나타냄
• dispatch(디스패치) 시, architectural register file(아키텍처 레지스터 파일)에서 <p, tag, value>를 읽은 후, 태그 인덱스의 ROB 내 생산 명령어에서 <p, result>를 읽고 필요한 경우 bypass(바이패스)하여 ROB에 복사
• 목적지 architectural register(아키텍처 레지스터) 항목에 <0, TAG, _>를 기록하며, TAG는 이 명령어의 ROB 인덱스와 동일함
• commit(커밋) 시 architectural register file(아키텍처 레지스터 파일)을 <1, _, Result>로 업데이트
• 트랩 발생 시 ROB가 flush(플러시)되므로 테이블을 재설정 (모든 p bit (Presence Bit)(P 비트) = 1)

p.21Data-in-ROB design(ROB 내 데이터 설계)에서의 data movement(데이터 이동)

• ROB
• architectural register file(아키텍처 레지스터 파일)
• decode(디코딩) 시 소스 오퍼랜드 읽기
• 이슈 시 소스 오퍼랜드 읽기
• functional unit(기능 유닛)
• commit(커밋) 시 결과 읽기
• dispatch(디스패치) 시 bypass old values(오래된 값 바이패스)
• 결과 데이터
• 완료 시 결과 쓰기
• commit(커밋) 시 결과 쓰기
• 소스 오퍼랜드
• dispatch(디스패치) 시 소스 쓰기

p.22unified physical register file(통합 물리 레지스터 파일)

• 모든 architectural register(아키텍처 레지스터)를 단일 physical register file(물리 레지스터 파일) 내 하나의 레지스터로 이름 변경 (ROB 내 데이터 없음)
• decode(디코딩) 시 레지스터 값 읽기 없음
• functional unit(기능 유닛)은 execute(실행) 중 commit(커밋)된 값과 일시적 값을 포함하는 단일 통합 레지스터 파일에서 읽고 씀
• commit(커밋)은 architectural register(아키텍처 레지스터)와 physical register(물리 레지스터) 간 매핑만 업데이트하며, data movement(데이터 이동) 없음

p.23lifetime of physical registers(물리 레지스터의 수명)

• physical register file(물리 레지스터 파일)은 commit(커밋)된 값과 speculative execution(추측 실행) 값 모두 보유
• physical register(물리 레지스터)는 ROB 항목과 분리됨 (ROB 내 데이터 없음)
• 어떤 시점에 architectural register(아키텍처 레지스터)에 매핑된 physical register(물리 레지스터)를 재사용할 수 있는가?
• → 동일한 architectural register(아키텍처 레지스터)를 쓰는 다음 명령어가 commit(커밋)될 때

p.24physical register(물리 레지스터) 관리

• op
• p1 PR1
• p2 PR2
• ex
• use
• Rd
• PRd
• LPRd
• <x6>
• P5
• <x7>
• P6
• <x3>
• P7
• P0
• Pn
• P1
• P2
• P3
• P4
• x5
• P5
• x6
• P6
• x7
• x0
• P8
• x1
• x2
• P7
• x3
• x4
• ROB
• rename table(이름 변경 테이블)
• physical register(물리 레지스터)
• free list(자유 목록)
• ld x1, 0(x3)
• addi x3, x1, #4
• sub x6, x7, x6
• add x3, x3, x6
• ld x6, 0(x1)
• p
• p
• p
• P0
• P1
• P3
• P2
• P4
• (LPRd는 rename table(이름 변경 테이블)에 대해 각 명령어당 세 번째 읽기 포트 필요)

p.25physical register(물리 레지스터) 관리

• - physical register file(물리 레지스터 파일): 물리 레지스터를 저장하는 저장소
• - reorder buffer(재정렬 버퍼): 명령어의 execute(실행) 순서를 관리하고, commit(커밋) 순서를 보장
• - free list(자유 목록): 사용 가능한 physical register(물리 레지스터)를 관리
• - rename table(이름 변경 테이블): architectural register(아키텍처 레지스터)를 physical register(물리 레지스터)로 매핑
• - p bit(P 비트): physical register(물리 레지스터)가 사용 중인지 여부를 나타냄
• - v bit(V 비트): physical register(물리 레지스터)의 값이 유효한지 여부를 나타냄
• - i bit(I 비트): 명령어가 이미 이슈되었는지 여부를 나타냄
• - ready bit(준비 비트): 데이터가 준비되었는지 여부를 나타냄
• - destination field(목적지 필드): 명령어의 목적지 레지스터를 지정
• - value field(값 필드): 명령어의 결과 값을 저장
• - instruction type field(명령어 유형 필드): 명령어의 유형을 식별
• - common data bus(공통 데이터 버스): functional unit(기능 유닛) 간 데이터 전달을 위한 경로
• - bypass(바이패스): 결과를 바로 다음 명령어에 전달하여 지연을 줄임
• - data movement(데이터 이동): physical register(물리 레지스터) 간의 데이터 전달
• - bypass old values(오래된 값 바이패스): 기존의 값이 유효할 경우 이를 재사용

p.26physical register(물리 레지스터) 관리

• - 명령어: ld x1, 0(x3)
• - register renaming(레지스터 이름 변경): x1 → P0
• - 이름 변경 테이블 업데이트: Rename Table에서 x1 → P0
• - physical register(물리 레지스터) P0 할당: Free List에서 P0 제거
• - p bit set(P 비트 설정): P0의 p bit (Presence Bit)(P 비트)를 1로 설정
• - v bit (Valid Bit)(V 비트) 초기화: P0의 V 비트를 0으로 설정
• - i bit (Issued Bit)(I 비트) 초기화: P0의 I 비트를 0으로 설정
• - ROB에 명령어 등록: ROB에 ld x1, 0(x3) 등록
• - destination field(목적지 필드): P0
• - ready bit(준비 비트): 0 (값 미완료)
• - common data bus(공통 데이터 버스)에 P0 연결

p.27physical register(물리 레지스터) 관리

• - 명령어: addi x3, x1, #4
• - register renaming(레지스터 이름 변경): x3 → P1
• - rename table(이름 변경 테이블) 업데이트: x3 → P1
• - physical register(물리 레지스터) P1 할당: Free List에서 P1 제거
• - p bit set(P 비트 설정): P1의 p bit (Presence Bit)(P 비트)를 1로 설정
• - v bit (Valid Bit)(V 비트) 초기화: P1의 V 비트를 0으로 설정
• - i bit (Issued Bit)(I 비트) 초기화: P1의 I 비트를 0으로 설정
• - ROB에 명령어 등록: ROB에 addi x3, x1, #4 등록
• - destination field(목적지 필드): P1
• - ready bit(준비 비트): 0 (값 미완료)
• - 사용 중인 레지스터: x1 → P0 (P 비트 1, v bit (Valid Bit)(V 비트) 0)
• - common data bus(공통 데이터 버스)에 P1 연결

p.28physical register(물리 레지스터) 관리

• - 명령어: sub x6, x7, x6
• - register renaming(레지스터 이름 변경): x6 → P2
• - rename table(이름 변경 테이블) 업데이트: x6 → P2
• - physical register(물리 레지스터) P2 할당: Free List에서 P2 제거
• - p bit set(P 비트 설정): P2의 p bit (Presence Bit)(P 비트)를 1로 설정
• - v bit (Valid Bit)(V 비트) 초기화: P2의 V 비트를 0으로 설정
• - i bit (Issued Bit)(I 비트) 초기화: P2의 I 비트를 0으로 설정
• - ROB에 명령어 등록: ROB에 sub x6, x7, x6 등록
• - destination field(목적지 필드): P2
• - ready bit(준비 비트): 0 (값 미완료)
• - 사용 중인 레지스터: x7 → P3 (P 비트 1, v bit (Valid Bit)(V 비트) 0), x6 → P3 (P 비트 1, V 비트 0)
• - common data bus(공통 데이터 버스)에 P2 연결

p.29physical register(물리 레지스터) 관리

• - 명령어: add x3, x3, x6
• - register renaming(레지스터 이름 변경): x3 → P3
• - rename table(이름 변경 테이블) 업데이트: x3 → P3
• - physical register(물리 레지스터) P3 할당: Free List에서 P3 제거
• - p bit set(P 비트 설정): P3의 p bit (Presence Bit)(P 비트)를 1로 설정
• - v bit (Valid Bit)(V 비트) 초기화: P3의 V 비트를 0으로 설정
• - i bit (Issued Bit)(I 비트) 초기화: P3의 I 비트를 0으로 설정
• - ROB에 명령어 등록: ROB에 add x3, x3, x6 등록
• - destination field(목적지 필드): P3
• - ready bit(준비 비트): 0 (값 미완료)
• - 사용 중인 레지스터: x3 → P1 (P 비트 1, v bit (Valid Bit)(V 비트) 0), x6 → P2 (P 비트 1, V 비트 0)
• - common data bus(공통 데이터 버스)에 P3 연결

p.30physical register(물리 레지스터) 관리

• - 명령어: ld x6, 0(x1)
• - register renaming(레지스터 이름 변경): x6 → P4
• - rename table(이름 변경 테이블) 업데이트: x6 → P4
• - physical register(물리 레지스터) P4 할당: Free List에서 P4 제거
• - p bit set(P 비트 설정): P4의 p bit (Presence Bit)(P 비트)를 1로 설정
• - v bit (Valid Bit)(V 비트) 초기화: P4의 V 비트를 0으로 설정
• - i bit (Issued Bit)(I 비트) 초기화: P4의 I 비트를 0으로 설정
• - ROB에 명령어 등록: ROB에 ld x6, 0(x1) 등록
• - destination field(목적지 필드): P4
• - ready bit(준비 비트): 0 (값 미완료)
• - 사용 중인 레지스터: x1 → P0 (P 비트 1, v bit (Valid Bit)(V 비트) 0)
• - common data bus(공통 데이터 버스)에 P4 연결
• - execute(실행) 및 commit(커밋) 단계: 모든 명령어가 실행 완료됨
• - commit(커밋): ROB에서 oldest instruction(가장 오래된 명령어)부터 순서대로 커밋
• - committed register mapping(커밋된 레지스터 매핑): architectural register file(아키텍처 레지스터 파일)에 physical register(물리 레지스터) 값 반영
• - physical register(물리 레지스터) reclaim(회수): commit(커밋)된 물리 레지스터는 Free List에 반환

p.31physical register(물리 레지스터) 관리

• op
• p1 PR1
• p2 PR2
• ex
• use
• Rd
• PRd
• LPRd
• ROB
• x
• sub p
• P6 p
• P5 x6 P3
• x
• addi
• P0 x3 P1
• x
• addi
• P0 x3 P1
• ld x1, 0(x3)
• addi x3, x1, #4
• sub x6, x7, x6
• add x3, x3, x6
• ld x6, 0(x1)
• Free List
• P0
• P1
• P3
• P2
• P4
• <x6>
• P5
• <x7>
• P6
• <x3>
• P7
• P0
• Pn
• P1
• P2
• P3
• P4
• Physical Regs
• p
• p
• p
• P8
• x5
• P5
• x6
• P6
• x7
• x0
• P8
• x1
• x2
• P7
• x3
• x4
• Rename Table
• P0
• P7
• P1
• P5
• P3
• P1
• P2
• x
• add P1 P3 x3 P2
• x
• ld P0 x6 P4
• P3
• P4
• Execute & Commit
• p
• p
• p
• <x1>
• P8
• x
• p
• p
• <x3>
• P7

p.32예외 발생 시 이름 변경 복구

• MIPS R10K의 rename table(이름 변경 테이블)은 ROB의 PRd/LPRd 필드를 사용하여 역순으로 명령어의 이름 변경을 복구한다.
• Alpha 21264는 유사한 physical register file(물리 레지스터 파일) 구조를 사용했지만, ROB 내 각 명령어에 대해 완전한 rename table(이름 변경 테이블) 스냅샷(총 80개)을 유지했다.
• 한 사이클 내에 스냅샷의 모든 비트를 활성 테이블로 flash copy(플래시 복사)한다.

p.33reorder buffer(재정렬 버퍼)는 활성 명령어를 보유한다

• (디코딩되었지만 commit(커밋)되지 않은 명령어)
• (오래된 명령어)
• (최근 명령어)
• cycle(사이클) t
• ...
• ld x1, (x3)
• add x3, x1, x2
• sub x6, x7, x9
• add x3, x3, x6
• ld x6, (x1)
• add x6, x6, x3
• sd x6, (x1)
• ld x6, (x1)
• ...
• Commit
• Fetch
• cycle(사이클) t + 1
• Execute
• ...
• ld x1, (x3)
• add x3, x1, x2
• sub x6, x7, x9
• add x3, x3, x6
• ld x6, (x1)
• add x6, x6, x3
• sd x6, (x1)
• ld x6, (x1)
• ...
• ROB 내용

p.34ROB와 이슈 창을 분리한다

• reorder buffer(재정렬 버퍼)는 commit(커밋)을 위한 예외 정보를 보유한다.
• 이슈 창은 decode(디코딩)되고 이름 변경되었지만 execute(실행)에 이슈되지 않은 명령어만 보유한다. 레지스터 태그와 존재 비트, ROB 항목에 대한 포인터를 포함한다.
• op
• p1 PR1
• p2 PR2
• PRd
• use ex
• ROB#
• ROB는 일반적으로 이슈 창보다 몇 배 더 크다. 왜일까?
• Rd
• LPRd
• PC
• Except?
• Oldest
• Free
• Done?

p.35superscalar register renaming(슈퍼스칼라 레지스터 이름 변경)

• decode(디코딩) 중에 명령어가 새로운 물리 목적지 레지스터를 할당받는다.
• 소스 연산자는 최신 값을 가진 physical register(물리 레지스터)로 이름 변경된다.
• execute(실행) 유닛은 오직 physical register(물리 레지스터) 번호만을 본다.
• Rename Table
• Op
• Src1 Src2
• Dest
• Op
• Src1 Src2
• Dest
• Register Free List
• Op
• PSrc1 PSrc2
• PDest
• Op
• PSrc1 PSrc2
• PDest
• Update Mapping
• 이 방법은 작동할까?
• Inst 1
• Inst 2
• Read Addresses
• Read Data
• Write Ports

p.36superscalar register renaming(슈퍼스칼라 레지스터 이름 변경)

• Rename Table
• Op
• Src1 Src2
• Dest
• Op
• Src1 Src2
• Dest
• Register Free List
• Op
• PSrc1 PSrc2
• PDest
• Op
• PSrc1 PSrc2
• PDest
• Update Mapping
• Inst 1
• Inst 2
• Read Addresses
• Read Data
• Write Ports
• =?
• =?
• 동일 사이클에 이슈되는 명령어 간의 RAW hazard(RAW 해저드)을 확인해야 한다. 이름 변경 검색과 병렬로 수행할 수 있다.
• MIPS R10K는 1사이클에 4개의 순차적 RAW 종속성 명령어를 이름 변경한다.

p.37