ps<<eof
丫的,我翻閱了一下《計算機系統結構》的書，把cache那章閱讀了下！
發現了新大陸，對自己當時學到的知識的領悟和體會似乎有了新的感受！計算機專業課，其實我都挺認真的學過的，哈哈，隻不過......
我把我覺得有用的摘錄下！！
為什麼好多那麼些開源滴優秀滴代碼讀不懂咧, 語言不熟練和算法素養很低是一方面, 其實還有好多方面…偶還是太菜了…
eof
許多相關cache的研究都緻力于降低cache的失效率。這裡就讨論這個！
按照産生失效的原因不同，可以把失效分為以下3類（簡稱為"3c"）:
(1). 強制性失效 (compulsory miss): 當第一次通路一個塊時，該塊不在 cache中, 需從下一級存儲中調入 cache, 這就是強制性失效。這種失效也稱為冷啟動失效，或首次通路失效。(增加塊大小，預取)
(2).
容量失效 (capacity miss): 如果程式執行時所需的塊不能全部調入 cache 中, 則當某些塊被替換後, 若又重新被通路, 就會發生失效。這種失效稱為容量失效。(增加容量) 抖動現象。
(3).
沖突失效 (conflict miss): 在組相聯或直接映像 cache 中, 若太多的塊映像到同一組(塊)中，則會出現改組中某個塊被别的塊替換、然後又被重新通路的情況。這就是發生了沖突失效。這種失效也稱為碰撞失效 (collision) 或幹擾失效
(interference)。(提高相聯度)
(1) 相聯度越高，沖突失效就越少。
(2) 強制性失效和容量失效不受相聯度的影響。
(3) 強制性生效不受 cache 容量的影響，但容量失效卻随着容量的增加而減少。
(4) 表中的資料符合 2:1 的 cache 經驗規則，即大小為n的直接映像 cache 的失效率約等于大小為 n/2 的 2 路組相聯 cache 的失效率。
前面所介紹的技術(增加塊大小、增加cache容量、提高相聯度、僞相聯、硬體預取以及預取指令等)都需要改變或者增加硬體。下面介紹的方法，無需對硬體做任何改動就可以降低失效率。或許，這也是能對我們的程式效率有幫助的地方！
我們能很容易地重新組織程式而不影響程式的正确性。例如，把一個程式中的幾個過程重新排序，就可能會減少沖突失效，進而降低指令失效率。mcfarling研究了如何使用記錄資訊來判斷指令組之間可能發生的沖突，并将指令重新排序以減少失效。他發現，這樣可将容量為2kb、塊大小為4kb的直接映像指令cache的失效率降低50%；對于容量為8kb的
cache，可将失效率降低75%。他還發現當能夠是某些指令根本就不進入 cache 時，可以得到最佳性能。但即使不這麼做，優化後的程式在直接映像 cache 中的失效率也低于未優化程式在同樣大小的8路組相聯映像 cache 中的失效率。
資料對存儲位置的限制比指令對存儲位置的限制還要少，是以更便于調整順序。我們對資料進行變換的目的是改善資料的空間局部性和時間局部性。例如，可以把對資料的運算改為對存放在同一 cache 塊中的所有資料進行操作，而不是按照程式員原來随意書寫的順序通路數組元素。
這種技術通過提高空間局部性來減少失效次數。有些程式同時用相同的索引來通路若幹數組中的同一維。這些通路可能會互相幹擾，導緻沖突失效。我們可以這樣來消除這種危險：将這些互相獨立的數組合并成為一個複合數組，使得一個 cache 塊中能包含全部所需的元素。
/* 修改前 */
/* 修改後 */
這個例子有一個有趣的特點：如果程式員能正确地使用記錄數組，他就能獲得與本優化相同的益處。
有些程式中含有嵌套循環，程式沒有按照資料在存儲器中存儲的順序進行通路。在這種情況下，隻要簡單地交換循環的嵌套關系，就能使程式按資料在存儲器中存儲的順序進行通路。和前一個例子一樣，這種技術也是通過提高空間局部性來減少失效次數，重新排列通路順序使得在一個 cache 塊被替換之前，能最大限度地利用塊中的資料。
修改前程式以100個字的跨距通路存儲器，而修改後的程式順序地通路一個 cache 塊中的元素，然後再通路下一塊中的元素。這種優化技術在不改變執行的指令條數的前提下，提高了 cache 的性能。
簡單測試:
編譯:
> gcc -wall a.c -o a
> gcc -wall b.c -o b
結果: //沒看cpu的情況,看起來貌似有效。。。
有些程式含有幾部分獨立的程式段，它們用相同的循環通路同樣的數組，對相同的資料做不同的運算。通過将它們融合為單一的循環，能使讀入 cache 的資料在被替換出去之前，得到反複的使用。和前面的兩種技術不同，這種優化的目标是通過改進時間局部性來減少失效次數。
修改前的程式在兩個地方通路數組a 和 c，一次是在第一個循環裡，另一次是在第二個循環裡。兩次循環分隔較遠，可能會産生重複失效，即在第一個循環中通路某個元素失效之後，雖已将相應塊調入 cache，但在第二個循環中再次通路該元素時，還可能産生失效。而在修改後的程式中，第二條語句直接利用了第一條語句通路 cache 的結果，無需再到存儲器去取。
這種優化可能是 cache 優化技術中最著名的一種，它也是通過改進時間局部性來減少時效。下面仍考慮對多個數組的通路，有些數組是按行通路，而有些規則是按列通路。無論數組是按行優先還是按列優先存儲，都不能解決問題，因為在每一次循環中既有按行通路也有按列通路。這種正交的通路意味着前面的變換方法，如内外循環交換，對此軍無能為力。
分塊算法不是對數組的整行或整列進行通路，而是對子矩陣或塊進行操作。其目的仍然是使一個 cache 塊在被替換之前，對它的通路次數達到最多。下面這個矩陣乘法程式有助于我們了解為什麼要采用這種優化技術。
還有好多
#堅持：有一定的理論素養，卻又始終以實踐為本！