本節書摘來自華章計算機《高性能科學與工程計算》一書中的第3章，第3.5節,作者:(德）georg hager gerhard wellein 更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視。
在基于cache的處理器上，許多循環的優化潛力可以通過觀察某些基本參數（像資料傳輸、算術運算和問題規模的伸縮性）很容易地估算出來。進而進一步确定優化的努力是否有意義。
3.5.1 o(n)/o(n)
如果算術運算量和資料傳輸量（加載/寫入）與問題規模（或者“循環長度”）n成比例，那麼優化潛力是非常有限的。标量乘、向量加和稀疏矩陣向量乘都是這類問題的典型執行個體。當n取值較大時，其性能不可避免地受訪存限制，并且使用編譯器生成的代碼就可以達到較高的性能。這是因為o(n)/o(n)循環往往很簡單，正确的軟體流水政策的作用非常明顯。但是嵌套循環是一個不一樣的問題（具體見下面的分析）。
然而，即使循環不嵌套，優化空間還是經常存在的。作為一個執行個體，考慮下面的向量加代碼：
左邊代碼的每一個循環都沒有優化空間。每個循環包含兩次資料讀取操作、一次資料寫入操作和一次加法操作（沒有計算寫配置設定），是以循環代碼均衡值為3/1。然而，數組b在第二個循環中被重新加載了一次，這是非常沒有必要的：将兩個循環整合為一個，資料b的元素就可以隻被讀取一次，循環代碼平衡值降為5/2。在其他條件都一樣的情況下，代碼性能（訪存受限）将會提高6/5（如果寫配置設定時不可避免，這個值将是8/7）。
對于這兩個循環來說，循環整合實作了o(n)的資料重用，減少了一個數組的資料讀取操作。像這種簡單情況，編譯器一般會自動使用該優化方法。
3.5.2 o(n2)/o(n2)
典型的循環長度為n的兩層嵌套循環中，有o(n2)算術運算操作和o(n2)資料讀取和寫入操作。稠密矩陣向量乘、矩陣轉置以及矩陣加都是這類問題的典型執行個體。盡管内層循環的情況和o(n)/o(n)相似，并且都訪存受限，但嵌套卻開啟了新的優化空間。然而，優化又一次僅限于一個常數因子的改善。考慮下面的稠密矩陣向量乘（matrix-vector multiply, mvm）代碼：
https://yqfile.alicdn.com/b2830f3bbd5f9f9c4f195d42d8e32ec25abdd504.png" >
上面代碼的代碼平衡值為1w/f（矩陣a、b兩次資料讀取和兩次算術運算）。數組c由外層循環變量索引，是以其更新可以在寄存器中進行（這裡我們通過使用标量tmp來說明，盡管編譯器可以自動進行這些轉換），進而不計算其讀取和寫入操作。矩陣a隻被加載一次，但是b卻被加載了n次（見圖3-11，外層循環每疊代一次，b就被加載一次）。我們可以采用上節所講的循環整合方法，但是這裡需要整合的内層循環有n個而不是兩個。解決方案是循環展開：外層循環間隔m周遊，内層循環重複m次。我們必須要面對外層循環長度不能被m整除的情況。在這種情況下，要單獨處理剩餘的循環。
https://yqfile.alicdn.com/76597789bedf0fdd889eb1f30455a61c7a79f756.png" >
“剩餘循環”可以采用同原始循環一樣的優化方法，但這不重要了。我們在下面的讨論中将忽略這些“剩餘循環”。
僅應用外層循環展開方法，除了代碼膨脹外我們什麼也沒有得到。然而，現在可以非常容易地使用循環整合方法了：
https://yqfile.alicdn.com/448f86a4376724efb50b2e62df7bbdfe55b58559.png" >
将外層循環展開，然後整合通常稱為展開與合并（unroll and jam）。m路展開與合并實作了寄存器中b每個元素的m次複用，代碼平衡值減小為(m+1)/2m。當m＞1時，該值顯然小于1。如果m取值非常大，由于b加載的次數大為減少，是以可獲得接近兩倍的性能提升。在理想情況下，b隻需加載一次。因為a（大小為n2）隻需加載一次，m路展開與合并的總資料傳輸量為n2(1+1/m)+n。圖3-12顯示了兩路展開的稠密矩陣向量乘的訪存模式。
https://yqfile.alicdn.com/45510f363aa0d7d76bdb6551c66fc9872156f3de.png" >
沖突被大約降低了一半，剩餘的循環在外層調用本例
然而，所有這一切都假設寄存器的壓力不會太大。即假設cpu有足夠多的寄存器來容納循環體内部數量相當可觀的操作數。如果不能，編譯器必須溢出寄存器資料到cache中，這樣會降低計算性能（見2.4.5節）。再一次強調，可用的編譯日志可以幫助确定這種情況。
循環展開與合并在進階别優化上可由有些編譯器自動實作。一個複雜的循環體可能會隐藏一些重要的優化資訊，是以手工優化是必需的：通過手工優化或者編譯器指令來指定像循環展開等進階别轉換。如果可用，編譯器指令是首要選擇的優化方法。這是因為指令比較容易維護且不會導緻明顯的代碼膨脹。可惜的是，編譯器指令本質上是不可移植的。
盡管同稠密矩陣向量乘相比，上節所讨論的矩陣轉置算法沒有直接機會優化資料傳輸（兩個矩陣隻需讀寫各一次），該算法同樣是o(n2)/o(n2)問題的典型執行個體。通過在矩陣轉置算法的“flipped”版本上應用循環展開與合并方法，得到了将近50%的性能提升（參見圖3-8的虛線）。
不要期望m = 4時會有明顯效果，因為基本性能分析沒有發生變化：當n取值中等時，可用的cache行數目足夠可以容納lc列資料。圖3-13顯示了m = 2的情況。每一次加載操作中，cache行中的m個元素可以連續通路。是以，盡管tlb依然太小而不能映射到整個工作集，但還是減少了tlb未命中。
盡管如此，當n取值較大進而使cache不能容納n個cache行的資料時，減少tlb未命中并不能阻止性能的下降。最好能有一個政策重用非連續cache行剩下的lc-m個元素，進而使cache行可以很快替換出去而不需要再次加載。一個“野蠻”方法是lc路循環展開，但是這個方法會導緻寫操作時更大間隔的非連續通路。同時，由于循環展開因子過大，導緻循環體中寄存器使用量的增加（算術操作引起的），是以這并不是一個通用的優化方法。循環分塊（loop blocking）能夠在不增加寄存器使用的情況下實作cache的最優使用。該方法不會減少資料讀取或者寫入操作，但是會增加cache的命中率。對于深度為d的嵌套循環，分塊引入了d個額外的外層循環，将原來的内層循環切分成塊：
https://yqfile.alicdn.com/364ed26c06ba97923040786f6bec9989aac9dc8e.png
" >
在這個例子中，除m路的循環展開與合并外，使用了二維分塊（分塊因子為b）方法。這個變化并沒有改變主循環體，是以并沒有改變儲存操作數的寄存器數目。然而，卻極大改進了cache行的訪存模式，如圖3-14所示，兩路循環展開與44分塊的結合。如果分塊因子選擇恰當，那麼非連續寫操作中的cache行将會在每一個分塊的最後得到充分利用，而且會快速地置換出去。是以，n取值較大時的性能下降現象将不複存在。圖3-8的虛線說明了5050的分塊結合4路循環展開消除了非連續記憶體通路帶來的所有訪存問題。
循環分塊是非常普遍和強大的優化方法，并且編譯器不會自動執行。最佳分塊因子應該通過精心的基準測試實驗獲得。然而，cache的大小也可以指導最佳分塊因子的選擇。即，當對l1 cache分塊時，内層循環中所有分塊的大小總和不應該超過cache大小的一半。究竟對哪一級cache進行分塊依賴于具體的算術操作，這裡沒有通用的指導建議。
3.5.3 o(n3)/o(n2)
如果算術計算量随着問題規模的擴大以一定的因子增長而大于訪存資料量，那麼這類算法具有巨大的優化空間。通過上述優化技術（循環展開與合并、循環分塊）的使用，這類算法性能可能不會受cache限制。這類算法展現了o(n3)/o(n2)特征，稠密矩陣矩陣乘（matrix-matrix multiplication，mmm）和稠密矩陣對角化是這類算法的典型執行個體。開發一個精心優化的mmm程式已經超過了本書的範圍，更不用說特征值計算。但是我們可以通過一個簡單的執行個體（實際o(n2)/o(n)類型）來說明這類算法優化的基本原理。
https://yqfile.alicdn.com/66fc459f3f6388d922ec51340e9ee4dbb6e1e55f.png" >
上面代碼的資料集大小為o(n)，但是卻進行了o(n2)運算（額外調用了foo()函數）。其中b從記憶體中被加載了n次，是以總存資料傳輸量為n(n+1)。使用m路循環展開與合并優化方法後，可将其減少到n(n/m+1)。但是循環展開因子過大的缺點在上節中已經指出。而内層循環的分塊（分塊大小為b）有兩個作用：
b從記憶體中僅加載一次，可使b足夠小以使b個元素可以加載到cache中，直到不需要它們為止。
a加載n/b次，而不是一次。
盡管a通過cache被加載了n/b次，但目前b分塊被置換出cache的可能性非常低。這是因為根據lru置換算法，當該cache行被頻繁使用時是不會被置換出去的。這使得記憶體傳輸非常高效：共傳輸n （n/b+1）個字。因為b的取值可以比典型循環展開因子大許多，是以分塊是最好的優化政策。此外，循環展開與合并方法依舊可以用來增加cache内部（in-cache）的代碼平衡值。基本的n2依賴還是存在的，但是結合前因子可以說明記憶體受限和cache受限程式的差異。當記憶體帶寬和訪存延遲不是性能限制因素時，該代碼是cache受限的。cache受限代碼在特定架構上能否達到預期性能目标依賴于cache大小、cache和記憶體間的資料傳輸速度，當然還有算法本身。
o(n3)/o(n2)算法是經過精心優化、其性能可以接近硬體理論峰值性能的典型候選算法。如果循環分塊和展開因子選擇恰當，則對于n×n的矩陣（當n取值不會過小時），稠密矩陣向量乘的性能經常會達到峰值性能的90%。系統廠商會提供該算法的高度優化版本，一般包含在blas（basic linear algebra subsystem，基本線性代數子系統）庫中。既然循環分塊已經完成了将代碼轉化為cache受限的絕大部分重要工作，為什麼還要應用循環展開方法？這是因為即使所有的資料都位于cache中，但許多處理器架構在每個時鐘周期内也不能持續維持足夠的加載和寫入操作來滿足算術運算的需要。例如，目前英特爾的x86架構處理器每個時鐘周期内隻能進行一次資料加載和一次寫入操作，這就使得當核心的循環嵌套使用多于一個資料加載操作時（特别是上例中o(n2)/o(n)算法的cache受限分塊），就需要使用循環展開與合并方法。
這裡的讨論是出于教育目的，是以沒有必要手工編寫和優化标準線性代數和矩陣操作。這些函數一般總是從高度優化的函數庫中調用。盡管如此，這裡讨論的優化方法是能夠應用到許多實際代碼中去的。稀疏矩陣向量乘就是一個有趣的例子（見3.6節）。