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
12153

Read more

留意浮點數運算的陷阱

科學、工程與統計等領域往往離不開浮點數的運用，因此，如何趨吉避凶，正是每位經常處理浮點數的程式開發者應具備的基本素養。儘管妥善運用浮點數是門深奧的學問，學校課程中對此著墨不多，頂多在數值方法這門課中略有涉及，其涵蓋的廣度與深度皆有限。本文探討操作浮點數的基本觀念，不涉及理論分析，並使用直覺的詞彙，刻意避開過於嚴謹或艱澀的定義，以降低理解門檻，閱讀本文所需的預備知識僅限於基礎的程式設計概念，例如單精度與倍精度浮點數的表示方式，預期多數讀者皆可順利閱讀。

Mar 29, 2025
位元旋轉實作和 Linux 核心案例

針對 2021 年暑期「Linux 核心」課程先決測驗題的測驗 $\alpha$ 共筆貢獻者: jserv, ekangmonyet, ChinYikMing, henrybear327, dmefs, JingWangTW, mickey30606, tanchihpin0517, ccs100203, RinHizakura, st9540808, yian02, 2011eric, alan23273850 位元旋轉 位元旋轉 (bitwise rotation 或 bit rotation) 的操作展示如下圖: 位元旋轉也稱為循環移位運算 (circular shift operation)，其作用是移動位元，但不捨棄位元或增加位元。分二種操作: 循環右移運算 (向右旋轉): 向右移動每個位元一個位置，最右邊的位元被循環成為最左邊的位元

Mar 29, 2025
圖解傅立葉分析

傅立葉 (Fourier) 分析不僅是個數學工具，更是種徹底顛覆一個人以前世界觀的思維模式。但不幸的是，傅立葉分析的公式看起來太複雜，很多人囫圇吞棗，並對它深惡痛絕。這麼有意思的東西居然成了大學裡的殺手課程，因此，筆者希望撰寫科普文章來解釋傅立葉分析，甚至讓高中生也能看懂，體會到藉由傅立葉分析看到世界的另一個樣貌。對於已有一定數理基礎的朋友，細讀後也會有新的發現。

Mar 29, 2025
你所不知道的 C 語言: 浮點數運算

工程領域往往是一系列的取捨結果，浮點數更是如此，在軟體開發有太多失誤案例源自工程人員對浮點數運算的掌握不足，本議程希望藉由探討真實世界的血淋淋案例，帶著學員思考 IEEE 754 規格和相關軟硬體考量點，除了關注浮點數原理，我們也會用 C 程式來操作浮點數內部，並談及定點數運算。最後也會探討在深度學習領域為了改善資料處理效率，而引入的 BFloat16 這樣的新標準。

Mar 29, 2025
Read more from sysprog
Published on HackMD