# 2017 年春季班第一次分組表
:::info
主講人: [jserv](http://wiki.csie.ncku.edu.tw/User/jserv) / 課程討論區: [2017 年系統軟體課程](https://www.facebook.com/groups/system.software2017/search/?query=week5)
:mega: 返回「[作業系統設計與實作](http://wiki.csie.ncku.edu.tw/sysprog/schedule)」課程進度表
:::
## Policy
* 選修課程的學生 **2 人**[color=red] 一組
* 日後會依據作業和報告份量調整分組
* 旁聽的學生可自由選擇加入 **既有的** 組別
* 旁聽學生的標注方式為「括號後方緊接著`#`」，如 ==`lonely (梅仁耀)#`==
* 每週更新共筆並準備進度報告影片
* 授課教師跟學生一同分組，也是每週做報告
* 示範: [春季班分組和工作清單](https://embedded2016.hackpad.com/2016-c9i9qW6eGpb)

## 分組名單 (GitHub 帳號 + 中文姓名; 中間用「空白」區隔)

---

### Team 1
- [ ]yangyang95 (翁瑞陽)
- [ ]changyuanhua (張圜華)
* Task: 比照 [B06: software-pipelining](https://hackmd.io/s/rks62p1sl) 要求，需要善用 perf stat 的 raw counter 命令。
* [開發紀錄(software-pipelining)](https://hackmd.io/s/S1fZ1m6pe) / [github](https://github.com/yangyang95/prefetcher) / [youtube](https://youtu.be/xTYonYcB4N0) (13min)
:::info
參照到 Wikipedia 時，一律用英文版本; 缺乏足夠的效能分析; 錄影字體太小，應該先切換到瀏覽器的 fullscreen 模式;
[May 2] 洽詢 champ 學長
:::

### Team 2
- [ ]tina0405 (許雅雯)
- [ ]heathcliffYang (楊惟晶)
* Task: 比照 [B08: mergesort-concurrent](https://hackmd.io/s/B1xV_p_jl) 要求，引入 [concurrent-ll](https://github.com/jserv/concurrent-ll) (concurrent linked-list 實作) 製圖分析 scalability，探討原有的 linked list + thread pool 設計缺失和 lock-free 演算法設計。
* [開發紀錄(mergesort-concurrent)](https://hackmd.io/s/S1Zrwcopx) / [github](https://github.com/heathcliffYang/mergesort-concurrent) / [youtube](https://www.youtube.com/watch?v=f_BuLTfwJZQ&list=PLAp9YQsljMlHoYIhL51426GTsvHrR0iFg)
:::info
注意螢幕字體，目前過小; 注意音量的一致性;
錄影分段過多，請用合併;
Part 3 / 1:30: memory 的台灣慣用翻譯是「記憶體」，不是「內存」;
Part 7 / 1:03: atomics 描述不精確;
Part 8 / 1:12: full barrier 為何？
Part 8 / 3:19: 如何解釋 add 的時間成本？
:::

### Team 3
- [ ]jack81306 (林宸慶)
- [ ]peterting (丁榮主)
* Task: 比照 [B09: microarch](https://hackmd.io/s/r1Olsp_og)，不只解題更要闡述相關的背景知識，探討各項限制中，如何開發對應的程式碼。
* [開發紀錄(microarch)](https://hackmd.io/s/SJCDl8mAl) / [github]() / [youtube](https://www.youtube.com/watch?v=Y8j8cek9WEs) (20min)
:::info
避免使用 bandicam，多用開放原始碼解決方案; data flow
[May 2] 移轉到 Team 10
:::

### Team 4
- [ ]ierosodin (許耕福)
- [ ]stanleytazi (蔡玉倫)#
- [ ]refleex (李孟儒)
* Task: 比照 [B07: phonebook-concurrent](https://hackmd.io/s/rkOExTOoe) 要求，分析 SuperMalloc 對於多執行緒程式的效能影響，延續 [針對多執行緒環境設計的 Memory allocator](https://hackmd.io/s/HkICAjeJg)。
* [開發紀錄(SuperMalloc)](https://hackmd.io/s/S1X1it3Tl) / [github](https://github.com/ierosodin/phonebook-concurrent.git) / [youtube](https://www.youtube.com/watch?v=fqxJP83R_S8&list=PLYcd6-bJ96RtxT-JzfHssQiZwulF3DevM&index=1)

### Team 5
- [ ]zhanyangch (陳展揚)
- [ ]hunng (郭泓梃)
* Task: 比照 [B02: raytracing](https://hackmd.io/s/HyuBWDwYl) 要求，以 SIMD 改善 math-toolkit.h 定義的若干數學操作函式，進而推廣到整個光線追蹤的演算法 (可在不影響正確性的前提下，將原本的實作替換)。
* [開發紀錄(raytracing)](https://hackmd.io/s/HkifAKiae#) / [github](https://github.com/zhanyangch/raytracing-1) / [youtube](https://www.youtube.com/watch?v=WEK_3FlDB1U) (12min)
:::info
顯示效果佳，程式碼請繼續
[May 2] ==new task==: 參考 Joshua Barczak 的 [SIMD Raytracing 實作](http://www.joshbarczak.com/blog/?p=787)，改寫原有的程式碼，但是 model 應該和 [B02: raytracing](https://hackmd.io/s/HyuBWDwYl) 一致
:::

### Team 6
- [ ] vtim9907 (徐偉庭)
- [ ] henry0929016816(林彥亨)
* Task: 比照 [B10: matrix](https://hackmd.io/s/rkrrpHm2e) 要求，需要一併考慮 data alignment 議題、留意記憶體存取機制 (避免 leak 和錯誤操作，善用 [AddressSanitizer](https://github.com/google/sanitizers))。
* [開發紀錄(matrix)](https://hackmd.io/s/r11wlGWRe) / [github]() / [youtube](https://www.youtube.com/watch?v=OqU6PJHtZ4c&t=9s) (21 min) / [youtube2](https://www.youtube.com/watch?v=wp7RvK_A7uI) (26 min)
:::info
錄影字體太小，應該先切換到瀏覽器的 fullscreen 模式;
4:35: 延伸閱讀 [Data Alignment](http://www.gamasutra.com/view/feature/3942/data_alignment_part_1.php?print=1)
5:45: 執行 `gdb` 時，加上 `-q` 參數以抑制冗長的授權聲明輸出;
10:53: 如何解釋程式執行結果？
25:58: data alignment 的衝擊為何？
[May 2] ==new task==: 擴充 [MathEX](https://github.com/jserv/MathEX)，設計高效能的數學表示式運算器，參考 [muparserSSE - A Math Expression Compiler](http://beltoforion.de/article.php?a=muparsersse&p=implementation)
:::

### Team 7
- [ ] zmke (柯宗銘）
- [ ] petermouse (林軒毅)
- [ ] 0xff07 (林有容)#
* Task: Task: 比照 [B08: mergesort-concurrent](https://hackmd.io/s/B1xV_p_jl) 要求，研究 thread pool 管理 worker thread 的實做，引入 lock-free 演算法。參考 [A Pragmatic Implementation of Non-Blocking Linked-Lists](https://www.cl.cam.ac.uk/research/srg/netos/papers/2001-caslists.pdf)
* [開發紀錄(mergesort-concurrent)](https://hackmd.io/s/BkZnq2gAg#) / [github](https://github.com/zmke/mergesort-concurrent) / [youtube](https://youtu.be/_YgoaNHSzmU) (6 min)/ [youtube 2](https://youtu.be/9UMsqhpohQA) (10 min)
:::info
2:47 補上 tqueue_{push,pop} 的實作示意圖; 4:47 描述整合時期所遇到的問題時，應一併探討如何修改 (patch); 缺乏效能分析
5:48: 是否考慮到 ABA problem?
[May 2] 併入 Team 2
:::

### Team 8
- [ ] Cayonliow (廖其忻)
- [ ] king1224 (洪正皇)
- [ ] csielee (李東霖)#
* Task: 比照 [B07: phonebook-concurrent](https://hackmd.io/s/rkOExTOoe) 要求，實作出刪除 (remove) 特定資料的功能，並且分析 concurrent insert/delete 對效能的影響。留意 race condition 和正確性議題。
* [開發紀錄(phonebook-concurrent)](https://hackmd.io/s/BycMwEs6l) / [github](https://github.com/sysprog2017team8/phonebook-concurrent) / [youtube](https://www.youtube.com/watch?v=yPdjzWUlizk) (11 min) / [youtube 2](https://www.youtube.com/watch?v=F9hKspTdSQ0&feature=youtu.be) (5 min)
:::info
改用 GraphViz 製圖; 08:51 刪除的時間計算不精準/不正確;
理工人不要隨便說「好像」;
0:5 是 "concurrent"，不是 "concurrency";
3:59: 時間刻度改為 ms，不要用 sec;
4:09: 用統計模型來表示 `append` 的時間成本;
4:39: 需要更好的正確性檢驗機制;
[May 2] 移轉到 Team 4
:::

### Team 9
- [ ] donbader(馮禹德)
- [ ] yanang(陳彥安)
* Task: 比照 [B03: compute-pi](https://hackmd.io/s/HkiJpDPtx) 要求，特別留意測量時間的機制 (Wall-clock time vs. CPU time)
* [開發紀錄(compute-pi)](https://hackmd.io/s/r1aZMZa6e#) / [github](https://github.com/donbader/compute-pi) / [youtube](https://youtu.be/2o8dcBGWUQk) (18min)
:::info
錄影字體太小，應該先切換到瀏覽器的 fullscreen 模式; 程式碼列表的字體也過小; ns 中文翻譯是「奈秒」;
[May 2] 併入 Team 5
:::

### Team 10
- [ ] laochanlam(劉俊林)
- [ ] etc276(洪得揚)
* Task: 延伸 [B04: clz](https://hackmd.io/s/ry1u0uDFg) 要求，探討 [carryless multiplication](https://bitmath.blogspot.tw/2013/05/carryless-multiplicative-inverse.html) 演算法和實作 (需要考慮到 Intel 延伸指令集)，介紹密碼學的應用
* [開發紀錄(clz)](https://hackmd.io/s/HkQfalnpe) / [github](https://github.com/laochanlam/AES-GCM) / [youtube](https://www.youtube.com/watch?v=UWXQd6eD38E) (17min)
:::info
錄影的字體太小, 注意 Galois 的發音;
需要考慮數值分佈
:::

### Team 11
- [ ] illusion030(李泓哲)
- [ ] ryanwang522(王韻華)
* Task: 比照 [B07: phonebook-concurrent](https://hackmd.io/s/rkOExTOoe) 要求，嘗試重構 (refactor) 給定的程式碼，使得程式更容易閱讀和維護。不只是在共筆上用文字提出良性詳盡的批評，也該反映在程式碼的變革
* [開發紀錄(phonebook-concurrent)](https://hackmd.io/s/rk5dwXmAx) / [github](https://github.com/ryanwang522/phonebook-concurrent) / [youtube](https://youtu.be/gB8pyki8SnE) (15 min) [ youtube2](https://youtu.be/iznlSoQG4kE) (13min)
:::info
避免用雙欄 (both) 模式，改用全螢幕瀏覽; 畫面偶有閃爍; 程式碼呈現用白底黑字; 重構前應該全面指出既有問題;
使用 Visual Studio Core 很潮!
2:01: 學習 Linux 核心 [list_for_each_entry](https://stackoverflow.com/questions/15754236/how-do-i-use-the-list-for-each-macro-in-list-h-from-the-linux-kernel-properly) 的技巧;
3:20: `localPtr` 的命名過於累贅;
3:41: 需要說明如何分離 interface 和 implementation，以及後續如何做 polymorphism;
4:47: `findLastName` 和 `removeByLastName` 命名不夠簡潔，只要能找到明確的人名，就可用 `remove` 移除，搜尋方法可能很多種 (如透過 regex [regular expression]); `checkAPI` 的存在是否必要？
5:29: `optProvider` 的命名不直覺;
5:39: 個別 phonebook 實作無可避免伴隨著各自的 structure，該如何用一致的 interface 去操作？
6:02: 與其用編譯時期挑選實作，不如在執行時期。還能因此設計更好的 benchmark suite;
6:39: `main` 函式應該簡化，將呼叫 interface 對應實作和效能比較的部分獨立出來;
6:57: 同前面討論，這部分的 abstraction 設計不佳;
8:53: 共用的程式碼如 _Generic 的處理，應該獨立出新的檔案;
9:52: 檔名和 build rules 應調整，將可共用的程式名稱放到 `SRCS_common`，個別的 phonebook 實作可用 `impl_naive.c`, `impl_hash.c`, `impl_mempool.c` 去區分;
10:49: 如何追蹤已配置的資源 (resources) 呢？該如何避免 leak 或者 shared memory 沒釋放的狀況？
:::

### Team 12
- [ ] baimao8437(石碩亨)
- [ ] xdennisx(徐銘宏)
* Task: 比照 [B08: mergesort-concurrent](https://hackmd.io/s/B1xV_p_jl) 要求，分析 mutex contention，引入更多工具 (如 ThreadSanitizer) 以理解原有程式的問題
* [開發紀錄(mergesort-concurrent)](https://hackmd.io/s/BkI3vnS0l) / [github](https://github.com/baimao8437/mergesort-concurrent) / [youtube](https://youtu.be/lmZVWZ-fQgA) (8 min)
:::info
編譯時應加上 `-g` 選項; 減少使用 Sublime 這類私有軟體，多用開放原始碼解決方案; 缺乏更深入的效能分析 (lock contention)
[May 2] ==new task==: 延續上學期 [MapReduce](https://hackmd.io/s/Hkb-lXkyg) 的成果，強化效能和應用案例
:::

### Team 13
- [ ] twzjwang (王贊鈞)
- [ ] rayleigh0407 (戴子祐)
* Task: 比照 [B10: matrix](https://hackmd.io/s/rkrrpHm2e) 要求，完整實作多種加速矩陣乘法的演算法，伴隨相關的 SIMD 改善機制
* [開發紀錄(matrix)](https://hackmd.io/s/BkTL8nWRl) / [github](https://github.com/twzjwang/matrix_oo) / [youtube](https://www.youtube.com/watch?v=EmDuuLygwHY) (10 min) / [youtube2](https://www.youtube.com/watch?v=RRUW3Az_KIw) (6 min)
:::info
YouTube 網址用較短的版本，如 `youtube.com/watch?v=EmDuuLygwHY`;
螢幕字體太小，請調整;
用軟體去除背景噪音，如 [Audacity](http://www.audacityteam.org/);
5:17: 在工程中，如何控制 error rate 並取捨呢？
[May 2] 移轉到 Team 6
:::

### Team 14
- [ ] hugikun999 (何俊逸)
- [ ] claaaaassic (黃經典)
- [ ] Weinux (黃士瑋)#
* Task: 比照 [B01: phonebook](https://hackmd.io/s/rJYD4UPKe)，支援 fuzzy search，允許搜尋 lastName 時，不用精準打出正確的寫法。指出原有 dataset 的問題 (需要有工程分析，拿出統計學) 並改進。
* [開發紀錄(phonebook)](https://hackmd.io/IbAc4MwJgRgWlAdgMYDY4BYao3ARsDKHMHgMzJ4Cs1qiApgCZA==) / [github](https://github.com/claaaaassic/phonebook) / [youtube 1](https://www.youtube.com/watch?v=1gwdjOkMNdk) / [youtube 2](https://youtu.be/SLcDNShJijc) / [youtube 3](https://youtu.be/a7B4QSA41Hw)
:::info
螢幕字體太小，請調整;
用軟體去除背景噪音，如 [Audacity](http://www.audacityteam.org/);
合併影片;
Part 1 / 8:44: 如何避免 sequential access 呢？能否透過多執行緒加速？又，如果資料是會持續變動 (考慮到 enqueue 和 dequeue)，該如何調整？
13:08: 在多執行緒環境中，如何透過 lock-free memory pool 來改善操作？參考: [How to write a thread-safe and efficient, lock-free memory allocator in C?](https://stackoverflow.com/questions/1995871/how-to-write-a-thread-safe-and-efficient-lock-free-memory-allocator-in-c) 和 [Allocating Memory in a Lock-Free Manne](http://www.cse.chalmers.se/~tsigas/papers/Allocating%20Memory%20in%20a%20Lock-Free%20Manner%20-%20ESA05.pdf)
13:30: fuzzy 音標拼音: [f'ʌzi];
18:30: 預期達到怎樣的效果呢？如何整合呢？
Part 2 / 3:40: 考慮到 first_name 和 last_name 的組合，該怎樣設計有效的資料結構呢？
Part 3 / 2:14: 命名方式應調整; `djb2`
Part 3 / 3:48: 為何不用 Part 2 的資料來測試;
[May 2] 合併到 Team 11
:::

### Team 15
- [ ] chenweiii (魏禛)
- [ ] Sean1127 (鄭宇軒)
- [ ] paul5566 (陳柏霖)#
- [ ] Lukechin (呂科進)#
* Task: 研讀 [Toward Concurrency](https://hackmd.io/s/Skh_AaVix)，整理和修正內容描述 (伴隨更多程式範例)
* [開發紀錄(Toward Concurrency 2.0)](https://hackmd.io/s/Sy1x0XiAe)
:::info
[May 2] 合併到 Team 12
:::