一種採用lru替換算法的緩存的製作方法

2023-04-28 11:08:36 2

專利名稱：：一種採用lru替換算法的緩存的製作方法
技術領域：
：本發明涉及Cache(緩存)，特別是一種採用LRU(LeastRecentlyUsed,最長時間沒有被用到)替換算法的緩存。
背景技術：
：緩存的組織，從存儲器映像的角度來看，主要有全相聯映像法、直接映像法和組相聯映像法。全相聯映像法的基本思想是把一個主存塊的地址(塊號)和塊的內容都拷貝到緩存行中；由於塊地址也保存在緩存中，因此可以拷貝到緩存中的任意位置。此法的優點是靈活，但是查找比較困難，而且硬體的實現較為困難。直接映像法的基本思想是一個主存塊只能拷貝到緩存中固定的行內。該按硬體成本低，但是由於一個緩存行要對應多個主存塊，在使用中當這些主存塊需要同時調入緩存時將發生衝突、增加調入調出的開銷。組相聯映像法是上述兩種方法的折衷方案。其基本思想是把緩存分為m個組(set),每個組分為n行。主存塊分配時對組是固定的、而在組內的位置可以任意。這樣就綜合了兩者的優點，這是目前最常用的方法。這種組織的緩存就叫做n路(Way)組相聯的緩存。由於緩存的容量總是遠小於下一級存儲器的容量，因此緩存中只能是下級存儲器的部分映像。為了使下級存儲器的內容都能在需要時拷貝到緩存中，必須隨時替換緩存內容即把當前不需要的內容調出緩存，騰出空間，調入當前需要的內存塊。在這種調入調出方法中，最重要的是替換的策略，即在需要時選擇緩存中的哪些行調出，再調入所需的內存塊。這種替換策略通常稱為替換算法，它是由硬體實現的。如果算法選擇不當，將大大增加調入調出的頻度。例如把一個當前不需要但是很快就將使用的行調出，必然會降低系統的效率。目前最常見的調度算法有隨機、循環、LRU算法等3種，其中LRU算法是最佳的現有LRU算法的通常實現方法是為每行設置一個計數器，命中行的計數器清零，其它各行中計數器加1。當需要替換時淘汰行計數器計數值最大的數據行出局。以最為常見得4路緩存為例來說，每一組有4行，每行設置一個計數器，計數器至少必須是2位位寬用於區別4行。這樣一個組就需要至少8位寄存器來實現LRU算法。此外，還需要一個比較器和選擇器來選出數值最大的數據行。由於緩存中組的數量通常比較大，這樣實現LRU算法就需要大量的寄存器，也就是說會佔用比較多的晶片面積資源。
發明內容本發明的目的在於提供一種採用LRU替換算法的緩存，主要解決現有緩存實現LRU算法需要大量的寄存器的技術問題，它不但能節省硬體成本，而且也不會佔用比較多的晶片資源。為實現上述發明目的，本發明是這樣實現的一種採用LRU替換算法的緩存，其特徵在於對緩存中每組的所有緩存行的被訪問時間相互關係的狀態進行編碼，並將上述狀態位編碼存儲於寄存器中以用於實現LRU替換算法。該狀態位編碼中的某幾位直接表示最長時間沒有訪問過的緩存4亍號。該寄存器位數N與每組的緩存行n之間的數值關係是N是滿足2N>=n!的最小整數，或者說整數N滿足2N〉=n!>2N"藉由上述技術方案，本發明的優點是本發明直接對所有緩存行的被訪問時間相互關係的狀態進行編碼，編碼直接顯示出最長時間沒有被用到的緩存行的行號，而且狀態改變邏輯電路可以給所有組共用，因此，在不降低緩存性能前提下，大大減少了LRU實現的面積需求，同時也降低了功耗。圖1是本發明的原理圖2是狀態寄存器的狀態改變邏輯實現示意圖。具體實施例方式本發明提供了一種採用LRU替換算法的緩存，與現有技術不同的是本發明不採用每行實現一個計數器的方法，而對整個組的狀態進行分析和編碼。以4路緩存為例，由於我們只關心4行之間的未被使用時間的長短相互關係，而不關心具體的訪問次數。所以可以不必具體計數。對於4行的一個組，一共有4!-24種可能出現的關係。所以我們只需要5位寄存器來記錄這24種可能的狀態(24<24L3;{S4}為0表示L2<L30321011101—13120110112320111100331021101043021110015301211000623101011172130100118230110110921031001010203110001112013,012mo01111131230011011413020111015120301100161032o薩17102301000tableseeoriginaldocumentpage7如表1所示編碼完全地直觀地描述了每一行的排序地位，{S0,S1}直接表示出最長時間未被使用的行的編號。不需要比較器和選擇器來選擇某一行。對於每一個組(Set),實現LRU替換的寄存器需求大大減少。由於寄存器少了，功耗也有相應降低。狀態字改變邏輯由組合邏輯實現，所以這個編碼的實現不會帶來緩存性能的損失。而且由於同一時刻只有一行會被更新，所以只需要一套這樣的組合邏輯電路，它可以被所有組(set)所共享。同時這套編碼也非常適合於實現對路(CacheWay)的鎖定。無論鎖定/解除鎖定時都不需要對狀態字進行特殊修改，對最長時間未被使用行的選擇也如同沒有發生鎖定時一樣容易。圖1是本實施例的一個4路組相聯緩存，其中狀態寄存器的狀態字表示了當前組內4個緩存行的被訪問時間的排序關係。如圖所示在(l)發生時，狀態字為Ollll，前2位01表示當前最長時間沒有被訪問過的是緩存行1，所以應該替換緩存行1。對於(1)的例子，發生在CPU訪問0x0000地址，而該地址所能夠存放的組0中沒有這個地址的數據而且所有的緩存行都存放著其他數據。(2)表示在(1)發生之後，狀態字發生變化，先前的01111對應於表1中排序的1320,當1中的數據被訪問後，排序變化為3201對應表1中狀態字11100。所以狀態字變化為11100。(3)中的變化是由CPU訪問到緩存行0中的數據引起的。先前的11100對應於排序3201,當0中的數據被訪問後，排序變化為3210對應表1中狀態字11101。所以狀態字變化為11101。圖2是本實施例的狀態寄存器的狀態改變邏輯電路實現示意圖，可以用實現有限狀態機的方法來實現。因為同一時刻只會有一個組被訪問到，所以這個組合邏輯電路是可以被所有的組(set)所共用。組合邏輯的實現，必須^T艮據這個緩存設計的具體功能來決定。比如是否有緩存鎖定功能等等。如上所述，本發明如果不考慮編碼中的某幾位直接表示最長時間沒有訪問過的緩存行號，只需把n!個狀態與2N個碼中的n!——對應即可。如果考慮編碼中的某幾位(任意)直接表示最長時間沒有訪問過的緩存行號，只需在對應時特別進行歸類即可。比如某類狀態都是第m行是最長時間沒有被訪問到的，那麼在選擇編碼是就把某幾位值為m的編碼與之對應即可。由於一般的緩存組內的行數n都是2的冪次，可以證明，這樣的分類方法總是可行的。編碼和狀態對應關係確定後，對應關係決定了LRU替換算法執行過程中編碼改變的規律原則。綜上所述僅為本發明的較佳實施例而已，並非用來限定本發明的實施範圍。即凡依本發明申請專利範圍的內容所作的等效變化與修飾，都應為本發明的技術範疇。權利要求1、一種採用LRU替換算法的緩存，其特徵在於對緩存中每組的所有緩存行的被訪問時間相互關係的狀態進行編碼，並將上述狀態位編碼存儲於寄存器中以用於實現LRU替換算法。2、根據權利要求1所述的採用LRU替換算法的緩存，其特徵在於該狀態位編碼中的某幾位直接表示最長時間沒有訪問過的緩存行_弓一3、根據權利要求1所述的採用LRU替換算法的緩存，其特徵在於該寄存器位數N與每組的緩存行n之間的數值關係是N是滿足2N〉=n！的最小整數，或者說整數N滿足2N>=n！>2N"。全文摘要本發明涉及一種採用LRU替換算法的緩存，對緩存中每組的所有緩存行的被訪問時間相互關係的狀態進行編碼，並將上述狀態位編碼存儲於寄存器中以用於實現LRU替換算法。它主要解決現有緩存實現LRU算法需要大量的寄存器的技術問題，它不但能節省硬體成本，而且也不會佔用比較多的晶片資源。文檔編號G06F12/12GK101286140SQ20071003941公開日2008年10月15日申請日期2007年4月12日優先權日2007年4月12日發明者吳子熙,朱志明申請人:智多微電子(上海)有限公司