Carved Marker

CPU 的 cache 和 latency [Part 2]

在上一篇文章中,已經簡單討論過 CPU 的 cache 和其對 latency 的影響。在這篇文章中,我們就以一個較為實際的例子,並說明 prefetch 的原理和用途。

這裡要用的「實際例子」,其實還是很理想化的。為了和 3D 繪圖扯上一點關係,這裡就用「4x4 的矩陣和 4 維向量相乘」做為例子。不過,一般在 3D 繪圖中,都是用 single precision 的浮點數(每個數需要 32 bits),而這裡為了讓記憶體的因素更明顯,我們使用 double precision 的浮點數(每個數需要 64 bits),也就是一個 4 維向量剛好需要 32 bytes。

在這個例子中,我們採取一個 3D 繪圖中,相當常見的動作,也就是把一大堆 4 維向量,乘上一個固定的 4x4 矩陣。如果向量的個數非常多,超過 CPU 的 cache 所能負擔,那麼 CPU 的表現就會大幅下降。

為了讓大家心裡有個底,這裡先把執行的結果列出來:

測試平台: Pentium III 500Mhz, PC100 SDRAM, 440BX chipset

Vector test result

程式集可以下載程式的原始碼和執行檔。

首先,我們來看沒有使用 prefetch 指令的結果。事實上,結果相當符合預測。在 L1 D-cache 的範圍內(即小於 16KB 的情形),平均的運算時間相當的穩定,約在 51 ~ 52 cycles 左右。這也是 Pentium III 在計算一個 4x4 矩陣和 4 維向量相乘時(使用 double precision 浮點數),可能達到的最快速度。當然,這個程式是用 C 寫成的。如果直接用手寫組合語言,可能還可以再快個 5 ~ 10 cycles。

當資料量超過 L1 D-cache 的範圍,但是還在 L2 cache 的範圍之內時,所需的時間提高到約 60 cycles 左右。在 Part 1 中,我們已經知道 Pentium III 500Mhz 的 L2 cache 大約有 10 cycles 的 latency,所以這個結果也是相當合理的。

當資料量超過 L2 cache 的範圍時,所有的資料就需要從主記憶體中取得了。從圖上可以很容易的看到,每次運算所需的時間增加到 145 ~ 150 cycles。這有點出乎意料之外:在 Part 1 中,讀取主記憶體的 latency 只有 30 cycles 左右,但是在這裡,latency 增加了約 100 cycles。不過,這個結果並不奇怪。因為在運算結束後,運算的結果必須要寫回記憶體中,而寫回記憶體的動作,需要很多時間。

從這裡可以看到,在資料量超過 L2 cache 的範圍時,CPU 可說是被記憶體的速度限制住了。事實上,如果記憶體的速度不變,那即使是用兩倍快的 CPU,速度的增加也會非常有限。以 3D 遊戲的角度來說,1024KB 或 2048KB 這樣的資料量並不算少見,因為一個 single precision 浮點數的 4 維向量,就需要 16 bytes 的空間。65,536 個 4 維向量就需要 1MB 的空間了。

事實上,記憶體的速度雖慢,但是要完成一個 32 bytes(一個四維向量的大小)的讀寫動作,也只需要 60 ~ 70 cycles 而已(以 Pentium III 500Mhz 配合 PC100 SDRAM 的情形來算)。而在不用 prefetch 的情形下,CPU 的動作類似下圖所示:

Vector computation diagram 1

在上圖中,CPU 的運算單元(即圖中的 Execution Units)大部分的時間都在等待資料輸入。而 Load/Store Unit 也有不少時間是不動作的。這顯然不是最好的方法,因為 CPU 的兩個單元都不是全速運作。

如果我們在 CPU 的運算單元進行計算工作時,就把下一個要計算的資料先載入到 CPU 的 cache 中,那麼,CPU 的動作就會變成類似下圖所示:

Vector computation diagram 2

現在,Load/Store Unit 變成全速運作了。Execution Units 還是沒有全速運作,但是這是沒辦法的。這種情形,就表示出瓶頸是在 Load/Store Unit,也就是在主記憶體的速度。已經沒有任何方法可以加快執行的速度了(除非加快記憶體的速度)。

要注意的一點是,上面的情形是很少發生的真實世界中的。實際的程式,通常瓶頸都是在運算單元。不過,我們的例子則剛好不是這樣(因為矩陣和向量相乘是很簡單的運算),而是類似圖中的情形。

要怎麼告訴 CPU,在計算的同時將下一個資料載入到 cache 中呢?這時就要用到 prefetch 的指令了。在我們的程式中,執行向量運算的程式如下:

  • for(i = 0; i < buf_size; i += 4) {
    • double r1, r2, r3, r4;
    • // 執行矩陣乘法
    • r1 = m[0] * v[i] + m[1] * v[i+1] + m[2] * v[i+2] + m[3] * v[i+3];
    • r2 = m[4] * v[i] + m[5] * v[i+1] + m[6] * v[i+2] + m[7] * v[i+3];
    • r3 = m[8] * v[i] + m[9] * v[i+1] + m[10] * v[i+2] + m[11] * v[i+3];
    • r4 = m[12] * v[i] + m[13] * v[i+1] + m[14] * v[i+2] + m[15] * v[i+3];
    • // 寫回計算結果
    • v[i] = r1;
    • v[i+1] = r2;
    • v[i+2] = r3;
    • v[i+3] = r4;
  • }

現在,我們在矩陣乘法的前面插入一個 prefetch 指令,變成:

  • for(i = 0; i < buf_size; i += 4) {
    • double r1, r2, r3, r4;
    • // 執行矩陣乘法
    • r1 = m[0] * v[i] + m[1] * v[i+1] + m[2] * v[i+2] + m[3] * v[i+3];
    • // 前一行執行完後,整個 4 維向量已經載入到 cache 中。
    • // 所以,現在用 prefetch 指令載入下一個 4 維向量。
    • prefetch(v + i + 4);
    • // 繼續進行計算
    • r2 = m[4] * v[i] + m[5] * v[i+1] + m[6] * v[i+2] + m[7] * v[i+3];
    • r3 = m[8] * v[i] + m[9] * v[i+1] + m[10] * v[i+2] + m[11] * v[i+3];
    • r4 = m[12] * v[i] + m[13] * v[i+1] + m[14] * v[i+2] + m[15] * v[i+3];
    • // 寫回計算結果
    • v[i] = r1;
    • v[i+1] = r2;
    • v[i+2] = r3;
    • v[i+3] = r4;
  • }

這段程式中的 prefetch 函式,裡面執行的是 SSE 的 prefetchnta 指令。Pentium III 和 Athlon 都支援這個指令(AMD 的 K6-2 中另外有一個 prefetch 指令,是 3DNow! 指令的一部分)。這個指令會將指定的資料載入到離 CPU 最近的 cache 中(在 Pentium III 即為 L1 cache)。

只不過加上這樣一行程式,執行結果就有很大的不同。回到前面的測試結果,我們可以看出,prefetch 指令,在資料已經存在 cache 中的時候,會有相當程度的 overhead(在這裡是大約 10 cycles)。但是,當資料不在 cache 中的時候,效率就有明顯的改善。特別是在資料量為 1024 KB 時,所需時間約為 70 cycles,說明了瓶頸確實是在 Load/Store Unit。在 1024 KB 之後,所需的 cycle 的增加,則是因為在多工系統中難以避免的 task switch 所產生的 overhead。

由此可知,prefetch 指令對於多媒體及 3D 遊戲等資料量極大的應用,是非常重要的。也可以預料,將來的程式一定會更加善用這類的功能,以達到最佳的效率。

[Part 1] [Part 2]

5/24/2000, Ping-Che Chen


Sorry, Traditional Chinese only. This page is encoded in UTF-8.

Copyright© 2000 Ping-Che Chen