分塊與貼磚(blocking and tiling)
你有一張巨大的試算表要處理,手邊只有一塊小寫字夾板。若想一次處理整張表,你會不停翻來翻去、失去頭緒。聰明的做法是把表切成各自能放上夾板的小片,在一片上把所有工作做完才換下一片,且絕不重新載入同一片。分塊(又稱貼磚)正是把這招用在數值程式上:你重構迴圈,使計算在能放進快取的小資料子塊上進行,在放手前把能做的重用全做完。
以矩陣乘法 C = A*B 作為典型案例。天真三重迴圈把整列整行串流過快取;n 大時資料放不下,於是每個值早在被重用前就被逐出,同樣的數一再從主記憶體被拖上來。分塊版本則把 A、B、C 切成小的 b×b 磚(b 取得讓三塊磚舒舒服服放進快取),以磚對磚相乘。A 的一塊磚與 B 的一塊磚一旦在快取中,就被相乘累加多次才釋放。浮點運算數不變——仍是 2*n^3——但慢記憶體流量從 n^3 量級降向 n^3 / b 量級,因為每塊只取一次、重用 b 次。選 b 是一種平衡:大到足以攤平取數成本,小到工作集仍駐留在所選的快取層。
分塊是高效能稠密線性代數背後最重要的單一變換,也是為何 LAPACK 建構在疊於 BLAS level-3 核心之上的區塊演算法、而非天真迴圈之上。同樣的想法在任何「資料比快取大」之處反覆出現:網格上的貼磚模板掃描、分塊 FFT、貼磚 GPU 核心(其中晶片上的共享記憶體扮演快取的角色)。心智模型始終如一——把一塊資料沿記憶體階層搬上來一次、把它的每一分重用都榨乾、再前進,使那趟昂貴的「下到慢記憶體」之旅付得越少越好。
對 n = 4096 的矩陣乘法,天真迴圈因無物常駐快取,約搬動 n^3 = 7e10 個字穿過慢記憶體。以 b = 64 分塊則每塊取一次、重用 64 次,把慢記憶體流量約砍掉 b 倍。在典型機器上,這把一個只跑到尖峰百分之幾的乘法,變成跑到尖峰 70-90% 的乘法——算術相同,等待大減。
相同的 2*n^3 次浮點運算,但藉由趁每塊磚還在快取時重用,慢記憶體流量約降 b 倍。
並無單一最佳塊大小:b 是針對特定機器的快取大小調出來的,對 L1 完美的磚可能讓 L2 顛簸。這就是為何高效能函式庫會自動調校、或出貨機器專屬核心,而非寫死一個塊大小。