CS:APP 第 4 章重點提示和練習

計算機組織與結構

導讀 (務必先預習，否則第 4 章很難充分掌握)
- 黃婷婷教授的 Computer Architecture 課程材料和重點提示 (NOTE)
- Modern Microprocessors (A 90-Minute Guide!) 重點提示和解說
- 現代處理器設計 (原理和關鍵特徵, cache 原理和多核心議題, 虛擬機器設計與實作)
圖靈獎得主 David Patterson：摩爾定律終結，計算機體系結構正迎來下一個黃金時代 Page 249, Page 250
- David Patterson: A New Golden Age for Computer Architecture: History, Challenges and Opportunities / video
  - Article, note
  - From Mainframe CPUs to Neural-Network TPUs and Open RISC-V
- 1965 年，作為 Intel 創始人之一的 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 年圖靈獎授予史丹佛大學前校長 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 等安全性問題上，需要從架構角度著手改進；
  - 開放原始碼體系架構設計：對計算機架構進行開放原始碼的發展，特別是針對指令集架構；
  - 晶片開發流程: 用敏捷開發 (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) 讀入最多兩個操作數;
執行 (execute): 算術/邏輯單元要不執行指令的操作、計算記憶體存取的有效地址，要不增加或減少 stack pointer;
記憶體存取 (memory): 將資料寫入記憶體，或從記憶體讀取出資料;
寫回 (write back): 最多可寫入兩個結果到暫存器檔案;
更新 PC(PC update): 將 PC 設定為下一道指令的地址;

硬體實作單元和上述處理階段的關聯: Page 272

取出指令: 將程式計數器暫存器作為地址，指令記憶體讀取指令的字節。PC 增加器 (PC incrementer) 計算 valP，也就是增加的程式計數器;
解碼: 暫存器檔案有兩個資料輸入 A 和 B，同時讀入暫存器值 valA 和 valB;
執行: 根據指令的類型，將算術/邏輯單元(ALU) 用於不同的目的;
記憶體存取: 資料記憶體讀出或寫入一個記憶體單元;
寫回: 暫存器檔案有兩個寫入方向: E 用來寫 ALU 計算出來的值，而 M 用來寫從資料記憶體中讀出的值;

SEQ 的實作包括組合邏輯和兩種記憶體裝置：

時鐘暫存器 (程式計數器和條件碼暫存器)
隨機存取記憶體 (暫存器檔案、指令記憶體和資料記憶體)

組合邏輯不需要任何時序或控制 —— 只要輸入變化量，值就通過邏輯閘傳播。現有 4 個硬體單元需要對它們的時序進行明確的控制:

程式計數器
條件碼暫存器
資料記憶體
暫存器檔案

這些單元通過一個時鐘信號來控制，它觸發將新值轉載到暫存器，並將值寫到隨機存取記憶體。每個時鐘週期，程式計數器都會裝載新的指令地址。只有在執行整數運算指令時，才會裝載條件碼暫存器。只有在執行 rmmovl, pushl, 或 call 指令時，才會寫入資料暫存器。根據下圖來理解處理器活動的時序控制：

可看出，其實所有的狀態更新實際上同時發生，且只在時鐘上升開始下一個週期時，保證這個等價性的原則是：處理器從來不需要為了完成一條指令的執行而去讀由該指令更新了的狀態。換句話說，一個週期內 (其實一個週期就是一道指令的執行) 執行的指令所更新的資料不會成為該指令讀取的資料。

上圖中週期 3 通過組合邏輯算出了條件碼的新值: 000, ％ebx 的新值，及程式計數器的新值 (0x00e)，但這些都是一個臨時狀態，是組合邏輯的出口值，在下一個週期開始的時候，也就是上升沿，把這些臨時的值更新到了相應的暫存器中，開始下一個邏輯運算。

線上 Y86-64 Simulator (建議使用 Chrome 瀏覽器)
- 支援的 ISA
取自 CS:APP 的 y86_64-tools Page 253

$ 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
- Part I [Y86_64]
  
  Page 264 SEQ = sequential 處理器, Page 250 exception
  
  Page 245 Y86-64 指令編碼和分類
  
  [ Page 21 ]
```
start:
    xorq %rax, %rax
    mrmovq 0x100(%rax), %rbx
    mrmovq 0x200(%rax), %rcx
    rmmovq %rcx, 0x100 (%rax)
    rmmovq %rbx, 0x200 (%rax)
    halt
```
(注意最後一行要是 blank)

Our program swaps the 8-byte values starting in memory locations 0x0100 (value A) and 0x0200 (value B).

Linus Torvalds 對於 cmov 指令的解說 Page 294
計算機有沒有對if語句的檢查進行優化？
Fast and slow if-statements: branch prediction in modern processors
Conditional Moves for Branchless Math
Binary Search eliminates Branch Mispredictions
Why is it faster to process a sorted array than an unsorted array?
- Part II [X86]
  
  Transmeta 的早期股東包括 Sony、Gateway、已故微軟創辦人 Paul Allen 的創投公司 Vulcan 等等。Linus Torvalds 也曾任職於此公司 6 年。參見: Linus，一生只為尋找歡笑
  
  為何有號數與無號數處理一樣呢？
  
  最佳化輸出: 12 = 3 * 4
- Part III
- Part IV
- Part V
- Part VI [Structures and Alignment, Union Allocation]

練習題: switch.c 和 Y86-64 組合語言輸出

/* 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;
}

推測這段程式的作用是將 switchv() 中印出 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)
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，用來初始化一個變數用
流程圖：

解題方法

走訪程式碼












/* 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



















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 送入 .switchv 內進行運算
$r10 : 儲存 Array 第一個 component address
$rdi : 當作 argument 傳入 switchv 中
$rax : switchv 做完回傳值
由於 $r10 是儲存 Array 第一個 address 的地方，第 6 行程式的 rmmovq %rax, (%r10) 是將值 store 到 Array 第一個位址，照這個程式邏輯去判斷，第一個位址應該要是存放 idx = -1 之值，寫入到 %rdi 值的順序是 -1, 1, 3, 5
接著進入 switchv 的部分












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

可推導得到上方缺少部分一定是要用目前儲存 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 的部分

 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 部分

addr: # jump using table address
	addq %r8, %rcx
	mrmovq (%rcx), %rdi
	pushq %rdi
	ret

將所取得到的 table address push 到 stack 內，並跳躍到指定的 table中
table 之值

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 的挖空部分

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

隨堂練習

4.47: 以 C 語言指標改寫原本使用陣列表示法的氣泡排序程式碼 (Page 327) / 延伸題目: 最佳化 / Analysis on Bubble Sort Algorithm Optimization

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

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.
Part 2

Page274 ~ Page 277

Pipeline

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

形式化驗證

共筆: 形式化驗證
video: 形式化驗證: 第 1 集

CS:APP 第 4 章重點提示和練習

計算機組織與結構

Y86-64

解題方法

Datapath

Pipeline

形式化驗證

tags: cs:app, csapp

Read more

圖解傅立葉分析

Linux 核心設計: RCU 同步機制

Linux 核心設計: Scheduler(9): Deadline Scheduling

並行程式設計: Atomics 操作

tags: `cs:app`, `csapp`