計(jì)算機(jī)組成原理課外實(shí)踐報(bào)告

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

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

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

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

5、e中對(duì)應(yīng)數(shù)據(jù)塊沒(méi)有被訪問(wèn)的時(shí)間。在全相聯(lián)映射方式下，Recent[i](0=i=15)的初始值為0，被命中的Cache的第i行的記錄Recent[i]=0，j（0=j=15）不為i的第j行的記錄Recent[j]的值加1，當(dāng)需要替換時(shí)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）當(dāng)?shù)趇組的第j塊命中時(shí)：Recent1[i][j]=0，而第i組沒(méi)有命中的另一塊的值加1其余組的Recent1[i][j]值保持不變。當(dāng)?shù)趇組已經(jīng)被數(shù)據(jù)塊填滿，而新的被訪問(wèn)的數(shù)據(jù)不在Cache中且需要映射到第i組時(shí)第i組中Recent1[i][j]值較大的第j行被替換掉，然后Recent1[i][j]=0，Recent1[i][1j]的值加1。最不經(jīng)常使用LFU算法將一段時(shí)間內(nèi)被訪問(wèn)次數(shù)最少的那行數(shù)據(jù)替換出，為此

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