893 views
 owned this note
# CS:APP 學習指引 (1) ## [CS:APP3e](http://csapp.cs.cmu.edu/) 簡介 [CS:APP3e](http://csapp.cs.cmu.edu/) 全名為 Computer Systems: A Programmer's Perspective,是 CMU 的計算機概論的教材 (難度相當於台灣的大學研究所),該書的簡體中文翻譯名稱為《深入理解計算機系統》。    在電腦科學領域中,80/20 原則依然適用,程式開發者平時用到的超過九成的電腦知識基本來自於這些電腦科學核心課程中的不到一成的內容,至於剩下的九成內容,雖然不至於沒用,然而它們沒有大用,至少,它們不會對你造成什麽損害。舉例來說,你可以不知道 [DMA 的原理](https://en.wikipedia.org/wiki/DMA),不知道 [(E)BNF 表示法](https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_form),你依然可以撰寫出堪用的程式碼;但若你連記憶體配置或是同步臨界區都搞不清楚的話,那就尷尬了,要不然你就會在為什麽不能初始化一個大小為 16MB 的區域變數這樣的問題上糾結半天,或者是對著多執行緒裡頭變幻莫測的全域變數百思不得其解。 CMU 兩位教授及 CSAPP 這本書背後的貢獻者著實了不起,他們非常巧妙的把程式設計及優化、數位電路基礎、指令集架構、組合語言、儲存裝置、連結器與載入器、行程、虛擬記憶體等等自各不同的學科的核心知識點攪和在一起,並以程式開發者的視角呈現,所以這本書的書名叫 "A programmer's perspective"。    這本書的簡介(引言)部分簡介明了:一個簡單的 Hello World 程式在電腦上的執行過程,前置處理器 `->` 編譯 `->` 組譯 `->` 連結 `->` 產生可執行的目標檔案 `->` 載入到記憶體 `->` 資料流 (stream) `->` 螢幕輸出顯示,沒有一句廢話。 指令集和計算機結構這一章,兩位作者為了讓讀者更好的理解指令集 (Intel x86),別具一格的搞出了一個簡化版的 Y86 指令集,並用其表示基本的運算和控制,甚至連數位電路的 HCL 都來了一筆。資料處理流程、數位邏輯和流水線,圖示 + 詳細的講解,一目了然。 儲存架構的內容的關鍵就是 locality,只有了解電腦的梯形儲存架構,才能體會到為什麽同樣邏輯的程式會產生如此之大的性能差距,雖然電腦設計者的初衷是把記憶體儲存裝置視作一個巨型陣列。然而這個巨大的陣列的不同區段差異極大。 ## 學習方式 搭配 [15-213/18-213/15-513: Intro to Computer Systems](http://www.cs.cmu.edu/~213/schedule.html) (目前 2017 Fall) 的投影片和錄影 (YouTube 可開字幕) :::info 1. 以下頁面以簡體中文《深入理解計算機系統》為主 2. 下方隨堂練習請在檢討後,於 11 月 25 日前,將完整作答和討論的共筆發信到 `<jserv.tw@gmail.com>`,標題是 `[sysprog] 你的姓名` (中間有空格) ::: ## 數值系統 * [重新理解數值](https://hackmd.io/s/BkRKhQGae) * Bits, Bytes, & Integers * [第一部分錄影](https://youtu.be/wb2u59QF2iY) * [第二部分錄影](https://youtu.be/cGjjDea7i8g) * 對應 CS:APP3e 的第 2 章: 2.3 整數運算 (==Page 60==) :::info - [ ] 練習題 2.30: `tadd_ok` (==Page 65==) ```C #include <stdbool.h> bool tadd_ok(int x, int y) { int sum = x + y; bool over_neg = (x < 0) && (y < 0) && (sum >= 0); bool over_pos = (x >= 0) && (y >= 0) && (sum < 0); return (!over_neg) && (!over_pos); } ``` ::: * Floating Point: [錄影](https://www.youtube.com/watch?v=cvE39UfP74Q) * 對應 CS:APP3e 的第 2 章: 2.4.2 IEEE 浮點數表示 (==Page 78==), 2.4.5 浮點運算 (==Page 85==) :::success 隨堂練習 - [ ] 2.58: 撰寫函式 `is_little_endian`,在 Little endian 機器上返回 `1`,反之返回 `0`,應能在任意機器、無論幾位元的架構都適用 (==Page 88==) - [ ] 2.66: 撰寫函式 `leftmost_one`,產生得以找出數值 x 最高位 `1` 的位元遮罩 (==Page 90==) - [ ] 2.92: 撰寫函式 `float_negate`,給定浮點數 `f`,回傳 `-f`,倘若 `f` 是 $NaN$,直接回傳 `f`。輸入數值範圍為有效的 2^32^ 個數值 (==Page 96==) ::: ## 計算機組織與結構 * [Computer Architecture](https://hackmd.io/s/H1sZHv4R) ([NOTE](https://hackmd.io/s/rkloHgHcx)) * [Modern Microprocessors (A 90-Minute Guide!) 重點提示和解說](https://hackmd.io/s/Hk2CscGcl) * [現代處理器設計](http://hackfoldr.org/cpu) (原理和關鍵特徵, cache 原理和多核心議題, 虛擬機器設計與實作) * 對應 CS:APP3e 的第 4 章, 第 6 章 :::success 隨堂練習 - [ ] 4.47: 以 C 語言指標改寫原本使用陣列表示法的氣泡排序程式碼 (==Page 327==) / 延伸題目: [最佳化](https://en.wikipedia.org/wiki/Bubble_sort#Optimizing_bubble_sort) / [Analysis on Bubble Sort Algorithm Optimization](http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=5635119) ::: * The Memory Hierarchy: [錄影](https://www.youtube.com/watch?v=vusQa4pfTFU) * 對應 CS:APP3e 的第 6 章: 6.3 儲存裝置的階層架構 (==Page 421==) * Cache Memories: [錄影](https://youtu.be/Spg7iTYLkS4) * 對應 CS:APP3e 的第 6 章: 6.4 快取記憶體 (==Page 425==) :::success 隨堂練習 - [ ] 6.37: 計算 `N=64` 和 `N=60` 的 cache miss rate (==Page 455==) - [ ] 6.45: 撰寫更快的轉置矩陣實作 (==Page 45==) - [ ] 6.46: 有向圖轉換為無向圖 (==Page 45==) / 參考: [Graph](http://www.csie.ntnu.edu.tw/~u91029/Graph.html), [相鄰矩陣 (Adjacency Matrix))](https://hellolynn.hpd.io/2017/09/22/%E5%AF%A6%E4%BD%9Cgraph%E8%88%87dfs%E3%80%81bfs%E8%B5%B0%E8%A8%AA/) :::