一疊記憶體，每往下一層就慢一步
上一篇留給你一個讓人不太舒服的事實：一次算術運算幾乎不要錢，而從主記憶體把它要用的那個數字抓過來，卻可能貴上百倍。如果機器真的每個數字都乖乖等，你的處理器這輩子大半時間都會閒著。硬體的解法是記憶體階層：不是單一一塊記憶體，而是一疊——上層小而快、下層大而慢。最頂端坐著幾十個暫存器，是算術單元直接讀取的便箋本。再往下是快取——最近用過的資料的小而快副本，通常分成 L1、L2、L3 三層。再下面是主記憶體（DRAM，你那幾 GB 的 RAM），而最底下、最慢的，是磁碟。
這些數字值得你刻進骨子裡，因為接下來的一切都由它們驅動。從暫存器讀取基本上是瞬間完成。L1 快取命中要花幾個週期；L2 是它的幾倍；L3 又是再幾倍；而一路跑到 DRAM 的代價，量級在幾百個週期。在一次 DRAM 抓取完成的時間裡，算術單元本來可以做上百次乘法。所以高效能計算真正的戲碼，不是「我的演算法做了幾次浮點運算」，而是「我需要每個數字的時候它住在哪裡、又得跑多遠才到」。
快取線，以及兩種風味的局部性
這裡有個讓一切豁然開朗的細節。快取不是一次抓一個數字的。它一次抓一整塊連續的區塊，叫做快取線——通常是 64 個位元組，剛好就是八個雙精度數。所以你第一次碰到某個 double 時，付的是完整的 DRAM 價錢，但它緊鄰的七個鄰居會一起免費搭便車進來，現在就坐在快取裡。下一次你要的值不在快取裡，那就是一次快取失誤，你又得付那筆長長的代價；而一個已經在快取裡的值，則是便宜的快取命中。
這個單一事實把「良好行為」分成兩種，而兩者合起來就是資料局部性的全部內容。空間局部性指的是：用的資料，緊挨著你剛剛用過的資料——筆直地走過一個陣列，元素 0、1、2、3，於是你付錢買來的每一條快取線，都在你往前走之前被完全用光——一次失誤換來八個數字。時間局部性指的是：第一次碰到某筆資料後，趁它還留在快取裡，很快就重複使用，於是第二、第三、第十次使用全是免費的命中。兩種局部性都強的核心運算，跑在快速層上；局部性差的核心運算，則一再退回 DRAM 而卡住。
一個小小的畫面就能讓賭注變得鮮明。矩陣被存成一條長長的數字序列——比方說一列接一列（row by row），所以整個第一列連續地坐在一起，接著是整個第二列。沿著列（按它被儲存的方式，橫著走）去加總，你就以完美的空間局部性掃過一條條快取線。把同一個矩陣改成一行一行（column by column）地加總，每一步在記憶體裡都往前跳了整整一列的長度；對一個大矩陣來說，幾乎每一次存取都落在一條全新的快取線上，於是你基本上對每個元素都吃一次失誤。一樣的浮點運算次數、一樣的答案——而行版本可能純粹因為資料被走訪的方式不同，就慢上好幾倍。
分塊：重新安排工作以重複利用資料
空間局部性大致關乎你如何儲存與走訪資料。時間局部性往往需要更多巧思，因為一個計算最直覺的寫法，常常會在資料本該被重複使用之前，老早就把快取裡的它丟掉了。經典的解藥是分塊（也叫鋪磚，tiling）：與其用一長趟掃過整個問題，你把它切成一塊塊小到能裝進快取的磚，趁某塊磚還是熱的時候把所有碰到它的工作做完，做完了才往下一塊走。算術是一模一樣的；你只是改了順序，好讓資料一旦抓進來，就在被趕出去之前被徹底榨乾。
矩陣相乘是教科書級的例子，值得細細描繪一次。要算兩個 n×n 矩陣的乘積 C = A B，最樸素的三層迴圈做了大約 n^3 次乘加，但也從記憶體讀了大約 n^3 個數字——B 的每個元素，都為 A 的每一列被重讀一次，而一個大的 B 根本不可能在兩次重用之間留在快取裡。分塊乘法改成把三個矩陣全都切成一塊塊小小的 b×b 磚，一磚一磚地相乘。一旦載入了 A 的一塊磚與 B 的一塊磚，它們在被丟棄之前，各被重複用於 b 次乘加。
for ii in 0, b, 2b, ... # tile row
for jj in 0, b, 2b, ... # tile col
for kk in 0, b, 2b, ... # tile depth
# multiply the b-by-b tiles, all of which fit in cache
for i in ii..ii+b
for j in jj..jj+b
for k in kk..kk+b
C[i,j] += A[i,k] * B[k,j]回報是戲劇性而且可量測的。樸素版本從慢速記憶體讀進量級為 n^3 個數字；分塊版本，只要把磚的大小 b 選成「三塊磚剛好裝進快取」，就只讀大約 n^3 / b 個。把 b 選在 64 上下，你就把慢速記憶體的流量砍掉了差不多那個倍數——原本無助地等著 DRAM 的計算，現在大半都從快取裡跑了。這是稠密線性代數裡最重要的一個變換，而它正是 第三級 BLAS 例程在底層替你做的事，下一篇會把它完整拆開來講。
算術強度：決定你命運的那個數字
為什麼分塊對矩陣相乘幫助這麼巨大，對例如「兩個向量相加」卻幾乎毫無作用？答案被一個漂亮的比值捕捉了，那就是一個計算的算術強度：它每從主記憶體搬進或搬出一個位元組，做了幾次浮點運算。寫成浮點運算次數除以位元組數。強度高的核心運算，每抓一個位元組就做大量算術，能把處理器餵得很忙；強度低的核心運算則是挨餓的，在一次次漫長的等資料之間，只滴出一點點算術。
比較兩個核心運算。把兩個長度為 n 的向量相加，c = a + b，做了 n 次加法，卻必須讀 2n 個數字、寫 n 個——每次浮點運算約三次記憶體存取，強度遠在 1 以下。再多的分塊也救不了它，因為每個數字剛好只用一次：根本沒有可供榨取的重用。再看矩陣相乘：n^3 次浮點運算，對上（在分塊之後）量級為 n^2 個被搬動的數字——一個會隨 n 增長的強度，能上到幾百甚至幾千。這正是為什麼分塊能脫胎換骨地改造矩陣相乘，卻完全碰不了向量相加。算術強度是數學本身的性質，它替任何實作可能跑多快，定下了一道天花板。
屋頂線：受記憶體限制，還是受計算限制
算術強度配得上一張圖，而這張圖有個名字：屋頂線模型。畫一張圖，橫軸放算術強度，縱軸往上放「可達到的效能」（每秒浮點運算次數）。機器加上兩道硬性的天花板。一道是它的尖峰算術速率——一條水平的平線，無論如何它每秒最多就能完成這麼多浮點運算。另一道是它的尖峰記憶體頻寬——一條從左邊升起的斜線，因為在低強度時，你的速度等於頻寬乘以強度：每位元組做越多浮點運算，每秒就越多浮點運算，直到撞上那條平的天花板。
兩條線在一個轉角相遇，而這個轉角告訴你一切。在它左邊、那段斜線上，你的核心運算是受記憶體限制的：它被位元組到達的快慢卡住，效能死死貼在頻寬的屋頂上。在它右邊、那段平線上，你的核心運算是受計算限制的：它有足夠的重用把算術單元餵到飽，只受原始浮點速率限制。把你的核心運算依它的強度擺上去，你立刻就知道自己正抵著哪一面牆——也因此知道哪些優化可能有用。向量加法落在最左邊，無可救藥地受記憶體限制；分塊做得好的矩陣相乘落在轉角上或轉角之後，是少數真正搆得到那片平屋頂的核心運算。
對屋頂線是什麼、不是什麼，要誠實。它是單一機器上的一個上界，一個乾淨的「信封背面」式天花板——不是承諾。真實的核心運算還會卡在指令額外開銷、不完美的預取、快取衝突，以及「把只用了一部分的快取線抓進來」這種沒有捨入卻很吃頻寬的流量上；所以實測效能坐在屋頂下面，往往遠在下面。這個模型的禮物不是精確的預測，而是一個診斷：它告訴你該去打記憶體那面牆還是計算那面牆，並且阻止你去優化一個從來就不是你瓶頸的東西。把這張地圖握在手裡——接下來的指南會從單一核心的快取，往上爬到向量化的 BLAS，再到許多核心與許多機器，到那時資料局部性會變成處理器之間的資料搬移，而同一課，會在大一號的尺度上再次回來。