# [CS:APP](https://hackmd.io/c/S1vGugaDQ/) 第 4 章重點提示和練習 ## 計算機組織與結構 * 導讀 (務必先預習,否則第 4 章很難充分掌握) * [黃婷婷教授的 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 原理和多核心議題, 虛擬機器設計與實作) * [圖靈獎得主 David Patterson:摩爾定律終結,計算機體系結構正迎來下一個黃金時代](https://36kr.com/p/5160657.html) ==Page 249==, ==Page 250== * 1965 年,作為 Intel 創始人之一的 [Gordon Moore](https://en.wikipedia.org/wiki/Gordon_Moore) 預言:價格不變時,半導體晶片中可容納的電晶體數目約每兩年會翻一倍,其效能也會同比提升。經過後來多年數據論證,這個時間週期實際在 18 個月上下 * 作為計算機架構宗師,David Patterson 曾帶領 UC Berkeley 團隊起草了精簡指令集 RISC-1,奠定 RISC 架構基礎,該架構後來被當時的巨頭 Sun Microsystems (後來被 Oracle收購) 選中用來製作 SPARC 處理器。2016 年從 UC Berkeley 退休後,David Patterson 以傑出工程師身份加入 Google Brain 團隊,為兩代 TPU 研發做出了卓越貢獻 * 2018 年 3 月 21 日,美國電腦協會(ACM)將 [2017 年圖靈獎](https://amturing.acm.org/) 授予史丹佛大學前校長 John L. Hennessy 和加州大學柏克萊分校退休教授 David A. Patterson,表彰他們開創了一種系統性、定量方法來設計和評價電腦架構,並對 RISC 微處理器工業產生持久的影響 * 每年生產超過 160 億個微處理器中有 99% 都是 RISC 處理器,幾乎所有智慧手機、平板電腦和數十億台組成 IoT 的內嵌式裝置都可以找到 * John L. Hennessy 教授為 MIPS 科技公司創始人、第 10 任史丹佛大學校長、Alphabet 公司董事長 * Hennessy 從 2004 年起便加入 Google(後來的 Alphabet 公司)董事會,並於 2007 年擔任獨立董事 * 1990 年代到 21 世紀初,計算機結構創新開始放緩...這帶來了兩個挑戰: * 效能提升減緩:單處理器的核心性能每年提升率已經下降到 3%; * 安全性問題:之前一直以軟體和系統來提升安全性而忽略對硬體安全性的把控,由於計算機結構的設計漏洞,Spectre 和 Meltdown 這類弱點也有了可乘之機; * 下一個黃金時代,在軟硬體協同設計、計算機結構安全性,以及晶片設計開發流程等方面都存在著創新機會: * 軟硬體協同設計:對於神經網絡、繪圖運算等需要高效能計算的領域,可以用專用體系結構和語言來提升晶片速度和性能; * 安全性:在防資訊洩露和 [side-channel attack](https://en.wikipedia.org/wiki/Side-channel_attack) 等安全性問題上,需要從架構角度著手改進; * 開放原始碼體系架構設計:對計算機架構進行開放原始碼的發展,特別是針對指令集架構; * 晶片開發流程: 用敏捷開發 (Agile Development) 的方式縮短晶片開發時間並降低成本,反覆以流片 (tape-out) 驗證有價值的晶片設計方案。 ## Y86-64 現代微處理器是人類創造的最複雜的系統之一。 ==Page 244== 一個處理器支持的指令和指令的編碼稱為它的指令集架構 (instruction-set architecture, ISA) Y86 每條指令的第一個位元組表明指令的類型,分為兩部分: * 高 4 位是運算子 (code) 部分 * 低 4 位是功能 (function) 部分 需要運算元 (operand) 的指令編碼更長一些,像是 `rmmovl %esp, 0x12345(%edx)` 的編碼 `0x40 0x42 0x45230100`,因為 `rmmovl` 指令第一個位元組是 0x40; 第二個位元組應是 `rArB` (r 代表來源的類型: r: 暫存器, m: 記憶體。這裡 r 是暫存器,而 A/B 代表目的類型),`%esp` 對應的數字為 4,`%edx` 對應的數字為 2,所以第二個位元組是 0x42。最後 4 個位元組是偏移量 `0x12345` 的編碼,首先補 0 填充為 4 個位元組: `00 01 23 45`, 然後反序插入:45230100。最後連起來就是 `404245230100`。 Y86 的特色: ==Page 245== * 15 個 64-bit 通用暫存器; * 指令地址暫存器,類似於 EIP,在 Y86 中稱為 PC;在 SEQ+ 時,沒有硬體暫存器來存放程式計數器 ==Page 289== * 地址從 0 開始的記憶體; * 狀態:正常運行、地址錯誤、指令錯誤、停機; * 3 個 Flags,分別對應 x86 中的 ZF, SF, OF,表示結果「為零」、「為負數」、「溢出」; Y86 指令執行流程: ==Page 264== * 取出指令 (fetch): 從記憶體讀取指令位元組,地址為程式計數器 (PC) 的值。它按順序方式計算目前指令的下一條指令的地址 valP (等於 PC 的值加上已取出指令的長度); * 解碼 (decode): 從暫存器檔案 (register file) 讀入最多兩個操作數; * 執行 (excute): 算術/邏輯單元要不執行指令的操作、計算記憶體存取的有效地址,要不增加或減少 stack pointer; * 記憶體存取 (memory): 將資料寫入記憶體,或從記憶體讀取出資料; * 寫回 (write back): 最多可寫入兩個結果到暫存器檔案; * 更新 PC(PC update): 將 PC 設定為下一道指令的地址; ![](https://i.imgur.com/VwyxcLJ.png) 硬體實作單元和上述處理階段的關聯: ==Page 272== 1. 取出指令: 將程式計數器暫存器作為地址,指令記憶體讀取指令的字節。PC 增加器 (PC incrementer) 計算 valP,也就是增加的程式計數器; 2. 解碼: 暫存器檔案有兩個資料輸入 A 和 B,同時讀入暫存器值 valA 和 valB; 3. 執行: 根據指令的類型,將算術/邏輯單元(ALU) 用於不同的目的; 4. 記憶體存取: 資料記憶體讀出或寫入一個記憶體單元; 5. 寫回: 暫存起檔案有兩個寫入方向: E 用來寫 ALU 計算出來的值,而 M 用來寫從資料記憶體中讀出的值; SEQ 的實作包括組合邏輯和兩種記憶體裝置: * 時鐘暫存器 (程式計數器和條件碼暫存器) * 隨機存取記憶體 (暫存器檔案、指令記憶體和資料記憶體) 組合邏輯不需要任何時序或控制 —— 只要輸入變化量,值就通過邏輯閘傳播。現有 4 個硬體單元需要對它們的時序進行明確的控制: * 程式計數器 * 條件碼暫存器 * 資料記憶體 * 暫存器檔案 這些單元通過一個時鐘信號來控制,它觸發將新值轉載到暫存器,並將值寫到隨機存取記憶體。每個時鐘週期,程式計數器都會裝載新的指令地址。只有在執行整數運算指令時,才會裝載條件碼寄存器。只有在執行 `rmmovl`, `pushl`, 或 `call` 指令時,才會寫入資料暫存器。根據下圖來理解處理器活動的時序控制: ![](https://i.imgur.com/NC7lnM0.png) 可看出,其實所有的狀態更新實際上同時發生,且只在時鐘上升開始下一個週期時,保證這個等價性的原則是:處理器從來不需要為了完成一條指令的執行而去讀由該指令更新了的狀態。換句話說,一個週期內 (其實一個週期就是一道指令的執行) 執行的指令所更新的資料不會成為該指令讀取的資料。 上圖中週期 3 通過組合邏輯算出了條件碼的新值: `000, %ebx` 的新值,及程式計數器的新值 (0x00e),但這些都是一個臨時狀態,是組合邏輯的出口值,在下一個週期開始的時候,也就是上升沿,把這些臨時的值更新到了相相應的暫存器中,開始下一個邏輯運算。 * 線上 [Y86-64 Simulator](https://boginw.github.io/js-y86-64/) (建議使用 Chrome 瀏覽器) * [支援的 ISA](https://github.com/boginw/js-y86-64/wiki/Instruction-set) * 取自 CS:APP 的 [y86_64-tools](https://github.com/sysprog21/y86_64-tools) ==Page 253== ```shell $ make $ cd misc $ make sum.yo $ ./yis sum.yo Stopped in 31 steps at PC = 0x13. Status 'HLT', CC Z=1 S=0 O=0 Changes to registers: %rax: 0x0000000000000000 0x0000000000000cba %rcx: 0x0000000000000000 0x0000000000000c00 %rbx: 0x0000000000000000 0x0000000000000008 %rsp: 0x0000000000000000 0x0000000000000200 Changes to memory: 0x01f0: 0x0000000000000000 0x000000000000005b 0x01f8: 0x0000000000000000 0x0000000000000013 ``` * Instruction Set Architecture (ISA): 取自 [CS 429: Computer Organization and Architecture](https://www.cs.utexas.edu/~byoung/cs429/syllabus429.html) * [Part I](https://www.cs.utexas.edu/~byoung/cs429/slides6-isa1.pdf) [Y86_64] ![](https://i.imgur.com/alNNn7O.png)</br> ==Page 264== SEQ = sequential 處理器, ==Page 250== exception</br> ![](https://i.imgur.com/hxt5Q7k.png)</br> ==Page 245== Y86-64 指令編碼和分類</br> ![](https://i.imgur.com/aqSYpDi.png) ![](https://i.imgur.com/ZGZ4aCY.png) [ Page 21 ] ```Clike start: xorq %rax, %rax mrmovq 0x100(%rax), %rbx mrmovq 0x200(%rax), %rcx rmmovq %rcx, 0x100 (%rax) rmmovq %rbx, 0x200 (%rax) halt ``` (注意最後一行要是 blank) ![](https://i.imgur.com/1RllwKi.png) Our program swaps the 8-byte values starting in memory locations 0x0100 (value A) and 0x0200 (value B). ![](https://i.imgur.com/Fvb3plS.png)</br> [Linus Torvalds 對於 cmov 指令的解說](https://yarchive.net/comp/linux/cmov.html) ==Page 294== [計算機有沒有對if語句的檢查進行優化?](https://www.zhihu.com/question/263995383) [Fast and slow if-statements: branch prediction in modern processors](http://igoro.com/archive/fast-and-slow-if-statements-branch-prediction-in-modern-processors/) [Conditional Moves for Branchless Math](http://assemblyrequired.crashworks.org/fcmp-conditional-moves-for-branchless-math/) [Binary Search *eliminates* Branch Mispredictions](https://www.pvk.ca/Blog/2012/07/03/binary-search-star-eliminates-star-branch-mispredictions/) [Why is it faster to process a sorted array than an unsorted array?](https://stackoverflow.com/questions/11227809/why-is-it-faster-to-process-a-sorted-array-than-an-unsorted-array)</br> ![](https://i.imgur.com/lUJiMKG.png) ![](https://i.imgur.com/upCKEoO.png)</br> * [Part II](https://www.cs.utexas.edu/~byoung/cs429/slides7-isa2.pdf) [X86]</br> ![](https://i.imgur.com/a06A43K.png) ![](https://i.imgur.com/CBhXLiT.png)</br> [Transmeta](https://en.wikipedia.org/wiki/Transmeta) 的早期股東包括 Sony、Gateway、已故微軟創辦人 Paul Allen 的創投公司 Vulcan 等等。Linus Torvalds 也曾任職於此公司 6 年。參見: [Linus,一生只為尋找歡笑](https://zhuanlan.zhihu.com/p/19796979)</br> ![](https://i.imgur.com/Or9GVGx.png) 為何有號數與無號數處理一樣呢?</br> ![](https://i.imgur.com/tMeSwc6.png) 最佳化輸出: 12 = 3 * 4</br> ![](https://i.imgur.com/xwWFSEh.png)</br></br> * [Part III](https://www.cs.utexas.edu/~byoung/cs429/slides8-isa3.pdf) ![](https://i.imgur.com/2oIDmjU.png) ![](https://i.imgur.com/PFzRrTZ.png) ![](https://i.imgur.com/vOu1AZi.png)</br></br> * [Part IV](https://www.cs.utexas.edu/~byoung/cs429/slides9-isa4.pdf) * [Part V](https://www.cs.utexas.edu/~byoung/cs429/slides10-isa5.pdf) * [Part VI](https://www.cs.utexas.edu/~byoung/cs429/slides11-isa6.pdf) [Structures and Alignment, Union Allocation] --- 練習題: `switch.c` 和 Y86-64 組合語言輸出 ```clike /* switch.c */ #include <stdio.h> long switchv(long idx) { long ret = 0; switch (idx) { case 0: ret = 0xaaa; break; case 2: case 5: ret = 0xbbb; break; case 3: ret = 0xccc; break; default: ret = 0xddd; } return ret; } int main() { long vals[8]; for (long i = 0; i < 8; i++) { vals[i] = switchv(i - 1); printf("idx = %ld, val = 0x%lx\n", i - 1, vals[i]); } return 0; } ``` 推測這段程式的作用是將 `swithv()` 中 印出 cases `-1` ~ `6`,並以 16 進位輸出,由於 `long` 型態 是 ==unsigned==,因此 assign 進去 vals 的值都皆為正數,而預期輸出結果應為: ``` idx = -1, val = 0xddd idx = 0, val = 0xaaa idx = 1, val = 0xddd idx = 2, val = 0xbbb idx = 3, val = 0xccc idx = 4, val = 0xddd idx = 5, val = 0xbbb idx = 6, val = 0xddd ``` * 背景知識補充: * $rsp 為 stack pointer register,指向 stack 的第一個位置(最高位置),並向下成長(由大到小) ,且須在一開始就設定好 * 有3個 Condition codes : ZF (Zero), SF (Negative), OF (Overflow),用來判斷==最近一次的算術或邏輯運算的情形==,若產生 Zero 則將 ZF 設為1,依此類推 * Branch Instructions 皆可以由 ZF, SF, OF 三者的邏輯運算進行判斷,簡易的判斷方法及為照指令上翻譯即可,如下: | Instruction | Meaning | Description | | :------: | ----------- | -------- | | JE | Jump If Equal | Jumps to `Dest` if `ZF` | | JNE | Jump If Not Equal | Jumps to `Dest` if `~ZF` | | JL | Jump If Less Than | Jumps to `Dest` if `SF^OF` | | JLE | Jump If Less or Equal | Jumps to `Dest` if `(SF^OF)|ZF` | | JG | Jump if Greater Than | Jumps to `Dest` if `~(SF^OF)&~ZF` | | JGE | Jump If Greater or Equal | Jumps to `Dest` if `~(SF^OF)` | | JMP | Uncondition | Jumps to `Dest` unconditionaly | * Common directive: * .pos x : 顯示程式開始於 address x * .align x : 將下行程式之 boundary 設定成 x-byte i.e. 以本題來說,long 需要 32 bits 及為 8 bytes 所以宣告 Array 時要 `.align 8` * .quad x : 將一個 8-byte x 值放入目前的 address,用來初始化一個變數用 * 流程圖: ```flow st=>start: Initialze e=>end: Halt op=>operation: main op2=>operation: switchv op3=>operation: def op4=>operation: mul op5=>operation: addr op6=>operation: table cond=>condition: idx>5? cond2=>condition: idx<0? cond3=>condition: %r10 == %rdi cond_end=>condition: is main ended? st->op->cond_end op2(right)->cond op3(left)->op2 cond_end(yes)->e cond_end(no,right)->op2 cond(yes)->op3 cond(no,right)->cond2 cond2(yes,left)->op3(bottom) cond2(no)->op4->cond3 cond3(yes)->op5 cond3(no)->op4(right)->op ``` ### 解題方法 * 走訪程式碼 ``` = /* switch.s */ .pos 0 irmovq stack, %rsp call main halt .align 8 array: .quad 0x0000000000000000 .quad 0x0000000000000000 .quad 0x0000000000000000 .quad 0x0000000000000000 ``` * `.pos 0` : 程式開始於 0 這個 address * `irmovq stack, %rsp` : 設定 stack 起始位置存於 %rsp 內 * `call main` : 跳到 main 的部份並將 return address `push` 到 `stack` 中 * `7-12` : 為進行 initialize array ``` assembly= main: irmovq array, %r10 irmovq $-1,%rdi call switchv rmmovq %rax, (%r10) irmovq $1,%rdi call switchv rmmovq %rax, 8(%r10) irmovq $3,%rdi call switchv rmmovq %rax, 16(%r10) irmovq $5,%rdi call switchv rmmovq %rax, 24(%r10) ret ``` * 這段為主程式,可以將其看作 4 個相似的部份,分別將 -1, 1, 3, 5 送入 `.swithv` 內進行運算 * `$r10` : 儲存 Array 第一個 component address * `$rdi` : 當作 arugment 傳入 swithv 中 * `$rax` : swithv 做完回傳值 * :::info 由於 $r10 是儲存 Array 第一個 address 的地方,第 6 行程式的 `rmmovq %rax, (%r10)` 是將值 store 到 Array 第一個位址,照這個程式邏輯去判斷,第一個位址應該要是存放 ==idx = -1== 之值,寫入到 %rdi 值的順序是 ==-1, 1, 3, 5== ::: * 接著進入 switchv 的部分 ```Clike= switchv: # contant irmovq $8, %r8 irmovq $0, %r10 irmovq $1, %r11 irmovq $0, %rax irmovq table, %rcx # table address rrmovq %rdi, %rdx ________ jg def # idx > 5 subq %r10, %rdi jl def # idx < 0 ``` :::info * 可推導得到上方缺少部分一定是要用目前儲存 idx 值的 register %rdi 或 %rdx 去減掉 %r8 (value = 8) * 但 subq 這個指令會將改掉 rB register 內的值,因 第11行 指令已經使用了 `%rdi` 因第 9 行就只能使用 ==subq %r8 %rdx== 去判斷是否 `%rdx > 8` * 若 idx > 8 或 idx < 0 都會跳到 def 內執行,由此可知 ==def 是進行超出邊界的處理== ::: * mul 的部分 ```Clike= mul: # calculate 8 * %rdi subq %r10, %rdi # %r10 = 0 je addr addq %r8, %rcx # %r8 = 8, %rcx = table address subq %r11, %rdi # %r11 = 1 jmp mul ``` * 利用判斷 %rdi 內的值是否等於0去將 ==%rcx = %rcx + 8 * %rdi== 得到的值可以去選取 table 內的值 * addr 部分 ```Clike addr: # jump using table address addq %r8, %rcx mrmovq (%rcx), %rdi pushq %rdi ret ``` * 將所取得到的 table address push 到 stack 內,並跳躍到指定的 table中 * table 之值 ```Clike= table: .quad LD # default branch .quad L0 # idx == 0 .quad L1 # idx == 1 .quad L2 # idx == 2 .quad L3 # idx == 3 .quad L4 # idx == 4 .quad L5 # idx == 5 ``` * 由此表可看出 table + 8 為 default branch(相當於 switch.c 中 switch 內 default 的部分),這也是為何在 addr 中要先將 %rcx+8 的原因 * 根據不同的位址,會跑到LD~L5中執行不同的運算,其中 L0-L5 就相當於 switch.c 中不同的 cases 一樣,將不同的值寫入 ==%rax== 中 * 最後跳回 main 時再將 %rax 內容存到對應的 Array address 中 * 最後看到 def 的挖空部分 ```Clike= def: # default branch irmovq table, %rcx ________ pushq %rdi ret ``` * 會進入到這邊的情況,都應該屬於 cases 中 default 的情形,包刮 <0 和 >8 * 因此從將 table 之 address load 進 %rcx,後面是 pushq %rdi 可推測,中間這個不分應該是要將 ==處理 default 的位置存到 %rdi 中== * 而 LD 位置為 &(%rcx) ,使用 ==mrmovq (%rcx), %rdi== 所以本題兩個答案應為: * `subq %r8 %rdx` * `mrmovq (%rcx), %rdi` 參考:[Introduction to X86-64 Assembly for Compiler Writers](https://www3.nd.edu/~dthain/courses/cse40243/fall2015/intel-intro.html) --- :::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) ::: ```clike void bubble_p(long *data, long count) { long *i, *last; for (last = data + count - 1; last > data; last--) { for (i = data; i < last; i++) { if (*(i + 1) < *i) { /* swap adjacent elements */ long t = *(i + 1); *(i + 1) = *i; *i = t; } } } } ``` 對應的 Y86-64 程式碼: ``` L4: mrmovq 8(%rax), %r9 mrmovq (%rax), %r10 rrmovq %r9, %r8 subq %r10, %r8 jge L3 rmmovq %r10, 8(%rax) rmmovq %r9, (%rax) ``` 50% jge is right, run 5 instructions; 50% jge is wrong, run 7 instructions and 2 nop bubble. so Cycles Per Loop is 50% * 5 + (7 + 2) * 50% = ==7== - [ ] ==4.48== 要求修改第 6 到 11 行,不使用跳躍,最多 3 次條件資料搬動 ``` L4: mrmovq 8(%rax), %r9 mrmovq (%rax), %r10 rrmovq %r9, %r8 subq %r10, %r8 cmovl %r9, %r11 cmovl %r10, %r9 cmovl %r11, %r10 rmmovq %r9, 8(%rax) rmmovq %r10, (%rax) ``` Cycles Per Loop is ==9== - [ ] ==4.49== 要求修改第 6 到 11 行,不使用跳躍,最多 1 次條件資料搬動 ``` L4: mrmovq 8(%rax), %r9 mrmovq (%rax), %r10 rrmovq %r9, %r8 rrmovq %r10, %r11 xorq %r9, %r10 subq %r11, %r8 cmovge %r11, %r9 xorq %r10, %r9 xorq %r9, %r10 rmmovq %r9, 8(%rax) rmmovq %r10, (%rax) ``` Cycles Per Loop is ==11== --- ## Datapath * [Part 1](https://www.cs.utexas.edu/~byoung/cs429/slides12-datapath1.pdf) ![](https://i.imgur.com/eB3BVCk.png) ==Page 272== ~ ==Page 274== * Stages * Fetch: Read instruction from instruction memory. * Decode: Read program registers * Execute: Compute value or address * Memory: Read or write back data. * Write Back: Write program registers. * PC: Update the program counter. ![](https://i.imgur.com/VnEGrlM.png) ![](https://i.imgur.com/VtbmzNc.png) * [Part 2](https://www.cs.utexas.edu/~byoung/cs429/slides13-datapath2.pdf) ![](https://i.imgur.com/SROkXyd.png) ![](https://i.imgur.com/3LaRZJA.png) ![](https://i.imgur.com/3FxmI2F.png) ==Page274== ~ ==Page 277== ## Pipeline * [Part 1](https://www.cs.utexas.edu/~byoung/cs429/slides14-pipeline1.pdf) * [Part 2](https://www.cs.utexas.edu/~byoung/cs429/slides15-pipeline2.pdf) * [Part 3](https://www.cs.utexas.edu/~byoung/cs429/slides16-pipeline3.pdf) Page `282` - `288` pipeline hazard: Page 295 有 3 種: - Structural Hazard * 由於部份功能單元沒有管線化,或是所需之資源沒有複製足夠多份,使 CPU 無法支援某些次序指令的執行。 - Control Hazard * 發生在會修改 Program Counter 的指令(Jump/Branch/else) 是最影響效能的 Hazard * 解決方法有 4 種: 1. flush the pipeline 2. branch predict taken 3. branch predict not taken 4. delayed branch. - Data Hazard --- ## 形式化驗證 * 共筆: [形式化驗證](https://hackmd.io/s/H1xxp3pF0) * video: [形式化驗證: 第 1 集](https://www.youtube.com/watch?v=CvIsM5-d8Nw) ###### tags: `cs:app`, `csapp`