owned this note
owned this note
Published
Linked with GitHub
# 2018 Homework1 (phonebook)
contributed by <`0922james0922`>
### Reviewed by `TingL7`
* github commit只有標題，沒有具體的內容，且標題下的沒什麼實際意義，完全不知道程式做了什麼更動。
* findName()減少的原因並非調整成BST，實際上也沒有改動findName()。
* 可以嘗試用hash function加速findName()，或者參考其他同學優化的方法。
>感謝同學提醒，以針對commit做修改跟更新，並且參考同學們的hash table的方法加速[name=0922james0922]
## 系統環境
```
$ lscpu
Architecture: x86_64
CPU 作業模式： 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
每核心執行緒數：2
每通訊端核心數：2
Socket(s): 1
NUMA 節點： 1
供應商識別號： GenuineIntel
CPU 家族： 6
型號： 69
Model name: Intel(R) Core(TM) i5-4210U CPU @ 1.70GHz
製程： 1
CPU MHz： 1842.468
CPU max MHz: 2700.0000
CPU min MHz: 800.0000
BogoMIPS: 4788.67
虛擬： VT-x
L1d 快取： 32K
L1i 快取： 32K
L2 快取： 256K
L3 快取： 3072K
NUMA node0 CPU(s): 0-3
```
## 環境建置
### 1.Ubuntu
原先想再自己的電腦灌雙系統順便學習一下怎麼灌雙系統，不幸電腦的硬碟所勝無己，只好找台LAB多的多的筆電來灌Ubuntu。
1. 首先你必須先找個不要的隨身碟或SD卡
2. 到[Ubuntu](https://www.ubuntu-tw.org/modules/tinyd0/)的官網下載對應版本的IOS映像檔
3. 利用[partition wizard](http://blog.xuite.net/yh96301/blog/394356641-MiniTool+Partition+Wizard+Free+9.1%E8%A4%87%E8%A3%BDWindows+10)免費的磁碟分割精靈將映像檔燒進隨身碟裡
4. 將需要灌進Ubuntu系統的電腦進入bias裡設定開機順序，將隨身碟或是SD卡放在第1順位後儲存離開，並重新開機，記得隨身碟要在開機前都插著。
5. 接著就是順著安裝步驟
## GitHub
1. [SSH key](http://wiki.csie.ncku.edu.tw/github) 的產生並綁定
2. 綁定後在[Embedded2016/phonebook](https://github.com/embedded2016/phonebook)做frok到自己帳號的動作
3. 在fork之前必須先在自己github帳號先新增專案資料夾，利用import repository 將需fork的連結貼在import repository的網址列
4. 接著在專案底下複製自己的網址
5. 在terminal內輸入
``＄git clone 網址``
6. 若改動程式碼要同步github輸入
``＄git add 改的檔案名``
7. 新增commit
``＄git commit``
8. push
``＄git push``
9. 檢查github看有沒有改動過，有的話就成功了！
---
## phonebook作業
先把原始的source code載來run看看效能如何
```
Performance counter stats for './phonebook_orig' (100 runs):
1,270,158 cache-misses # 90.979 % of all cache refs ( +- 0.41% )
1,396,101 cache-references ( +- 0.40% )
261,187,057 instructions # 1.33 insns per cycle ( +- 0.02% )
195,800,630 cycles ( +- 0.11% )
0.074808492 seconds time elapsed ( +- 0.15% )
```
* 發現cache miss高達90.979%
### 試著縮減entry size
* 想法：
除了 lastName 以外的欄位都不是搜尋時會用到的
* 優點：
size of entry 縮小後由於佔用 cache 較小，應能降低cache-miss
* 缺點：
需要多一次 `malloc` 來分配記憶體給這些欄位，可能增加 `append()` 時間
```clike=
typedef struct __PHONE_BOOK_ENTRY {
char lastName[MAX_LAST_NAME_SIZE];
/*
char firstName[16];
char email[16];
char phone[10];
char cell[10];
char addr1[16];
char addr2[16];
char city[16];
char state[2];
char zip[5];
*/
struct Data *data;
struct __PHONE_BOOK_ENTRY *pNext;
} entry;
/* optimal version */
typedef struct Data {
char firstName[16];
char email[16];
char phone[10];
char cell[10];
char addr1[16];
char addr2[16];
char city[16];
char state[2];
char zip[5];
} detail;
```
* 我利用註解的方式將上面那一陀不需要的資料放在下面的struct detail裡，用以節省size of entry的大小
* 結論：
會造成 cache miss 就是因為 CPU 在 cache 中找不到資料，而透過程式碼就會發現，資料只有比對 lastName 若把其他資料用另一個 struct 包起來，那麼同樣大小的 cache 是否能放入更多筆資料，進而減少 cache miss 數。
### 測試結果
```
Performance counter stats for './phonebook_opt' (100 runs):
119,876 cache-misses # 26.887 % of all cache refs ( +- 0.38% )
445,848 cache-references ( +- 0.30% )
244,031,449 instructions # 1.85 insns per cycle ( +- 0.02% )
131,755,942 cycles ( +- 0.25% )
0.050892418 seconds time elapsed ( +- 0.32% )
```
> 文字輸出請直接複製貼上，避免使用圖片
> [name=課程助教][color=red]
>>好的感謝助教提醒以做改正 [name=0922james0922]
:::success
cache miss由原本的90幾降到將近30%而已，可見降低entry的size確實能夠改善cache miss rate
:::
### 用gnuplot比較以上四者與original版本效能
[gnuplot](https://hackmd.io/s/Skwp-alOg#)跟[Makefile](https://hackmd.io/s/SySTMXPvl#)的語法算是我比較不熟的部份，所以都是一部一部慢慢學，也有學到如何改變圖表的設定，嘗試起來特別有趣
`$ make plot`
* ==append()==
optimized (只用縮減的 struct entry size )所花的時間，比 original 低了許多
* ==findname()==
original 版本的時間複雜度是O(n)，而調整成 BST 後時間複雜度為 O(logn)。
### 問題探討
* 我有參考其他同學改善後的cache miss rate，都還是高達50%幾甚至60%，而我的cache miss rate卻可以降到30左右，我也有做清空cache的動作但還是一樣效果，在想是不是硬體規格或是品牌或是硬體衰退等等的關係，這邊可能要請教一下老師大大。
:::warning
讀了資訊工程，結果提了「文組^TM^」等級的幻想問題，這樣對得起自己嗎？至少用 microarchitecture 去思考差異點。
:notes: jserv
:::
### 嘗試使用hash table
* 參考`bauuuu1021`同學的hash table作法，這次採用[BKDR](http://blog.csdn.net/diana_cherry/article/details/7260243) Hash Function
* 相較字首分群 findName 有快一些，但 append 增加了許多，推測是每筆資料都要跑一次 hash() 以求得 index number 的緣故。
### 測試結果
```
Performance counter stats for './phonebook_opt' (100 runs):
87,974 cache-misses # 26.002 % of all cache refs ( +- 1.51% )
338,336 cache-references ( +- 0.77% )
239,850,870 instructions # 1.74 insns per cycle ( +- 0.02% )
137,698,676 cycles ( +- 0.36% )
0.053710217 seconds time elapsed ( +- 0.49% )
```
* miss rate 有些許下降，但跟其他同學相比還是太高。我想試著調整seed來測試看看其他大小的變化
* ==seed從31調整到131==
```
Performance counter stats for './phonebook_opt' (100 runs):
78,807 cache-misses # 40.787 % of all cache refs ( +- 1.17% )
193,213 cache-references ( +- 0.72% )
239,900,369 instructions # 1.79 insns per cycle ( +- 0.02% )
134,365,402 cycles ( +- 0.29% )
0.051935153 seconds time elapsed ( +- 0.36% )
```
* cache-misses反增了！！
Google Drive
Gist
Clipboard
Sign in with Wallet
