# COMP_ORG HW3 懶人包

hello~
可能沒人跟我一樣極限但想說有可能有些人還沒做完然後感謝筍包大大每次的救援 >< 我決定也寫一份hack_md說不定可以幫到一些人做作業趕死線maybe~?*因為自己也受到許多貴人的指點也希望說不定這份能夠幫到一些人 XD*

~~(先聲明我沒寫過hackmd所以排版可能會很醜)~~

我自己看了大概幾個小時才開始動手～因為實在是有點看不懂XD

以下先整理一下這次作業的幾個重點：


首先我先在原先這張圖上面做了標記，這邊看懂了應該就會對怎麼去實現幾個policy清楚很多～

這次作業最主要的就是去修改

victimize()

&

check_tag()

建議同學們可以先去原始碼看過一遍，大概了解一下原本的幾個variable是在做啥用的～

[可以參考這篇筍包大大整理的文件](https://hackmd.io/@swenbao/HJ6Q6_Nw3 )

### 再來是好用的data structures

std::vector

只能說這真的太好用了，這次所有的policy幾乎都可以直接用這個去完成

std::vector<std::vector<int>> grid;

非常好用的點在於可以去做nesting的動作

同樣的也可以用

std::queue<int> myQueue;

int myArray[5];

去做相同得事情。

# FIFO

可以把這個policy想像成是這個模樣


> *以上採用左邊刪掉後>右邊插入*

因為first-in => first-out

# LRU
別於FIFO, LRU會根據hit的狀況去調整順序

> *以上採用左邊刪掉後>右邊插入*

# LFU
別於FIFO, LFU也會根據hit的狀況去調整順序

> *以上採用左邊刪掉後>右邊插入*

這題比較tricky一點，假如是用2維陣列去標記counter的話，可能會遇到只檢查index=0的問題＝**這通常是會一直replace第一個**，導致miss rate超級高。

## 這三個Policy有個重點
就是在MISS的情況下，都還是是以FIFO為主。
在HIT的情況下，會有不同的動作。

## 完成三個policy後
可以用 （摘錄至DC@培根）

#!/usr/bin/bash

Policy=lfu
>output"$Policy".txt
make $Policy
for block in $(seq 3 6)
do
    for set in $(seq 0 $((6-$block)))
    do
        way=$((6-$set-$block))
        
        #change config and print config
        printf "[cache]\nSet = $((2**$set))\nWay = $((2**$way))\nBlockSize = $((2**$block))\nPolicy = \"$Policy\"" > config.conf
#        echo $set $way $block        
        #make score
        make test 2>&1 | grep -A 3 ==== >> output"$Policy".txt
    done
done

> 1.把Policy改成你要的
> 2.把這個存成 bruteforce.sh
> 3.在terminal打 chmod 777 bruteforce.sh 改權限讓你可以執行他
> 4.在terminal打 ./bruteforce.sh 等他跑完
> 5.點開output.txt來看或是 cat output.txt*

去執行條件下的各種setting,以便找到最佳的config~

## 參考結果

*我自己的測試結果，僅供參考*

### FIFO

=======================================================================
Data Cache Setting with: 1:8:8
Miss Rate: 50.0967 %
bbl loader
=======================================================================
Data Cache Setting with: 2:4:8
Miss Rate: 49.8777 %
bbl loader
=======================================================================
Data Cache Setting with: 4:2:8
Miss Rate: 50.063 %
bbl loader
=======================================================================
Data Cache Setting with: 8:1:8
Miss Rate: 52.0297 %
bbl loader
=======================================================================
Data Cache Setting with: 1:4:16
Miss Rate: 40.337 %
bbl loader
=======================================================================
Data Cache Setting with: 2:2:16
Miss Rate: 38.8623 %
bbl loader
=======================================================================
Data Cache Setting with: 4:1:16
Miss Rate: 40.45 %
bbl loader
=======================================================================
Data Cache Setting with: 1:2:32
Miss Rate: 35.4383 %
bbl loader
=======================================================================
Data Cache Setting with: 2:1:32
Miss Rate: 35.4987 %
bbl loader
=======================================================================
Data Cache Setting with: 1:1:64
Miss Rate: 36.4023 %
bbl loader

### LRU

=======================================================================
Data Cache Setting with: 1:8:8
Miss Rate: 48.898 %
bbl loader
=======================================================================
Data Cache Setting with: 2:4:8
Miss Rate: 48.715 %
bbl loader
=======================================================================
Data Cache Setting with: 4:2:8
Miss Rate: 49.307 %
bbl loader
=======================================================================
Data Cache Setting with: 8:1:8
Miss Rate: 52.0297 %
bbl loader
=======================================================================
Data Cache Setting with: 1:4:16
Miss Rate: 38.5147 %
bbl loader
=======================================================================
Data Cache Setting with: 2:2:16
Miss Rate: 38.36 %
bbl loader
=======================================================================
Data Cache Setting with: 4:1:16
Miss Rate: 40.45 %
bbl loader
=======================================================================
Data Cache Setting with: 1:2:32
Miss Rate: 34.983 %
bbl loader
=======================================================================
Data Cache Setting with: 2:1:32
Miss Rate: 35.4987 %
bbl loader
=======================================================================
Data Cache Setting with: 1:1:64
Miss Rate: 36.4023 %
bbl loader

### LFU

=======================================================================
Data Cache Setting with: 1:8:8
Miss Rate: 63.2277 %
bbl loader
=======================================================================
Data Cache Setting with: 2:4:8
Miss Rate: 59.7217 %
bbl loader
=======================================================================
Data Cache Setting with: 4:2:8
Miss Rate: 55.1817 %
bbl loader
=======================================================================
Data Cache Setting with: 8:1:8
Miss Rate: 52.0297 %
bbl loader
=======================================================================
Data Cache Setting with: 1:4:16
Miss Rate: 49.8243 %
bbl loader
=======================================================================
Data Cache Setting with: 2:2:16
Miss Rate: 45.066 %
bbl loader
=======================================================================
Data Cache Setting with: 4:1:16
Miss Rate: 40.45 %
bbl loader
=======================================================================
Data Cache Setting with: 1:2:32
Miss Rate: 41.7063 %
bbl loader
=======================================================================
Data Cache Setting with: 2:1:32
Miss Rate: 35.4987 %
bbl loader
=======================================================================
Data Cache Setting with: 1:1:64
Miss Rate: 36.4023 %
bbl loader