1753 views
 owned this note
# 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 :::