[Computer Architecture] Assignment 5 - Cache

"Cache"

[Objective]

Direct-Mapped Data Cache에 Victim Cache Buffer 추가를 통해 Conflict Miss를 줄여 Cache Memory의 효율을 높이기
CPU → Data Cache → Victim Cache → Memory

[Implementation]

▣ Remove
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
block_t victim_cache_t::remove(uint64_t m_addr) {
    block_t block;
    num_accesses++;
    uint64_t tag = m_addr >> 5;
    for (uint64_t i = 0; i < num_entries; i++) {
        if (blocks[i].valid && (blocks[i].tag == tag)) {
            num_hits++;
            block = blocks[i];
            for (uint64_t j = i; j < num_entries - 1; j++) {
                blocks[j] = blocks[j + 1];
            }
            blocks[num_entries - 1].valid = 0;
            num_entries--;
            return block;
        }
    }
    block.valid = 0;
    return block;
}
cs

· 주소 "m_addr"에 해당하는 Block이 Victim Cache에 존재 → Victim Cache에서 제거해서 반환(없는 경우 Invalid Block 반환)

2 : 나중에 Victim Cache에서 못 찾았을 때 Invalid Block을 반환할 용도
3 : Victim Cache가 검색 된 횟수 증가(Data Cache Hit : Victim Cache 검색 X / Data Cache Miss : Victim Cache 검색 O)
4 : Victim Cache에서 찾기 위해 Block Offset을 나타내는 Bit를 제거하여 Victim Cache용 Tag 형식으로 전환
    → Direct-Mapped Data Cache = [Tag][Set Index][Block Offset]
    → Victim Cache = Fully Associative Cache = [Tag' = {Tag, Set Index}]
5 : 일치하는 Block을 찾기 위해 전체 Entry에서 검사
6 : Entry가 유효 & Tag가 일치하는 Block 존재
7 : Victim Cache Hit 횟수 증가
8 : Hit Block을 "block"에 저장
9 : Victim Cache의 FIFO 순서를 유지하기 위해 Hit Block Index부터 반복
10 : Hit Block Index부터 뒤의 값을 앞으로 당겨서 Hit Block 제거 후 FIFO 유지
12 : 앞으로 당긴 후 마지막 Entry는 기존 값이 중복으로 남아 있을 수 있으므로 Invalid Block으로 처리
13 : Valid Block 개수 감소
14 : Hit Block 반환
17 : Victim Cache Miss → Invalid Block
18 : Invalid Block 반환

** block_offset : "data_cache_t" Class의 Member 변수 → remove( ) : "victim_cache_t" Class 함수
∴ block_offset을 직접 사용 불가(32B이므로 5로 대체)

▣ Insert
1
2
3
4
5
6
7
8
9
10
11
void victim_cache_t::insert(block_t m_block) {
    if(num_entries == size) {
        if(blocks[0].dirty) { num_writebacks++; }
        for (uint64_t i = 0; i < size - 1; i++) {
            blocks[i] = blocks[i + 1];
        }
        blocks[size - 1] = m_block;
    } else {
        blocks[num_entries++] = m_block;
    }
}
cs

· Data Cache에서 쫓겨난 Block을 Victim Cache에 저장
    → Victim Cache가 꽉 찬 경우 : 오래된 Block 제거 후 추가 / Victim Cache가 꽉 안 찬 경우 : Block 추가

2 : Victim Cache가 꽉 찬 경우
3 : 가장 오래된 Block이 수정된 적이 있는 경우 Memory에 변경 사항을 반영해야 하므로 Writeback 발생 횟수 증가
4~6 : 가장 오래된 Block에 해당하는 0번 Index부터 뒤의 값을 한 칸씩 앞당김
7 : 마지막 Index에 Data Cache에서 쫓겨난 Block을 추가
8 : Victim Cache가 꽉 안 찬 경우
9 : 현재 Victim Cache에 들어있는 데이터 개수 + 1에 해당하는 Index에 Data Cache에서 쫓겨난 Block 추가

** Victim Cache가 꽉 찬 경우 : 이미 Size개가 들어 있었고, 하나 빼고 하나 넣으면 여전히 Size 만족(∴ num_entries 증가 X)

▣ Read
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
void data_cache_t::read(inst_t *m_inst) {
    uint64_t addr = m_inst->memory_addr;
    if(addr & 0b111) {
        cerr << "Error: invalid alignment of memory address " << addr << endl;
        exit(1);
    }
 
    uint64_t set_index = (addr & set_mask) >> block_offset;
    uint64_t tag = addr >> set_offset;
 
    block_t *block = &blocks[set_index][0];
    if(!block->valid || (block->tag != tag)) { block = 0; }
 
    if(block) {
        block->last_access = *ticks;
        m_inst->rd_val = *(block->data + ((addr & block_mask) >> 3));
#ifdef DATA_FWD
        m_inst->rd_ready = true;
#endif
        num_accesses++;
        num_loads++;
    }
    else {
        block_t victim_block = victim_cache->remove(addr);
 
        if (victim_block.valid) {
            block_t old_block = blocks[set_index][0];
            if (old_block.valid) {
                old_block.tag = (old_block.tag << (set_offset - block_offset)) | set_index;
                victim_cache->insert(old_block);
            }
            victim_block.tag = tag;
            blocks[set_index][0] = victim_block;
            read(m_inst);
        } else {
            missed_inst = m_inst;
            memory->load_block(addr & ~block_mask, block_size);
            num_misses++;
        }
#ifdef DEBUG
        cout << *ticks << " : cache miss : addr = " << addr
             << " (tag = " << tag << ", set = " << set_index << ")" << endl;
#endif
    }
}
cs

· Load 명령어를 Data Cache에서 처리(Data Cache Miss인 경우 Victim Cache 먼저 확인)

2 : Load 명령어가 요구하는 Target Memory 주소를 Load
3 : 주소가 8-Byte 단위로 맞아 떨어지는지 검사
8 : Block Offset 제거 후, Set Mask를 이용해 Tag와 분리된 Set Index 계산
9 : Block Offset과 Set Offset을 제거하여 Data Cache용 Tag 계산
11 : Data Cache는 Direct-Mapped 방식이므로 확인할 위치는 하나
12 : Block이 Invalid 또는 Tag가 불일치 → Data Cache Miss → "block = 0"
14 : Data Cache Hit
15 : 마지막으로 접근한 시간을 현재 시간으로 갱신
16 : Block 내부에서 정확한 위치로 찾아가 8-Byte 단위로 데이터를 읽어 Register에 저장
20~21 : 통계용 Counter 증가
23 : Data Cache Miss
24 : Victim Cache에서 확인
26 : Victim Cache Hit
27 : Victim Cache Hit Block이 Data Cache로 이동 → Data Cache이 Victim Cache Block으로 쫓겨나므로 "old_block"에 복사
28 : Valid한 Data Cache Block
29 : Victim Cache에서 저장하기 위해 Block Offset을 제외한 Tag와 Set Index를 결합하여 Tag 형식 변환
    → Direct-Mapped Data Cache = [Tag][Set Index][Block Offset]
    → Victim Cache = Fully Associative Cache = [Tag' = {Tag, Set Index}]
30 : Data Cache Block을 Victim Cache FIFO 끝에 추가
32 : Victim Cache Hit Block을 Data Cache로 이동하려면 [Tag]만 저장
33 : Data Cache에 추가
34 : read 함수를 다시 실행하여 Data Cache Hit로 빠지도록 함
35 : Victim Cache Miss
36~38 : Block 시작 주소를 만들어 Main Memory에 block_size만큼 요청 후 Miss Counter 증가

▣ Write
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
void data_cache_t::write(inst_t *m_inst) {
    uint64_t addr = m_inst->memory_addr;
    if(addr & 0b111) {
        cerr << "Error: invalid alignment of memory address " << addr << endl;
        exit(1);
    }
 
    uint64_t set_index = (addr & set_mask) >> block_offset;
    uint64_t tag = addr >> set_offset;
 
    block_t *block = &blocks[set_index][0];
    if(!block->valid || (block->tag != tag)) { block = 0; }
 
    if(block) {
        block->last_access = *ticks;
        block->dirty = true;
        *(block->data + ((addr & block_mask) >> 3)) = m_inst->rs2_val;
        num_accesses++;
        num_stores++;
    }
    else {
        block_t victim_block = victim_cache->remove(addr);
 
        if (victim_block.valid) {
            block_t old_block = blocks[set_index][0];
            if (old_block.valid) {
                old_block.tag = (old_block.tag << (set_offset - block_offset)) | set_index;
                victim_cache->insert(old_block);
            }
            victim_block.tag = tag;
            blocks[set_index][0] = victim_block;  
            write(m_inst); 
        } else {
            missed_inst = m_inst;
            memory->load_block(addr & ~block_mask, block_size);
            num_misses++;
        }
#ifdef DEBUG
        cout << *ticks << " : cache miss : addr = " << addr
             << " (tag = " << tag << ", set = " << set_index << ")" << endl;
#endif
    }
}
cs

· Store 명령어가 Data Cache에 값을 Write(Data Cache Miss인 경우 Victim Cache 먼저 확인)

2 : Store 명령어가 요구하는 Target Memory 주소를 Load
3 : 주소가 8-Byte 단위로 맞아 떨어지는지 검사
8 : Block Offset 제거 후, Set Mask를 이용해 Tag와 분리된 Set Index 계산
9 : Block Offset과 Set Offset을 제거하여 Data Cache용 Tag 계산
11 : Data Cache는 Direct-Mapped 방식이므로 확인할 위치는 하나
12 : Block이 Invalid 또는 Tag가 불일치 → Data Cache Miss → "block = 0"
14 : Data Cache Hit
15 : 마지막으로 접근한 시간을 현재 시간으로 갱신
16 : CPU가 Cache에 있는 데이터를 수정했으므로 Dirty Bit On
17 : "m_inst"에 담겨 있는, CPU가 저장하라고 보낸 새로운 데이터 값을 Cache Block의 정확한 위치에 저장
18~19 : 통계용 Counter 증가
21 : Data Cache Miss
22 : Victim Cache에서 확인
24 : Victim Cache Hit
25 : Victim Cache Hit Block이 Data Cache로 이동 → Data Cache가 Victim Cache Block으로 쫓겨나므로 "old_block"에 복사
26 : Valid한 Data Cache Block
27 : Victim Cache에서 저장하기 위해 Block Offset을 제외한 Tag와 Set Index를 결합하여 Tag 형식 변환
    → Direct-Mapped Data Cache = [Tag][Set Index][Block Offset]
    → Victim Cache = Fully Associative Cache = [Tag' = {Tag, Set Index}]
28 : Data Cache Block을 Victim Cache FIFO 끝에 추가
30 : Victim Cache Hit Block을 Data Cache로 이동하려면 [Tag]만 저장
31 : Data Cache에 추가
32 : write 함수를 다시 실행하여 Data Cache Hit로 빠지도록 함
33 : Victim Cache Miss
34~36 : Block 시작 주소를 만들어 Main Memory에 block_size만큼 요청 후 Miss Counter 증가

▣ Handle Response
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void data_cache_t::handle_response(int64_t *m_data) {
    uint64_t addr = missed_inst->memory_addr;
    uint64_t set_index = (addr & set_mask) >> block_offset;
    uint64_t tag = addr >> set_offset;
 
    block_t *victim = &blocks[set_index][0];
    if(victim->valid) {
#ifdef DEBUG
        cout << *ticks << " : cache eviction : addr = " << addr
             << " (tag = " << tag << ", set = " << set_index << ")" << endl;
#endif
        block_t victim_block = *victim;
        victim_block.tag = (victim->tag << (set_offset - block_offset)) | set_index;
        victim_cache->insert(victim_block);
    }
    *victim = block_t(tag, m_data, /* valid */ true);
 
    if(missed_inst->op == op_ld) { read(missed_inst); }
    else { write(missed_inst); }
    missed_inst = 0;
}
cs

· Main Memory에서 Miss가 발생한 Block이 도착했을 때 처리하는 함수

2 : Miss가 발생했던 Load/Store 명령어 Load
3 : Set Index 계산
4 : Tag 계산
6 : Direct-Mapped Cache라서 들어갈 위치는 하나
7 : 해당 Cache Line에 이미 유효한 Block 존재(해당 Block을 Victim Cache로 이동)
12 : Data Cache에 있던 Block을 복사
13 : Victim Cache에 넣기 위해 Tag 변환
14 : Victim Cache FIFO 끝에 추가
16 : Memory에서 온 Block을 Data Cache에 배치
18~19 : Cache Access 다시 실행(ld : read / sd : write)
20 : Miss 초기화

[Result]

 

[Reference]

· cache (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...
자세한 내용 보기