Amdahl 定律與並行主題 (Amdahl's Law & Concurrency Themes)

Overview Table

1.9.1 Amdahl's Law(p.58-60)

Gene Amdahl 的觀察:加速系統的某一部分時,對整體效能的影響同時取決於「該部分佔多重」與「加速多少」。設原始執行時間為 $T_{old}$,某部分佔整體時間比例 $\alpha$(0 ≤ α ≤ 1),該部分被加速 k 倍,則:

整體加速比 (speedup) $S=T_{old}/T_{new}$:

• 書中例子:α = 0.6、k = 3 → $S=1/[0.4+0.6/3]=1.67\times$。即使對佔 60% 的主要部分做 3 倍加速,整體只有 1.67 倍。
• 核心洞見:要顯著加速整個系統,必須改善整體中非常大比例的部分;電腦領域常見 2× 以上的效能改進,只能靠優化系統的大部分達成 (p.60)。

極限情形:k → ∞(Equation 1.2)

把某部分加速到耗時趨近於零 ($k=\mathrm{\infty }$),加速比仍有上限:

• 例:加速 60% 的部分到「幾乎不花時間」,整體加速仍只有 $1/0.4=2.5\times$。
• 未被加速的 (1−α) 部分是不可逾越的瓶頸。

時間軸示意 (α = 0.6, 加速部分 → 0):

T_old:  |■■■■■■■■■■■■ α=0.6 ■■■■■■■■■■■■|▓▓▓▓▓ 1-α=0.4 ▓▓▓▓▓|
                    ↓ k = ∞(該段時間 → 0)
T_new:  |▓▓▓▓▓ 1-α=0.4 ▓▓▓▓▓|          ← 剩下這段砍不掉

S∞ = T_old / T_new = 1 / 0.4 = 2.5×  ← 上限(天花板)

Practice Problems 對應的計算模式(p.58-59, 解答 p.64)

1.9.2 Concurrency 與 Parallelism(p.60-62)

驅動電腦進步的兩個恆常需求:做更多 (do more) 與 跑更快 (run faster)。兩者都靠處理器「同時做更多事」改善。

• Concurrency(並行/並發):一般性概念,指系統中存在多個同時進行的活動。
• Parallelism(平行):利用 concurrency 讓系統跑更快。平行可在多個抽象層次上開發,由高到低有三層:

抽象層次(高 → 低)
┌─────────────────────────────────────────────┐
│ Thread-Level Concurrency    (多處理器/多執行緒) │  ← 建立在 process 抽象之上
├─────────────────────────────────────────────┤
│ Instruction-Level Parallelism (pipelining/    │  ← 每週期執行多條指令
│                               superscalar)    │
├─────────────────────────────────────────────┤
│ SIMD Parallelism            (單指令多資料)     │  ← 一條指令做多個運算
└─────────────────────────────────────────────┘

Thread-Level Concurrency(p.60-62)

建立在 process 抽象之上,多個程式同時執行;threads 更讓單一 process 內有多條控制流。自 1960 年代初 time-sharing 以來即有支援,但傳統上只是模擬的並行——單一處理器在多個行程間快速切換(如雜耍者拋接多顆球)。

• Uniprocessor system:單一處理器靠切換模擬並行。
• Multiprocessor system:多個處理器由單一 OS kernel 控制;1980 年代即用於大型計算,因 multi-core 與 hyperthreading 而普及。

Figure 1.16 處理器分類 (p.60)

              All processors
              ┌────────────────────────────┐
              │            ┌─────────────────────────┐
              │            │  Multiprocessors        │
              │ ┌────────┐ │ ┌───────┐ ┌───────────┐ │
              │ │  Uni-  │ │ │ Multi-│ │  Hyper-   │ │
              │ │processors│ │ core  │ │ threaded  │ │
              │ └────────┘ │ └───────┘ └───────────┘ │
              │            └─────────────────────────┘
              └────────────────────────────┘

Multi-core processor(Figure 1.17, p.61):多個 CPU(稱為 cores)整合在單一 IC 晶片上。每個 core 有自己的 L1 與 L2 cache,L1 又分成 i-cache(指令)與 d-cache(資料);所有 cores 共用 L3 cache 與主記憶體介面。業界預期單晶片將達數十甚至數百核。

Figure 1.17 四核處理器組織 (p.61)

Processor package
┌───────────────────────────────────────────────┐
│  Core 0                        Core 3          │
│ ┌────────────┐               ┌────────────┐    │
│ │    Regs    │               │    Regs    │    │
│ │ ┌───┐┌───┐ │      ...      │ ┌───┐┌───┐ │    │
│ │ │L1 ││L1 │ │               │ │L1 ││L1 │ │    │
│ │ │d-c││i-c│ │               │ │d-c││i-c│ │    │
│ │ └───┘└───┘ │               │ └───┘└───┘ │    │
│ │ L2 unified │               │ L2 unified │    │
│ └────────────┘               └────────────┘    │
│ ┌───────────────────────────────────────────┐ │
│ │     L3 unified cache (shared by all cores)│ │
│ └───────────────────────────────────────────┘ │
└───────────────────────┬───────────────────────┘
                        │
                 ┌──────┴──────┐
                 │ Main memory │
                 └─────────────┘

Hyperthreading(又稱 simultaneous multi-threading):讓單一 CPU 執行多條控制流。

• 硬體上:部分元件有多份(program counter、register file),部分只有單份(如浮點運算單元)。
• 傳統處理器切換 thread 需約 20,000 clock cycles;hyperthreaded 處理器逐週期 (cycle-by-cycle) 決定執行哪個 thread。
• 好處:某 thread 等待資料載入 cache 時,CPU 可先執行另一個 thread,更充分利用運算資源。
• 例:Intel Core i7 每核可執行 2 threads → 四核系統可平行執行 8 threads。

Multiprocessing 改善效能的兩種方式(p.61-62):

1. 減少執行多工時「模擬並行」的需要。
2. 讓單一應用程式跑更快——但前提是該程式以多執行緒方式撰寫且能有效平行執行。詳見 12-Concurrent-Programming/02-Threads。

Instruction-Level Parallelism(p.62)

更低的抽象層次:現代處理器可同時執行多條指令。

• 早期微處理器(如 1978 年 Intel 8086)執行一條指令需 3–10 個 clock cycles;近代處理器可持續達 每週期 2–4 條指令。
• 單一指令從頭到尾可能需 20 cycles 以上,但處理器用各種技巧同時處理多達 100 條指令。
• Pipelining(第 4 章):把執行指令所需的動作切成不同步驟,硬體組織成一連串 stages,各 stage 平行運作、處理不同指令的不同部分;簡單設計即可逼近 1 instruction/cycle。見 04-Processor-Architecture/04-Pipelining-Principles。
• Superscalar processors:可持續超過 1 instruction/cycle 的處理器;現代處理器多屬此類。第 5 章的高階模型讓程式設計師理解並提高程式的 instruction-level parallelism。見 05-Program-Optimization/02-Modern-Processor-Operation。

SIMD Parallelism(p.62)

最低層次:single-instruction, multiple-data (SIMD) ——一條指令引發多個平行運算。

• 例:近代 Intel/AMD 處理器有指令可平行加 8 對單精度浮點數(C 的 float)。
• 主要用途:加速影像、聲音、視訊處理的應用。
• 有些編譯器嘗試從 C 程式自動抽取 SIMD 平行,但更可靠的方法是使用編譯器(如 gcc)支援的 vector data types 撰寫程式(Web Aside opt:simd)。

1.9.3 抽象 (Abstractions) 的重要性(p.62-63)

抽象是資訊科學最重要的概念之一。良好程式設計實務的一環是為一組函式制定簡單的 API,讓使用者不必深入內部運作;不同語言提供不同形式的抽象支援(Java class 宣告、C function prototypes)。

Figure 1.18 電腦系統提供的抽象層 (p.63)

                    Virtual machine ──────────────────────────┐
                          Processes ──────────────┐           │
   Instruction set                                │           │
     architecture ───┐        Virtual memory ──┐  │           │
                     │                         │  │  Files ─┐ │
   ┌──────────────┬──┴────────┬────────────────┴──┼─────────┴─┼──┐
   │  Operating   │ Processor │  Main memory      │ I/O devices  │
   │  system      │           │                   │              │
   └──────────────┴───────────┴───────────────────┴──────────────┘
   (抽象 → 被抽象的實體)

• 處理器側:Instruction Set Architecture (ISA) 抽象化實際處理器硬體——機器碼程式表現得彷彿一次只執行一條指令;底層硬體實際上平行執行多條指令,但始終與簡單的循序模型一致。維持相同執行模型,使不同處理器實作能執行相同機器碼,同時提供不同的成本/效能組合。
• 作業系統側已介紹三種抽象:files 抽象化 I/O 裝置、virtual memory 抽象化程式記憶體、processes 抽象化執行中的程式(見 01-Computer-Systems-Tour/03-OS-Abstractions-and-Networks)。
• 新增第四種:virtual machine——抽象化整台電腦(含 OS、處理器、程式)。由 IBM 於 1960 年代提出,近年因需在同一機器上執行多種 OS(Windows、Mac OS X、Linux)或同一 OS 的不同版本而再度重要。

1.10 Summary(p.63-64)

第 1 章總結,對應各主題筆記:

• 電腦系統 = 硬體 + 系統軟體合作執行應用程式;資訊以 bits 群組表示,意義取決於 context;程式從 ASCII 文字經 compiler 與 linker 翻譯為二進位可執行檔(見 01-Computer-Systems-Tour/01-Information-and-Program-Translation)。
• 處理器讀取並解譯存於主記憶體的二進位指令;因電腦大部分時間都在記憶體、I/O 裝置、CPU registers 之間搬移資料,儲存裝置排成階層 (hierarchy):CPU registers → 多層 cache → DRAM 主記憶體 → 磁碟。越高層越快、每 bit 越貴;高層裝置作為低層裝置的 cache。理解並利用記憶體階層可優化 C 程式效能(見 06-Memory-Hierarchy/02-Locality-and-Memory-Hierarchy)。
• OS kernel 是應用程式與硬體的中介,提供三大抽象:(1) files 抽象 I/O 裝置;(2) virtual memory 抽象主記憶體與磁碟;(3) processes 抽象處理器、主記憶體與 I/O 裝置。
• 網路讓系統彼此通訊;從單一系統的觀點,網路只是另一種 I/O 裝置。

Bibliographic Notes(p.64):Ritchie 關於 C 與 Unix 早期歷史的第一手記述;Ritchie & Thompson 的首篇 Unix 論文;Silberschatz 等人的 Unix 各流派歷史;GNU、Linux 網站與線上 Posix 標準。

Exam/Test Patterns

Related Notes

• 01-Computer-Systems-Tour/01-Information-and-Program-Translation
• 01-Computer-Systems-Tour/02-Hardware-Organization-and-Program-Execution
• 01-Computer-Systems-Tour/03-OS-Abstractions-and-Networks
• 01-Computer-Systems-Tour/Practice-Computer-Systems-Tour
• 04-Processor-Architecture/04-Pipelining-Principles
• 05-Program-Optimization/02-Modern-Processor-Operation
• 05-Program-Optimization/03-Loop-Unrolling-and-Parallelism
• 06-Memory-Hierarchy/02-Locality-and-Memory-Hierarchy
• 12-Concurrent-Programming/02-Threads
• 12-Concurrent-Programming/04-Parallelism-and-Thread-Safety