詳細的題目要求和實驗資源可以到教材官網 或者 課程官網 擷取。 本次實驗難點在Part B的64 * 64部分，主要介紹這一部分。
<code>getopt</code>和<code>fscanf</code>系列庫函數對于這次實驗很重要，不太明白的可以<code>man</code>一下，或者參考這兩篇文章：
Linux下getopt()函數的簡單使用
C 庫函數 - fscanf()
1.由于我們的模拟器必須适應不同的s, E, b，是以資料結構必須動态申請（malloc系列），注意初始化。
2.測試資料中以“I”開頭的行是對指令緩存（i-cache）進行讀寫，我們編寫的是資料緩存（d-cache），這些行直接忽略。
3.這次實驗假設記憶體全部對齊，即資料不會跨越block，是以測試資料裡面的資料大小也可以忽略。
4.為了使得評分程式正常運作，<code>main</code>函數最後需要加上：
5.建議把<code>-v</code>這個選項也實作了，這樣自己debug的時候也友善一些。另外，可以先從規模小的測試資料開始，然後用大的。
1.這次實驗隻要求我們測試hit/miss/eviction的次數，并沒有實際的資料存儲 ，是以我們不用實作line中的block部分。
2.這次實驗要求使用LRU（least recently used），即沒有空子產品（valid為0）時替換最早使用的那一個line。是以我們應該在line中實作一個能夠記錄目前line最後一次寫入的時間參量，每次”寫入“line的時候就更新一下該參量。（這一點csapp上沒有詳細說）
3.綜上，結合書上對cache的描述，我們可以得到如下資料結構：
注意到cache（sets的入口）和set（lines的入口）都是用指針實作的，sets構成一個指針數組，因為它們不含任何資料，唯一的用處就是通過偏移量尋找到指定的line。
下面結合代碼執行的順序對我實作的程式進行解釋，由于寫了很多注釋，就不詳細的說了（我的sublime寫不了中文，就用的英文注釋的，文法有錯還請指出）
更新：一航介紹了一個插件，可以解決Ubuntu下sublime中文輸入的問題
--> sublime-text-imfix
頭檔案：
為什麼要包含該頭檔案的原因在右側注釋中寫出來了。由于我們實驗使用的64位位址，是以将tag和set的索引用64位儲存就足夠了，我這裡使用了C99中的固定長度類型uintN_t，可移植性好一些。另外要注意的是，C99必須包含unistd.h和getopt.h兩個頭檔案才能正常使用<code>getopt</code> 。
宏定義：
我喜歡用_Bool+宏定義true和false，你也可以使用stdbool.h。
資料結構類型定義：
time_counter初始化的時候都是0，其值越大代表這個line最近剛剛被寫入——我們不應該替換它——是以valid為0的line的time_counter一定也是0（最小值），因為他們連使用都沒有被使用過，即我們一定會先替換valid為0的line，這符合書上的政策。
我将結果設計成了一個結構體，這樣函數友善傳回一些。（少用全局變量）
main函數的資料類型：
注釋已經寫的很清楚了，我解釋一下help_message的寫法，有的同學可能不知道C中字元串的寫法：兩個字元串中間隻有空格，C編譯器會自動将它們合并。例如：
那麼test_string就會是“hello world”。
另外，在C中，一行寫不下的時候可以使用\字元隔開，編譯器會自動合并的。
main函數讀取參數：
關于<code>getopt</code>的用法可以參考文章開頭的文章；<code>perror</code>和<code>fopen</code>的用法請<code>man</code>一下，fopen失敗後會設定errno的。
如果讀取的參數中沒有s或者b或者E或者檔案，那麼那他們将會是對應的初始值。
main函數調用函數并結束程式：
<code>InitializeCache</code>是用來動态申請資料結構的，<code>ReadAndTest</code>是本程式的核心，用來測試hit/miss/eviction的次數。另外不要忘記或者重複釋放記憶體。下面分别介紹這三個函數。
我們首先根據S（set的數目）申請一個數組，該數組元素是lines的入口的指針。接着循環S次每次申請E個line資料結構，并讓剛剛的指針數組的元素指向它們：
釋放之前申請的記憶體：
不解釋。
核心部分，測試hit/miss/eviction的次數：
如果指令是“L”或者“M”，我們就進入<code>HitMissEviction</code>一次判斷其是否hit或者miss以及是否發生替換，如果是M就相當于一次“L”和一次“M”，需要進入<code>HitMissEviction</code>兩次，其結果可能為兩次hit，也可能為一次miss+(eviction）一次hit。我們在<code>ReadAndTest</code>裡通過一些位運算找到對應的set（即entry_of_lines），然後以此作為參數調用<code>HitMissEviction</code> 判斷到底是miss（有沒有eviction）還是hit。
<code>HitMissEviction</code>裡面需要注意的地方是時間參量的更新，我們既要找到最“老”的line，也要同時記住最“新”的line的時間參量（我這裡是周遊搜尋，也可以在設計set的資料類型時設計為結構體，其中放一個最新的時間參量），以此來更新時間參量。如果我們要替換的line的valid為1，則發生了一次eviction。
partA完整代碼下載下傳
運作結果：
轉置矩陣
最簡單的轉置實作：
1.最多隻能定義12個局部變量。
2.不允許使用位運算，不允許使用數組或者malloc。
3.不能改變原數組A，但是可以修改轉置數組B。
1.block的大小為32byte，即可以放下8個int，即miss的最低限度是1/8。
2.cache的大小為32*32，即32個block，128個int。
3.blocking是一種很好的優化技術，這次實驗基本就靠他了；）其大緻概念為以資料塊的形式讀取資料，完全利用後丢棄，然後讀取下一個，這樣防止block利用的不全面。可以參考卡耐基梅隆的一篇文章：waside-blocking
4.盡量将一個block讀入完全或者寫入完全，例如假設一個block可以放兩個數，進行如下轉置操作，其讀取時“盡力”讀取，完全利用了一個block，但是在寫入的時候浪費了1/2的空間。
5.盡量使用剛剛使用的block（還是“熱乎的”），因為它們很可能還沒有被替換，hit的機率會很大。
6.讀出和寫入的時候注意判斷這兩個位置映射在cache中的位置是否相同，（我們這個cache是直接映射，一個set隻有一個block，是以絕大部分的miss伴随着替換），也可以說，我們要盡量避免替換的發生。
下面我結合實驗要求的三個例子具體講。
32 × 32 (M = 32, N = 32)
由于我們的block能存8個int，是以blocking的資料塊最好是以它為機關的，這樣能盡可能利用block，例如8 * 8或者16 * 16。
在32*32的情況中，一行是32個int，也就是4個block，是以cache可以存8行，由此可以推出映射沖突的情況：隻要兩個int之間相差8行的整數倍，那麼讀取這兩個元素所在的block就會發生替換，再讀後面連續的元素也會不斷發生抖動（thrashing）下圖中标出了與一個元素沖突的位置（包括他自己本身的位置，因為我們A，B兩個數組在記憶體中是相鄰的，而32*32又是cache的整數倍。）：
但是轉置的過程中這樣的情況會發生嗎？圖中的BCD三點對于A來說僅僅是行差了8K，這在轉置中是不可能發生的！因為轉置是将A[i][j]送到B[j][i]，不會有B[i][j+8k]的情況出現。
但是對于A點而言，如果A[i][j]中i = j，那麼B也會是B[i][j]，即映射遇到同一個block中，而當i = j的時候，就是對角線的情況：
是以現在我們隻要單獨處理對角線的情況就可以啦，這裡有兩種處理方法：
由于我們可以使用12個局部變量，是以我們可以用8個局部變量一次性将包含對角線int的block全部讀出，這樣即使寫入的時候替換了之前的block也不要緊，因為我們已經全部讀出了。
我們用一個局部變量暫時先儲存這個對角線元素，并用另一個變量記錄它的位置，待block的其他7個元素寫完以後，我們再将這個會引起替換的元素寫到目的地。
下面的代碼使用第一種方法，另外，由于相差8行就會有沖突，是以我們blocking的時候用8*8的資料塊。
64 × 64 (M = 64, N = 64)
此時，數組一行有64個int，即8個block，是以每四行就會填滿一個cache，即兩個元素相差四行就會發生沖突。
如果我們使用4*4的blocking，這樣固然可以成功，但是每次都會有1/2的損失，優化不夠。如果使用剛剛的8*8的blocking，那麼在寫入的時候就會發生沖突：
這個時候可以使用一下“divide and conquer”的思想，我們先将8*8的塊分成四部分：
本來我們是要将右上角的2移動到左下角的3的（轉置），但是為了防止沖突我們先把他們移動到2的位置，以後再來處理：
對于3和4，我們采取一樣的政策，就可以得到如下結果，在這個過程中沒有抖動的發生：
這個時候再将23互換就可以啦。
但是，測試以後并不能滿足優化的要求，說明我們将23轉換的時候（或是之後）又發生很多miss，是以我們應該在将右上角的34轉換的過程中将2的位置複原，這裡的複原是整個實驗中最具技巧性的，由前面的要點5：盡量使用剛剛使用的block（還是“熱乎的”），因為它們很可能還沒有被替換，hit的機率會很大。我們在轉換2的時候逆序轉換：
同時在讀取右上角34的時候按列來讀，這樣的好處就是把2換到3的過程中是從下到上按行換的，因為這樣可以先使用“最熱乎”的block：
接着轉換：
最後的效果：
61 × 67 (M = 61, N = 67)
這個題隻要求miss < 2000，比較寬松。
這個時候由于不對稱，是以也不存在相差4行就必定沖突的情況，我們可以試一下16 * 16這種blocking。但是“對角線”的元素（橫坐标等于縱坐标）肯定還是會沖突的（其實這個時候不是對角線了，因為不是正方形）。我們在這裡用32*32分析中的第二種方法。
partB完整代碼下載下傳
最終結果為滿分：