# cache 原理和實驗
###### tags: `sysprog2017`

在本次作業中，會學習到 perf 這個工具，你可能會得到下面的輸出結果:
什麼是 cache-misses 呢？
這裡我們會解說 cache 的相關知識

 Performance counter stats for './perf_stat_cache_miss' (5 runs):
    4,416,226        cache-misses        #    3.437 % of all cache refs    ( +-  0.27% )
    128,483,262      cache-references                                      ( +-  0.02% )
    2,123,281,496    instructions        #    0.65  insns per cycle        ( +-  0.02% )
    3,281,498,034    cycles                                                ( +-  0.21% )
        1.299352302 seconds time elapsed                                   ( +-  0.19% )

### 為什麼需要 cache?
早期，main memory 的速度非常慢而且也非常貴，但當時的 CPU 速度也慢，因此還未有 cache 出現。但從 1980 年代開始，main memory 和 CPU 的差距急速拉大(如下圖)，main memory 的速讀雖有提升，卻仍不及 CPU 的進展，因此需要 cache 來補強兩者間的差距。

### cache 是什麼？
"cache" 是為了讓資料存取的速度適應 CPU 的處理速度

允許 CPU 直接到 cache memory 查看所需資料是否存在。若是，則直接存取不必再到 main memory —— 減少到 main memory 存取的次數，解決 main memory 存取不夠快的問題。

* **static random access memory (SRAM)** 組成
* [cache line](http://cenalulu.github.io/linux/all-about-cpu-cache/)
Cache Line 可以簡單的理解為 cache 中的最小單位。目前主流的 cache 的 cache line 大小都是64B。==請務必詳閱超連結 cache line 內容==
* **分層**：
未來或許會再出現更多層的 cache，因為當 cache 和 main memory 的速度差距再拉大時，多一層容量比原本 cache 大但速度較慢的 cache 比起將原本的容量加大更來的符合成本考量。

* **L1 cache**: 2 KB 到 64 KB 之間，最靠近 CPU ，速度最快
* L1i: instruction
* L1d: data
* **L2 cache**: 256 KB 到 2 MB 之間，速度次之
* **L3 cache**: 1 MB 到 8 MB 之間，雖然是 cache 當中速度最慢的，但仍比 RAM 快

* **associativity**：
快取記憶體的動態位址轉換，採用硬體實作的技術來完成，每個 CPU 包含 tag RAM，用來紀錄一個 memory block 要對映到那一個 cache block
* **direct mapping**: 1:1，每個 cache block 僅可以對應到唯一的一個 main memory block
* 優點：搜尋時間短
* 缺點：hit rate 低
* **fully associative**: 任意 cache block 可以對應到任意的 main memory block
* 優點：hit rate 高
* 缺點：搜尋時間長，CPU 必須掃過整個 cache 才能決定是否該繼續往 main memory 撈資料
* **n-way associative**: 把 cache 分成多個 set，CPU 必須檢查指定 set 內的每個 block 是否有可用的 cache
* 優點：搜尋時間短且 hit rate 高
* worst case: Fully Associative 的情況，也就是 CPU 要檢查整個 cache

### cache miss
在 cache 裡找不到需要的指令或資料，因此須繼續往 main memory 找，而 latency (延遲)時間會愈長。

cache miss 還分為以下三種類型：
* instruction read miss
* data read miss
* data write miss

## caching
caching 在電腦系統中是一個很重要的原理。

**運作方式**：
資訊通常會存放在某些儲存裝置上(如 main memory)。使用時，會將資訊複製到比較快的儲存裝置上 —— cache —— 一個暫存。
當我們需要某些資訊時，會優先檢查它是否在 cache 中，若存在則直接取用；不存在則往下一階 (也就是資訊的來源) 儲存裝置拿取資訊，並複製一份到 cache 中，因我們假設近期還會再用到同一塊資料。

引用自書籍：Operating System Concept
>caching is an important principle of computer systems. Here's how it works. Information is normally kept in some storage system(such as main memory.) As it is used, it is copied into a faster storage system -- the cache -- on a temporary basis. When we need a particular piece of information, we first check wherther it is in the cache. If it is, we use the information directly from the cache. If it is not, we use the information from the source, putting a copy in the cache under the assumption that we will need it again soon.

main memory 可以被視為 secondary storage 的 cache。因 secondary storage 的資訊必須先複製到 main memory 上才能使用，且資訊一定是先存放在 main memory 上才能再存回 secondary storage。

>main memory can be viewed as a fast cache for secondary storage, since data in secondary storage must be copied into main memory for use and data must be in main memory before being moved to secondary storage for safekeeping.

而這個 caching 的概念貫徹了整個儲存系統


## 參考及引用資料
* [CPU cache](https://en.wikipedia.org/wiki/CPU_cache#Cache_miss)
* [cache computing](https://en.wikipedia.org/wiki/Cache_(computing))
* [How L1 and L2 CPU caches work, and why they’re an essential part of modern chips](https://www.extremetech.com/extreme/188776-how-l1-and-l2-cpu-caches-work-and-why-theyre-an-essential-part-of-modern-chips)
* [How Computer Memory Works](http://computer.howstuffworks.com/computer-memory4.htm)
* [淺談 memory cache](http://opass.logdown.com/posts/249025-discussion-on-memory-cache)
* [关于 CPU Cache -- 程序猿需要知道的那些事](http://cenalulu.github.io/linux/all-about-cpu-cache/)
* [2016 春季班 code review](https://embedded2016.hackpad.com/Mar-8-2016--kpfgwU6YgOF)