# Lab 6 Report
- Team number: 21
- Team member:
- 윤병준(20190766)
- 백재훈(20190277)
- Date: 2021.05.25

# Introduction
이번 랩에서는 우리는 2-way set associative cache를 설계하고, pipeline cpu에 캐시를 추가하여 그 전과 후의 성능을 비교하려 한다. 이를 통해 어떻게 캐시가 CPU와 메모리 사이의 차이를 좁히고 어떻게 성능 향상을 꾀하는지 알아 볼 수 있다.
## 학습목표
- Understand how cache works
- Evaluate the speed-sup achieved by using cache
## 구현목표
- Implement a set-associative cache on your pipelined CPU

# Design
2-way set-associative 캐시를 구현하는데 있어 다음과 같은 디자인적인 선택을 내렸다.
## Unified vs Separate Cache
Unified는 하나의 캐시가 8개의 라인을 가지고 인스트럭션과 데이터들 모두 들고 각 스테이지마다 올바르게 CPU에 있는 Instruction Memory와 Data Memory에 값을 전달해준다. Separate I/D 캐시는 두개의 분리된 캐시가 각각 CPU의 IM, DM의 값을 전달해준다. ICache, DCache가 시그널을 주고 받아야할 상황을 고려하여 각 캐시를 분리하되 하나의 모듈안에 쌓여져있게 하였다. 또한, 캐시의 포트를 두개씩 만들어서 하나의 모듈이 두 곳으로 값을 전달 할 수 있도록 하였다.

## Replacement policy
Random, LRU, FIFO 등의 캐시의 내용물을 교체하는 다양한 방법이 있다. 하지만, 이번에 구현하는 캐시는 웨이가 2개짜리 캐시라 LRU를 표시하는데 필요한 비트가 1개 뿐이고 구현이 매우 간단하다. 따라서 다른 구현보다 적절하다 생각되는 LRU를 선택하였다.

## Write policy
쓰기에 관해서는, Write Through 구현을 택했다. 쓰기가 발생했을때, 정보가 캐시에 있는 블럭과 lower-level memory의 블럭에 동시에 쓰여지게 된다. Write back과 비교했을때, write 가 느리다는 단점이 있긴 하지만, 메인메모리가 가장 최근의 카피를 가지고 있는 consistancy 때문에 Write Through을 채택했다.

Write miss 가 발생했을때는 두가지 방법이 있는데, Write Allocate와 Write no-Allocate 이다. Write allocate는 데이터를 갱신하였으니, 주 메모리의 데이터를 갱신 하고 캐쉬에도 이 데이터를 올려놓는 것이고, no-allocate는 메모리만 갱신하는 정책이다. 이번 랩에서는 write through 와 no-allocate 정책을 사용하여 구현하였다. 따라서 캐시의 작동은 다음과 같을 것이다. 만약 힛 한다면, 캐시와 메모리 두 곳 모두에 값을 쓴다. 캐시에서 미스가 나면 메인 메모리의 블럭을 allocate하고 캐시로 가져오지는 않는다.

## Modularization

## Submodule
이번 과제에서는 파이프라인 cpu 코드들을 거의 전부 활용하고, cpu가 메모리 접근을 하는 곳에 대하여 캐시를 끼워넣는 형태로 구현하였다. 이를 위해서 ack/rdy 등의 시그널을 추가하고, 간결성을 위해 명령어 메모리 접근은 읽기 전용으로 유지했다. 기존의 모듈들도 일부 수정하고, 두 개의 모듈을 처음부터 만들었다.

### cache
이 모듈은 내부에는 assign으로 입력 포트와 출력 포트를 연결해 놓은 것이 전부이다. 이름이 캐시이지만 실제로 캐시로서 기능하지는 않으며, 베이스라인을 구현할 때 이 더미 캐시 모듈을 만들어 놓음으로서, 캐시가 추가된 버전을 만들 때 이 캐시 모듈의 자리에 같은 정의를 가진 진짜 캐시 모듈을 삽입함으로서 구현의 편의성을 늘리고자 만들어진 모듈이다. 따라서, 베이스라인에서는 사용되지만 캐시 구현에서는 사용되지 않는 모듈이다.

#### TwoWayCache
이 모듈은 실제 캐시로, 2-way set assosiative cache로 구현되어 있다. 16비트 주소를 사용하므로, 하나의 태그는 12비트로 이루어져 있으며, 하위 4비트가 인덱스 2비트와 오프셋 2비트로 나뉘어 접근된다. 각 인덱스에 대응되는 set에는 두개의 way가 존재하며, 각 way당 하나의 태그와 4개의 워드 데이터가 저장된다. 하나의 set당 cold 비트가 있으며, 이 cold 비트는 접근한지 오래되어 eviction의 대상이 될 way를 가리킨다.

# Implementation
## Cache Victim Selection
캐시에 새로운 데이터를 추가할 때, 우선 valid 비트를 우선적으로 검증하여, 앞의 way부터 valid하지 않은 캐시 라인이 있으면 그곳을 우선적으로 목표로 한다. 둘 다 valid 할 경우에는 cold 비트를 참조하여 cold로 표지된 캐시 라인을 목표로 한다.

이 cold 비트는 캐시에 대해 읽기나 쓰기 접근이 일어나면 재설정된다.

## Instruction Cache

    always @(posedge clk) begin
        if(access_done1) begin
            tags[`IDX(i_address_c)][i_victim] = `TAG(i_address_c);
            data[`IDX(i_address_c)][i_victim][0] = i_data_m[`WORD_SIZE*1-1:`WORD_SIZE*0];
            data[`IDX(i_address_c)][i_victim][1] = i_data_m[`WORD_SIZE*2-1:`WORD_SIZE*1];
            data[`IDX(i_address_c)][i_victim][2] = i_data_m[`WORD_SIZE*3-1:`WORD_SIZE*2];
            data[`IDX(i_address_c)][i_victim][3] = i_data_m[`WORD_SIZE*4-1:`WORD_SIZE*3]; 
            cold[`IDX(i_address_c)] = !i_victim;
            valid[`IDX(i_address_c)][i_victim] = 1;
            /* ... code... */
        end
    end
    /* ... code ... */
if(i_read_m) begin
    if(!init) begin
        if((i_read_c || stall_resolution) && !i_hit_mask && i_rdy_m) begin
        end
    /* ... code... */
end else begin
    if(i_read_c && !i_hit_mask) begin
        //instruction read miss
        i_read_m = 1;
    end
end

인스트럭션 캐시 부분이다. 아래쪽 코드 중 가장 중요한 부분은 `i_read_c` 요청이 왔는데 미스가 났을 때다. 이렇게 인스트럭션 읽기 미스가 날 경우엔 `i_read_m` 시그널을 켜서 메모리에서 `port2_delay` 에 딜레이 카운터를 넣고 매 사이클 값을 1씩 줄여나간다. 그렇게 총 4사이클이 지난 후에 `port2_delay2 == 1` 이 되면, 메모리에서 라인 한개를 캐시로 옮겨주면서 `access_done1` 시그널을 준다. 캐시 사이드에서 해당 시그널이 들어오면 i_data_m 포트에서 한 줄을 읽어와 캐시 내부에 적재한다.

## Data Cache

if(d_read_c) begin
    if(d_read_m) begin    
        if(!d_hit_mask && d_rdy_m) begin
            //data read resolution
            tags[`IDX(d_address_c)][d_victim] = `TAG(d_address_c);
            data[`IDX(d_address_c)][d_victim][0] = d_data_m[`WORD_SIZE*1-1:`WORD_SIZE*0];
            data[`IDX(d_address_c)][d_victim][1] = d_data_m[`WORD_SIZE*2-1:`WORD_SIZE*1];
            data[`IDX(d_address_c)][d_victim][2] = d_data_m[`WORD_SIZE*3-1:`WORD_SIZE*2];
            data[`IDX(d_address_c)][d_victim][3] = d_data_m[`WORD_SIZE*4-1:`WORD_SIZE*3];
            cold[`IDX(d_address_c)] = !d_victim;
            valid[`IDX(d_address_c)][d_victim] = 1;
            d_read_m = 0;
        end 
    end
    /* ... code... */
end else if(d_write_c) begin
    if(d_hit_mask) begin
        //data cache update
        data[`IDX(d_address_c)][d_hit_mask-1][`OFF(d_address_c)] = d_data_c;
        cold[`IDX(d_address_c)] = !(d_hit_mask-1);    
    end 
    /* ... code... */
end

/* ...code... */

### Data read
인스트럭션 캐시와 마찬가지로, 미스가 나고 메모리에 쓰고 있는 상태가 아니라면, `d_read_m`을 켜서 메모리에 데이터를 요청한다. 동일한 로직으로 메모리에서 딜레이를 기다린후 값을 주게 되면, `d_rdy_m` 이 액티브 되어 `d_data_m`으로 읽어온 값을 캐시에 다시 적재한다.

### Data Write
데이터 쓰기의 경우에는 Write-no-allocate 구현을 채택하였으므로, 쓰기 접근이 hit인지 miss인지와는 관계없이 항상 메모리에 한 word씩 접근하여 데이터를 갱신한다. 캐시 hit의 경우에는 물론 캐시를 갱신하여 실행을 이어나갈 수 있다.

# Discussion
## Analyzing Performance
| 구현 방법 | cycle 수 |
| -------- | -------- |
| Baseline CPU|2538|
| Cache CPU |2520|

과제에서 주어진 Latency 룰에 따라 Baseline CPU (메모리 접근시 2 사이클 소요)과 Cache CPU (hit시 1사이클, miss시 6 사이클 소요)를 구현하였다. 두 프로세서의 동작을 비교한 결과, Baseline CPU는 2538 사이클이 나왔고, Cache CPU는 2520 사이클이 나왔다. Cache CPU가 약 1.01배의 성능 향상을 보였다. 이러한 결과가 나온 이유에 대해서 생각해보자면, Baseline CPU는 하나의 인스트럭션을 가져올 때, 2 사이클이 소요된다. 그에 비해, Cache CPU는 한 개의 라인 (4개의 워드)를 가져오는데 6 사이클이 소요된다. 그리고, 그 다음 세 번의 IF에 대해서는 각 1사이클 씩 걸릴 것이다. 그렇다면, 4개의 인스트럭션을 fetching하는데 총 9 (6+1+1+1) 사이클이 걸린다면, 평균적으로 인스트럭션 한 개당 2.25 사이클이 걸리는 것이다. 따라서, locality가 없다면, 캐시가 추가된 프로세서가 느린 것이 당연한 것이다. 하지만, 테스트 어셈블리의 마지막은 루프를 돌며 피보나치를 계산하는데 이 때 instruction 의 로컬리티가 보장될 것이다. 또한, data memory는 Memory[0]~[8] 에 많이 접근한다. 이런 면에서 data 읽기/쓰기 또한 locality적인 면에서 이득으로 보아 성능이 비슷하게 나왔다.

## Hit ratio
| 종류| 총 접근 횟수 | Hit 수 | Miss 수 | Hit ratio|
|-|-|-|-|-|
|Data Read|124|57|67|50.0% |
|Data Write|288|164| 124| 56.9%|
|Instruction Read|981|904| 77|92.2%|
|Total|1393 |1125 | 268| 80.7%|

## Important decisions
- Replacement policy를 결정할 때, 웨이가 두개밖에 안되는 점을 고려해서 LRU를 선택하는 것이 구현상 많이 편리했다.
- 처음에는 Write-Back, Write-Allocate 캐시를 구현하려고 했지만, 캐시에서 읽기가 미스나고, 원래 있던 값이 evict 되어야한다면 명령어 메모리 접근에서도 메모리 쓰기가 읽어날 수 있고, 또 한번의 메모리 접근에서 읽기와 쓰기가 모두 일어난다는 점도 고려해야 하여, Write-Through, Write-no-Allocate 캐시를 구현하는 방향으로 선회하였다. 그래서 지금 돌아보면, 캐시 모듈에 dirty라는 벡터 배열이 남아있다.
## Difficulties
- JPR로 점프를 뛰고, 캐시가 딜레이를 기다리는 동안 JPR 다음에 있던 HLT가 실행되는 등의 문제가 있어 `IF_ID_Inst`의 업데이트 조건을 추가함으로 더 까다롭게 고침으로써 해결하였다.
- 명령어 메모리와 데이터 메모리 접근에서 캐시 미스가 모두 발생할 수 있는데, 이 둘이 연속적으로 발생하자 생각보다 많은 문제가 발생해 골치아팠으나, PVS 갱신 조건을 더 추가하여 해결했다.
# Conclusion
테스트 벤치의 모든 테스트들을 정상적으로 통과하였고, 주어진 레이턴시 조건하에 우리의 Cache CPU는 Baseline CPU 보다 1.01배의 성능 향상을 보였다.