深入理解計算機系統——第六章 The Memory Hierarchy

• 6.1 Storage Technologies
• • 6.1.1 Random Access Memory
  • • Nonvolatile Memory
    • Accessing Main Memory
    • Disk Geometry
    • Connecting I/O Devices
  • 6.1.3 Solid State Disks
  • 6.1.4 Storage Technology Trends
• 6.2 Locality
• 6.3 The Memory Hierarchy
• • 6.3.1 Caching in the Memory Hierarchy
• 6.4 Cache Memories
• • 6.4.1 Generic Cache Memory Organization
  • 6.4.2 Direct-Mapped Caches
  • 6.4.3 Set Associative Caches
  • 6.4.4 Fully Associative Caches
  • 6.4.5 Issues with Writes
  • 6.4.6 Anatomy of a Real Cache Hierarchy
  • 6.4.7 Performance Impact of Cache Parameters
  • • Impact of Cache Size
    • Impact of Block Size
    • Impact of Associativity
    • Impact of Write Strategy
• 6.5 Writing Cache-Friendly Code
• 6.6 Putting It Together: The Impact of Caches on Program Performance
• • 6.6.1 The Memory Mountain
  • 6.6.2 Rearranging Loops to Increase Spatial Locality
  • 6.6.3 Exploiting Locality in Your Programs

資源：

視頻課程
視頻課件1
視頻課件2
請問CPU，內核，寄存器，緩存，RAM，ROM的作用和他們之間的聯系？

前面講匯編語言時，提到將內存當作一個字節數組，可以用地址作為下標來訪問該數組的元素。
但實際上存儲系統（memory system）是一個非常復雜的設備層次結構（hierarchy of devices)，它提供一個抽象，將內存結構抽象為一個大的線性數組。

6.1 Storage Technologies

6.1.1 Random Access Memory

特點：

• RAM is traditionally packaged as a chip.
• Basic storage unit is normally a cell (one bit per cell).
• Multiple RAM chips form a memory.

分類，根據存儲單元（cell) 的實現方式：

• SRAM (Static RAM)
• DRAM (Dynamic RAM)

兩者區別見下圖：

• DRAM 只需要1個晶體管（transistor) 去存儲1比特（bit)，而 SRAM 更復雜，需要 4 或者 6個晶體管，因此 SRAM 的成本更高，但訪問速度更快。

• DRAM 對干擾很敏感（DRAM memory cell is very sensitive to any disturbance），因此需要刷新（The memory system must periodically refresh every bit of memory by reading it out and then rewriting it. ），做錯誤檢測等。

• SRAM 不需要刷新，只要不斷電，能保持穩定（Even when a disturbance, such as electrical noise, perturbs the voltages, the circuit will return to the stable value when the disturbance is removed.）。

• SRAM 用于那些內存容量小但速度快的芯片中，叫高速緩存（cache memory).

• DRAM 被廣泛用于主存（main memory)，以及圖形中的幀緩存（frame buffers associated with graphic cards）中。

相同點：
兩者都是易失的（volatile），即斷電將會丟失保存的信息。

---

Nonvolatile Memory

非易失性存儲器（nonvolatile memory)，即在斷電后也能保存其內容，因為歷史的原因，這些存儲器被叫只讀存儲器（read-only memories, ROMs)，但其實有些 ROMs 也能寫數據。

類型：

• Read-only memory (ROM): programmed during production.

• Programmable ROM (PROM) : can be programmed exactly once.

• Erasable programmable ROM (EPROM): can be erased and reprogrammed on the order of 1,000 times.

• Electrically erasable PROM (EEPROM): electronic erase capability (it does not require a physically separate programming device). An EEPROM can be reprogrammed on the order of $10^5$ times before it wears out.

• Flash memory: based on EEPROMs, with partial (block-level) erase capability.

用途：

• 固件（firmware）中使用
  Programs stored in ROM devices are often referred to as firmware. When a computer system is powered up, it runs firmware stored in a ROM.
  Some systems provide a small set of primitive input and output functions in firmware—for example, a PC’s BIOS (basic input/output system) routines.
  Complicated devices such as graphics cards and disk drive controllers also rely on firmware to translate I/O (input/output) requests from the CPU.

• 固態硬盤（Solid state disks, SSD)中使用
  系統仍將它當作傳統的旋轉硬盤（rotating disks），但它更快。

---

Accessing Main Memory

總線（bus)：a collection of parallel wires that carry address, data, and control signals.

Data flows back and forth between the processor and the DRAM main memory over shared electrical conduits called buses.

Buses are typically shared by multiple devices.

Each transfer of data between the CPU and memory is accomplished with a series of steps called a bus transaction.

示例：

例如執行 load 操作，即將主存中的數據寫到 CPU 中：

movq A,%rax

操作過程為：
CPU 將地址 A 放到系統總線上，然后通過 I/O bridge 傳輸到存儲器總線上， 主存接收到該信號后讀取地址 A 處的數據并寫到存儲器總線上，最后經過系統總線傳給 CPU，CPU 讀取總線上的數據后復制到寄存器 %rax 中。

如果執行 store 操作則是相反的過程，即將 CPU 中的數據寫入到主存，如：

movq %rax,A

操作過程為：
CPU 將地址 A 放到系統總線上，然后通過 I/O bridge 傳輸到存儲器總線上， 主存接收到該信號后讀取地址 A 并等待數據到達；然后 CPU 將寄存器 %rax 的內容復制到系統總線上，最終主存從存儲總線上讀取數據并存儲在地址 A 處。

注意：從圖中可以看到寄存器文件（register file）和 算術邏輯單元 （ALU）很近，因此它們之間的操作很快；但內存是離 CPU 相對較遠的一些芯片組，因此讀寫內存的操作相對較慢。

---

Disk Geometry

這一小節沒看書，視頻講的很清楚，很好理解。

Notice that manufacturers express disk capacity in units of gigabytes (GB) or terabytes (TB), where 1 GB = $10^9$ bytes and 1 TB = $10^{12}$ bytes. （注意廠商表示磁盤容量不是用二進制，而是十進制）

這種磁盤訪問速度比 DRAM 慢了接近 250 倍。

現代磁盤控制器將磁盤作為一系列的邏輯塊提供給 CPU，每個塊是扇區大小的整數倍，一個扇區是 512 bytes，最簡單的情況下，一個邏輯塊就是一個扇區，塊號是一系列增長的數字，從 0 開始，0， 1，2 ，等。磁盤控制器控制物理扇區和邏輯塊的映射。

磁盤控制器會將一些柱面保留作為備用柱面，這些區域沒有被映射為邏輯塊，如果有個柱面的扇區壞了，磁盤控制器將數據復制到備用的柱面，然后磁盤就能繼續正常工作。因此磁盤的格式容量（formatted capacity）比實際容量小。

---

Connecting I/O Devices

Figure 6.11 shows a representative I/O bus structure that connects the CPU, main memory, and I/O devices.

讀取磁盤扇區的過程：
1、 CPU 通過三個指令初始化磁盤

• 給磁盤發送一個讀的命令告訴磁盤執行讀操作，同時告訴磁盤當讀數據結束后是否給 CPU 發一個中斷信號
• 第二條指令告訴磁盤讀取數據邏輯塊編號
• 第三條指令告訴讀取扇區的內容后存放在主存中的地址

2、 磁盤讀取數據，同時 CPU 繼續做其他事，磁盤取得總線的控制權直接復制數據，然后通過 I/O 橋將數據傳輸給主存，此過程無 CPU 參與，該過程稱為直接存儲訪問 （direct memory access, DMA）。

3、 在 DMA 過程結束后，磁盤控制器給 CPU 發送一個中斷信號通知 CPU。This causes the CPU to stop what it is currently working on and jump to an operating system routine. The routine records the fact that the I/O has finished and then returns control to the point where the CPU was interrupted. 例如，如果目前有某個程序等著將數據寫到內存中，那么CPU可執行該操作并處理內存（之前總線控制交給磁盤）。

這種直接存儲訪問的方式原因是：磁盤讀數據過程很慢，CPU 如果等磁盤讀數據，則太浪費時間。

6.1.3 Solid State Disks

固態硬盤（SSD）的訪問速度介于旋轉磁盤和 DRAM 之間。

對于 CPU 來說，固態硬盤和旋轉磁盤完全相同，它們有相同的接口，但固態硬盤沒有那些機械部件，他是完全由閃存構建。

見上圖所示，固態硬盤中有一個固件（firmware)設備 ，稱為閃存翻譯層（flash translation layer），充當旋轉磁盤中磁盤控制器（disk controller）的功能。

固態硬盤中以頁（page）為單位從閃存中讀寫數據，頁的大小根據技術的不同，通常在 512 字節 to 4 KB。

一系列的頁組成一塊（block），注意這個塊和前面提到的的邏輯塊不同。

寫數據：如果要寫數據到某一頁，必須保證該頁所在的塊的內容全部被擦除（erased），因此在寫數據前必須將該塊的其他頁的數據內容復制到一個新的已經被擦除的塊中，因此寫操作很復雜。

讀數據：直接讀取。

一個塊被反復擦除大約10萬次后將被磨損，無法使用。

SSD 的性能：



從上圖可見：

• 順序訪問（Sequential access）比隨機訪問（Random access）更快;
• 隨機寫數據的速度十分慢，因為前面提到的要擦除和復制的過程。

SSD 和 旋轉磁盤 的比較：

1）優點

• SSD 沒有移動部分，因此讀寫速度更快，耗電更少，更結實。

2）缺點

• 可能磨損，但對于現在的固態硬盤，可能該問題沒有跟大影響，如 Intel SSD 730 在磨損前可以寫 128 PB（petabyte） 次。

• 比旋轉磁盤貴。

6.1.4 Storage Technology Trends

下圖展示了不同存儲設備相對于 CPU 的性能：

y 軸表示訪問時間，在 2003 以前，制造商通過減小CPU的尺寸， 讓各個部分更緊密，按比例增加時鐘頻率，從而使 CPU 的時鐘周期更短。

但由于時鐘頻率越高，消耗的功率越大，因此在 2003 因為功率的問題達到瓶頸，停止繼續增加時鐘頻率。

為了時 CPU 更快，2003 年后開始在芯片上放置更多處理器內核（process cores），將 CPU 芯片細分為獨立的處理器內核，每個內核可以執行自己的指令，通過并行運行，提高效率。

現代的 CPU 執行時間逐漸趨于穩定。

從圖中可以看出，旋轉磁盤，SSD，DRAM 和 CPU 訪問時間相差很大，而程序使用的數據很多存在磁盤和內存中，因此盡管 CPU 的執行時間越來越短，但存儲設備的訪問速度卻基本不變，甚至相對來說越來越慢，那么計算機的性能實際不會增加，因為受訪問數據的時間限制。

6.2 Locality

The key to bridging this CPU-Memory gap is a fundamental property of computer programs known as locality.

Principle locality : Programs tend to use data and instructions with address near or equal to those they have used recently.

局部性有兩種形式：

Temporal locality
Recently referenced items are likely to be referenced again in the near future.

Spatial locality
If a memory location is referenced once, then the program is likely to reference a nearby memory location in the near future.

示例：

上述代碼分析：

循環內部每次引用數組元素，由于是連續的步長為1的引用，因此是 Spacial locality。

循環內每次對 sum 變量的引用屬于 temporal locality。

循環內每次迭代引用一系列的指令，屬于 spacial locality。

每次循環都要循環使用相同的指令，屬于 temporal locality。

對程序局部性的評估：

圖 6.18 的程序局部性好，而圖 6.19 程序的局部性差。
第二段代碼的 spacial locality 很差，因為不是連續的訪問數組元素，數組的元素在內存中是按行存儲的（row-major order，row-wise）。

6.3 The Memory Hierarchy

Some fundamental and enduring properties of storage technology and computer software:

• Faster storage technologies cost more per byte than slower ones and have less capacity and require more power (heat!).

• The gap between CPU and main memory speed is widening.

• Well-written programs tend to exhibit good locality.

Their complementary nature suggests an approach for organizing memory systems, known as the memory hierarchy, that is used in all modern computer systems.

在存儲器的層次結構中，每一層都包含從下一個較低級別層次所檢索的數據。如最頂層的寄存器保存從 L1 高速緩存器中檢索的數據。

6.3.1 Caching in the Memory Hierarchy

Cache: A small, fast storage device that acts as a staging area (暫存區) for the data objects stored in a larger, slower device.

Central idea of a memory hierarchy:
For each k, the faster and smaller storage device at level k serves as a cache for the larger and slower storage device at level k+1.

Why do memory hierarchies work?

• Because programs tend to exhibit locality, programs tend to access the data at level k more often than they access the data at level k+1. 如果要訪問第 k+1 層存儲單元，我們將會將其拷貝到第 k 層，因為很有可能會再次訪問它。

• 由于不經常訪問 k+1 層的數據，因而使用速度更低，更便宜的存儲設備。

The basic principle of caching in a memory hierarchy：

緩存是一個通用的概念，能應用于存儲器層次結構中的所有層。

Cache Hits： 當程序需要在 k+1 層的數據時，會在 k 層查看是否有該數據，如果正好有，則稱為 緩存命中 （cache hit）。

Cache Misses: 當程序需要在 k+1 層的數據時，會在 k 層查看是否有該數據，如果正沒有該數據，則稱為 緩存未命中 （cache miss）；例如上圖中如果在 k+1 層查找 塊12 的數據，而第 k 層沒有，因此會將 k+1 層 塊12 的數據復制到 k 層，替換第 k 層中 塊9 的數據。

緩存未命中的種類：

Cold (compulsory) miss
Cold misses occur because the cache is empty.
這是不可避免的，將數據慢慢填充到空的緩存中的過程稱為 warming up your cache。

Capacity miss
Occur when the set of active cache blocks (working set) is larger than the cache.
這個是由于緩存的大小有限造成的，例如上圖中緩存只有4塊，如果需要8塊的內容，則會造成 Capacity miss。 不斷被程序訪問的一組塊被稱為工作集 （working set），因此當執行不同的程序時，工作集是會變的。

Conflict miss
沖突未命中（conflict miss) 和緩存的實現方式有關。大多數緩存，尤其是硬件緩存，由于它們需要設計的較為簡單，因此限制了塊可以被放置的位置。例如 block i 只能放在 block (i mod cache size) 的地方，以上圖為例，緩存的大小為4，如果要取 block 8的數據，則只能放在緩存的第0塊，同樣，block 9 放在緩存的 block 1處。因此，如果要取的塊為 block 0， block 4，block 8，那么計算出來都應該放在緩存 block 0的位置，因此放 block 4時，會覆蓋原來 block 0的數據，加入需要循環的訪問 block 0，block 8，block 0，block 8，這樣就會一直不能命中，即使緩存有多余的空間，但位置的限制導致一直覆蓋緩存上 block 0 的數據，造成沖突未命中。

---

Cache Management:

緩存管理：當有請求從較低的層次中讀取內容時，需要有一個過程決定如何處理這個請求，如何將其放入緩存中的某一位置。

6.4 Cache Memories

The memory hierarchies of early computer systems consisted of only three levels: CPU registers, main memory, and disk storage.

However, because of the increasing gap between CPU and main memory, system designers were compelled to insert a small SRAM cache memory, called an L1 cache (level 1 cache) between the CPU register file and main memory.

緩存存儲器 （cache memory）在 CPU 芯片上，完全由硬件管理。
上圖中位于寄存器文件附近的緩存用于存儲主存中經常訪問的塊。

6.4.1 Generic Cache Memory Organization

因為緩存由硬件管理，因此硬件必須知道如何查找緩存中的塊，并確定是否包含特定的塊，因此必須以嚴格且簡單的方式去組織緩存存儲器。

Valid: 初始時，緩存中沒有內容，但上圖中 B 字節的塊中有一些無效的數據，因此需要 有效位（Valid） 來識別 B 字節中的數據是否有效，0 則無效，1 有效。

Tag: 標志位，幫助搜尋塊。

緩存大小: 一個緩存有 S 組，一組有 E 行，一行中的塊有 B 字節，因此緩存的大小 C = S * E * B。

塊的大小由內存系統決定，是內存系統的固定參數。

---

緩存硬件讀取過程：
當程序執行 load 指令時，需要從主存的地址 A 處讀取數據，因此 CPU 將地址 A 發送給緩存，緩存將地址 A 分成多個區域（由緩存的組織結構決定），如果找到該地址的內容則直接讀取數據后返回給 CPU，否則從內存讀取數據并放入緩存中，再將數據傳給 CPU。

緩存參數：

如果有4組，那么 S 為4，s 為 2，s 表示代表組的索引的位數，組的索引為 00，01，10， 11，因此只需要2位就能表示。

如果內存地址是4位，則 m 為 4。

如果一個數據塊有 2 個字節，那么 B 為 2（block[0]，block[1]），b 為1，則將用最低的一位作為偏移量，表示所讀取的字（word）開始的位置，例如地址 7 （0111）的偏移量為 1，將讀取數據的地址起始位置為該組相應行的 block[1] 處。

標志位（Tag）：如果 S 為4，E 為 1，B 為 2，m 為 4， 則標志為的數目 t = 4 - (2 + 1) = 1，即標志位只有 1 位。標志位用于比較緩存中該行的標志位和地址 A 的標志位是否一致，從而判斷緩存中的根據索引找到的行的數據是否是要查找的地址 A 的數據。

（這些參數看后面的示例了解其意義）

6.4.2 Direct-Mapped Caches

直接映射緩存：E 為1，即一組只有一行。

假設一塊的大小為 8 字節，一個 word 大小為 4 字節：

上圖所示，如果地址中 偏移位 為 4（100），假設組的索引為（ s bits） 1（00001）：

緩存將查找 Set 1 那組的數據，忽略其他組；

然后將比較標志位和有效位；

有效位可以知道緩存上塊的數據是否有效；

標志位則查看緩存上的數據是否是想要查找的數據；

如果標志位有效，則通過偏移4找到數據的起始地址處，圖中獲取的數據為 $w_0{w}_1{w}_2{w}_3$，然后直接返回給 CPU并放入寄存器中。

如果 標志位 tag 不匹配，則表示未命中，需要去內存中找到相應的塊然后將該處的塊覆蓋掉（包括 tag），再取出數據返回給 CPU；

關于索引，前面講過有的硬件對塊存放的位置有嚴格的要求，有計算公式，因此塊的位置時固定的。

---

示例2：
Suppose we have a direct-mapped cache described by
$$(S,E,B,m)=(4,1,2,4)$$

緩存有4組，每組一行，每塊有2字節，地址為 4 bits；假設一個 word 為 1 字節。

從上圖可以看出，一個塊包含內存中的兩個地址，如 block 0 包含地址 0 和 1，他們的 Tag 和 組的索引都相同，只是偏移量不同，block 0 的偏移量為 0，block 1 的偏移量為 1。

圖 6.30 可看出組的索引號采用地址的中間兩位，這是考慮到前面提過的 spacial locality，如果讀取相鄰地址的內容，則索引會分到不同的組，而用高位作為索引則會分到相同組，容易造成 conflict miss：

讀地址 0 （0000）的數據：將在緩存 set 0 中查找，初始時緩存為空，因此其有效位（Valid）值為 0，因此未命中，需要從內存中找到 block 0 的數據放入緩存中，注意因為 block 0 包含兩個地址 0 和 1，因此都會存入緩存，然后返回 m[0] 給 CPU：

放入后有效位變為 1，Tag 設置為 0。

讀地址 1 （0001）的數據：將在緩存 set 0 中查找，此時已有數據，且有效位和 Tag 均符合，因此根據偏移 1 獲取數據 m[1] 直接發送給 CPU。

讀地址 13 （1101）的數據：將在 set 2 中查找，無數據，因此從內存獲取數據放入緩存，并根據偏移 1 獲取 m[13] 發送給 CPU：

讀地址 8 （1000）的數據：將在 set 0 中查找，其標志位為 1，和緩存中已有的標志位 0 不同，因此需要從內存中取數據并覆蓋掉緩存中 set 0 的數據，返回 m[8] 到 CPU：

如果再讀地址 0 的數據，則又會未命中，然后從內存取數據覆蓋 set 0 中數據，盡管還有 set 1 和 set 3 兩組未使用，但仍會選擇相同的 set 從而造成 conflict miss。

因此緩存需要增大 E 的數目，提高關聯性。

6.4.3 Set Associative Caches

當 E 大于1時，稱為 E-way set associative cache ：

上圖 E 為2，假如入要查詢的地址組索引為 set 1，set 1 中有兩行，緩存將會同時比較兩行的有效位和標志位，找到標志位符合的一行。

E 為 2時，如果查詢的地址為0，組為 set 0，從內存中放入 m[0]和m[1] 到 set 0 的第一行后，還會同時獲取 m[8] 和 m[9] 放到 set[0] 的第二行，因此從內存中獲取數據塊時，會盡可能的將該組中空的塊寫入數據。

6.4.4 Fully Associative Caches

A fully associative cache consists of a single set (i.e., E = C/B) that contains all of the cache lines.

全相聯高速緩存，只有一組（set），所有行都在這一組中，因此沒有組索引。

全相聯高速緩存和之前介紹的緩存工作模式相同，但因為所有行都在一組中，而查詢時需要同時比較所有行的 Tag，因此很難做到緩存既大又快，這種設計比較適合小的緩存（如 translation lookaside buffers (TLBs) in virtual memory systems that cache page table entries）。

6.4.5 Issues with Writes

向內存中寫數據和讀數據相反的過程。

1. write hit
如果要寫的數據 w 已經在緩存中，即是一個 write hit，那么緩存更新了 w 后，有兩種處理方式：

• Write-through
  將更新后的 w 立刻寫到下一個低等級的塊中（前面講過，存儲器的層次等級，當前命中的緩存保存的是它第一等級的部分數據的副本），這樣很費時，因為訪問低層次的時間更長。

• Write-back
  w 先保存在當前緩存中，只有當前塊的內容要被覆蓋時才將數據寫回到低等級塊中。這樣做的缺點是需要額外的 dirty-bit 來表示該緩存塊是否被修改。

2. Write miss
如果緩存中沒有數據，有兩種處理方式：

• Write-allocate
  找到要寫入的數據塊放到緩存中，更新緩存的塊。缺點是這樣每次未命中都要額外花時間將數據寫到緩存中，這種方式是考慮到 spacial locality，可能接下來用到的數據已經在緩存中，能命中了。

• No-write-allocate
  直接將數據寫到低層次的塊中，不放入緩存中。

通常的方式是：

• Write-through + No-write-allocate
• Write-back + Write-allocate (更常用)

6.4.6 Anatomy of a Real Cache Hierarchy

In fact, caches an hold instructions as well as data.

• A cache that holds instructions only is called an i-cache.

• A cache that holds program data only is called a d-cache.

• A cache that holds both instructions and data is known as a unified cache.

Modern processors include separate i-caches and d-caches.

i-caches are typically read-only, and thus simpler.

將指令緩存和數據緩存分開的原因：
1、處理器能同時讀指令和數據
2、防止數據訪問和指令訪問的 conflict miss

Characteristics of the Intel Core i7 cache hierarchy：

見上圖，如果 L1 未命中，將向 L2 發送請求嘗試在 L2 中查找數據，如果 L2 找不到，則向 L3 發送請求，查看能否在 L3 中找到數據，如果 L3 也找不到，則放棄查找。

6.4.7 Performance Impact of Cache Parameters

對緩存性能的評估：

• Miss Rate
  The fraction of memory references not found in cache.

• Hit Time
  Time to deliver a line in the cache to the CPU, including the time for set selection, line identification, and word selection. Hit time is on the order of several clock cycles for L1 caches.

• Miss Penalty
  Any additional time required because of a miss. 如果未命中，需要去取數據，然后再寫到緩存中更新緩存等額外花費的時間。

---

Impact of Cache Size

大的緩存趨向增大命中率 （hit rate)，因為大的緩存很難運行快，因此在存儲器的層級結構中，低層次的緩存比高層次的大。

---

Impact of Block Size

塊的尺寸對性能的影響：如果程序有更多的 spacial locality 比 temporal locality，那塊的尺寸大會增加命中率；而如果程序更多的是 temporal locality，那么塊的尺寸太大，對應的行的數量就會減少（緩存大小一樣的話）， 因此反而降低 hit rate；并且塊越大，miss penalty 越大，因為未命中時花費的傳輸數據的時間更多。

---

Impact of Associativity

6.4.3 中講過提高關聯性，即增大一組中的行數能減小 conflict miss，但這種設計對硬件的要求高。而且行數越多，則需要用于判讀的 Tag 的位越多，因此更復雜，也會增加 miss penalty 的時間。

通常的做法：更高層次相關性較低，低層次緩存相關性更高（為了增加 hit rate），如前面圖 6.39 所示， L3 是 16-way，L1 和 L2 是 8-way。

---

Impact of Write Strategy

In general, caches further down the hierarchy are more likely to use write-back than write-through.

6.5 Writing Cache-Friendly Code

Good programmers should always try to write code that is cache friendly, in the sense that it has good locality.

• Repeated references to local variables are good because the compiler can cache them in the register file (temporal locality).
• Stride-1 reference patterns are good because caches at all levels of the memory hierarchy store data as contiguous blocks (spatial locality).

6.6 Putting It Together: The Impact of Caches on Program Performance

6.6.1 The Memory Mountain

• Read throughput (read bandwidth)
  Number of bytes read from memory per second (MB/s).
• Memory mountain
  Measured read throughput as a function of spacial and temporal locality.
  Compact way to characterize memory system performance.

測試函數：

上面測試函數通過改變 size 和 stride 兩個參數分別控制 temporal locality 和 spacial locality。size 越小，則 temporal locality 越好；stride 越小，則 spacial locality 越好。

通過反復給不同尺寸的 size 和 stride 參數來執行測試函數，就能生成一個 two-dimensional function of read throughput versus temporal and spatial locality. 這個函數就是 memory mountain.

6.6.2 Rearranging Loops to Increase Spatial Locality

矩陣乘法示例：

代碼實現如下：

分析循環內部代碼：
對于版本 (a) ，矩陣 A 的數據是按行取，而 B 的數據則是按列取，B 的 stride 是 n (假設 n 很大），那么每次循環 B 都不能命中。

改進后的版本 (f)，A 和 B 都是按行取，因此降低了未命中率。

Core i7 matrix multiply performance：

6.6.3 Exploiting Locality in Your Programs

In particular, we recommend the following techniques:

• Focus your attention on the inner loops, where the bulk of the computations and memory accesses occur.

• Try to maximize the spatial locality in your programs by reading data objects sequentially, with stride 1, in the order they are stored in memory.

• Try to maximize the temporal locality in your programs by using a data object as often as possible once it has been read from memory.

總結

以上是生活随笔為你收集整理的深入理解计算机系统——第六章 The Memory Hierarchy的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。