計算機組成原理課外實踐報告

1、計算機組成原理課外實踐報告Cache的不同映射算法2011年12月28日星期三一一實驗目的實驗目的1.加深掌握Cache的三種地址映射方式，即全相聯(lián)映射、直接映射和組相聯(lián)映射的映射原理和不同映射方式下主存的邏輯劃分。2加深理解替換Cache原存數(shù)據(jù)塊的四種算法，即先進先出FIFO(FirstInFirstOut)算法、近期最少使用LRU(LeastRecentlyUsed)算法、最不經(jīng)常用LFU(LeastFrequentlyUsed)

2、算法和隨機替換(RomReplacement)算法的算法原理和算法過程。圖11假定的主存和Cache容量及劃分（3）直接映射方式主存塊和Cache塊是一一對應的，所以不需要選擇替換算法，換而言之四種替換算法只有在映射方式是全相聯(lián)映射和二路組相聯(lián)映射時才起作用。先進先出FIFO算法的基本思想是按照數(shù)據(jù)進入Cache的先后決定替換的順序，即在需要替換的時候，選擇最先調(diào)入Cache的塊作為替換塊，這種方法要求為Cache中每塊數(shù)據(jù)記錄他們進入

3、Cache的先后次序，在程序設(shè)計時，使用兩個數(shù)組Number[16]、Number1[8][2]分別記錄在全相聯(lián)映射方式下和二路組聯(lián)的方式下的數(shù)據(jù)進入的次序。在全相聯(lián)映射方式下，Number[16]數(shù)組中元素的值，根據(jù)進入Cache的先后次序分別為123…1516Cache被數(shù)據(jù)填滿之后Number[i]為1的塊被替換掉，新的被替換第i行的Number[i]值為16，其余每個值都減1，其中0=i=15；在二路組相聯(lián)映射方式下，Numbe

4、r[i][0]和Number[i][0]值，根據(jù)進入Cache的先后次序分別為12當Cache的第i組數(shù)據(jù)需要替換時Number[i][j]的值1的第i組的第j塊被替換，Number[i][j]的值為2，更改Number[i][1j]的值為1。近期最少使用LRU算法是將近期內(nèi)長久沒有被訪問過的行換出。為此在本次程序設(shè)計過程中使用了Recent[16]和Recent1[8][2]兩個數(shù)組分別來記錄在全相聯(lián)映射和二路組相聯(lián)映射方式下Cach

5、e中對應數(shù)據(jù)塊沒有被訪問的時間。在全相聯(lián)映射方式下，Recent[i](0=i=15)的初始值為0，被命中的Cache的第i行的記錄Recent[i]=0，j（0=j=15）不為i的第j行的記錄Recent[j]的值加1，當需要替換時Recent[i]值最大的第i行被替換，然后Recent[i]=0，而另外的j（0=j=15）不為i的第j行的記錄Recent[j]的值加1；在二路組相聯(lián)映射方式下，Recent1[i][j]的初始值為0（

6、0=i=7，0=j=1）當?shù)趇組的第j塊命中時：Recent1[i][j]=0，而第i組沒有命中的另一塊的值加1其余組的Recent1[i][j]值保持不變。當?shù)趇組已經(jīng)被數(shù)據(jù)塊填滿，而新的被訪問的數(shù)據(jù)不在Cache中且需要映射到第i組時第i組中Recent1[i][j]值較大的第j行被替換掉，然后Recent1[i][j]=0，Recent1[i][1j]的值加1。最不經(jīng)常使用LFU算法將一段時間內(nèi)被訪問次數(shù)最少的那行數(shù)據(jù)替換出，為此

7、在本次程序設(shè)計過程中使用了Time[16]和Time1[8][2]兩個數(shù)組分別來記錄在全相聯(lián)映射和二路組相聯(lián)映射方式下Cache中對應數(shù)據(jù)塊有被訪問的次數(shù)。在全相聯(lián)映射方式下，Time[i](0=i=15)的初始值為0，被命中的Cache的第i行的記錄Time[i]的值加1，j（0=j=15）不為i的第j行的記錄Time[j]的值加1，當需要替換時Time[i]值最小的第i行被替換，然后Time[i]=1，而另外的j（0=j=15）不為