owned this note
owned this note
Published
Linked with GitHub
2017q3 Homework1 (phonebook)
===
contributed by < `shanshow` >
### 預期目標
* 適度修改 phonebook_opt.c 和 phonebook_opt.h 兩個檔案，使得這兩者執行時期的 cache miss 降低。請用 perf 驗證，而且改進的過程中，不能有功能方面的減損。
* 於是，先行理解和為 cache miss 及有何種方式使其降低。
* 閱讀老師提供的 [Programming small](https://hackmd.io/s/SkfffA-jZ)，以及 [cache 原理和實驗](https://hackmd.io/s/S14L26-_l)
* 其中，關於 struct 的大小計算並非一開始想像的直接把char內的數值相加，因為 struct 的空間分配不是直接使用連續空間的，為記憶體的對齊問題。
* [struct 結構佔記憶體容量計算](http://blog.csdn.net/myblog_dwh/article/details/13035005)
### cache miss：
* 在 cache 裡找不到需要的指令或資料，因此須繼續往 main memory 找，而 latency (延遲)時間會愈長。
* 有三種類型：([參考投影片EECC551 - Shaaban](http://meseec.ce.rit.edu/eecc551-winter2001/551-1-30-2002.pdf))
#### Compulsory:
```
On the first access to a block; the block must be brought into the cache;
also called cold start misses, or first reference misses.
第一次存取某尚未存在於 cache 內的 block 的時候發生，這無法避免，畢竟
你一定得先把 block 放到 cache 內才有意義。又稱 cold start miss
```
#### Capacity:
```
Occur because blocks are being discarded from cache because
cache cannot contain all blocks needed for program execution
(program working set is much larger than cache capacity).
因為在程式執行的期間， cache 沒辦法把所有需要的 block 一起放進去( capacity 不足)，
所以縱使那個 block 稍後仍然需要，也得先行拋棄。
```
#### Conflict:
```
In the case of set associative or direct mapped block placement strategies,
conflict misses occur when several blocks are mapped to the same set or block frame;
also called collision misses or interference misses.
在 set associative 跟 direct mapped block caches 內發生，
很多個 block 搶奪同一個 set 導致 miss ，又稱 called collision misses 或 interference misses 。
```
* 其中， Capacity 與 Conflict 的概念容易混淆。
* 以[老師提供的文件](http://hackfoldr.org/cpu/https%253A%252F%252Fhackmd.io%252Fs%252FHkW3Dr1Rb)作為參考與概念釐清。
#### Capacity misses ：
如果有一個 64KB 的陣列需要重複存取，因為數組大小遠大於 cache 大小，所以沒辦法全部放入 cache 。第一次存取陣列發生的 cache misses 全都是 compulsory misses 。但之後存取陣列發生的 cache misses 全都是 capacity misses ，這時的 cache 已存滿，容量不足以儲存全部的資料。
#### Conflict misses ：
如果有兩個 8KB 的數組需要來回存取，但是這兩個數組都映射到相同的地址， cache 的大小足夠儲存全部的數據，但是因為相同地址發生衝突，需要來回替換，這時候發生的 cache misses 全都是 conflict misses（不過，第一次存取陣列發生的 cache misses 仍然都是 compulsory misses），這時 cache 並沒有存滿。
* 解決 conflict misses 的辦法：
* LRU(least recently used,最近罕用)：將集合中目前最不常用的的區塊加以取代
* 舉個例子，假設 block frame 為 3 ，進入 block 的順序為 1 3 2 3 5 1
* 1 3 2 先後進入 block，由左至右表示它的優先程度的遞減：2 3 1 。
* 而後 3 再次進入，導致 block 內的 3 優先度提升至最前： 3 2 1 。
* 5 進入，因為 1 的優先度最低，因此被拋棄： 5 3 2。以此類推。
* 可減少失誤次數,實作困難且成本高,常用在虛擬記憶體中
* FIFO(first in first out,先進先出)
* 將集合中最早進入的區塊加以取代
* 設 block frame = 3 ，順序為 1 2 3 4
* 1 2 3 先後進入 block ： 3 2 1
* 4 進入時，把最早進入的 1 捨棄： 4 3 2
* 實作較簡單,失誤較高
#### 額外啟發：快取分區方法：
我參閱[交通大學的碩士論文](https://ir.nctu.edu.tw/handle/11536/46632)，裡面提到
當越來越多處理器共享一個快取時，
會使得處理器之間對於快取資源的競爭更加劇烈，
進而影響個別單一程序的效能。
* 快取分區方法是一個可以降低程序間互相競爭的方法，其通常將快取分割給各個處理器單獨使用，然而此方法在程序不平衡的存取快取時，會造成快取分區利用率不佳的問題。針對此問題，我們提出兩個方法做改善:
* 1. 額外增加一塊共享分區供所有處理器共同使用
* 2. 針對每一個處理器，給予不同的索引方式。另外，我們針對所有分區，在一般常用於減少失誤的方法下(可變動區塊大小、可變動關聯度、改變替代策略)進行討論。
* 論文偏長，需持續精進閱讀與補充此條目。
### 效能改善
作業要求如下
適度修改 phonebook_opt.c 和 phonebook_opt.h 兩個檔案，
使得這兩者執行時期的 cache miss 降低。
請用 perf 驗證，而且改進的過程中，
不能有功能方面的減損。
* 根據[AMAT的計算式](https://zh.wikipedia.org/wiki/CPU%E7%BC%93%E5%AD%98#.E9.99.8D.E4.BD.8E.E5.A4.B1.E6.95.88.E7.8E.87)，可以看出優化快取可從三個方面入手：
* 一、減少命中時間($T_{hit}$)。
* 二、降低失效率($MR$)。
* 三、減輕失效代價($MP$)。
* $AMAT=T_{hit}+MR\times MP$
* $T_{hit}$為 Hit Time ：從定位快取塊、經標籤比較並選中，一直到傳回資料所需的時間。
* $MR$為 Miss Rate ，在特定次數的記憶體訪問中，發生 cache miss 次數所占的比重。
* $MP$為 Miss Penalty：從定位快取塊、經標籤比較判定失效，然後再從記憶體中定位資料並載入快取，最後直到把目標資料返回所需的時間。
* 首先觀看 phonebook_orig.c 檔案，可發現裡面使用的資料結構是 Linked list。
* 在[Programming small](https://hackmd.io/s/SkfffA-jZ)中提到一個 phone book 案例，有一個優化方式：使用體積較小的 struct 。
* 根據題目要求，我們只需要知道「有沒有找到 last name」，對於 email、phone number、address、zip 等等資訊是可以在搜尋過程中忽略不看。另外我又希望能不改變原本 phonebook entry 的結構，所以我另外設計一個 struct 只儲存 last name，並用一個指向 phonebook entry 的指標叫 *detail 來儲存詳細資訊，新的 struct 大小只有 32 bytes，這樣搜尋的過程中，cache 就可以塞進 (32 * 1024) / (32 * 8) = 128 個單字，增加 cache hit 的機率。
* 以此為參考設計程式：
```clike=
typedef struct __LAST_NAME_ENTRY{
char lastName[MAX_LAST_NAME_SIZE];
entry *detail;
struct __LAST_NAME_ENTRY *pNext;
} lastNameEntry;
```
* 根據這個程式碼，將其餘不必要的參數用 __PHONE_BOOK_DETAIL 另行放置，然後改寫 __PHONE_BOOK_ENTRY 。
* 因為 findName 只會查詢 lastName ，然而最初的程式碼會把 Entry 總共 136 bytes 的資料都搬進去 cache 內，造成效率不足。
* 於是將一些不會用到的資料以 struct __PHONE__BOOK_DETAIL 的形式另外儲存，再用指標的方式讓原本的 Entry連過去，可以有效把 Entry 的大小縮至 32 bytes 。
* 進行 make cache-test
```clike=
Performance counter stats for './phonebook_orig' (100 runs):
2,104,919 cache-misses # 91.069 % of all cache refs ( +- 0.04% )
2,311,356 cache-references ( +- 0.05% )
261,910,733 instructions # 1.18 insn per cycle ( +- 0.02% )
221,715,446 cycles ( +- 0.32% )
0.077304586 seconds time elapsed ( +- 1.00% )
```
```clike=
Performance counter stats for './phonebook_opt' (100 runs):
446,366 cache-misses # 61.120 % of all cache refs ( +- 0.38% )
730,312 cache-references ( +- 0.32% )
244,530,784 instructions # 1.62 insn per cycle ( +- 0.02% )
150,966,012 cycles ( +- 0.23% )
0.048559588 seconds time elapsed ( +- 1.03% )
```
* 原本的情形， cache misses 達到91.069 %，更改後的 則急遽減少至61.120 %。
### 使用 hash table 的效能增長(待改進
* Linked list 搜尋時的時間複雜度為 O(N)，在數目龐大時將損耗效能。
* 思考是否有其餘資料結構能夠用更精簡的時間複雜度。
* 依據 [Hash Table：Intro(簡介)](http://alrightchiu.github.io/SecondRound/hash-tableintrojian-jie.html) ，如果使用 Hash Table 結構，進行搜尋的時間複雜度將變為 O(1)。
Google Drive
Gist
Clipboard
Sign in with Wallet
