Try   HackMD

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

計算機組織與結構

  • 導讀 (務必先預習，否則第 4 章很難充分掌握)
  • 圖靈獎得主 David Patterson：摩爾定律終結，計算機體系結構正迎來下一個黃金時代 Page 249, Page 250
    • David Patterson: A New Golden Age for Computer Architecture: History, Challenges and Opportunities / video
    • 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

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

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

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

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

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

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

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

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

$ 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

練習題: 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，用來初始化一個變數用

  • 流程圖：

Created with Raphaël 2.2.0Initialzemainis main ended?Haltswitchvidx>5？defidx<0?mulyesnoyesnoyesno

解題方法

  • 走訪程式碼

    











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

隨堂練習

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

形式化驗證

tags: cs:app, csapp
Last changed by 
 
sysprog
System Software Programming
3
12360

Read more

KVM: Linux 虛擬化基礎建設

KVM (Kernel-based Virtual Machine) 是 Linux 核心提供的系統虛擬機器基礎建設，它是個 Linux 核心模組，能讓 Linux 系統成為一個 Type-2 Hypervisor 。KVM 透過硬體虛擬化支援 (Intel VT, AMD-V) 來提供 CPU 和記憶體虛擬化功能。藉由硬體虛擬化技術，客體作業系統 (Guest OS) 不必經由軟體模擬或轉換指令，即可高效率且安全地直接執行在硬體上。使用者空間的管理程式只要負責模擬週邊裝置、呼叫 KVM API ，即可建立並高效率地執行虛擬機器。 本講座將介紹 KVM 運作原理，並展示一個以 KVM 為基礎的精簡虛擬機器管理程式實作，它能在 x86-64 及 Arm64 平台上運作，提供基本的硬體周邊和 VirtIO 裝置，並可在其上執行 Linux 系統。

May 20, 2025
Linux 核心設計: 不僅是個執行單元的 Process

Linux 核心對於 UNIX Process (繁體中文翻譯為「行程」，簡體翻譯為「進程」) 的實作相當複雜，不僅蘊含歷史意義 (幾乎每個欄位都值得講古)，更是反映出資訊科技產業的變遷，核心程式碼的 task_struct 結構體更是一絕，廣泛涵蓋 process 狀態、處理器、檔案系統、signal 處理、底層追蹤機制等等資訊，更甚者，還很曖昧地保存著 thread (繁體中文翻譯為「執行緒」，簡體中文翻譯為「線程」) 的必要欄位，好似這兩者天生就脫不了干係。 本講座期望帶著聽眾得知 Linux 核心設計的特有思維，像是如何透過 LWP 和 NPTL 實作執行緒，又如何透過行程建立記憶體管理的一種抽象層，再者回顧行程間的 context switch 及排程機制，搭配 signal 處理 (千萬不要小看 kill，裡頭可是大有玄機!)。聽眾應可不至於迷失在茫茫程式碼大海中。

May 20, 2025
2025 年 Linux 核心設計課程期末專題

「Linux 核心設計」課程期末專題清單

May 20, 2025
並行程式設計: 概念

解說錄影: Part 1 / Part 2 / Part 3 / Part 4 / Part 5/ Part 6 / Part 7

May 18, 2025
Read more from sysprog
Published on HackMD