2009年7月22日 星期三

Cache的妙用

基本上, Cache最重要的兩個原理是:

1. 長江後浪推前浪 (Temporal locality)
2. 一人得道, 雞犬昇天 (Spatial locality)

熟悉Cache原理的人大概可以瞭解這兩個比喻吧!

第一點其實是讓Cache可以這麼小卻這麼好用的原因, 因為小小的Cache後宮裡留存的都是最年輕最有希望的辣妹, 而剛好程式這傢伙是個喜新厭舊的咖, 自然臨幸的幾乎都是這些年輕辣妹了, 老掉的貨色通通推到冷宮去, 也就是 DRAM , 太老的甚至還會被貶到硬碟去睡覺.

第二點可以這麼解釋: 當某某年輕辣妹被選入宮中, 風風光光地進入程式皇帝的Cache後宮, 跟她住在一起的姐妹們也會順便一起被帶進Cache, 因為程式是個貪心的咖, 經常連姐妹都不放過的. 而"順便帶入後宮"的動作其實非常地重要, 因為如果每次都只招一名女子進宮, 恐怕滿足不了程式皇帝的味口. 總不能等到他想換口味的時後再去找吧? 因為每次要從DRAM帶新鮮的辣妹進宮需要花不少時間的 (access latency) , 所以要未雨籌謀, 順道多帶幾個辣妹 (pre-fetch的觀念). 當然, 這些順便帶的不見得合程式皇帝的味口, 可能很快就會再度被打回去.

以上對Cache的說明, 接下來我們根據這些特性來探討performance是如何被Cache提昇的.
所謂的performance, 就是要無時無客滿足程式, 不能讓他等太久

我們先假設程式的口味沒那麼挑, 所有順便一起帶入宮的他都會臨幸.
如果一條cache line裡面有4筆data(四金釵), 那麼其中有一筆一定是程式想要換換口味嘗鮮時,才千辛萬苦地大老遠從DRAM搬進來的, 這段時間是程式一定要等的. 如果程式對每個辣妹都只臨性一次, 就代表四次會有一次要等. hit rate = 75%. 但是如果程式對每個辣妹都臨性兩次, 就代表八次才會有一次要等, hit rate = 87%. 如果是三次呢, hit rate 可達九成.

但是, 我們只知道程式老大的口味, 大致上是
1. 喜歡年輕的 (Temporal locality)
2. 姐妹也不放過 (Spatial locality)
但是我們不知道他會不會有時後又想找熟女, 結果又得到DRAM去找;
我們也無法預期順便帶回的姐妹是不是恐龍, 程式要不要?
此外, 我們更無從得知程式對同一位辣妹會臨幸幾次...

這些都不是硬邦邦的硬體能預知的, 但這些確實對hit rate有莫大的影響.

cache的電路再怎麼做, 也無法改變這些變數, 只能期待程式老大儘量配合了.

不過, 如果每次去DRAM都能順便多帶些年輕辣妹回宮, 對於hit rate的提升會有蠻大的幫助的. 另外, 所謂汰舊換新的規則(LRU), 如果能做到true LRU, 也會比較營合程式老大的口味才對.

最後, 歸納幾點是硬體可以改善的:
1. Cache Size 變大 (連熟女也留下)
2. True LRU (不要把年輕的踢出卻留下老的)
3. Cache Line 加長 (一次順便帶回更多)

特別注意的是第三點, 一次順便帶回更多就代表Line Fill 的時間可能會變長, 如果Line Fill與正常的Memory access可以independant的話會比較好!





沒有留言: