# 21 世紀的系統軟體 ###### tags: `sysprog` :::info 主講人: [jserv](http://wiki.csie.ncku.edu.tw/User/jserv) / 課程討論區: [2017 年系統軟體課程](https://www.facebook.com/groups/system.software2017/) :mega: 返回「[進階電腦系統理論與實作](http://wiki.csie.ncku.edu.tw/sysprog/schedule)」課程進度表 ::: ## 有所變,有所不變 * 1980 年代的電腦廣告: [IMSAI 8080](https://en.wikipedia.org/wiki/IMSAI_8080) ![](https://hackpad-attachments.s3.amazonaws.com/embedded2015.hackpad.com_xDmCCv0k00K_p.299401_1446127674000_computer.jpg) * source: [twitter](https://twitter.com/HistoryInPics/status/552536619849613312) * USD $5995 (而且是 35 年前的物價!) 只能買到 8-bit 微處理器,搭配 64 KB 主記憶體和 10 MB 硬碟。有趣的是,當時軟體開發的模式部分還延續至今 * 硬體突飛猛進,軟體的問題依舊還在 ## Maslow’s pyramid of code review ![](https://hackpad-attachments.s3.amazonaws.com/embedded2015.hackpad.com_xDmCCv0k00K_p.299401_1446087965957_code-revew.png) * 21 世紀的軟體開發均已規模化,絕非「有就好」,而是持續演化和重構,code review 是免不了的訓練 * uber 工程師 Charles-Axel Dein 認為好的程式碼應該要: * [ Correct ] : 做到預期的行為了嗎?能夠處理各式邊際狀況嗎?即便其他人修改程式碼後,主體的行為仍符合預期嗎? * [ Secure ] : 面對各式輸入條件或攻擊,程式仍可正確運作嗎? * [ Readable ] : 程式碼易於理解和維護嗎? * [ Elegant ] : 程式碼夠「美」嗎?可以簡潔又清晰地解決問題嗎? * [ Altruist ] : 除了滿足現有的狀況,軟體在日後能夠重用嗎?甚至能夠抽離一部分元件,給其他專案使用嗎? * 「需求」層次: 正確 → 安全 → 可讀 → 優雅 → 利他 * @[Chaoint](https://twitter.com/Chaoint) : 「沒關係」總是講給自己聽的。 * 「人們不敘述自己的過往,而是為自己的過往作證。」—— Frantz Fanon * 「如果你把游泳池當作浴缸泡著,再泡幾年還是不會游泳」 -- jserv 延伸閱讀: [Code Reading](https://en.wikipedia.org/wiki/Code_Reading) * 大量篇幅回顧 C 語言概念,以及在真實世界中的程式如何展現,細節! ## 什麼叫做簡潔? ![](https://hackpad-attachments.s3.amazonaws.com/embedded2015.hackpad.com_xDmCCv0k00K_p.299401_1446123262319_math.jpg) 尤拉猜想是 Euler 在 1769 年對費馬定理的延伸: n 個正整數的 k 次方的總和,若是另一個正整數的 k 次方,則 n 不可能小於 k。n = 2 就是費馬最後定理,不過這個猜想在 1966 年被號稱「最短論文」給否定。 延伸閱讀: * [美麗的錯誤--猜想的真與假](http://www.mathland.idv.tw/fun/erroneous.htm) * [邏輯思維:費馬大定理](https://www.youtube.com/watch?v=7nORW4edSaI) (YouTube) ## 「事實」很容易被遮蔽,所以我們要 Benchmark / Profiling ![](https://hackpad-attachments.s3.amazonaws.com/embedded2015.hackpad.com_xDmCCv0k00K_p.299401_1446124062219_truth.jpg) source: [twitter](https://twitter.com/Harvey1966/status/624099087466500096) ## 《[進擊的鼓手](https://en.wikipedia.org/wiki/Whiplash_(2014_film))》之後 ![](https://hackpad-attachments.s3.amazonaws.com/embedded2015.hackpad.com_xDmCCv0k00K_p.299401_1446103470188_pain.png) "No pain, no gain" source: [CSAIL at MIT twitter](https://twitter.com/MIT_CSAIL/status/614140774620332032/photo/1) ## 運算模式的巨變 [ [source](https://www.facebook.com/shihhaohung/posts/995419510500537) ] * 早年計算能力相對低的年代,常常有用查表法代替計算,有空間換取時間的做法,來增進效能。... 那個時候 個人電腦的 CPU 可以在一個時脈週期中讀取一筆資料,但是要做乘法計算則需要幾十個時脈週期,所以用查表的比較快。除法和超越函數更是如此,而現在還有一些低階的處理器,還在用這些技巧。 * 後來當 CPU 時脈提高,但記憶體存取相對變慢的時候,我們必須反過來減少記憶體存取的次數,所以高階處理器 cache 越來越大,做 data prefetch 來提早取得資料、使用 multi-threaded architecture 來容忍資料遲到的狀況、使用壓縮的方式傳送資料,甚至還會用 speculation 的方式來猜測資料是在哪裡和是什麼。 * 在多處理機和多核心電腦上,存取資料的問題更嚴重,除了時間延遲和頻寬之外,還要考慮到尖峰時刻塞車的問題,所以有時候簡單的工作,就可能就不分工了,要不就由一個 CPU 代表去做,做完把結果給大家,要不就大家都做同樣的事情。前者多半在有共享記憶體的多核心處理器上看到,後者多半在分散式的系統看到。 * 到了異質計算的年代,CPU 和 GPU 的分工,更需要好好地做效能分析。因為傳統 GPU 和 CPU 不共享記憶體,透過較慢的 PCIe Bus 交換資料,所以有些工作 CPU 自己做比較快。另一方面,當 GPU 有超過 2000 個核心的時候,用重複的計算 (redundant computation)取代資料交換,也是常見的事。 * [HSA](http://www.hsafoundation.com/) * 更進一步談巨量資料,為了節省資料的取得時間,我們往往費盡心思。我們花時間將資料和計算擺在同一個地方,做所謂的 data computation co-location,將重複出現的資料利用 data deduplication 技術節省儲存空間和取得時間,用一堆目錄 (indexing) 讓資料可以快速被找到。 * 當計算機結構有所不同時,優化的策略可能會隨之而變,不能食古不化。但原理雖然簡單,系統和實作技巧卻越來越複雜,軟硬體優化的機會越來越多,可惜能夠真正連通理論和實務的人則越來越少。 * 以上這些技術,講起來很容易,但在實作上,必須先搞清楚運算和資料的相對位置、距離、時間先後、相依性、數量等等,才知道該如何取捨。但很多人根本不會用效能分析工具,就在那邊瞎子摸象,隨便亂講,這時候要解決問題,就需要瞎貓遇到死耗子的運氣。 * i586 和 i686 看起來指令相似,但本質不同! * 從 i686 (Pentium Pro) 開始,底層已經是 RISC 架構 * 因為現在計算機結構改變很大,即便把程式用組合語言重寫,效能也不見得比 Compiler 產生的還好 * 效能的問題在存取資料本身 * 組合語言會快,是因為你分析過程式要怎樣寫才可以比較快 * 直接照著程式碼的邏輯改寫組合語言不見得比較好 * [Bloom Filter](http://www.evanlin.com/BloomFilter/) * 處理大型資料的時候,往往需要一個索引可以快速的找到資料.這樣的索引就被成為 filter * 針對要搜尋一個數字的位址或是是否存在,簡單的方式就是每一個都找過一次,這樣下去的時間複雜度就是 `O(n)`。也有一個比較快的方式就是將所有的數字變成一個陣列,然後該數字存在就將其紀錄為 `1` 的 (Mapping Table) 方式,這樣的時間複雜度就會優化為 `O(1)`,但是空間複雜度就會變成 `n` * 是否存在一種資料結構能夠兼具 `O(1)` 的時間複雜度,但是又不需要有 `n` 的空間複雜度的 Filter 呢? * Bloom Filter 是個提供 `O(1)` 搜尋時間複雜度的手法 * [Bloom filter calculator](https://hur.st/bloomfilter) * [hyperloglog](https://en.wikipedia.org/wiki/HyperLogLog) * 使用 1.5k 表達 10 億筆資料 * [Python implementation of Hyperloglog, redis, fuzzy hashing for malware detection](https://bigsnarf.wordpress.com/2013/03/16/python-implementation-of-hyperloglog-redis-fuzzy-hashing-for-malware-detection/) ## Deep Learning 背後的資訊建設 * video: [GTC CHINA: AI, Deep Learning with Jen-Hsun Huang & Baidu's Andrew Ng](https://www.youtube.com/watch?v=mJvTAWsYiSI) * Nvidia 將未來 GPU 的發展聚焦在 AI 上 (更確切地說, 聚焦在 Deep Learning 上), 影片中間也請到 Andrew Ng 介紹百度的 AI 研究 * [做別人不喜歡做的事,為 AI 革命鳴槍的 NVIDIA 創辦人黃仁勳](http://www.bnext.com.tw/article/view/id/41045) * [Andrew Ng (吳恩達)](http://www.andrewng.org/) * [Coursera: 機器學習](https://zh-tw.coursera.org/learn/machine-learning) * [你以為NVIDIA只是畫了個餅,其實他早已布好了整個局](http://mp.weixin.qq.com/s?__biz=MzAwODY4Njg2OA%3D%3D&mid=2652006436&idx=1&sn=24f117b7bf0b0e186f210ffdf4160467)