緩存是現(xiàn)代計(jì)算機(jī)的重要部件，了解緩存的工作機(jī)制可以編寫出緩存友好的程序，提高程序的速度。

partA

實(shí)現(xiàn)一個(gè)緩存模擬器，需要了解緩存的工作細(xì)節(jié)，完成后可以對(duì)緩存有更深入的理解。這個(gè)實(shí)現(xiàn)沒有唯一的答案，不同的人實(shí)現(xiàn)方式都有差別。相對(duì)難點(diǎn)是實(shí)現(xiàn)LRU替換，如果換錯(cuò)了行會(huì)導(dǎo)致后邊緩存行為的一系列錯(cuò)誤。具體原理書里已經(jīng)講的非常詳細(xì)了，相信只要理解了實(shí)現(xiàn)起來比較容易。我的代碼見附1，需要的可以參考。

對(duì)于我代碼的幾點(diǎn)說明：

1、 我把行中的有效位和標(biāo)記位放到了一個(gè)64位的變量中，有效位在最低位，標(biāo)記位是高63位；

2、 組中的每一行用一個(gè)數(shù)字表示其訪問情況，數(shù)字最大（E-1）的表示剛剛訪問過，數(shù)字最?。?）表示距上次訪問最久遠(yuǎn)，每次命中、miss、替換都要調(diào)整。

3、 模擬實(shí)際不需要為block分配空間，只需要有效位和標(biāo)記即可，我剛開始不知道就分配了，后續(xù)懶得改了。

?

partB

這個(gè)稍微有點(diǎn)難度，同樣考察對(duì)緩存的理解，不過是從應(yīng)用的角度。即便在partA中實(shí)現(xiàn)了緩存模擬器，到應(yīng)用階段還是會(huì)遇到很多問題，可見一個(gè)概念想要真正熟悉需要從不同的角度不斷練習(xí)。

這部分的核心思想是數(shù)據(jù)加載到行中，應(yīng)用盡用，盡可能讓這行數(shù)據(jù)只加載這一次，以后就不需要再換回來。

緩存大小是1k，塊大小是32字節(jié)，矩陣元素是int型，4字節(jié)，所以一個(gè)塊可以放8個(gè)數(shù)，根據(jù)前面的原則，在處理時(shí)要盡可能一次處理8個(gè)數(shù)。另外還有個(gè)技術(shù)是blocking（分塊），利用分塊可以減少miss數(shù)，具體原理可以看這篇官方手冊(cè)推薦的文章http://csapp.cs.cmu.edu/public/waside/waside-blocking.pdf。

緩存只有1k，所以對(duì)于32x32的矩陣可以緩存8行而沒有沖突，64x64的矩陣可以緩存4行而沒有沖突。由于有這個(gè)區(qū)別，很多人的處理方法是分開處理，32x32專門寫一個(gè)程序，64x64專門寫一個(gè)，61x67專門寫一個(gè)。當(dāng)然這樣可以拿滿分，不過我覺得不夠優(yōu)雅，所以我想用一個(gè)程序?qū)崿F(xiàn)對(duì)三種矩陣的處理，最后雖然沒有拿到滿分（差0.1），但是卻收獲滿滿。

具體的方法真的不太容易想到，我也是網(wǎng)上看到再優(yōu)化的，下面具體來說說。

我們的目的是從矩陣A變到矩陣B，先來分析哪些情況可能會(huì)出現(xiàn)問題。

如果一次一行處理8個(gè)數(shù)，32x32沒什么問題，但是64x64不行，存前4個(gè)數(shù)B加載前4行，但是存后4個(gè)數(shù)的時(shí)候，由于64x64一次只能緩存4行，所以矩陣B的后四行會(huì)與前4行發(fā)生替換，下一次還會(huì)重復(fù)這個(gè)過程，這樣一直換入換出很明顯命中率不高。

如果一次處理4個(gè)數(shù)，而緩存一行可以加載8個(gè)數(shù)，很明顯緩存利用率只有1/2，剩下的4個(gè)數(shù)在處理前很可能會(huì)被換出去，下次處理再加載回來，命中率還是不高。

還有一種情況是A和B的某些地址位于相同的行，這樣存B的時(shí)候會(huì)把A換出去，下次讀A的數(shù)據(jù)又要加載進(jìn)來，這樣的命中率也會(huì)下降。

針對(duì)以上問題，我們提出以下方案，

1、 首先分塊是8x8，一次大循環(huán)處理8行8列，8x8的塊進(jìn)一步分成4x4的塊；

2、 用8個(gè)中間變量存需要處理的數(shù)據(jù)，這樣即便有沖突被換出去也沒關(guān)系；

3、 用B的空間暫存A后四個(gè)數(shù)據(jù)，這樣A即便被換出去也沒關(guān)系；

具體過程如下：

1、 先處理前4行8個(gè)數(shù)，前4列正常處理，A的后4列轉(zhuǎn)置后暫存在B的后4列中。

?這里我們可以發(fā)現(xiàn)，B右上角黃色塊的數(shù)據(jù)就是最終B紫色塊的數(shù)據(jù)，接下來我們想辦法復(fù)制過去就行。

2、 下面的一系列處理很巧妙，充分利用了緩存的特點(diǎn)。

先把B的第一行后4列暫存到臨時(shí)變量中，把A的后4行的第一列存到臨時(shí)變量中，如果是64x64，此時(shí)A的前4行被換了出去，緩存中是A的后4行；

?將暫存的A數(shù)據(jù)存到B的第一行后4列，此時(shí)B的第一行已經(jīng)是最終的數(shù)據(jù)；

取出A的后四行的第5列存入臨時(shí)變量中，此時(shí)A的后四行位于緩存中，可以命中。

將臨時(shí)變量的值存到B的第5行。如果是64x64，此時(shí)B的第5行會(huì)把第一行從緩存中換掉，而第一行已經(jīng)是最終的數(shù)據(jù)，換出去也沒關(guān)系。

以此類推，將上述過程再重復(fù)三次，處理剩下的數(shù)據(jù)。此過程充分利用了緩存中的數(shù)據(jù)，換出去的行以后不會(huì)再訪問，大大提高了緩存命中率。

對(duì)于61x67，由于行列不是8的整數(shù)倍，所以經(jīng)過上面的處理后會(huì)有遺漏，需要單獨(dú)處理。對(duì)于列，一次取出一列8個(gè)數(shù)據(jù)，實(shí)測這樣的命中率對(duì)于沒對(duì)齊的矩陣命中率很高，對(duì)于剩余的行，同樣按列讀取，按行存命中率要高。

使用上面的方法，測試結(jié)果如下：

32x32和64x64的表現(xiàn)都很好，61x67多了10個(gè)miss，這10個(gè)miss實(shí)在不知道怎么優(yōu)化了。

具體實(shí)現(xiàn)的代碼如下

?這個(gè)lab個(gè)人覺得還是有點(diǎn)難度的，尤其是之前完全不了解緩存機(jī)制的情況下，更是讓人迷惑。不過，正是有這些疑惑，才逼自己一行行的分析trace，看看程序的實(shí)際行為如何，進(jìn)而發(fā)現(xiàn)問題，找到解決的辦法，這個(gè)過程中也不斷的加深了對(duì)緩存的理解和認(rèn)識(shí)。

附1：