2017q3 Homework1 (phonebook)

contributed by < shanshow >

預期目標

• 適度修改 phonebook_opt.c 和 phonebook_opt.h 兩個檔案，使得這兩者執行時期的 cache miss 降低。請用 perf 驗證，而且改進的過程中，不能有功能方面的減損。

• 於是，先行理解和為 cache miss 及有何種方式使其降低。

• 閱讀老師提供的 Programming small，以及 cache 原理和實驗

• 其中，關於 struct 的大小計算並非一開始想像的直接把char內的數值相加，因為 struct 的空間分配不是直接使用連續空間的，為記憶體的對齊問題。

• struct 結構佔記憶體容量計算

cache miss：

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

• 有三種類型：(參考投影片EECC551 - Shaaban)

  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 的概念容易混淆。

• 以老師提供的文件作為參考與概念釐清。

  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

  • 實作較簡單,失誤較高

額外啟發：快取分區方法：

我參閱交通大學的碩士論文，裡面提到

​​​​當越來越多處理器共享一個快取時，
​​​​會使得處理器之間對於快取資源的競爭更加劇烈，
​​​​進而影響個別單一程序的效能。 

• 快取分區方法是一個可以降低程序間互相競爭的方法，其通常將快取分割給各個處理器單獨使用，然而此方法在程序不平衡的存取快取時，會造成快取分區利用率不佳的問題。針對此問題，我們提出兩個方法做改善:

• 1. 額外增加一塊共享分區供所有處理器共同使用
• 2. 針對每一個處理器，給予不同的索引方式。另外，我們針對所有分區，在一般常用於減少失誤的方法下(可變動區塊大小、可變動關聯度、改變替代策略)進行討論。

• 論文偏長，需持續精進閱讀與補充此條目。

效能改善

作業要求如下

​​​​適度修改 phonebook_opt.c 和 phonebook_opt.h 兩個檔案，
​​​​使得這兩者執行時期的 cache miss 降低。
​​​​請用 perf 驗證，而且改進的過程中，
​​​​不能有功能方面的減損。

• 根據AMAT的計算式，可以看出優化快取可從三個方面入手：

  • 一、減少命中時間(
    $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中提到一個 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 的機率。

• 以此為參考設計程式：

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

 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% )

 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(簡介) ，如果使用 Hash Table 結構，進行搜尋的時間複雜度將變為 O(1)。