[Computer Architecture] Assignment 4 - Branch

"Branch Prediction"

[Objective]

Kite Processor Pipeline에서 2-Level Local Branch Predictor와 BTB(Branch Target Buffer)를 구현하여 Branch Prediction Accuracy를 99.9%까지 향상시키기

[Background]

▣ Local 2-Level Branch Predictor
> BHT(Branch History Table)
· 각 Entry는 해당 Branch의 최근 h번 결과를 Bit로 저장
· LSB : 가장 최근 Branch Outcome / MSB : 가장 오래된 Branch Outcome

> PHT(Pattern History Table)
· Branch History Pattern마다 2-bit Saturating Counter를 저장(2p x 2h = 23 x 23 = 64개의 Counter 존재)

▣ Prediction Flow
① PC
② (PC >> 2)의 하위 b-bit : BHT Index / 하위 p-bit : PHT Row Index / BHT[Index]의 h-bit History : PHT의 Column Index
③ PHT[Row][Column]의 2-bit Counter 확인 (0, 1 : Not Taken / 2, 3 : Taken)

▣ Update
· Branch가 Write-Back Stage에 도달하면 실제 결과를 알 수 있음

> Saturating Counter
· 실제 Taken : PHT Counter + 1 (Until 최대 3)
· 실제 Not Taken : PHT Counter - 1 (Until 최소 0)

> BHT
· 기존 History를 왼쪽을 1-bit Shift 후, 실제 결과를 LSB에 삽입하여 h-bit만 유지

** 분기 명령이 Fetch Stage에서 BHT를 읽고, PHT Counter를 선택한 후, 해당 명령이 Write-Back Stage에 도달하기 전까지 앞선 Branch들이 같은 BHT Entry를 바꿀 수 있음
→ Write-Back에서 BHT를 다시 읽으면 Fetch 때 사용했던 PHT Counter와 다른 Counter를 Update
∴ "inst_t" Class에 새 변수를 추가해서 Fetch 당시 사용한 정보를 저장

▣ BTB(Branch Target Buffer)
· Branch Predictor는 "Taken인지, Not Taken인지"만 예측하고, Taken이라고 예측했을 때 "어디로 갈지"는 BTB가 담당
→ 이번 과제의 BTB는 Direct-Mapped Cache처럼 동작하고, Entry 수는 16개

· BTB Entry에는 Taken Branch의 Target Address가 저장
· Fetch Stage에서 Branch가 Taken으로 예측되면 BTB에서 Target을 Read
· Write-Back Stage에서 실제 Brach가 Taken이면 BTB를 Update

[Implementation]

▣ inst.h
uint64_t pht_index;
· "pht_index"를 "inst_t" Class에 추가
→ Branch Prediction에 사용된 PHT Index를 저장하고, Write-Back 단계에서 동일한 PHT Counter를 갱신하기 위함
 
▣ br_predictor.cc
> Branch Predictor
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// Branch predictor
br_predictor_t::br_predictor_t(unsigned m_bht_bits, unsigned m_pht_bits, unsigned m_hist_len) :
    bht(0),
    pht(0),
    b(m_bht_bits),
    p(m_pht_bits),
    h(m_hist_len) {
    // Create branch history table (BHT) and pattern history table (PHT).
    bht = new uint8_t[1 << b];
    pht = new uint8_t[(1 << p) * (1 << h)];
 
    // Initialize BHT = 0
    for (uint64_t i = 0; i < (1 << b); i++) {
        bht[i] = 0;
    }
 
    // Initialize PHT Counter = 1(01 : Weakly Not Taken)
    for (uint64_t i = 0; i < ((1 << p) * (1 << h)); i++) {
        pht[i] = 1;
    }
}
cs

· "br_predictor_t" 객체가 생성될 때 실행되는 생성자
· bht(0) : BHT Pointer를 Null로 초기화 → bht = 0
· pht(0) : PHT Pointer를 Null로 초기화 → pht = 0
· b(m_bht_bits) : 변수 b를 BHT Index Bit 값으로 초기화 → b(m_bht_bits) = b(3) → b = 3
· p(m_pht_bits) : 변수 p를 PHT Index Bit 값으로 초기화 → p(m_pht_bits) = p(3) → p = 3
· h(m_hist_len) : 변수 h를 Branch History 길이로 초기화 → h(m_hist_len) = h(3) → h = 3
· bht : BHT 배열을 동적으로 생성 → BHT Entry 8개 생성
· pht : PHT 배열을 동적으로 생성 → 64개의 2-bit Counter 생성
· BHT의 모든 Entry를 0으로 초기화
· PHT의 모든 Counter를 1(01 : Weakly Not Taken)로 초기화

> is_taken( ) 함수
1
2
3
4
5
6
7
8
9
10
11
12
13
// Is a branch predicted to be taken?
bool br_predictor_t::is_taken(inst_t *m_inst) {
    // Predict always not taken. H
    uint64_t pc_index = m_inst->pc >> 2;                // Removed Lower 2-bit(4-Byte -> 2-Byte = 00 -> Elision)
    uint64_t bht_index = pc_index & ((1 << b) - 1);     // Select BHT Entry Using Lower b-bit
    uint64_t pht_row = pc_index & ((1 << p) - 1);       // Select PHT Row Using Lower p-bit
    uint64_t history = bht[bht_index] & ((1 << h) - 1); // Read h-bit Local Branch History
    uint64_t pht_index = pht_row * (1 << h) + history;  // Convert 2D Array To 1D Array
 
    m_inst->pht_index = pht_index;                      // Save PHT Index Used At Prediction Time
 
    return pht[pht_index] >= 2;                         // Counter Value = 2 or 3 -> Predict "Taken"
}
cs

· Fetch Stage에서 호출되며, 현재 Branch Instruction이 Taken될지, Not Taken될지 예측
· pc_index : Instruction의 PC를 가져와서 오른쪽으로 2-bit Shift(4-Byte 단위로 정렬 → PC의 하위 2-bit는 항상 00 → 생략)
· bht_index : BHT Index 계산(PC Index의 하위 3-bit를 사용하기 위해 Masking)
· pht_row : PHT에서 PC에 해당하는 Row Index 계산(PC Index의 하위 3-bit를 사용하기 위해 Masking)
· history : Branch Instruction의 Local History를 BHT에서 가져옴(최근 Branch 결과들이 Bit 형태로 저장되어 있는 bht의 하위 3-bit를 사용)
· pht_index : 2차원 PHT Index를 1차원 배열 Index로 변경
· Fetch Stage에서 사용한 PHT Index를 Instruction 안에 저장
    → 나중에 Write-Back Stage에서 Predictor를 Update할 때, 같은 PHT Counter를 수정해야 하기 때문에 중요
· PHT Counter 값 = 0, 1 : False → Not Taken / PHT Counter 값 = 2, 3 : True → Taken

> update( ) 함수
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// Update a prediction counter.
void br_predictor_t::update(inst_t *m_inst) {
    uint64_t pc_index = m_inst->pc >> 2;                // Removed Lower 2-bit(4-Byte -> 2-Byte = 00 -> Elision)
    uint64_t bht_index = pc_index & ((1 << b) - 1);     // Select BHT Entry Using Lower b-bit
    uint64_t pht_index = m_inst->pht_index;             // Use PHT Index Saved At Prediction Time
 
    // Update 2-bit Saturating Counter
    if (m_inst->branch_taken) {
        if (pht[pht_index] < 3) {
            pht[pht_index]++;
        }
    } else {
        if (pht[pht_index] > 0) {
            pht[pht_index]--;
        }
    }
 
    // Shift In Actual Branch Outcome To Update Local Branch History
    bht[bht_index] = ((bht[bht_index] << 1) | m_inst->branch_taken) & ((1 << h) - 1);
}
cs

· Write-Back Stage에서 호출되며, 실제 Branch 결과를 바탕으로 BHT와 PHT를 갱신
· pc_index : Instruction의 PC를 가져와서 오른쪽으로 2-bit Shift(4-Byte 단위로 정렬 → PC의 하위 2-bit는 항상 00 → 생략)
· bht_index : 갱신해야 할 BHT Index 계산(PC Index의 하위 3-bit를 사용하기 위해 Masking)
· pht_index : Fetch Stage에서 저장해 둔 PHT Index Load
    ** 그 사이에 BHT 값이 바뀌었을 수 있기 때문에 PHT Index를 다시 계산하지 않음
· Branch 결과 = Taken : Counter가 최댓값 3보다 작으면 Counter 증가 / Counter가 최댓값 3이면 Counter 유지
· Branch 결과 = Not Taken : Counter가 최솟값 0보다 크면 Counter 감소 / Counter가 최솟값 0이면 Counter 유지
· 최근 3번의 결과가 저장되어 있는 "bht"를 왼쪽으로 1칸 밀어 오래된 기록을 없애고 LSB에 Branch 결과 Load 후, 하위 3-bit를 사용

> BTB Constructor
1
2
3
4
5
6
7
8
9
10
11
12
// Branch target buffer
br_target_buffer_t::br_target_buffer_t(uint64_t m_size) :
    num_entries(m_size),
    buffer(0) {
    // Create a direct-mapped branch target buffer (BTB).
    buffer = new uint64_t[num_entries];
 
    // Initialize BTB Entry = 0
    for (uint64_t i = 0; i < num_entries; i++) {
        buffer[i] = 0;
    }
}
cs

· BTB 객체가 생성될 때 호출되는 생성자 ("m_size"는 BTB Entry 개수)
· num_entries(m_size) : 변수를 BTB Entry 개수로 초기화 → num_entries(m_size) = num_entries(16) → num_entries = 16
· buffer(0) : BTB 배열 Pointer를 Null로 초기화
· buffer : BTB Target Address를 저장할 배열 생성(각 Entry에는 Branch Target Address가 저장)
· BTB의 모든 Entry를 0으로 초기화

> get_target( ) 함수
1
2
3
4
5
// Get a branch target address.
uint64_t br_target_buffer_t::get_target(uint64_t m_pc) {
    // Return Target Address From Indexed BTB Entry(4-Byte -> 2-Byte = 00 -> Elision)
    return buffer[(m_pc >> 2) & (num_entries - 1)];
}
cs

· Branch가 Taken으로 예측되었을 때 호출되며, 예측 Branch Target Address를 반환
· 하위 2-bit를 사용하지 않으므로 PC의 하위 2-bit를 제거 & BTB가 16개의 Entry를 가지므로 하위 4-bit를 이용하여 BTB Index 계산

> update( ) 함수
1
2
3
4
5
// Update the branch target buffer.
void br_target_buffer_t::update(uint64_t m_pc, uint64_t m_target_addr) {
    // Store Actual Target Address In BTB(4-Byte -> 2-Byte = 00 -> Elision)
    buffer[(m_pc >> 2) & (num_entries - 1)] = m_target_addr;
}
cs

· BTB를 갱신하는 함수로, 실제 Taken Branch의 PC와 실제 Target Address를 받음
· 하위 2-bit를 사용하지 않으므로 PC의 하위 2-bit를 제거 & BTB가 16개의 Entry를 가지므로 하위 4-bit를 이용하여 BTB Index 계산
· 해당 BTB Entry에 Branch Target Address를 저장 (다음에 같은 Branch가 Taken으로 예측되면 이 주소를 Target으로 사용)

** "get_target( )"에서 사용한 방식과 반드시 같아야 나중에 같은 Branch PC로 접근했을 때 같은 Entry Read 가능

[Result]

▼

[Reference]

· branch (Computer Architecture) - William J. Song

댓글

댓글 쓰기

이 블로그의 인기 게시물

[Mini-NPU RTL] NN Reference Model

이미지
"NN Reference Model" 1. Neuron 단 1개의 Neuron만 존재하며 해당 Neuron이 가중합을 잘 구하고 활성화 함수를 제대로 통과시키는지 확인 → 28x28=784개의 입력 데이터와 784개의 가중치를 각각 곱한 후 ∑, 이후 활성화 함수를 통과시킨 뒤, 1개의 값 출력 → "test_data.txt"에서 데이터를 읽어 Neuron에 직접 넣음 → 가중치와 편향이 "w_1_0.mif", "b_1_0.mif"로부터 정적으로 고정되어 Load neuron_tb.sv) include.v) 공통 상수를 미리 정해두는 파일로, 숫자를 고치면 Network 깊이, Neuron 개수 등을 조절 ReLU.v) 공통 활성화 함수인 ReLU를 하드웨어로 구현한 코드 Sig_ROM.v) 공통 Sigmoid 함수 연산을 실시간으로 계산하지 않고  미리 계산된 결과값 을 메모리에서 꺼내 쓰는  LookUp Table  방식의 구현 Weight_Memory.v) 공통 가중치를 저장하는 메모리 장치로 가중치를 읽고 쓴다. Neuron.v) 공통 입력 데이터를 받아 가중치와 곱하고, 누적 한 후, 편향을 더하고, 활성화 함수를 거쳐 출력하는 연산 Unit 2. Network 수많은 Neuron이 합쳐진 전체 시스템의 데이터 흐름과 제어 Logic이 제대로 작동하는지 확인 → 28x28=784개의 입력 데이터가 30개의 Neuron에게 동시에 전달되면 784x30개의 가중치를 곱해 30개의 결과 출력     (첫 번째 입력이 1 Cycle에 서로 다른 30개의 가중치와 병렬 연산으로 곱해진다. ∴ 784 Cycle) → 30개의 입력이 다음 Layer의 20개 Neuron에 전달되어 30x20개의 가중치를 곱해 20개의 결과 출력 → 20개의 입력이 다음 Layer의 10개 Neuron에 전달되어 20x10개의 가중치를 곱해 10개의 결과 출력 → 10개의 출력은 입력 이미지 0~9의 점수를 나...
자세한 내용 보기

[Mini-NPU RTL] TPU (Study Paper)

이미지
"In-Datacenter Performance Analysis of a Tensor Processing Unit" 1. Introduction to Neural Networks   NN은 입력 값들의 가중 합에 비선형 함수(ex. max(0, value))를 적용하는 단순한 인공 뉴런에 기초한다.   ※ 가중합 : 입력 데이터에 중요도인 가중치 를 곱해서 더한다.   ※ 비선형 함수 : 계산된 합을 그대로 쓰지 않고 변형하는 함수(활성화 함수)   ※ max(0, value) : ReLU(Rectified Linear Unit) 함수이며, 음수면 0, 양수면 해당 값을 그대로 내보낸다.   NN은 계층(Layer) 으로 모이며, 한 계층의 출력은 다음 계층의 입력이 된다.   DNN(Deep Neural Networks) 은 NN에서 계층의 수가 많은 것 을 의미한다.   NN은 개발 단계인 Training(학습) 단계와 실전 단계인 Inference(추론) 단계가 있다.   개발자는 계층의 수 와 NN의 유형 을 선택하고, 학습 과정을 통해 가중치 를 결정한다.   학습이 끝난 후, 추론 단계에서는 소수점 아래 긴 자리까지 필요 없는 경우가 많다.   ∴ Quantization(양자화) 단계에서 단순한 정수( 8-bit )로 바꿔 용량↓ & 속도↑         → 8-bit 정수 곱셈 : 16-bit 부동소수점 곱셈보다 에너지 소모 6배↓ & 칩 면적 6배↓         → 8-bit 정수 덧셈 : 16-bit 부동소수점 덧셈보다 에너지 소모 13배↓ & 칩 면적 38배↓   NN의 유형은 3가지로 볼 수 있다.   ·  MLP(Multi-Layer Perceptrons) : 각 계층은 이전 계층의 모든 출력 값(Fully Conn...
자세한 내용 보기