預取數據控制器及其方法
2023-05-14 22:04:51 2
專利名稱：預取數據控制器及其方法
技術領域：
本發明提供一種提取一存儲裝置所存儲的數據的裝置及方法，特別指一種可有效率地預取一存儲裝置所存儲的數據的預取控制器及方法。
背景技術：
一般而言，計算機系統會包含有一運算單元(例如一中央處理器)以及一存儲單元(例如一動態隨機存取存儲器)，亦即存儲單元紀錄數據與指令，而運算單元便自存儲單元提取所要的數據與指令來完成一預定邏輯運算，此外，運算單元亦會將該預定邏輯運算所產生的輸出數據回存至存儲單元。如本技術領域所公知，隨著製造工藝進步，中央處理器的運算時鐘便快速地提升，因此一般而言，中央處理器的運算時鐘遠高於動態隨機存取存儲器的工作時鐘，亦即中央處理器的數據處理速度快於動態隨機存取存儲器的數據處理速度。所以，當中央處理器執發出一數據提取指令以提取動態隨機存取存儲器中一預定數據後，中央處理器必須等待動態隨機存取存儲器讀取該預定數據，並傳回該預定數據至中央處理器，因此便會因為動態隨機存取存儲器的延遲時間而影響中央處理器的運算效能。所以，快取存儲器(cache)便用來減輕存儲器的延遲時間對中央處理器的影響，相較於公知動態隨機存取存儲器，快取存儲器(例如靜態隨機存取存儲器)具有高速的數據存取速度，但是由於快取存儲器的生產成本較高，因此計算機系統所設置的快取存儲器(例如中央處理器中的L2快取)的容量遠小於動態隨機存取存儲器的容量。
請參閱圖1，圖1為公知數據處理系統10的功能方塊圖。數據處理系統10包含有一快取存儲器12，一預取控制器(pre-fetch controller)14，一存儲器控制器(memory controller)16，以及一動態隨機存取存儲器18。如上所述，快取存儲器12的數據存取速度快於動態隨機存取存儲器18的數據存取速度，因此當中央處理器執行一邏輯運算時，若中央處理器可直接自快取存儲器12讀取到所要的數據，則中央處理器便可進一步地提升其運算效能，所以預取控制器14便先預測中央處理器執行該邏輯運算需自動態隨機存取存儲器18提取數據DATAa、DATAb、DATAc，然後告知存儲器控制器16以驅動存儲器控制器16自動態隨機存取存儲器18讀取數據DATAa、DATAb、DATAc，並傳送至快取存儲器12中存儲。因此，當中央處理器執行該邏輯運算的過程中，若數據DATAa、DATAb、DATAc為其所要的數據，亦即中央處理器搜尋快閃記憶體會產生公知快取命中(cache hit)，因此中央處理器便可直接由快取存儲器12提供所需的數據DATAa、DATAb、DATAc來執行該邏輯運算。然而，一般而言，預取控制器14的預測結果與該邏輯運算的數據需求不一定會完全吻合，亦即該邏輯運算需自動態隨機存取存儲器18讀取其存儲的數據DATAa、DATAb、DATAd，但是預取控制器14卻預測中央處理器執行該邏輯運算需自動態隨機存取存儲器18提取數據DATAa、DATAb、DATAc，因此，當中央處理器執行該邏輯運算時，中央處理器搜尋快取存儲器12中的數據DATAa、DATAb會產生快取命中，因此中央處理器可順利地自快取存儲器12讀取數據DATAa、DATAb，然而，當中央處理器於快取存儲器12中搜尋數據DATAd時會產生公知快取未命中(cache miss)，因此便必須經由存儲器控制器16自動態隨機存取存儲器18提取數據DATAd，最後，數據DATAd會存儲於快取存儲器12中，並同時會傳送給中央處理器，換句話說，中央處理器便必須等待，直到接收到動態隨機存取存儲器18所輸出的數據DATAd後才能繼續執行該邏輯運算。
由上可知，數據DATAc並非為所要的數據DATAd，因此預取控制器14預先讀取動態隨機存取存儲器18中的數據DATAc便會耗費存儲器控制器16與動態隨機存取存儲器18之間的頻帶寬度，所以，當預取控制器14的預測準確率太低時，亦即當中央處理器搜尋快取存儲器12時不斷地產生快取未命中，因此預先讀取數據的操作便會使計算機系統的整體效能大幅地惡化。
發明內容
因此，本發明提供一種可有效率地預取一存儲裝置所存儲的數據的預取控制器及方法，以解決上述問題。
根據本發明，公開一種控制預取存儲器的數據的方法。該方法包括有初始化一計數值；當預取操作時，提取該存儲器的數據並使得該計數值減去一第一數值；當預取命中時，使得該計數值累加一第二數值；以及比較將該計數值與一第一閾值，若該計數值小於該第一閾值，則暫停提取該存儲器的數據。
由於本發明預取控制器與其操作方法不斷地監測預測準確度，並動態地調整一計數值，當預取控制器的預測準確度不佳時，該計數值會達到一閾值，因此本發明預取控制器與其操作方法便會停止預先讀取數據的操作，以便緩和過量快取未命中對存儲器傳輸頻帶寬度所造成的影響。
圖1為公知數據處理系統的功能方塊圖。
圖2為本發明第一種預取控制器的功能方塊示意圖。
圖3為本發明第一種預取控制的方法流程4為本發明第二種預取控制器的功能方塊示意圖。
附圖符號說明10 數據處理系統 12 快取存儲器14、20、40 預取控制器16 存儲器控制器18 動態隨機存取存儲器22 控制電路24 計數寄存器26、44 減法器28、42 加法器30、46 比較模塊32 運算單元 34 檢測單元36 輸出單元具體實施方式
請參閱圖2，圖2為本發明第一種預取控制器20的功能方塊示意圖。預取控制器20包含有一控制電路22，一計數寄存器24，一減法器26、一加法器28，以及一比較模塊30。控制電路22中則包含有一運算單元32，一檢測單元34，以及一輸出單元36。此外，計數寄存器24中存儲有一計數值CNT。請注意，如本技術領域所公知，減法器26亦可經由加法器與XOR邏輯運算電路來加以實施。預取控制器20的操作方法詳述如下，首先，當預取控制器20啟動時，計數寄存器24會初始其紀錄的計數值CNT，舉例來說，計數寄存器24可紀錄10個位，亦即計數值CNT的最小值對應」0000000000」，而計數值CNT的最大值對應」1111111111」，因此計數值CNT的初始值需介於其最大值與最小值之間，本實施例中，該初始值為最大值與最小值的中間值，亦即」0000011111」。然後，控制電路22的運算單元32便開始預測中央處理器執行邏輯運算所要讀取的預定數據，並產生相對應數據提取指令(request)，並經由輸出單元36傳送該數據提取指令至圖1所示的存儲器控制器16，以便自動態隨機存取存儲器18讀取所要的預定數據。此外，當輸出單元36輸出一數據提取指令時，其會觸發一控制信號pf_get，且控制信號pf_get會進一步地啟動減法器26執行邏輯運算，因此計數值CNT與一第一數值N1便會經由減法器26計算計數值CNT減去第一數值N1的運算結果，然後該運算結果便進一步地更新(update)計數寄存器24所記錄的計數值CNT。
此外，控制電路22的檢測單元34則會檢測中央處理器執行邏輯運算所要的數據與運算單元32產生的數據提取指令所對應的預取數據是否符合，當一數據提取指令所對應的預取數據符合中央處理器所要的數據時，檢測單元34會輸出一控制信號pf_hit，且控制信號pf_hit會進一步地啟動加法器28執行邏輯運算，因此計數值CNT與一第二數值N2便會經由加法器28計算計數值CNT與第二數值N2相加的運算結果，然後該運算結果便進一步地更新計數寄存器24所記錄的計數值CNT。
如上所述，控制信號pf_get表示預取控制器20自圖1所示的動態隨機存取存儲器預先讀取一數據，而控制信號pf_hit則表示預取控制器20所預先讀取的數據符合中央處理器所要的數據，一般而言，預取控制器20的預測結果與該邏輯運算的數據需求不一定完全吻合，因此可能輸出單元36已觸發產生複數次控制信號pf_get後，檢測單元34才會產生一次控制信號pf_hit，亦即控制信號pf_hit與控制信號pf_get之間的比例便代表預取控制器20的預測準確度。換句話說，若預取控制器20的預測準確度越高，則控制信號pf_hit的發生頻率便越頻繁。本實施例中，假設控制信號pf_hit與控制信號pf_get之間的比例為A∶B時，中央處理器仍可維持良好的運算效能，因此本實施例便設定第一數值N1與第二數值N2之間的比例對應A∶B，舉例來說，若控制信號pf_hit與控制信號pf_get之間的比例為1∶4時，預取控制器22的運作視為有效率的，因此便設定第一數值N1與第二數值N2之間的比例對應1∶4，所以，本實施例中，第一數值N1與第二數值N2分別等於1與4。所以，當輸出單元36產生一次控制信號pf_get時，計數值CNT會遞減1，以及當檢測單元34產生一次控制信號pf_hit時，計數值CNT會遞增4。
如前所述，計數值CNT的初始值為」0000011111」，因此若輸出單元36每產生4控制信號pf_get中，檢測單元34有產生一次控制信號pf_hit，則計數值CNT會保持不變，亦即計數值CNT仍紀錄該初始值」00011111」。若輸出單元36每產生4次以上(例如5次)的控制信號pf_get中，檢測單元34才有產生一次控制信號pf_hit，因此計數值CNT會小於該初始值」00011111」，並逐漸地趨近最小值」0000000000」，換句話說，當計數值CNT逐漸地減少時，則表示預取控制器20的預測準確率不佳而造成執行效能不佳。此外，若輸出單元36每產生4次以下(例如3次)的控制信號pf_get中，檢測單元34便可產生一次控制信號pf_hit，因此計數值CNT會大於該初始值」00011111」，並逐漸地趨近最大值」1111111111」，換句話說，當計數值CNT逐漸地增加時，則表示預取控制器20的預測準確率良好而產生極佳執行效能。
本實施例中，比較模塊30會比較計數值CNT以及一閾值TH1，而閾值TH1小於上述初始值」0000011111」。由上可知，當預取控制器20的預測準確率不佳時，表示控制信號pf_hit的發生頻率降低，因此計數值CNT會逐漸地趨近最小值」0000000000」，明顯地，當預取控制器20的預測準確率太低，則表示中央處理器搜尋圖1所示的快取存儲器12時會不斷地產生快取未命中，因此預取控制器20預先讀取數據的操作便會使計算機系統的整體效能大幅地惡化，所以當比較模塊30判斷計數值CNT小於閾值TH1時，比較模塊30會驅動控制電路22以中斷輸出單元36的功能，亦即輸出單元36不再將運算單元32所產生的數據提取指令傳送至圖1所示的存儲器控制器16，因此輸出單元36便停止產生控制信號pf_get至減法器26，換句話說，當輸出單元36停止輸出控制信號pf_get後，計數值CNT便不會再降低。
請注意，運算單元32與檢測單元34此時仍會正常地運作，亦即運算單元32仍會不斷預測中央處理器執行邏輯運算時所需的數據，並產生相對應數據提取指令，而檢測單元34會檢測數據提取指令於動態隨機存取存儲器18所對應的數據與中央處理器執行邏輯運算於動態隨機存取存儲器18所提取的數據，雖然輸出單元36不會輸出數據提取指令至存儲器控制器16以執行預先讀取數據的操作，然而檢測單元34仍會繼續監測運算單元32的預測結果是否準確，因此當檢測單元34檢測到運算單元32所預測的數據與中央處理器自動態隨機存取存儲器18所提取的數據相同時，則檢測單元34會產生控制信號pf_hit，因此加法器28便會啟動來提升計數值CNT，如上所述，當輸出單元36停止輸出控制信號pf_get後，計數值CNT便不會再降低，亦即計數值CNT便會因為檢測單元34陸陸續續地輸出控制信號pf_hit而逐漸地增加。
本實施例中，比較模塊30會比較計數值CNT與一閾值TH2來決定是否驅動控制電路22重新啟動輸出單元36，閾值TH2大於閾值TH1，且大於上述初始值」0000011111」，因此若閾值TH2等於閾值TH1，則預取控制器20便可能於啟動輸出單元36的操作與關斷輸出單元36的操作之間不停地切換，所以本發明預取控制器20便使用不同的閾值TH1、TH2來避免上述情況。當計數值CNT超過閾值TH2後，輸出單元36會重新啟動，若此時預取控制器20的預測準確率仍未改善，亦即控制信號pf_hit的發生頻率過低，因此計數值CNT會快速地減少，當計數值CNT又小於閾值TH1時，則比較模塊30會告知控制電路22以暫停輸出單元36的功能，因此可減輕存儲器控制器16與動態隨機存取存儲器18之間的數據傳輸負荷。
圖3為本發明第一實施例的流程圖，當預取操作時，計數值CNT會減去一第一數值N1，當預取命中時，計數值CNT會增加一第二數值N2，如果計數值CNT小於閾值TH1，則表示預測的準確率太差，因此會停止存取存儲器的數據。此時還是有預取操作，只是計數值CNT不再減少，但若是預取命中時，則計數值CNT會增加第二數值N2，直到計數值CNT大於閾值TH2時，才會重新在啟動存儲器控制器到存儲器中存取數據。
綜上所述，當計數值CNT小於閾值TH1時，運作中的輸出單元36會被關斷，而當計數值CNT大於閾值TH2時，關斷中的輸出單元36會開始運作。然而，本發明預取控制器20亦可於計數值CNT高於一閾值時，關斷目前運作中的輸出單元36，以及於計數值CNT小於另一閾值時，重新啟動目前關斷中的輸出單元36，請參閱圖2與圖3，圖3為本發明第二種預取控制器40的功能方塊示意圖。請注意，圖3所示的預取控制器40與圖2所示的預取控制器20中，大部分的同名元件具有相同的功能，因此不再重複贅述。主要的不同的處在於加法器42、減法器44以及比較模塊46的操作，本實施例中，當輸出單元36輸出一控制信號pf_get時，控制信號pf_get會啟動加法器42而非減法器44，此時，加法器42會將計數值CNT與一數值N3相加，並以運算結果更新計數值CNT。另外，當檢測單元34輸出一控制信號pf_hit時，控制信號pf_hit會啟動減法器44而非加法器42，此時，減法器44會將計數值CNT減去一數值N4，並以運算結果更新計數值CNT。數值N3、N4的設定規則與上述數值N1、N2的設定規則相同，因此數值N3、N4之間的比例即對應預取控制器40的預定預測準確率。
圖2所示的實施例中，當檢測單元34輸出一控制信號pf_hit時，加法器28會啟動以使用數值N2來提升計數值CNT，以及當輸出單元36輸出一控制信號pf_get時，減法器26會啟動以使用數值N1來降低計數值CNT。然而，本發明預取控制器20於檢測單元34輸出一控制信號pf_hit時，啟動加法器28以使用數值N3來提升計數值CNT，以及於輸出單元36輸出一控制信號pf_get時，啟動減法器26以使用數值N4來降低計數值CNT。如前所述，計數值CNT的初始值為」0000011111」，因此若輸出單元36每產生4次控制信號pf_get中，檢測單元34產生一次控制信號pf_hit，則計數值CNT會保持不變，亦即計數值CNT仍紀錄該初始值」00011111」。若輸出單元36每產生4次以上(例如5次)的控制信號pf_get中，檢測單元34才有產生一次控制信號pf_hit，因此計數值CNT會大於該初始值」00011111」，並逐漸地趨近最大值」1111111111」，換句話說，當計數值CNT逐漸地增加時，則表示預取控制器40的預測準確率不佳而造成執行效能不彰。此外，若輸出單元36每產生4次以下(例如3次)的控制信號pf_get中，檢測單元34便可產生一次控制信號pf_hit，因此計數值CNT會小於該初始值」00011111」，並逐漸地趨近最小值」0000000000」，換句話說，當計數值CNT逐漸地減少時，則表示預取控制器40的預測準確率良好而可產生極佳執行效能。
比較模塊46會比較計數值CNT以及一閾值TH3，而閾值TH3大於上述初始值」0000011111」。當比較模塊46判斷計數值CNT大於閾值TH3時，比較模塊46會驅動控制電路22以中斷輸出單元36的功能，亦即輸出單元36不再將運算單元32所產生的數據提取指令傳送至圖1所示的存儲器控制器16，因此輸出單元36便停止產生控制信號pf_get至加法器42，換句話說，當輸出單元36停止輸出控制信號pf_get後，計數值CNT便不會再增加。如前所述，檢測單元34仍會繼續監測運算單元32的預測結果是否準確，因此當檢測單元34檢測到運算單元32所預測的數據與中央處理器自動態隨機存取存儲器18所提取的數據相同時，則檢測單元34會產生控制信號pf_hit，因此減法器44便會啟動來降低計數值CNT，所以計數值CNT便會因為檢測單元34陸陸續續地輸出控制信號pf_hit而逐漸地降低。
然後，比較模塊46會比較計數值CNT與一閾值TH4來決定是否驅動控制電路22重新啟動輸出單元36，閾值TH4小於閾值TH3，且低於上述初始值」0000011111」，因此，當計數值CNT小於閾值TH4後，輸出單元36會重新啟動，若此時預取控制器40的預測準確率仍未改善，亦即控制信號pf_hit的出現頻率仍過低，因此計數值CNT便會快速地增加，當計數值CNT又超過閾值TH3時，則比較模塊30會告知控制電路22以暫停輸出單元36的功能，因此便可減輕存儲器控制器16與動態隨機存取存儲器18之間的數據傳輸負荷。
本發明預取控制器與其操作方法不斷地監測預測準確度，並動態地調整一計數值，當預取控制器的預測準確度不佳時，該計數值會達到一閾值，因此本發明預取控制器與其操作方法便會停止預先讀取數據的操作，以便緩和過量快取未命中對存儲器傳輸頻帶寬度所造成的影響。此外，上述數值N1、N2、N3、N4與閾值TH1、TH2、TH3、TH4為可編程(programmable)，所以，本發明預取控制器與其操作方法可彈性地設定上述數值N1、N2、N3、N4與閾值TH1、TH2、TH3、TH4來進一步地微調(tune)預取控制器的效能。再者，本發明預取控制器應用簡單的電路結構來計算計數值以控制預先讀取數據的操作，因此不但生產成本低且實作容易。
以上所述僅為本發明的較佳實施例，凡依本發明權利要求所進行的等效變化與修改，皆應屬本發明的涵蓋範圍。
權利要求
1.一種控制預取存儲器的數據的方法，包括有初始化一計數值；當預取操作時，提取該存儲器的數據並使得該計數值減去一第一數值；當預取命中時，使得該計數值累加一第二數值；以及將該計數值與一第一閾值相比較，若該計數值小於該第一閾值，則暫停提取該存儲器的數據。
2.如權利要求1所述的控制預取存儲器數據的方法，其中當暫停提取該存儲器數據時，不使得該計數值減去該第一數值，但其中當預取命中時，使得該計數值累加該第二數值。
3.如權利要求2所述的控制預取存儲器數據的方法，其中當該計數值大於一第二閾值時，重新啟動提取該存儲器的數據，且其中該第二閾值大於該第一閾值。
4.如權利要求1所述的控制預取存儲器數據的方法，其中該第二數值為第一數值的整數倍。
5.一種控制預取存儲器的數據的方法，包括有初始化一計數值；當預取操作時，提取該存儲器的數據並使得該計數累加一第一數值；當預取命中時，使得該計數值減去一第二數值；以及比較將該計數值與一第一閾值，若該計數值大於該第一閾值，則暫停提取該存儲器的數據。
6.如權利要求5所述的控制預取存儲器數據的方法，其中當暫停提取該存儲器數據時，暫停使得該計數值累加該第一數值，但其中當預取命中時，使得該計數值減去該第二數值。
7.如權利要求6所述的控制預取存儲器數據的方法，其中當該計數值小於一第二閾值時，重新啟動提取該存儲器的數據，且其中該第二閾值小於該第一閾值。
8.如權利要求5所述的控制預取存儲器數據的方法，其中該第二數值為第一數值的整數倍。
9.一種預取控制器，用以預取一存儲器的數據以提供一邏輯運算單元的使用，該預取控制器包含有一計數寄存器，寄存有一計數值；以及一控制電路，連接到該計數寄存器，用以當預取操作及預取命中時，使得該計數值改變。
10.如權利要求9所述的預取控制器，其中該控制電路還包含有一運算單元，用以當預取操作時，預測該邏輯運算單元執行所需的數據，並至該存儲器中提取該數據。
11.如權利要求9所述的預取控制器，其中該控制電路還包含有一輸出單元，用以當預取操作時，使得該計數值減去一第一數值。
12.如權利要求11所述的預取控制器，其中該控制電路還包含有一檢測單元，用以當預取命中時，使得該計數值累加一第二數值。
13.如權利要求11所述的預取控制器，其中還包含有一比較模塊，連接在該計數寄存器與該控制電路間，用以當該計數值小於一第一閾值時，停止提取該存儲器的數據，以及當停止提取後，若該計數值大於一第二閾值時，則重新啟動預取該存儲器的數據。
14.如權利要求13所述的預取控制器，其中當停止預取該存儲器數據時，使得該計數值不減去該第一數值，但若預取命中時，使得該計數值累加該第二數值。
15.如權利要求13所述的預取控制器，其中該第二閾值大於該第一閾值。
16.如權利要求9所述的預取控制器，其中該控制電路還包含有一輸出單元，用以當預取操作時，使得該計數值累加一第三數值。
l7.如權利要求16所述的預取控制器，其中該控制電路還包含有一檢測單元，用以當預取命中時，使得該計數值減去一第四數值。
18.如權利要求17所述的預取控制器，其中還包含有一比較模塊，連接在該計數寄存器與該控制電路間，用以當該計數值大於一第三閾值時，停止提取該存儲器的數據，且以及當停止提取後，該計數值小於一第四閾值時，重新啟動預取該存儲器的數據。
19.如權利要求18所述的預取控制器，其中當停止提取該存儲器數據後時，使得該計數值不累加該第三數值，以及若預取命中時，使得該計數值減去該第四數值，且其中該第四閾值小於該第三閾值。
20.如權利要求9所述的預取控制器，其中還包含有一減法器，連接到該計數寄存器，使得該計數值改變，以及一加法器，連接到該計數寄存器，使得該計數值改變。
全文摘要
本發明為一種預取存儲器數據的預取控制器與方法，該方法包含有初始化一計數值；當預取操作時，提取該存儲器的數據並使得計數值減去第一數值；當預取命中時，使得計數值累加第二數值；以及將該計數值與第一閾值相比較，若計數值小於第一閾值，則暫停提取存儲器的數據。
文檔編號G06F12/08GK1570887SQ20041007512
公開日2005年1月26日 申請日期2004年8月31日 優先權日2003年10月7日
發明者徐文芝 申請人:威盛電子股份有限公司