958 views
 owned this note
# B04: clz ###### tags: `sysprog2017` :::info 主講人: [jserv](http://wiki.csie.ncku.edu.tw/User/jserv) / 課程討論區: [2016 年系統軟體課程](https://www.facebook.com/groups/system.software2016/) :mega: 返回「[嵌入式作業系統設計與實作](http://wiki.csie.ncku.edu.tw/sysprog/schedule)」課程進度表 ::: ## 作業要求 * 閱讀 [重新理解數值](/s/Hy-pTh8Fl) 裡頭關於 count leading zero ([clz](https://en.wikipedia.org/wiki/Find_first_set#CLZ)) 的描述,設計實驗,比較 32-bit 數值對以下實做的效能差異: * recursive version * iteration version * binary search technique * byte-shift version * Harley's algorithm * 除了在 [重新理解數值](/s/Hy-pTh8Fl) 列出的程式,詳閱[劉亮谷的實驗紀錄](/s/BJBZn6Q6),予以重現並解釋個別實作的運作原理 * 解說影片: [Count Leading Zero](https://www.youtube.com/watch?v=DRkXFjLfaVg) [必看!] * 走訪全部的 32-bit 數值,用上述演算法帶入計算 clz 值,先驗證正確性,如果演算法不正確,試圖改正 * 在 GitHub 上 fork [clz-tests](https://github.com/sysprog21/clz-tests),以此為基礎進行以下調整 * 用 C99 或 C11 改寫程式碼,其中 C11 的 [_Generic](http://www.robertgamble.net/2012/01/c11-generic-selections.html) 非常好用,詳情可見 [你所不知道的 C 語言:前置處理器應用篇](https://hackmd.io/s/S1maxCXMl) * 比照 [phonebook](/s/rJYD4UPKe) 和 [compute-pi](/s/HkiJpDPtx),設計一套 benchmark suite,得以針對所有的 32-bit 數值進行個別 clz 實做效能的分析,並透過 gnuplot 製圖 * 要附上個別數值實際耗費時間,不能只列出平均值 * 提供落點分析圖,類似 [tcp-anaysis](https://upload.wikimedia.org/wikipedia/commons/6/65/Gnuplot_tcp_analysis.png) ([with-code](https://commons.wikimedia.org/wiki/File:Gnuplot_tcp_analysis.png)) * 為了避免編譯器最佳化的影響,務必指定編譯參數 `-O0` 來抑制最佳化 * 找至少 3 個案例,說明 clz 的應用場合 * 示範: [A Fast Hi Precision Fixed Point Divide](http://me.henri.net/fp-div.html) * 提示:透過 [Google Books](https://books.google.com/) 可以找到一些專門探討 optimization 的書籍,裡頭會有 clz 的應用 * 將你的觀察、上述要求的解說、應用場合探討,以及各式效能改善過程,善用 gnuplot 製圖,紀錄於「[作業區](/s/Hy2rieDYe)」 ## 截止日期 * Mar 4, 2017 (含) 之前 * 越早在 GitHub 上有動態、越早接受 code review,評分越高 ## 參考資料 :::warning 引用過往作業成果時,務必標註出處 (包含 GitHub 帳號或人名),連帶相關的超連結 ::: * [2016 年秋季班課程作業區](https://hackmd.io/s/H1B7-hGp): 提供錄影解說