108 年 國立中正大學資訊工程學系碩士班《計算機概論》

Quicksort 是一種基於分治策略（Divide and Conquer）的排序演算法。

(a) Quicksort 的工作原理：
Quicksort 的核心思想是「分割」（Partition）和「遞歸」（Recursion）。

1. 選擇基準點 (Pivot)：從要排序的數列中選擇一個元素作為基準點。選擇基準點的方法有很多種，例如：選擇第一個元素、最後一個元素、中間元素，或者隨機選擇一個元素，甚至可以採取「三數取中法」（median-of-three）來選擇。
2. 分割 (Partition)：重新排列數列，使得所有小於基準點的元素都位於基準點的左側，所有大於基準點的元素都位於基準點的右側。等於基準點的元素可以放在任一邊。這個過程完成後，基準點就位於它最終排序後的位置。
3. 遞歸 (Recursion)：對基準點左側的子數列和右側的子數列分別遞歸地應用 Quicksort 演算法，直到子數列的大小為 0 或 1，此時數列即已排序完成。

常見的 Partition 實作方式（例如 Hoare's partition scheme 或 Lomuto's partition scheme）：
以 Lomuto's partition scheme 為例，假設我們選擇數列的最後一個元素作為 pivot：

• 維護一個指標 i，代表最後一個小於或等於 pivot 的元素的下標。初始化 i 為起始下標減一。
• 遍歷數列中從起始下標到倒數第二個元素（不包含 pivot）。
• 如果當前元素小於或等於 pivot，則將 i 加一，並交換當前元素與 i 指向的元素。
• 遍歷結束後，將 pivot 與 i+1 指向的元素交換。此時，i+1 就是 pivot 的最終位置。

(b) 時間複雜度分析：

• 最壞情況時間複雜度 (Worst Case Time Complexity)：

TCP (Transmission Control Protocol) 透過多種擁塞控制策略來避免網路擁塞，維持資料傳輸的穩定性。擁塞窗口 (Congestion Window, CWND) 和慢啟動 (Slow Start) 是其中兩個基本機制。

(a) 擁塞窗口 (Congestion Window, CWND)：
擁塞窗口是 TCP 發送端維護的一個參數，它限制了在任何時刻，發送端可以發送但尚未收到接收端確認 (Acknowledgement, ACK) 的資料量。CWND 的大小會根據網路的擁塞程度動態調整。

• 目的：防止發送端以過快的速率發送資料，導致網路路由器或接收端不堪負荷而發生封包遺失。
• 機制：
  • 當網路狀況良好（例如，連續收到 ACK，表示封包未遺失），CWND 會逐漸增大，以提高傳輸速率。
  • 當偵測到網路擁塞（例如，發生封包遺失，通常是透過收到逾時重傳的 ACK 或重複的 ACK 來判斷），CWND 會顯著減小，以降低發送速率，緩解網路壓力。
• 與接收窗口 (Receive Window, RWND) 的關係：TCP 的實際發送窗口是 CWND 和 RWND 中較小者，即 Send Window = min(CWND, RWND)。RWND 是接收端緩衝區大小決定的，而 CWND 則由發送端根據網路狀況決定。

(b) 慢啟動 (Slow Start)：
慢啟動是 TCP 擁塞控制演算法中的一個階段，用於在連接建立初期或在偵測到網路擁塞後，逐步探測網路的可用頻寬，避免一開始就以高速率衝擊網路。

計算一個正整數 $n$ 的階乘 ($n!$)，即 $n! = 1 \times 2 \times 3 \times \dots \times n$。此問題可以使用遞迴 (Recursion) 的方式來定義。

遞迴函數的設計需要考慮兩個關鍵要素：

1. 基本情況 (Base Case)：這是遞迴停止的條件，必須是可直接計算的。
2. 遞迴步驟 (Recursive Step)：將問題分解成一個或多個規模較小的相同問題，並將其結果組合起來。

對於階乘函數，其遞迴定義如下：

• 基本情況：

  • $0! = 1$
  • $1! = 1$
    在實際應用中，通常會以 $0! = 1$ 或 $1! = 1$ 作為基本情況。如果題目限定為「正整數 $n$」，則 $1! = 1$ 是最直接的基本情況。

• 遞迴步驟：
  對於任何大於 1 的正整數 $n$，其階乘可以表示為 $n! = n \times (n-1)!$。
  這意味著，計算 $n!$ 的問題可以轉化為計算 $(n-1)!$ 的問題，然後將結果乘以 $n$。

基於上述定義，我們可以設計一個遞迴函數。以下是用 C 語言風格的偽碼表示：

這是一個關於全連接神經網路（Fully-Connected Neural Network）的前向傳播計算問題，涉及到神經網路的結構、計算公式以及程式實現。

神經網路結構：

• 輸入層 (Layer 1)：256 個節點。
• 隱藏層 (Layer 2, 3, 4)：各 16 個節點。
• 輸出層 (Layer 5)：10 個節點。

層與層之間的連接：

• Layer 1 -> Layer 2: 256 個節點到 16 個節點。
• Layer 2 -> Layer 3: 16 個節點到 16 個節點。
• Layer 3 -> Layer 4: 16 個節點到 16 個節點。
• Layer 4 -> Layer 5: 16 個節點到 10 個節點。

計算公式：

• 隱藏層 (i = 2, 3, 4)：
  $x_{i,j} = \max\left(\sum_{k=0}^{N-1} x_{i-1,k} \times W_{i,j,k} + b_{i,j}, 0\right)$
  其中：

  • $x_{i,j}$ 是第 $i$ 層第 $j$ 個神經元的輸出。
  • $x_{i-1,k}$ 是前一層（第 $i-1$ 層）第 $k$ 個節點的輸出。
  • $W_{i,j,k}$ 是連接前一層第 $k$ 個節點到當前層第 $j$ 個神經點的權重。
  • $b_{i,j}$ 是第 $i$ 層第 $j$ 個神經點的偏差值 (bias)。
  • $N$ 是前一層的節點數。
    • 對於 $i=2$ (Layer 1 to Layer 2)，$N=256$。
    • 對於 $i=3$ (Layer 2 to Layer 3)，$N=16$。
    • 對於 $i=4$ (Layer 3 to Layer 4)，$N=16$。
  • $\max(\cdot, 0)$ 表示 ReLU 激活函數。

• 輸出層 (Layer 5, i = 5)：
  $x_{5,j} = \sum_{k=0}^{15} x_{4,k} \times W_{5,j,k} + b_{5,j}$
  其中：

  • $x_{5,j}$ 是輸出層第 $j$ 個節點的輸出。
  • $x_{4,k}$ 是前一層（Layer 4）第 $k$ 個節點的輸出。
  • $W_{5,j,k}$ 是連接 Layer 4 第 $k$ 個節點到輸出層第 $j$ 個節點的權重。
  • $b_{5,j}$ 是輸出層第 $j$ 個節點的偏差值。
  • 此層不使用 ReLU 激活函數。

(a) C 程式撰寫：
我們需要編寫一個 C 程式來模擬這個神經網路的前向傳播。程式需要讀取 256 個輸入值，並根據網路結構和計算公式，計算出 10 個輸出值。由於輸入是 unsigned char，權重和偏差是單精度浮點數，計算過程應使用浮點數。

這是一個關於快取記憶體 (Cache Memory) 的問題，特別是應用在神經網路權重管理的情境。題目要求我們分析直接映射快取 (Direct-Mapped Cache) 的相關儲存需求、命中率與錯失類型，並提出改善方案。

問題背景回顧：

• 神經網路權重總數 (來自 Problem 4)：4768 個權重。
• 權重儲存：每個權重是單精度浮點數 (4 bytes)。
• 要求使用 1 KByte (1024 bytes) 的 SRAM 作為快取。
• 快取組織：直接映射快取。
• 每個快取區塊 (Cache Block) 大小：32 bytes。
• 權重實際儲存在外部記憶體 (Off-chip)。

計算權重總大小：
權重總數 = 4768 個。
每個權重大小 = 4 bytes。
總權重資料大小 = $4768 \times 4$ bytes = 19072 bytes。

分析快取參數：

• 快取總容量 (Cache Size) = 1 KB = 1024 bytes。
• 區塊大小 (Block Size) = 32 bytes。
• 區塊數量 (Number of Blocks)：
  快取總容量 / 區塊大小 = 1024 bytes / 32 bytes = 32 個區塊。

(a) 除了 1 KByte SRAM 外，額外需要的 on-chip 儲存。
直接映射快取 (Direct-Mapped Cache) 的結構包含三個部分：

1. Data Block: 儲存實際的資料（權重）。這部分由 SRAM 承擔，容量為 1024 bytes。
2. Tag: 每個區塊都需要一個 Tag 來識別它所對應的外部記憶體位址。
3. Index: 用來決定該區塊在快取中的位置。在直接映射中，Index 直接由位址的某部分決定，它決定了「哪個」區塊可以放在「哪個」快取槽位。

在直接映射快取中，由於有 32 個快取區塊，我們需要 32 個 Tag。
每個 Tag 的大小取決於外部記憶體的位址空間。我們需要知道外部記憶體有多少位址線 (Address Lines)。
外部記憶體總大小是 19072 bytes (所有權重)。
假設我們需要能定址到這 19072 bytes 的所有資料，至少需要 $\lceil \log_2(19072) \rceil$ 位址線。
$2^{14} = 16384$, $2^{15} = 32768$。所以至少需要 15 位址線來定址到 19072 bytes 的資料。
然而，快取設計通常基於固定的位址線寬度（例如 32 位元或 64 位元）。我們假設主記憶體的位址寬度是 32 位元 (W bits)。

一個 32 位元的位址可以劃分為：

• Tag bits
• Index bits
• Offset bits (或 Block Offset bits)

其中，Offset bits 的數量由區塊大小決定：
Offset bits = $\log_2(\text{Block Size}) = \log_2(32) = 5$ bits。

Index bits 的數量由快取中的區塊數量決定：
Index bits = $\log_2(\text{Number of Blocks}) = \log_2(32) = 5$ bits。

Tag bits 的數量 = 位址寬度 - Index bits - Offset bits。
假設位址寬度為 32 bits：
Tag bits = $32 - 5 - 5 = 22$ bits。

因此，每個 Tag 需要 22 bits。
總共有 32 個快取區塊，所以需要 32 個 Tag。
總 Tag 儲存需求 = 32 個 Tag $\times$ 22 bits/Tag = 696 bits。
轉換成 Bytes：696 bits / 8 bits/byte = 87 bytes。

此外，快取還需要一些額外的控制邏輯和狀態位元（例如，用於判斷快取是否有效 Valid bit）。通常每個區塊會有一個 Valid bit (1 bit)。
總 Valid bit 儲存需求 = 32 個區塊 $\times$ 1 bit/區塊 = 32 bits = 4 bytes。

所以，除了 1 KByte SRAM (Data Block) 之外，額外需要的 on-chip 儲存是 Tag 和 Valid bits。
額外儲存 = Tag 儲存 + Valid bit 儲存 = 87 bytes + 4 bytes = 91 bytes。

重要假設：

• 我們假設外部記憶體的位址空間是 32 位元。如果位址空間更大或更小，Tag 的大小會改變。
• 題目說「assume biases are handled independently」，這表示我們只需要考慮權重的快取，而不是所有模型參數。
• N=256 for $i=1$ implies the first layer has 256 nodes. The weights for this layer are $256 \times 16$. The total weight size is 19072 bytes. This is significantly larger than the 1KB cache.

(b) 快取錯失率 (Miss Rate) 及錯失類型。
由於權重總大小 (19072 bytes) 遠大於快取容量 (1024 bytes)，這意味著並非所有權重都能同時存放在快取中。當 CPU 需要一個不在快取中的權重時，就會發生快取錯失 (Cache Miss)。

• 快取錯失率 (Miss Rate)：
  Miss Rate = (Number of Misses) / (Total Number of Memory Accesses)

  在這個場景下，權重的使用模式是關鍵。如果每次計算都從頭開始，並且需要訪問大量不在快取中的權重，那麼錯失率會很高。
  假設神經網路的計算流程是：

  1. 載入 Layer 1 -> Layer 2 的權重。
  2. 計算 Layer 2。
  3. 載入 Layer 2 -> Layer 3 的權重。
  4. 計算 Layer 3。
     ...
  • 權重總數：4768 個。
  • 權重總 bytes：19072 bytes。
  • 快取容量：1024 bytes。
  • 區塊數量：32 個。

  由於 19072 bytes >> 1024 bytes，快取無法容納所有權重。
  每次需要讀取的權重區塊 (32 bytes) 如果不在快取中，就會發生一次錯失。
  假設權重是連續儲存的，並且按照計算順序訪問。

  • Layer 1-2 權重：$256 \times 16 \times 4 = 16384$ bytes。
  • Layer 2-3 權重：$16 \times 16 \times 4 = 1024$ bytes。
  • Layer 3-4 權重：$16 \times 16 \times 4 = 1024$ bytes。
  • Layer 4-5 權重：$16 \times 10 \times 4 = 640$ bytes。

  當計算 Layer 1->2 時，需要載入 16384 bytes 的權重。
  這 16384 bytes 的權重需要分成 $16384 / 32 = 512$ 個區塊來載入。
  但是快取只有 32 個區塊。這意味著，當載入第 33 個區塊時，它將會替換掉第一個區塊（在直接映射中）。

  分析錯失類型：

  • Compulsory Miss (初次錯失)：當一個區塊第一次被訪問時，必然會發生錯失，因為它不在快取中。
  • Capacity Miss (容量錯失)：當一個程式需要訪問的資料量總和超過了快取容量時，即使有良好的映射策略，也會發生錯失。
  • Conflict Miss (衝突錯失)：在直接映射或組相聯快取中，如果兩個或多個區塊被映射到快取中的同一個位置（或同一組），當它們都需要被載入時，就會發生錯失，因為它們會互相替換。

  在這個問題中：

  • Compulsory Miss：第一次載入任何權重區塊都會是 compulsory miss。
  • Capacity Miss：由於總權重大小 19072 bytes 遠大於快取容量 1024 bytes，即使是最好的快取策略，也無法全部容納，因此必然存在 capacity miss。
  • Conflict Miss：在直接映射快取中，每個記憶體區塊只能映射到快取中的一個固定位置。如果有多個記憶體區塊被映射到同一個快取位置，當它們都需要時，就會發生 conflict miss。
    • 外部記憶體位址空間的 Index bits (5 bits) 決定了它能映射到哪個快取區塊。
    • Layer 1-2 的權重共 16384 bytes，需要 $16384 / 32 = 512$ 個區塊。
    • 快取只有 32 個區塊。
    • 當訪問第 33 個權重區塊時，它會被映射到快取中的某個位置。如果這個位置已經被一個「活躍」的區塊佔用，就會發生錯失。在直接映射中，這是不可避免的，因為 512 個區塊必須映射到 32 個槽位。