預取單元、數據預取方法以及微處理器的製作方法

2023-07-02 19:33:31 3

專利名稱：：預取單元、數據預取方法以及微處理器的製作方法
技術領域：
：本發明涉及一般微處理器的快取存儲器，特別是涉及將數據預取至微處理器的快取存儲器。
背景技術：
：以最近的計算機系統而言，在快取失敗(cachemiss)時，微處理器存取系統存儲器所需的時間，會比微處理器存取快取存儲器(cache)多上一或兩個數量級。因此，為了提高快取命中率(cachehitrate)，微處理器整合了預取技術，用來測試最近數據存取樣態(examinerecentdataaccesspatterns)，並且企圖預測哪一個數據為程序下一個存取的對象，而預取的好處已是眾所皆知的範疇。然而，申請人注意到某些程序的存取樣態並不為現有微處理器的預取單元所能檢測的。例如，圖1所示為當執行的程序包括經由存儲器進行一序列的儲存操作時，第二級快取存儲器(L2Cache)的存取樣態，而圖中所描繪的為各時間的存儲器地址。由圖1可知，雖然總趨勢為隨著時間而增加存儲器地址，即由往上的方向，然而在許多狀況下，所指定的存取存儲器地址亦可較前一個時間往下，而非總趨勢的往上，使其不同於現有預取單元實際所預測的結果。雖然就數量相對大的樣本而言，總趨勢是朝一個方向前進，但現有預取單元在面臨小樣本時卻可能出現混亂狀況的原因有兩個。第一個原因為程序是依循其架構對存取存儲器，不論是由演算法特性或是不佳的編程(poorprogramming)所造成。第二個原因為非循序(out-of-orderexecution)微處理器核心的管線與隊列在正常功能下執行時，常常會用不同於其所產生的程序順序來進行存儲器存取。因此，需要一個數據預取單元(器)能夠有效地為程序進行數據預取，其必須考慮到在較小時窗(timewindows)進行存儲器存取指令(操作)時並不會呈現明顯的趨勢(nocleartrend)，但當以較大樣本數進行審查時則會出現明顯的趨勢。
發明內容本發明揭示一種預取單元，設置於具有一快取存儲器的一微處理器中，其中預取單元用以接收對一存儲器區塊的多個地址的多個存取要求，每一存取要求對應存儲器區塊的地址中的一個，並且存取要求的地址隨著時間函數非單調性地(non-monotonically)增加或減少。預取單元包括一儲存裝置以及一控制邏輯。控制邏輯，耦接至儲存裝置，其中當接收到存取要求時，控制邏輯則用以維持儲存裝置中的存取要求的一最大地址以及一最小地址，以及最大地址以及最小地址的變化的計數值、維持存儲器區塊中最近被存取的快取線的一歷史記錄，最近被存取的快取線是與存取要求的地址相關、根據計數值，決定一存取方向、根據歷史記錄，決定一存取樣態，並且根據存取樣態並沿著存取方向，將快取存儲器內尚未被歷史記錄指示為已存取的快取線預取至存儲器區塊中。本發明揭示一種數據預取方法，用以預取數據至一微處理器的一快取存儲器，數據預取方法，包括接收對一存儲器區塊的多個地址的多個存取要求，每一存取要求對應存儲器區塊的地址中的一個，並且存取要求的地址隨著時間函數非單調性地(non-monotonically)增加或減少；當接收到存取要求時，維持存儲器區塊中的一最大以及一最小地址，並且計算最大以及最小地址的變化的計數值；當接收到存取要求時，維持存儲器區塊中最近被存取的快取線的一歷史記錄，最近被存取的快取線是與存取要求的地址相關；根據計數值決定一存取方向；根據歷史紀錄決定一存取樣態；以及根據存取樣態並沿著存取方向，將快取存儲器內尚未被歷史記錄指示為已存取的快取線預取至存儲器區塊中。本發明揭示一種微處理器，包括多個核心、一快取存儲器以及一預取單元。快取存儲器，由核心所共享，用以接收對一存儲器區塊的多個地址的多個存取要求，每一存取要求對應存儲器區塊的地址中的一個，存取要求的地址隨著時間函數非單調性地(non-monotonically)增加或減少。預取單元，用以監視存取要求，並維持存儲器區塊中的一最大地址以及一最小地址，以及最大地址以及最小地址的變化的計數值、根據計數值，決定一存取方向並且沿著存取方向，將存儲器區塊中未命中的快取線預取至快取存儲器中。本發明揭示一種微處理器，包括一第一級快取存儲器、一第二級快取存儲器以及一預取單元。預取單元用以檢測出現在第二級快取存儲器中的最近存取要求的一方向以及樣態，以及根據方向以及樣態，將多個快取線預取至第二級快取存儲器中、從第一級快取存儲器，接收第一級快取存儲器所接收的一存取要求的一地址，其中地址與一快取線相關、決定在方向中所相關的快取線的後被樣態所指出的一個或多個快取線並且導致一個或多個快取線被預取至第一級快取存儲器中。本發明揭示一種數據預取方法，用以預取數據至具有一第二級快取存儲器的一微處理器的一第一級快取存儲器，數據預取方法包括檢測出現在第二級快取存儲器中的最近存取要求的一方向以及樣態，以及根據方向以及樣態，將多個快取線預取至第二級快取存儲器中；從第一級快取存儲器，接收第一級快取存儲器所接收的一存取要求的一地址，其中地址與一快取線相關；決定在方向中所相關的快取線的後被樣態所指出的一個或多個快取線；以及導致一個或多個快取線被預取至第一級快取存儲器中。本發明揭示一種微處理器，包括一快取存儲器以及一預取單元。預取單元用以檢測具有一第一存儲器區塊的多個存儲器存取要求的一樣態，並且根據樣態從第一存儲器區塊預取多個快取線至快取存儲器中、監視一第二存儲器區塊的一新的存儲器存取要求、決定第一存儲器區塊是否虛擬鄰近於第二存儲器區塊，並且當自第一存儲器區塊延續至第二存儲器區塊時，則決定樣態是否預測到第二存儲器區塊的新的存儲器存取要求所相關的一快取線在第二存儲器區塊中、並且根據樣態，從第二存儲器區塊將相映的快取線預取至快取存儲器中。本發明揭示一種數據預取方法，用以預取數據至一微處理器的一快取存儲器，數據預取方法包括檢測具有一第一存儲器區塊的多個存儲器存取要求的一樣態，並且根據樣態從第一存儲器區塊預取快取線至上至快取存儲器中；監視一第二存儲器區塊的一新的存儲器存取要求；決定第一存儲器區塊是否虛擬鄰近於第二存儲器區塊，並且當自第一存儲器區塊延續至第二存儲器區塊時，決定樣態是否預測到第二存儲器區塊的新的存儲器存取要求所相關的一快取線在第二存儲器區塊中；以及根據樣態，從第二存儲器區塊將多個快取線預取至快取存儲器中，以回應決定步驟。圖1所示為當執行經由存儲器包括一序列儲存操作的的程序時，一種第二級快取存儲器的樣態存取表現。圖2為本發明的一種微處理器的方塊圖。圖3為本發明圖2的預取單元更詳細的方塊圖。圖4為本發明圖2的微處理器以及特別是圖3的預取單元的操作流程圖。圖5為本發明圖3的預取單元對圖4的步驟的操作流程圖。圖6為本發明圖3的預取單元對圖4的步驟的操作流程圖。圖7為本發明圖3的預取要求隊列的操作流程圖。圖8A和圖8B為本發明一存儲器區塊的兩個圖型存取點，用以表示本發明的定界框預取單元。圖9為本發明圖2所示的微處理器的操作範例的方塊圖。圖10為本發明延續圖9的範例的圖2所示的微處理器的操作範例的方塊圖。圖IlA和圖IlB為本發明延續圖9以及10圖的範例的圖2所示的微處理器的操作範例的方塊圖。圖12為本發明另一實施例的一種微處理器的方塊圖。圖13為本發明圖12所示的預取單元的操作流程圖。圖14為本發明根據圖13步驟的圖12所示的預取單元的操作流程圖。圖15為本發明另一實施例具有一定界框預取單元的一種微處理器的方塊圖。圖16為本發明圖15的虛擬雜湊表的方塊圖。圖17為本發明圖15的微處理器的操作流程圖。圖18為本發明根據經由圖17範例敘述的在預取單元的操作後的圖16的虛擬雜湊表的內容。圖19A和圖19B為本發明圖15的預取單元的操作流程圖。圖20為本發明另一實施例的用在圖15的預取單元的一雜湊物理地址至雜湊虛擬地址庫的方塊圖。圖21本發明的一多核微處理器的方塊圖。附圖符號說明100微處理器102指令快取存儲器104指令解碼器106暫存器別名表108保留站112執行單元132其他執行單元134載入/儲存單元124預取單元114引退單元116第一級數據快取存儲器118第二級快取存儲器122總線接口單元162虛擬雜湊表198隊列172第一級數據搜尋指標器178第一級數據樣態地址196第一級數據存儲器地址194樣態預測快取線地址192快取線配置要求188快取線數據354存儲器區塊虛擬雜湊地址欄356狀態欄302區塊位遮罩暫存器303區塊號碼暫存器304最小指標暫存器306最大指標暫存器308最小改變計數器312最大改變計數器314總計數器316中間指標暫存器318周期匹配計數器342方向暫存器344樣態暫存器346樣態順序暫存器348樣態區域暫存器352搜尋指標暫存器332硬體單元322控制邏輯328預取要求隊列324提取指標器326推進指標器2002雜湊虛擬地址庫2102A核心A2102B核心B2104高度反應式的預取單元2106共享的高度反應式的預取單元具體實施例方式以下將詳細討論本發明各種實施例的製造及使用方法。然而值得注意的是，本發明所提供的許多可行的發明概念可實施在各種特定範圍中。這些特定實施例僅用於舉例說明本發明的製造及使用方法，但非用於限定本發明的範圍。廣泛而言，關於上述問題的解決方法可以後續敘述加以解釋。當一存儲器的所有存取(指令、操作或要求)皆表示在一張圖上時，所有存取(指令、操作或要求)的一集合可被一定界框圈起來。當外加的存取要求亦表示於同一圖上時，這些存取要求亦可被調整大小後的定界框圈起來。上述首張圖如圖8所示為一存儲器區塊的兩次存取(指令或操作)中。圖8的X軸表示指令的存取的時間，Y軸表示具有4KB區塊的存取的64位元組快取線的索引。首先，描繪第一次的兩個存取第一個存取是對快取線5進行存取，第二個存取要求是對快取線6進行存取。如圖所示的一定界框將代表存取要求的兩點圈起來。再者，第三個存取要求發生於快取線7，定界框變大使得代表第三個存取要求的新點可被定界框圈起在內。隨著新的存取不斷發生，定界框必隨著X軸擴大，並且定界框的上緣亦隨著Y軸擴大(此為向上的例子)。上述定界框上緣以及下緣的移動的歷史紀錄將用以決定存取樣態的趨勢為向上、向下或者都不是。除了追蹤定界框的上緣以及下緣的趨勢以決定一趨勢方向外，追蹤個別的存取要求也是必要的，因為存取要求跳過一或兩個快取線的事件時常發生。因此，為了避免跳過所預取快取線的事件發生，一旦檢測到一向上或向下的趨勢，預取單元則使用額外的準則決定所要預取的快取線。由於存取要求趨勢會被重新排列，預取單元會將這些暫態的重新排列存取歷史紀錄予以刪除。此操作藉由標記位(markingbit)在一位遮罩(bitmask)中完成的，每一位對應具有一存儲器區塊的一快取線，，且當位遮罩中對應的位被設置時，表示特定的區塊可被存取。一旦對存儲器區塊的存取要求已達到一充分數量，預取單元會使用位遮罩(其中位遮罩不具有存取的時序的指示)，並基於如下所述的較大的存取觀點(廣義largeview)去存取整個區塊，而非基於較小的存取觀點(狹義smallview)以及現有預取單元般僅根據存取的時間去存取的區塊。圖2所示為本發明的微處理器100的方塊圖。微處理器100包括一個具有多個階層的傳遞路徑，並且傳遞路徑中亦包括各種功能單元。傳遞路徑包括一指令快取存儲器102，指令快取存儲器102耦接至一指令解碼器104；指令解碼器104耦接至一暫存器別名表106(registeraliastable,RAT)；暫存器別名表106耦接至一保留站108(reservationstation)；保留站108耦接至一執行單元112(executionunit)；最後，執行單元112耦接至一引退單元114(retireunit)。指令解碼器104可包括一指令轉譯器(instructiontranslator)，用以將巨集指令(例如x86架構的巨集指令)轉譯為微處理器100的類似精簡指令集(reduceinstructionsetcomputerRISC)的巨集指令。保留站108產生並且傳送指令至執行單元112，用以使執行單元112依照程序順序(programorder)執行。引退單元114包括一重新排序緩衝器(reorderbuffer)，用以依據程序順序執行指令的引退(Retirement)。執行單元112包括載入/儲存單元134以及其他執行單元132(otherexecutionunit),例如整數單元(integerunit)、浮點數單元(floatingpointunit)、分支單元(branchunit)或者單指令多重數據串流(SingleInstructionMultipleData,SIMD)單元。載入/儲存單元1用以讀取第一級數據快取存儲器116(leVel1datacache)的數據，並且寫入數據至第一級數據快取存儲器116。一第二級快取存儲器118用以支持(back)第一級數據快取存儲器116以及指令快取存儲器102。第二級快取存儲器118用以經由一總線接口單元122讀取以及寫入系統存儲器，總線接口單元122是微處理器100與一總線(例如一區域總線(localbus)或是存儲器總線(memorybus))間的一接口。微處理器100亦包括一預取單元124，用以自系統存儲器預取數據到第二級快取存儲器118和/或第一級數據快取存儲器116。如圖3所示為圖2的預取單元1較詳細的方塊圖。預取單元1包括一區塊位遮罩暫存器302。區塊位遮罩暫存器302中的每一位對應具有一存儲器區塊的一快取線，其中存儲器區塊的區塊號碼儲存在一區塊號碼暫存器303內。換言之，區塊號碼暫存器303儲存了存儲器區塊的上層地址位(upperaddressbits)。當區塊位遮罩暫存器302中的一位的數值為真(truevalue)時，是指出所對應的快取線已經被存取了。初始化區塊位遮罩暫存器302將使得所有的位值為假(false)。在一實施例中，存儲器區塊的大小為4KB，並且快取線的大小為64位元組。因此，區塊位遮罩暫存器302具有64位的容量。在某些實施例中，存儲器區塊的大小亦可與實體存儲器分頁(physicalmemorypage)的大小相同。然而，快取線的大小在其他實施例中可為其他各種不同的大小。再者，區塊位遮罩暫存器302上所維持的存儲器區域的大小是可改變的，並不需要對應於實體存儲器分頁的大小。更確切的說，區塊位遮罩暫存器302上所維持的存儲器區域(或區塊)的大小可為任何大小(二的倍數最好)，只要其擁有足夠的快取線以便進行利於預取方向與樣態的檢測即可。預取單元1亦可包括一最小指標暫存器304(minpointerregister)以及一最大指標暫存器306(maxpointerregister)。最小指標暫存器304以及最大指標暫存器306分別用以在預取單元1開始追蹤一存儲器區塊的存取後，持續地指向此存儲器區塊中已被存取的最低以及最高的快取線的索引(index)。預取單元1還包括一最小改變計數器308以及一最大改變計數器312。最小改變計數器308以及最大改變計數器312分別用以在預取單元1開始追蹤此存儲器區塊的存取後，計算最小指標暫存器304以及最大指標暫存器306改變的次數。預取單元IM亦包括一總計數器314，用以在預取單元IM開始追蹤此存儲器區塊的存取後，計算已被存取的快取線的總數。預取單元1亦包括一中間指標暫存器316，用以在預取單元IM開始追蹤此存儲器區塊的存取後，指向此存儲器區塊的中間預取存儲器線的索引(例如最小指標暫存器304的計數值以及最大改變計數器312的計數值的平均)。預取單元1亦包括一方向暫存器342(directionregister)、一樣態暫存器344，一樣態周期暫存器346、一樣態區域暫存器348以及一搜尋指標暫存器352，其各功能如下所述。預取單元IM亦包括多個周期匹配計數器318(periodmatchcounter)。每一周期匹配計數器318維持一不同周期的一計數值。在一實施例中，周期為3、4以及5。周期是指中間指標暫存器316左/右的位數。周期匹配計數器318的計數值在區塊的每一存儲器存取進行的後更新。當區塊位遮罩暫存器302指示在周期中對中間指標暫存器316左邊的存取與對中間指標暫存器316右邊的存取相匹配時，預取單元IM則接著增加與該周期相關的周期匹配計數器318的計數值。關於周期匹配計數器318更詳細的應用以及操作，將特別在下述的圖4、圖5講述。預取單元IM亦包括一預取要求隊列328、一提取指標器324(poppointer)以及一推進指標器326(pushpointer)。預取要求隊列3包括一循環的項目(entry)隊列，上述項目的每一個用以儲存預取單元124的操作(特別是關於第4、6以及7圖)所產生的預取要求。推進指標器3指出將分派至預取要求隊列328的下一個項目(entry)。提取指標器3M指出將從預取要求隊列3移出的下一個項目。在一實施例中，因為預取要求可能以失非循序的方式(outoforder)結束，所以預取要求隊列3是可以非循失序的方式提取(popping)已完成的(completed)項目。在一實施例中，預取要求隊列328的大小是由於線路流程中，所有要求進入第二級快取存儲器118的標記的線路(tagpipeline)的線路流程而選擇的，於是使得預取要求隊列328中項目的數目至少和第二級快取存儲器118內的管線層級(stages)—樣多。預取要求將維持直至第二級快取存儲器118的管線結束，在這個時間點，要求)可能是三個結果之一，如圖7更詳細的敘述，亦即命中(hitin)第二級快取存儲器118、重新執行(r印lay)、或者推進一全隊列管道項目，用以從系統存儲器預取需要的數據。預取單元IM亦包括控制邏輯322，控制邏輯322控制預取單元IM的各元件執行其功能。雖然圖3隻顯示出一組與一主動(active)存儲器區塊有關的硬體單元332(區塊位遮罩暫存器302、區塊號碼暫存器303、最小指標暫存器304、最大指標暫存器306、最小改變計數器308、最大改變計數器312、總計數器314、中間指標暫存器316、樣態順序暫存器346、樣態區域暫存器348以及搜尋指標暫存器35，但預取單元IM可包括多個個如圖3所示的硬體單元332，用以追蹤多個主動存儲器區塊的存取。在一實施例中，微處理器100亦包括一個或多個高度反應式的(highlyreactive)預取單元(未圖示)，高度反應式的預取單元是在非常小的暫時樣本(sample)中使用不同的演算法來進行存取，並且與預取單元1配合操作，其說明如下。由於此處所述的預取單元1分析較大存儲器存取的數目(相較於高度反應式的預取單元)，其必趨向使用更長的時間去開始預取一新的存儲器區塊，如下所述，但卻比高反應式的預取單元更精確。因此，使用高度反應式的預取單元與預取單元124同時操作，微處理器100可擁有高反應式的預取單元的更快反應時間以及預取單元124的高精確度。另外，預取單元IM可監控來自其他預取單元的要求，並且在其預取演算法中使用這些要求。如圖4所示為圖2的微處理器100的操作流程圖，並且特別是圖3的預取單元IM的操作。流程開始於步驟402。在步驟402中，預取單元IM接收一載入/儲存存儲器存取要求，用以存取對一存儲器地址的一載入/儲存存儲器存取要求。在一實施例中，預取單元1在判斷預取哪些快取線時，會將出載入存儲器存取要求與儲存存儲器存取要求加以區分。在其他實施例中，預取單元IM並不會在判斷預取哪些快取線時，辨別載入以及儲存。在一實施例中，預取單元IM接收載入/儲存單元134所輸出的存儲器存取要求。預取單元IM可接收來自不同來源的存儲器存取要求，上述來源包括(但不限於)載入/儲存單元134、第一級數據快取存儲器116(例如第一級數據快取存儲器116所產生的一分派要求，於載入/儲存單元134存儲器存取未擊中第一級數據快取存儲器116時)，和/或其他來源，例如微處理器100的用以執行與預取單元1不同預取演算法以預取數據的其他預取單元(未圖示)。流程進入步驟404。在步驟404中，控制邏輯322根據比較存儲器存取地址與每一區塊號碼暫存器303的數值，判斷是否對一主動區塊的存儲器進行存取。也就是，控制邏輯322判斷圖3所示的硬體單元332是否已被分派給存儲器存取要求所指定的存儲器地址所相關的存儲器區塊。若是，則進入步驟406。在步驟406中，控制邏輯322分派圖3所示的硬體單元332給相關的存儲器區塊。在一實施例中，控制邏輯322以一輪替(round-robin)的方式分派硬體單元332。在其他實施例，控制邏輯322為硬體單元332維持最久未用到的頁取代法(least-recently-used)的信息，並且以一最久未用到的頁取代法(least-recently-used)的基礎進行分派。另外，控制邏輯322會初始化所分派的硬體單元332。特別是，控制邏輯322會清除區塊位遮罩暫存器302的所有位，將存儲器存取地址的上層位填充(populate)至區塊號碼暫存器303，並且清除最小指標暫存器304、最大指標暫存器306、最小改變計數器308、最大改變計數器312、總計數器314以及周期匹配計數器318為0。流程進入到步驟408。在步驟408中，控制邏輯322根據存儲器存取地址更新硬體單元332，如圖5所述。流程進入步驟412。在步驟412中，硬體單元332測試(examine)總計數器314用以判斷程序是否已對存儲器區塊進行足夠的存取要求，以便檢測一存取樣態。在一實施例中，控制邏輯322判斷總計數器314的計數值是否大於一既定值。在一實施例中，此既定值為10，然而此既定值有很多種本發明不限於此。若已執行足夠的存取要求，流程進行至步驟414；否則流程結束。在步驟414中，控制邏輯322判斷在區塊位遮罩暫存器302中所指定的存取要求是否具有一個明顯的趨勢。也就是說，控制邏輯322判斷存取要求有明顯向上的趨勢(存取地址增加)或是向下的趨勢(存取地址減少)。在一實施例中，控制邏輯322根據最小改變計數器308以及最大改變計數器312兩者的差值(difference)是否大於一既定值來決定存取要求是否有明顯的趨勢。在一實施例中，既定值為2，而在其他實施例中既定值可為其他數值。當最小改變計數器308的計數值大於最大改變計數器312的計數值一既定值，則有明顯向下的趨勢；反之，當最大改變計數器312的計數值大於最小改變計數器308的計數值一既定值，則有明顯向上的趨勢。當有一明顯的趨勢已產生，則進入步驟416，否則結束流程。在步驟416中，控制邏輯322判斷在區塊位遮罩暫存器302所指定的存取要求中是否為具有一明顯的樣態周期贏家(patternperiodwinner)。在一實施例中，控制邏輯322根據周期匹配計數器318的一個與其他周期匹配計數器318計數值的差值是否大於一既定值來決定是否有一明顯的樣態周期贏家。在一實施例中，既定值為2，而在其他實施例中既定值可為其他數值。周期匹配計數器318的更新操作將於圖5加以詳述。當有一明顯的樣態周期贏家產生，流程進行到步驟418；否則，流程結束。在步驟418中，控制邏輯322填充方向暫存器342以指出步驟414所判斷的明顯的方向趨勢。另外，控制邏輯322用在步驟416檢測的清楚贏家樣態周期(clearwinningpatternperiod)N填充樣態順序暫存器346。最後，控制邏輯322將步驟416所檢測到的明顯的贏家樣態周期填充至樣態暫存器344中。也就是說，控制邏輯322用區塊位遮罩暫存器302的N位至中間指標暫存器316的右側或者左側(根據圖5步驟518所述而匹配)來填充樣態暫存器；344。流程進行到步驟422。在步驟422中，控制邏輯322根據所檢測到的方向以及樣態開始對存儲器區塊中尚未被預取的快取線(non-fetchedcacheline)進行預取(如圖6中所述)。流程在步驟422結束。圖5所示為圖3所示的預取單元IM執行圖4所示的步驟408的操作流程。流程開始於步驟502。在步驟502中，控制邏輯322增加總計數器314的計數值。流程進行到步驟504。在步驟504中，控制邏輯322判斷目前的存儲器存取地址(特別是指，最近存儲器存取地址所相關的快取線的存儲器區塊的索引值)是否大於最大指標暫存器306的值。若是，流程進行到步驟506；若否則流程進行至步驟508。在步驟506中，控制邏輯322用最近存儲器存取地址所相關的快取線的存儲器區塊的索引值來更新最大指標暫存器306，並增加最大改變計數器312的計數值。流程進行到步驟514。在步驟508中，控制邏輯322判斷被最近存儲器存取地址所相關的快取線的存儲器區塊的索引值是否小於最小指標暫存器304的值。若是，流程進行至步驟512；若否，則流程進行至步驟514。在步驟512中，控制邏輯322用最近存儲器存取地址所相關的快取線的存儲器區塊的索引值來更新最小指標暫存器304，並增加最小改變計數器308的計數值。流程進行到步驟514。在步驟514中，控制邏輯322計算最小指標暫存器304與最大指標暫存器306的平均值，並且用所算的出平均值更新中間指標暫存器316。流程進行到步驟516。在步驟516中，控制邏輯322檢查區塊位遮罩暫存器302，並且以中間指標暫存器316為中心，切割成左側與右側各N位，其中N為與每一周期匹配計數器318有關的每一個的位的位數。流程進行到步驟518。在步驟518中，控制邏輯322決定在中間指標暫存器316的左側的N位是否與中間指標暫存器316的右側的N位相匹配。若是，流程進行到步驟522；若否，則流程結束。在步驟522中，控制邏輯322增加具有一N周期的周期匹配計數器318的計數值。流程結束於步驟522。圖6所示為圖3的預取單元IM執行圖4的步驟422的操作流程圖。流程開始於步驟602。在步驟602中，控制邏輯322初始化會在離開檢測方向的中間指標暫存器316的樣態順序暫存器346中，對搜尋指標暫存器352以及樣態區域暫存器(pattenlocation)348進行初始化。也就是說，控制邏輯322會將搜尋指標暫存器352以及樣態區域暫存器348初始化成中間指標暫存器316與所檢測到的周期(N)兩者之間相加/相減後的值。例如，當中間指標暫存器316的值為16，N為5，並且方向暫存器342所示的趨勢為向上時，控制邏輯322則將搜尋指標暫存器352以及樣態區域暫存器348初始化為21。因此，在本例中，為了比較的目的(如下所述)，樣態暫存器344的5位可設置於區塊位遮罩暫存器302的位21到25。流程進行到步驟604。在步驟604中，控制邏輯322測試區塊位遮罩暫存器302中在方向暫存器342所指的位以及樣態暫存器344中的對應位(該位是位於樣態區域暫存器348中，用以對應區塊位遮罩暫存器)，用以預測是否預取存儲器區塊中的對應快取線。流程進行到步驟606。在步驟606中，控制邏輯322預測是否需要所測試的快取線。當樣態暫存器344的位為真(true)，控制邏輯322則預測此快取線是需要的，樣態預測程序將會存取此快取線。若快取線是需要的，流程進行到步驟614;否則，流程進行到步驟608。在步驟608中，控制邏輯322根據方向暫存器342是否已到達區塊位遮罩暫存器302的盡頭，判斷在存儲器區塊中是否有其他未測試的快取線。若已無未測試的快取線，則流程結束；否則，流程進行至步驟612。在步驟612中，控制邏輯322增加/減少方向暫存器342的值。另外，若方向暫存器342已超過樣態暫存器344的最後一位時，控制邏輯322將用方向暫存器342的新數值更新樣態區域暫存器348，例如將樣態暫存器344轉移(shift)至方向暫存器342的位置。流程進行到步驟604。在步驟614中，控制邏輯322決定所需要的快取線是否已被預取。當區塊位遮罩暫存器302的位為真，控制邏輯322則判斷所需要的快取線已被預取。若所需要的快取線已被預取，流程進行到步驟608；否則，流程進行到步驟616。在判斷步驟616中，若方向暫存器342為向下，控制邏輯322決定判斷列入參考的快取線是否自最小指標暫存器304多於一既定值(既定值在一實施例中為16)；，或者若方向暫存器342為向上，控制邏輯322將判斷決定列入參考的快取線是否自最大指標暫存器306多於一既定值。若控制邏輯322決定列入參考的多於上述的判斷為真既定值，則流程結束；否則，流程進行到判斷步驟618。值得注意的是，若快取線大幅多於(遠離)最小指標暫存器304/最大指標暫存器306則流程結束，但這樣並不代表預取單元IM將不接著預取存儲器區塊的其它快取線，因為根據圖4的步驟，對存儲器區塊的快取線的後續存取亦會再觸發更多的預取操作。在步驟618中，控制邏輯322判斷預取要求隊列3是否滿了。若是預取要求隊列3滿了，則流程進行到步驟622，否則流程進行到步驟624。在步驟622中，控制邏輯322暫停(stall)直到預取要求隊列3不滿(non-full)為止。流程進行到步驟624。在步驟624中，控制邏輯322推進一項目(entry)至預取要求隊列328，以預取快取線。流程進行到步驟608。如圖7所示為圖3的預取要求隊列3的操作流程圖。流程開始於步驟702。在步驟702中，在步驟624中被推進到預取要求隊列3中的一預取要求被允許進行存取(其中此預取要求用以對第二級快取存儲器118進行存取)，並繼續進行至第二級快取存儲器118的管道。流程進行到步驟704。在步驟704中，第二級快取存儲器118判斷快取線地址是否命中第二級快取存儲器118。若快取線地址命中第二級快取存儲器118，則流程進行到步驟706；否則，流程進行到判斷步驟708。在步驟706中，因為快取線已經在第二級快取存儲器118中準備好，故不需要預取快取線，流程結束。在步驟708中，控制邏輯322判斷第二級快取存儲器118的回應是否為此預取要求必須被重新執行。若是，則流程進行至步驟712；否則，流程進行至步驟714。在步驟712中，預取快取線的預取要求重新推進(re-pushed)至預取要求隊列328中。流程結束於步驟712。在步驟714中，第二級快取存儲器118推進一要求至微處理器100的一全隊列(fillqueue)(未圖示)中，用以要求總線接口單元122將快取線讀取至微處理器100中。流程結束於步驟714。如圖9所示為圖2的微處理器100的操作範例。如圖9所示為對一存儲器區塊進行十次存取後，區塊位遮罩暫存器302(在一位位置上的星號表示對所對應的快取線進行存取)、最小改變計數器308、最大改變計數器312、以及總計數器314在第一、第二以及第十存取的內容。在圖9中，最小改變計數器308稱為」cntrjiiiruchange」，最大改變計數器312稱為」cntr_max_change」，以及總計數器314稱為」cntr_total」。中間指標暫存器316的位置在圖9中則以」M」所指示。由於對地址0X4dced300所進行的第一次存取(如圖4的步驟40是在存儲器區塊中位於索引12上的快取線上進行，因此控制邏輯322將設定區塊位遮罩暫存器302的位12(圖4的步驟408)，如圖所示。另外，控制邏輯322將更新最小改變計數器308、最大改變計數器312以及總計數器314(圖5的步驟502、506以及512)。由於對地址0xked260的第二次存取是在存儲器區塊中位於索引9上的快取線進行，控制邏輯322根據將設定區塊位遮罩暫存器302的位9，如圖所示。另外，控制邏輯322將更新最小改變計數器308以及總計數器314的計數值。在第三到第十次存取中(第三到第九次存取的地址未予圖示，第十次的存取地址為0x4dced6c0)，控制邏輯322根據會對區塊位遮罩暫存器302進行適當元的設置，如圖所示。另外，控制邏輯322對應於每一次存取更新最小改變計數器308、最大改變計數器312以及總計數器314的計數值。圖9底部為控制邏輯322在每個執行十次的存儲器的存取中，當執行完步驟514到522後的周期匹配計數器318的內容。在圖9中，周期匹配計數器318稱為」cntr_peri0d_N_matches」，其中N為1、2、3、4或者5。如圖9所示的範例，雖然符合步驟412的準則(總計數器314至少為十)以及符合步驟416的準則(周期5的周期匹配計數器318較其他所有的周期匹配計數器318至少大於2)，但不符合步驟414的準則(最小改變計數器308以及區塊位遮罩暫存器302之間的差少於2)。因此，此時將不會在此存儲器區塊內執行預取操作。如圖9底部亦顯示在周期3、4以及5中，從周期3、4以及5至中間指標暫存器316的右側與左側的樣態。如圖10所示為圖2的微處理器100延續圖9所示的範例的操作流程圖。圖10描繪相似於圖9的信息，但不同處於在對存儲器區塊的進行第十一次以及第十二次的存取(第十二次存取的地址為0X4dced760)。如圖所示，其符合步驟412的準則(總計數器314至少為十)、步驟414的準則(最小改變計數器308以及區塊位遮罩暫存器302之間的差至少為2)以及步驟416的準則(周期5的周期匹配計數器318在周期5的計數較其他所有的周期匹配計數器318至少大於2)。因此，根據圖4的步驟418，控制邏輯322填充(populate)方向暫存器342(用以指出方向趨勢為向上)、樣態順序暫存器346(填入數值幻、樣態暫存器344(用樣態「**」或者「01010」)。控制邏輯322亦根據圖4的步驟422與圖6，為存儲器區塊執行預取預測，如圖11所示。圖10亦顯示控制邏輯322在圖6的步驟602操作中，方向暫存器342在位21的位置。如圖11所示為圖2的微處理器100延續圖9以及圖10的範例的操作流程圖。圖11經由範例中描繪十二不同範例的每一個(表標示成0到11)經過圖6的步驟604到步驟616直到存儲器區塊的快取線被預取單元IM預測發現需要被預取的存儲器區塊的的操作。如圖所示，在每一範例中，方向暫存器342的值是根據圖6步驟612而增加。如圖11所示，在範例5以及10中，樣態區域暫存器348會根據圖6的步驟612被更新。如範例0、2、4、5、7以及10所示，由於在方向暫存器342的位為假(false)，樣態指出在方向暫存器342上的快取線將不被需要。圖中還顯示，在範例1、3、6以及8中，由於在方向暫存器342中樣態暫存器；344的位為真(ture)，樣態暫存器344指出在方向暫存器342上的快取線將被需要，然而快取線已經準備被取出(fetched)，如區塊位遮罩暫存器302的位為真(ture)的指示。最後如圖所示，在範例11中，由於在方向暫存器342中樣態暫存器344的位為真(ture)，所以樣態暫存器344指出在方向暫存器342上的快取線將被需要，但是因區塊位遮罩暫存器302的位為假(false)，所以此快取線尚未被取出(fetched)。因此，控制邏輯322根據圖6的步驟6M推進一預取要求至預取要求隊列3中，用以預取在地址0X4dced800的快取線，其對應於在區塊位遮罩暫存器302的位32。在一實施例中，所描述的一個或多個既定值可藉由作業系統(例如經由一樣態特定暫存器(modelspecificregister,MSR))或者經由微處理器100的熔絲(fuses)來編程，其中熔絲可在微處理器100的生產過程中熔斷。在一實施例中，區塊位遮罩暫存器302的大小可為了節省電源(power)以與及裸片晶片大小機板(dierealestate)而減小。也就是說，在每一區塊位遮罩暫存器302中的位數，將少於在一存儲器區塊中快取線的數量。例如，在一實施例中，每一區塊位遮罩暫存器302的位數僅為存儲器區塊所包含的快取線的數量的一半。區塊位遮罩暫存器302僅追蹤對上半區塊或者下半區塊的存取，端看存儲器區塊的那一半先被存取，而一額外的位用以指出存儲器區塊的下半部或者上半部是否先被存取。在一實施例中，控制邏輯322並不如步驟516/518所述地測試中間指標暫存器316上下N位，而是包括一序列引擎(serialengine)，一次一個或兩個位地掃描區塊位遮罩暫存器302，用以尋找周期大於一最大周期的樣態(如前所述為5位)。在一實施例中，若在步驟414沒有檢測出明顯的方向趨勢、或者在步驟416並未檢測出明顯的樣態周期、以及總計數器314的計數值到達一既定臨界值(用以指出在存儲器區塊中的大部份的快取線已被存取)時，控制邏輯322則繼續執行以及預取在存儲器區塊中剩下的快取線。上述既定臨界值為存儲器區塊的快取存儲器數量的一相對高的百分比值，例如區塊位遮罩暫存器302的位的值。結合第二集快取存儲器以及第一級數據快取存儲器的預取單元近代的微處理器包括具有一階層結構的快取存儲器。典型地，一微處理器包括一又小又快的第一級數據快取存儲器以及一較大但較慢的第二級快取存儲器，分別如圖2的第一級數據快取存儲器116以及第二級快取存儲器118。具有一階層結構的快取存儲器有利於預取數據至快取存儲器，以改善快取存儲器的命中率速度(hitrate)。由於第一級數據快取存儲器116的速度較快，故較佳的狀況為預取數據至第一級數據快取存儲器116。然而，由於第一級數據快取存儲器116的存儲器容量較小，快取存儲器命中的速度率可能實際上較差變慢，由於如果預取單元不正確預取數據進第一級數據快取存儲器116使得最後數據是不需要的，便需要而替代以其他需要的數據做替代。因此，數據被載入第一級數據快取存儲器116或者第二級快取存儲器118的結果，是預取單元是否能正確預測數據是否被需要的函數(function)。因為第一級數據快取存儲器116被要求較小的尺寸，第一級數據快取存儲器116傾向較小的容量以及因此具有較差的準確性；反之，由於第二級快取存儲器標籤以及數據陣列的大小使得第一級快取存儲器預取單元的大小顯得很小，所以一第二級快取存儲器預取單元可為較大的容量因此具有較佳的準確性。本發明實施例所述微處理器100的優勢，在於一載入/儲存單元134用以作為第二級快取存儲器118以及第一級數據快取存儲器116的預取需要的基礎。本發明的實施例提升載入/儲存單元134(第二級快取存儲器118)的準確性，用以應用在解決上述預取進入第一級數據快取存儲器116的問題。再者，實施例中也完成了運用單體邏輯(singlebodyoflogic)來處理第一級數據快取存儲器116以及第二級快取存儲器118的預取操作的目標。如圖12所示為根據本發明各實施例的微處理器100。圖12的微處理器100相似於圖2的微處理器100並具有如下所述的額外的特性。第一級數據快取存儲器116提供第一級數據存儲器地址196至預取單元124。第一級數據存儲器地址196藉由載入/儲存單元134對第一級數據快取存儲器116進行載入/儲存存取的實體地址。也就是說，預取單元1會隨著載入/儲存單元134存取第一級數據快取存儲器116時進行竊聽(eavesdrops)。預取單元1提供一樣態預測快取線地址194至第一級數據快取存儲器116的一隊列198，樣態預測快取線地址194為快取線的地址，其中的快取線是預取單元1根據第一級數據存儲器地址196預測載入/儲存單元134即將對第一級數據快取存儲器116所提出的要求。第一級數據快取存儲器116提供一快取線配置要求192至預取單元124，用以從第二級快取存儲器118要求快取線，而這些快取線的地址儲存於隊列198中。最後，第二級快取存儲器118提供所要求的快取線數據188至第一級數據快取存儲器116。預取單元IM亦包括第一級數據搜尋指標器172以及第一級數據樣態地址178，如圖12所示。第一級數據搜尋指標器172以及第一級數據樣態地址178的用途與圖4相關且如下所述。如圖13所示為圖12的預取單元124的操作流程圖。流程開始於步驟1302。在步驟1302中，預取單元IM從第一級數據快取存儲器116接收圖12的第一級數據存儲器地址196。流程進行到步驟1304。在步驟1304中，由於預取單元124已事先檢測到一存取樣態並已開始從系統存儲器預取快取線進入第二級快取存儲器118，故預取單元IM檢測屬於一存儲器區塊(例如分頁(page))的第一級數據存儲器地址196，如第1至11圖中相關處所述。仔細而言，由於存取樣態已被檢測，故預取單元1用以維持(maintain)—區塊號碼暫存器303，其指定存儲器區塊的基本地址。預取單元1藉由檢測區塊號碼暫存器303的位是否匹配第一級數據存儲器地址196的對應位，來檢測第一級數據存儲器地址196是否落在存儲器區塊中。流程進行到步驟1306。在步驟1306中，從第一級數據存儲器地址196開始，預取單元IM在存儲器區塊中所檢測到的存取方向(detectedaccessdirection)上尋找下兩個快取線，這兩個快取線與先前所檢測的存取方向有關。步驟1306更詳細的執行操作將於後續的圖14中加以說明。流程進行到步驟1308。在步驟1308中，預取單元IM提供在步驟1306找到的下兩個快取線的實體地址至第一級數據快取存儲器116，作為樣態預測快取線地址194。在其他實施例中，預取單元124所提供的快取線地址的數量可多於或少於2。流程進行到步驟1312。在步驟1312中，第一級數據快取存儲器116把在步驟1308中所提供的地址推進至隊列198中。流程進行到步驟1314。在步驟1314中，無論何時只要隊列198為非空(non-empty)，第一級數據快取存儲器116將下一個地址取出隊列198，並發出一快取線配置要求192至第二級快取存儲器118，以便取得在該地址的快取線。然而，若在隊列198的一地址已出現於第一級數據快取存儲器116，第一級數據快取存儲器116將拋棄(dumps)該地址以及放棄自第二級快取存儲器118要求其快取線。第二級快取存儲器118接著提供所要求的快取線數據188至第一級數據快取存儲器116。流程結束於步驟1314。如圖14所示為圖12所示的預取單元IM根據圖13的步驟1306的操作流程圖。圖14所敘述的操作是在圖3所檢測到樣態方向為向上(upward)的狀況下。然而，若所檢測到的樣態方向為向下，預取單元1亦可用以執行同樣的功能。步驟1402到1408的操作用以將圖3中的樣態暫存器344放置在存儲器區塊中適當的位置，使得預取單元IM藉由從第一級數據存儲器地址196上開始的樣態暫存器344的樣態搜尋下兩個快取線中進行搜尋，並只要有需求時在該存儲器區塊上複製該樣態暫存器344的樣態344即可。流程開始於步驟1402。在步驟1402中，預取單元IM以相似於圖6在步驟602初始化搜尋指標暫存器352以及樣態區域暫存器348的方式，用圖3的樣態順序暫存器346以及中間指標暫存器316的總和，來初始化圖12的第一級數據搜尋指標器172以及第一級數據樣態地址178。例如，若中間指標暫存器316的值為16以及樣態順序暫存器346為5，並且方向暫存器342的方向為往上，預取單元1初始化第一級數據搜尋指標器172以及第一級數據樣態地址178至21。流程進行到步驟1414。在步驟14014中，預取單元IM決定第一級數據存儲器地址196是否落入在具有目前所指定位置的樣態暫存器344的樣態中，樣態的目前位置開始是根據步驟1402所決定的，並可根據步驟1406進行更新。也就是說，預取單元IM決定第一級數據存儲器地址196的適當位(relevantbits)的值(即除了去確認存儲器區塊的位，以及具有快取線中用來的指定字節補償偏移(byteoffset)的位外)，是否大於或者等於第一級數據搜尋指標器172的值，以及是否小於或者等於第一級數據搜尋指標器172的值與樣態順序暫存器346的值兩者所相加的總合。若第一級數據存儲器地址196落入(fallwithin)樣態暫存器344的樣態中，流程進行到步驟1408；否則流程進行到步驟1406。在步驟1406中，預取單元IM根據樣態順序暫存器346增加第一級數據搜尋指標器172以及第一級數據樣態地址178。根據步驟1406(與後續的步驟1418)所述的操作，若第一級數據搜尋指標器172已達到存儲器區塊的終點則結束搜尋。流程回到步驟1404。在步驟1408中，預取單元IM將第一級數據搜尋指標器172的值設置(set)為第一級數據存儲器地址196所相關的快取線的存儲器頁的偏移量(offset)。流程進行到步驟1412。在步驟1412中，預取單元IM在第一級數據搜尋指標器172中測試樣態暫存器344中的位。流程進行到步驟1414。在步驟1414中，預取單元124決定步驟1412所測試的位是否設置好了。如果在步驟1412所測試的位設置好了，流程進行到步驟1416；否則流程進行到步驟1418。在步驟1416中，預取單元IM將步驟1414被樣態暫存器344所預測的快取線標記為已準備好傳送實體地址至第一級數據快取存儲器116，以作為一樣態預測快取線地址194。流程結束於步驟1416。在步驟1418中，預取單元IM增加第一級數據搜尋指標器172的值。另外，若第一級數據搜尋指標器172已超過上述樣態暫存器344的最後一個位，預取單元IM則用第一級數據搜尋指標器172的新的數值更新第一級數據搜尋指標器172的值，亦即轉換(shift)樣態暫存器344至新的第一級數據搜尋指標器172的位置。步驟1412到1418的操作反覆執行，直到兩快取線(或者快取線的其他既定值)被找到為止。流程結束於步驟1418。圖13中預取快取線至第一級數據快取存儲器116的好處是第一級數據快取存儲器116以及第二級快取存儲器118所需要的改變較小。然而，在其他實施例中，預取單元124亦可不提供樣態預測快取線地址194至第一級數據快取存儲器116。例如，在一實施例中，預取單元1直接要求總線接口單元122自存儲器獲擷取快取線，然後將所接收的寫入快取線寫入至第一級數據快取存儲器116。在另一實施例中，預取單元124自用以提供數據至預取單元124的第二級快取存儲器118要求並取得快取線(如果為命中失敗(missing)則從存儲器取得快取線)，並將收到的快取線寫入至第一級數據快取存儲器116。在其他實施例中，預取單元124自第二級快取存儲器118要求快取線(如果為命中失敗(missing)則從存儲器取得快取線)，其直接將快取線寫入第一級數據快取存儲器116。如上所述，本發明的各實施例的好處在於具有單一的預取單元IM總計數器314，作為第二級快取存儲器118以及第一級數據快取存儲器116兩者的預取需要的基礎。雖然圖2、圖12以及圖15所示(如下討論的內容)為名明不同的區塊，預取單元124在空間安排上可佔據鄰近於第二級快取存儲器118的標籤(tag)以及數據列(dataarray)的位置並且概念上包括第二級快取存儲器118，如圖21所示。各實施例允許載入/儲存單元134具大空間的安排來提升的其精確度與其大空間的需求，以應用一單體邏輯來處理第一級數據快取存儲器116以及第二級快取存儲器118的預取操作，以解決現有技術中只能預取進入數據給容量較小的第一級數據快取存儲器116的問題。具有減少跨頁上的暖機損失(warm-upPenalty)的定界框預取單元本發明所述的預取單元IM在一存儲器區塊(例如，一實體存儲器頁)上檢測較複雜的存取樣態(例如，一實體存儲器頁)，其不同於現有一般預取單元的檢測。舉例而言，預取單元IM可以根據一樣態檢測正在進行存取一存儲器區塊的程序，即使微處理器100的非循失序執行(out-of-orderexecution)管線(pipeline)會不以程序命令的順序而重新排序(re-order)存儲器存取，這可能會造成現有一般預取單元不去檢測存儲器存取樣態以及而導致沒有預取操作。這是由於預取單元1隻考慮對存儲器區塊的進行有效地存取，而時間順序(timeorder)並非其考量點。然而，為了滿足識別更複雜的存取樣態和/或重新排序存取樣態的能力，相較於現有的預取單元，本發明的預取單元IM可能需要一較長的時間去檢測存取樣態，如下所述的「暖機時間(warm-uptime)」。因此需要一減少預取單元124暖機時間的方法。預取單元IM用以預測一個之前藉由一存取樣態正在存取一存儲器區塊的程序，是否已經跨到(crossover)實際上與舊的存儲器區塊相鄰的一新存儲器區塊，以及預測此程序是否會根據相同的樣態繼續存取這個新的存儲器區塊。因應於此，預取單元IM使用來自舊的存儲器區塊的樣態、方向以及其他相關信息，以加快在新的存儲器區塊檢測存取樣態的速度，即減少暖機時間。如圖15所示為具有一預取單元124的微處理器100的方塊圖。圖15的微處理器100相似於圖2以及圖12的微處理器100，並且具有如下所述的其它特性。如圖3中的相關敘述，預取單元IM包括多個硬體單元332。每一硬體單元332相較於圖3所述還包括一存儲器區塊虛擬雜湊虛擬地址欄(hashedvirtualaddressofmemory,HVAMB)354以及一狀態欄(status)356。在圖4所述的步驟406初始化已分派的硬體單元332的過程中，預取單元IM取出區塊號碼暫存器303中的實體區塊碼(physicalblocknumber)，並在將實體區塊碼轉譯成一虛擬地址後，根據後續圖17所述的步驟1704所執行的相同雜湊法則(thesamehashingalgorithm)將實體區塊碼轉譯成一虛擬地址(雜湊(hash)此的虛擬地址)，並將其雜湊演算的結果儲存至存儲器區塊虛擬雜湊地址欄354。狀態欄356具有三種可能的數值非主動(inactive)、主動(active)或者試用(probationary)，如下所述。預取單元1亦包括一虛擬雜湊表(virtualhashtable,VHT)162，關於虛擬雜湊表162組織架構以及操作的詳細說明請參考後續第16到19圖的敘述。如圖16所示為圖15的虛擬雜湊表162。虛擬雜湊表162包括多個項目，最好組織成一隊列。每一項目包括一有效位(validbit)(未圖示)以及三個欄一負1雜湊虛擬地址1602(HVAMl)、一未修改雜湊虛擬地址1604(HVAUN)以及一正1雜湊虛擬地址1606(HVAP1)。用以填充上述欄位的數值的生成請參考後續圖17所述。圖17所述為圖15的微處理器100的操作流程圖。流程開始於步驟1702。在步驟1702中，第一級數據快取存儲器116接收來自載入/儲存單元134的一載入/儲存要求，其載入/儲存要求包括一虛擬地址。流程進行到步驟1704。在步驟1704中，第一級數據快取存儲器116對步驟1702中所接收的雜湊地址選擇的位執行一雜湊功能(函數)，用以產生一未修改雜湊虛擬地址1604(HVAUN)。另外，第一級數據快取存儲器116增加一存儲器區塊大小(MBQ至在步驟1702所接收的雜湊地址所選擇的位，用以產生一加總值，並對加總值執行一雜湊功能，以產生一正1雜湊虛擬地址1606(HVAPl)。另外，第一級數據快取存儲器116從在步驟1702所接收的雜湊地址選擇的位，減去存儲器區塊的大小，用以產生一差值，並對此差值執行一雜湊功能，以產生一負1雜湊虛擬地址1602(HVAMl)。在一實施例中，存儲器區塊大小為4KB。在一實施例中，虛擬地址為40位，虛擬地址的位39:30以及11:0被會雜湊功能忽略。剩下的18個虛擬地址位為」已處理(dealt)」，如已擁有的信息，是通過雜湊位位置來處理。其想法為虛擬地址的較低位具有最高亂度(entropy)以及較高位具有最低亂度。用此方法處理可保證亂度階級(entropylevel)為較一致交叉雜湊的位。在一實施例中，剩下的虛擬地址的18位是根據後續表1的方法雜湊至6位。然而，在其他實施例中，亦可考慮使用不同雜湊演算法；此外，若有性能支配空間(performancedominatesspace)以及電力消耗的設計考量，實施例可考慮不使用雜湊演算法。流程進行到步驟1706。assignhash[5]=VA[29]"VA[18]"VA[17]assignhash[4]=VA[28]"VA[19]"VA[16]assignhash[3]=VA[27]"VA[20]"VA[15]assignhash[2]=VA[26]"VA[21]"VA[14]assignhash[l]=VA[25]"VA[22]"VA[13]assignhash=VA[24]"VA[23]"VA[12]表1在步驟1706中，第一級數據快取存儲器116提供在步驟1704中所產生的未修改雜湊虛擬地址(HVAUN)1604、正1雜湊虛擬地址(HVAPl)1606以及負1雜湊虛擬地址(HVAMl)1602至預取單元124。流程進行到步驟1708。在步驟1708中，預取單元124用步驟1706所接收的未修改雜湊虛擬地址(HVAUN)1604、正1雜湊虛擬地址(HVAPl)1606以及負1雜湊虛擬地址(HVAMl)1602選擇性地更新虛擬雜湊表162。也就是說，如果虛擬雜湊表162已包括一具有未修改雜湊虛擬地址1604(HVAUN)、正1雜湊虛擬地址1606(HVAPl)以及負1雜湊虛擬地址1602(HVAMl)的項目，預取單元1則放棄更新虛擬雜湊表162。相反地，預取單元IM則以先進先出(first-in-first-out)的方式將未修改雜湊虛擬地址1604(HVAUN)、正1雜湊虛擬地址1606(HVAPl)以及負1雜湊虛擬地址1602(HVAMl)推進至虛擬雜湊表162最頂端的項目，並將所推進的項目標記為有效(valid)。流程結束於步驟1708。如圖18所示為圖16的虛擬雜湊表162在預取單元124在載入/儲存單元134根據圖17的敘述操作的後的內容，其中在載入/儲存單元134因應於程序的執行，已經由兩存儲器區塊(標示為AandA+MBS)在一向上的方向上進行，並進入一第三存儲器區塊(標示為A+2*MBQ，以便回應已填充虛擬雜湊表162的預取單元124。仔細而言，虛擬雜湊表162距離尾端的兩個項目的項目包括在負1雜湊虛擬地址(HVAMl)1602的A-MBS的雜湊、在未修改雜湊虛擬地址(HVAUN)1604的A的雜湊以及在正1雜湊虛擬地址(HVAPl)1606的A+MBS的雜湊；虛擬雜湊表162項目是距離尾端的一個項目的項目包括負1雜湊虛擬地址(HVAMl)1602的A的雜湊、在未修改雜湊虛擬地址(HVAUN)1604的A+MBS的雜湊以及在正1雜湊虛擬地址(HVAPl)1606的A+2*MBS的雜湊；虛擬雜湊表162項目是在尾端的項目(，即最近時間所最近的推進的項目)包括在負1雜湊虛擬地址(HVAMl)1602的A+MBS的雜湊、在未修改雜湊虛擬地址(HVAUN)1604的A+2*MBS的雜湊以及在正1雜湊虛擬地址(HVAPl)1606的A+3*MBS的雜湊。如圖19所示(由圖19A以及圖19B組成)的圖5的預取單元124的操作流程圖。流程開始於步驟1902。在步驟1902中，第一級數據快取存儲器116傳送一新的配置要求(allocationrequest,AR)至第二級快取存儲器118。新的配置要求是要求一新存儲器區塊。也就是說30預取單元1決定與配置要求相關的存儲器區塊是新的，意即尚未配置一硬體單元332給新的配置要求所相關的存儲器區塊。也就是說，預取單元1最近未接受(encountered)一新存儲器區塊的配置要求。在一實施例中，配置要求是在一載入/儲存第一級數據快取存儲器116結果失敗並隨的由第二級快取存儲器118要求同一快取線所產生的要求。在一實施例中，配置要求用以指定一實體地址，實體地址所相關的一虛擬地址是由實體地址轉譯而來的。第一級數據快取存儲器116根據一雜湊功能(意即與圖17的步驟1704相同的雜湊功能)，雜湊與配置要求的實體地址有關的虛擬地址，用以產生配置要求的一已雜湊虛擬地址(HVAAR)，並且將配置要求的已雜湊虛擬地址提供至預取單元124。流程進行至步驟1903。在步驟1903中，預取單元IM配至一個新的硬體單元332給新的存儲器區塊。如果有不活動(inactive)的硬體單元332存在，預取單元IM配置一不活動的硬體單元332給新的存儲器區塊。否則，在一實施例中，預取單元1則配置一個最近最少使用的硬體單元332給新的存儲器區塊。在一實施例中，一旦預取單元124已經預取樣態所指示的存儲器區塊的所有快取線時，預取單元1則會鈍化(inactivate)硬體單元332。在一實施例中，預取單元IM具有固定(Pin)硬體單元332的能力，使其就算為一個最近最少使用的硬體單元332亦不會被重置。舉例而言，若預取單元IM檢測到已經根據樣態對存儲器區塊進行一既定次數的存取，但預取單元124尚未根據樣態對整個存儲器區塊完成所有的預取，預取單元124即可固定與存儲器區塊有關的硬體單元332，使其就算成為一個最近最少使用的硬體單元332仍不夠資格被重置。在一實施例中，預取單元IM維持每一硬體單元332的相對期間(從原始配置)，並且當其期間(age)到達一既定期間臨界值時，預取單元IM則會鈍化硬體單元332。在另一實施例中，若預取單元124(藉由後續的步驟1904到1926)檢測一虛擬相鄰的存儲器區塊，並且已完成自虛擬鄰近的存儲器區塊的預取，預取單元1則會選擇性地重複使用在虛擬相鄰的存儲器區塊的硬體單元332，而不是配置一新的硬體單元332。在此實施例中，預取單元IM選擇性地初始化重複使用的硬體單元332的各種儲存元件(例如方向暫存器342、樣態暫存器344與樣態區域暫存器348)，以便維持儲存在其內的可用信息。流程進行至步驟1904。在步驟1904中，預取單元124比較在步驟1902所產生的已雜湊虛擬地址(HVAAR)與虛擬雜湊表162的每一項目的負1雜湊虛擬地址1602(HVAMl)和正1雜湊虛擬地址1606(HVAPl)。預取單元124根據步驟1904到1922的操作是為了決定一已主動(active)存儲器區塊是否虛擬相鄰至新存儲器區塊，預取單元1根據步驟1擬4到1擬8的操作是為了預測存儲器存取是否將根據事先檢測到的存取樣態與方向，繼續自虛擬相鄰的已主動存儲器區塊進入新的存儲器區塊，用以以降低預取單元124的暖機時間，使得預取單元IM可較快開始預取新的存儲器區塊。流程進行至步驟1906。在步驟1906中，預取單元IM根據步驟1904執行的比較方式，決定已雜湊虛擬地址(HVAAR)是否與虛擬雜湊表162的任何一項目匹配。若已雜湊虛擬地址(HVAAR)與虛擬雜湊表162的一項目匹配，流程進行至步驟1908；否則，流程進行至步驟1912。在步驟1908中，預取單元IM設定一候補方向旗幟(candidate_directionflag)至一數值，以指示向上的方向。流程進行至步驟1916。在步驟1912中，預取單元IM根據步驟1908所執行的比較方式，決定已雜湊虛擬地址(HVAAR)是否與虛擬雜湊表162的任何一項目匹配。若已雜湊虛擬地址(HVAAR)與虛擬雜湊表162的一項目匹配，流程進行至步驟1914；否則，流程結束。在步驟1914中，預取單元IM設定候補方向旗幟(candidate_directionflag)至一數值，以指示向下的方向。流程進行至步驟1916。在步驟1916中，預取單元IM將候補雜湊暫存器(candidate_havregister)(未圖示)設定為步驟1906或1912所決定的虛擬雜湊表162的未修改雜湊虛擬地址1604(HVAUN)的一數值。流程進行至步驟1918。在步驟1918中，預取單元124比較候選雜湊(candidatejwa)與預取單元124中每一主動存儲器區塊的存儲器區塊虛擬雜湊地址欄(HVAMB)3M。流程進行至步驟1922。在步驟1922中，預取單元IM根據步驟1918所執行的比較方式，決定候選雜湊(candidate_hva)是否與任何一存儲器區塊虛擬雜湊地址欄(HVAMB)3M匹配。若候選雜湊(candidatejwa)與一存儲器區塊虛擬雜湊地址欄(HVAMB)3M匹配，流程進行至步驟19M;否則，流程結束。在步驟1擬4中，預取單元124已確定步驟1922所找到的匹配主動存儲器區塊確實虛擬鄰近於新的存儲器區塊。因此，預取單元124比較(步驟1908或者1914所指定的)候選方向與匹配主動存儲器區塊的方向暫存器342，用以根據先前檢測到的存取樣態與方向，預測存儲器存取是否將繼續自虛擬相鄰的已主動存儲器區塊進入新的存儲器區塊。仔細而言，若候選方向與虛擬相鄰存儲器區塊的方向暫存器342不同，存儲器存取不太可能會根據先前檢測到的存取樣態與方向，繼續自虛擬相鄰的已主動存儲器區塊進入新的存儲器區塊。流程進行至步驟1擬6。在步驟1擬6中，預取單元IM根據步驟1擬4所執行的比較方法，決定候選方向與匹配主動存儲器區塊的方向暫存器342是否匹配。若候選方向與匹配主動存儲器區塊的方向暫存器；342匹配，則流程進行至步驟1擬8；否則，流程結束。在步驟1擬8中，預取單元IM決定在步驟1902所接收到的新的重置要求是否被指到步驟1擬6所檢測到的匹配虛擬相鄰主動存儲器區塊的一已被樣態暫存器344所預測的快取線。在一實施例中，為了執行步驟19的決定，預取單元IM根據其樣態順序暫存器346有效地轉換與複製匹配虛擬相鄰主動存儲器區塊的樣態暫存器344，用以在虛擬相鄰存儲器區塊繼續樣態位置樣態區域暫存器348，以便在新的存儲器區塊維持樣態334連貫性。若新的配置要求是要求匹配主動存儲器區塊的樣態暫存器344所相關的一快取存儲器列，流程進行至步驟1934；否則，流程進行至步驟1932。在步驟1932中，預取單元IM根據圖4的步驟406與408，初始化與填充(步驟1903所配置的)新的硬體單元332，希望其最後可根據上述與圖4到圖6相關的方法，檢測對新的存儲器區塊的存取的新樣態，而這將需要暖機時間。流程結束於步驟1932。在步驟1934中，預取單元IM預測存取要求將會根據匹配虛擬相鄰主動存儲器區塊的樣態暫存器344與方向暫存器342繼續進入新的存儲器區塊。因此，預取單元124以相似於步驟1932的方式填充新的硬體單元332，但會有些許不同。仔細而言，預取單元IM會用來自虛擬相鄰存儲器區塊的硬體單元332的對應數值來填充方向暫存器342、樣態暫存器344以及樣態順序暫存器346。另外，樣態區域暫存器348的新的數值是藉由繼續轉換於增加的樣態順序暫存器346的值所決定，直到其交叉進入新的存儲器區塊，以提供樣態32暫存器344持續地進入新的存儲器區塊，如步驟1擬8中的相關敘述。再者，新的硬體單元332中的狀態欄356用以標記新的硬體單元332為試用(prcAationary)。最後，搜尋指標暫存352被初使化以便由一存儲器區塊的開頭進行搜尋。流程進行至步驟1936。在步驟1936中，預取單元IM繼續監視發生於新存儲器區塊的存取要求。若預取單元1檢測到對存儲器區塊的至少一既定數量的後續存取要求是要求樣態暫存器344所預測的存儲器線，接著預取單元IM促使硬體單元332的狀態欄356自試用(probationary)轉為主動，並且接著如圖6所述開始自新的存儲器區塊進行預取。在一實施例中，存取要求的既定數量為2，雖然其他實施例可考慮為其它既定數量。流程進行至步驟1936。如圖20所示為圖15所示的預取單元IM所用的一雜湊實體地址至雜湊虛擬地址_(hashedphysicaladdress-to-hashedvirtualaddressthesaurus)2002。^.地址至雜湊虛擬地址庫2002包括一項目陣列。每一項目包括一實體地址(PA)2004以及一對應的雜湊虛擬地址(HVA)2006。對應的雜湊虛擬地址2006是由實體地址2004轉譯成的虛擬地址加以雜湊的結果。預取單元1藉由對最近的雜湊物理地址至雜湊虛擬地址庫2002進行竊聽，用以在跨越載入/儲存單元134的管線。在另一實施例中，於圖19的步驟1902，第一級數據快取存儲器116並未提供已雜湊虛擬地址(HVAAR)至預取單元124，但只提供配置要求所相關的物理地址。預取單元1在雜湊物理地址至雜湊虛擬地址庫2002中尋找實體位置，以找到一匹配實體地址(PA)2004，並獲得相關的雜湊虛擬地址(HVA)2006，所獲得的雜湊虛擬地址(HVA)2006將在圖19其他部分成為已雜湊虛擬地址(HVAAR)。將雜湊物理地址至雜湊虛擬地址庫2002包括在預取單元IM可緩和第一級數據快取存儲器116提供配置要求所要求的雜湊虛擬地址的需要，因此可簡化第一級數據快取存儲器116與預取單元1之間的接口。在一實施例中，雜湊實體地址至雜湊虛擬地址庫2002的每一項目包括一雜湊實體地址，而不是實體地址2004，並且預取單元IM將自第一級數據快取存儲器116所接收的配置要求實體地址雜湊成一雜湊物理地址，用以找尋雜湊實體地址至雜湊虛擬地址庫2002，以便獲得適當的對應的雜湊虛擬地址(HVA)2006。本實施例允許較小的雜湊實體地址至雜湊虛擬地址庫2002，但需要另外的時間對實體地址進行雜湊。如圖21所示為本發明實施例的多核微處理器100。多核微處理器100包括兩個核心(表示成核心A2102A以及核心B2102B)，可整個視為核心2102(或者單一核心2102)。每一核心具有相似於如圖2所示的單核微處理器100的元件12或15。另外，每一核心2102具有如前所述的高度反應式的預取單元2104。該兩個核心2102共享第二級快取存儲器118以及預取單元124。特別的是，每一核心2012的第一級數據快取存儲器116、載入/儲存單元134以及高度反應式的預取單元2104是耦接至共享的第二級快取存儲器118以及預取單元124。另外，一共享的高度反應式的預取單元2106是耦接至第二級快取存儲器118以及預取單元124。在一實施例中，高度反應式的預取單元2104/共享的高度反應式的預取單元2106隻預取一存儲器存取所相關的快取線後的下一個相鄰的快取線。預取單元IM除了監控載入/儲存單元134以及第一級數據快取存儲器116的存儲器存取之外，亦可監控高度反應式的預取單元2104/共享的高度反應式的預取單元2106所產生的存儲器存取，用以進行預取決定。預取單元1可監控從不同組合的存儲器存取來源的存儲器存取，以執行本發明所述的不同的功能。例如，預取單元1可監控存儲器存取的一第一組合，以執行圖2到圖11所述的關相功能，預取單元1可監控存儲器存取的一第二組合，以執行圖12到圖14所述的相關功能，並且預取單元IM可監控存儲器存取的一第三組合，以執行圖15到圖19所述的相關功能。在實施例中，共享的預取單元124由於時間因素難以監控每一核心2102的載入/儲存單元134的行為。因此，共享的預取單元IM經由第一級數據快取存儲器116所產生的傳輸狀況(traffic)間接地監控載入/儲存單元134的行為，作為其載入/儲存未命中(miss)的結果。本發明的不同實施例已於本文敘述，但本領域的技術人員應能了解這些實施例僅作為範例，而非限定於此。本領域的技術人員可在不脫離本發明的精神的情況下，對形式與細節上做不同的變化。例如，軟體可致能本發明實施例所述的裝置與方法的功能、組建(fabrication)、塑造(modeling)、模擬、描述(description)、以和/或測試，亦可通過一般程序語言(C、C++)、硬體描述語言(HardwareDescriptionLanguages,HDL)(包括VerilogHDL、VHDL等等)、或其他可利用的程序語言來完成。此軟體可配置在任何已知的計算機可使用媒介，例如磁帶、半導體、磁碟，或是光碟(例如⑶-R0M、DVD-R0M等等)、網際網路、有線、無線、或其他通訊媒介的傳輸方式之中。本發明所述的裝置與方法實施例可被包括於半導體智慧財產權核心，例如微處理器核心(以HDL來實現)，並轉換成集成電路產品的硬體。此外，本發明所述的裝置與方法通過硬體與軟體的結合來實現。因此，本發明不應局限於所揭示的實施例，而是依本發明的權利要求與等效實施所界定。特別是，本發明可實施在使用於一般用途計算機中的微處理器裝置內。最後，本發明雖以較佳實施例揭示如上，然其並非用以限定本發明的範圍，本領域的技術人員，在不脫離本發明的精神和範圍的前提下，可做若干的更動與潤飾，因此本發明的保護範圍是以本發明的權利要求為準。權利要求1.一種預取單元，設置於具有一快取存儲器的一微處理器中，包括其中上述預取單元用以接收對一存儲器區塊的多個地址的多個存取要求，每一存取要求對應上述存儲器區塊的地址中的一個，並且上述存取要求的地址隨著時間函數非單調性地增加或減少；一儲存裝置；以及一控制邏輯，耦接至上述儲存裝置，其中當接收到上述存取要求時，上述控制邏輯則用以維持上述儲存裝置中的上述存取要求的一最大地址以及一最小地址，以及上述最大地址以及最小地址的變化的計數值；維持上述存儲器區塊中最近被存取的快取線的一歷史記錄，上述最近被存取的快取線是與上述存取要求的地址相關；根據上述計數值，決定一存取方向；根據上述歷史記錄，決定一存取樣態；以及根據上述存取樣態並沿著上述存取方向，將上述快取存儲器內尚未被上述歷史記錄指示為已存取的快取線預取至上述存儲器區塊中。2.如權利要求1所述的預取單元，其中上述控制邏輯還用以在上述存儲器區塊中最近被存取的快取線的數量大於一既定值之前，暫緩上述預取的操作。3.如權利要求2所述的預取單元，其中上述既定值至少為9。4.如權利要求2所述的預取單元，其中上述既定值至少為上述存儲器區塊中快取線的數量的百分之十。5.如權利要求1所述的預取單元，其中為了根據上述計數值決定上述存取方向，上述控制邏輯用以當上述最大地址的變化的計數值與上述最小地址的變化的計數值之間的差值大於一既定值時，決定上述存取方向是向上；以及當上述最小地址的變化的計數值與上述最大地址的變化的計數值之間的差值大於上述既定值時，決定上述存取方向是向下。6.如權利要求1所述的預取單元，其中上述控制邏輯還用以在上述最大地址的變化的計數值與上述最小地址的變化的計數值間的差值的絕對值大於一既定值之前，暫緩上述預取操作。7.如權利要求1所述的預取單元，其中上述歷史記錄包括一位遮罩，上述位遮罩用以指出上述最近被存取的快取線，並且上述最近被存取的快取線是與上述存儲器區塊的地址所相關；當接收到上述存取要求時，上述控制邏輯還用以計算上述位遮罩中的上述最近被存取的快取線的一中間指標暫存器；以及當上述中間指標暫存器的左側的上述位遮罩的N位與上述中間指標暫存器的右側的上述位遮罩的N位匹配時，為多個個不同的位周期中的每一個，增加上述位周期所相關的一匹配計數器的計數值，其中N為上述位周期中的位數。8.如權利要求1所述的預取單元，其中為了根據上述位遮罩決定上述存取樣態，上述控制邏輯用以檢測上述位周期的一個所相關的上述匹配計數器與上述位周期的其它者所相關的上述匹配計數器之間的差值是否大於一既定值；以及決定被上述位遮罩的上述中間指標暫存器的其中一側的N位所指定的上述存取樣態，其中N為上述位周期的一個的位數，上述位周期的上述一個所具有的相關匹配計數器與上述位周期的其它者所具有的相關匹配計數器之間的差值大於上述既定值。9.如權利要求8所述的預取單元，其中為了根據上述存取樣態並沿著上述存取方向，將上述存儲器區塊中被上述位遮罩標指為最近尚未被存取的快取線預取至上述快取存儲器中，上述控制邏輯用以沿著上述存取方向，分派一搜尋指標器以及距離上述中間指標器N位的上述存取樣態；以及當上述搜尋指標器上的上述存取樣態中的位指示一存取時，預取上述搜尋指標器上的上述位遮罩中的上述位所相關的快取線。10.如權利要求9所述的預取單元，其中為了根據上述存取樣態並沿著上述存取方向，將上述存儲器區塊中被上述位遮罩標指為最近尚未被存取的快取線預取至上述快取存儲器中，上述控制邏輯用以根據上述存取方向，增加/減少上述搜尋指標器的值；以及當增加/減少後的上述搜尋指標器上的上述存取樣態中的位指示一存取時，預取上述已增加/減少的上述搜尋指標器上的上述位遮罩中的上述位所相關的快取線。11.如權利要求10所述的預取單元，其中上述控制邏輯還用以重複上述增加上述搜尋指標器的值以及進行預取的操作，直到一狀況出現，其中上述狀況包括當上述存取方向是向上時，上述搜尋指標器上的上述位遮罩之中的位與在上述最大地址所相關的上述位遮罩之中的位之間的距離大於一第二既定值；以及當上述存取方向是向下時，上述搜尋指標器上的上述位遮罩之中的位與上述最小地址所相關的上述位遮罩中的位之間的距離大於上述第二既定值。12.如權利要求7所述的預取單元，其中上述控制邏輯還用以在上述不同位周期的一個所相關的上述匹配計數器與上述不同位周期的其它者所相關的上述匹配計數器之間的差值大於一既定值之前，暫緩上述預取操作。13.如權利要求1所述的預取單元，其中上述位周期為3、4以及5位。14.如權利要求1所述的預取單元，其中上述控制邏輯還於上述快取線已出現在上述微處理器的任一快取存儲器時，放棄預取上述快取線。15.如權利要求1所述的預取單元，其中上述存儲器區塊的大小是4千字節。16.如權利要求1所述的預取單元，還包括多個個上述儲存裝置；其中上述控制邏輯用以接收一存取要求，上述存取要求的地址不在上述儲存裝置的一個所相關的一新的存儲器區塊中，並且分派上述儲存裝置的一個給上述新的存儲器區塊。17.如權利要求16所述的預取單元，其中上述控制邏輯還用以清除上述最大地址的改變的計數值、上述最小地址改變的計數值，以及上述儲存裝置被分派的一個的上述歷史記錄。18.一種數據預取方法，用以預取數據至一微處理器的一快取存儲器，上述數據預取方法，包括接收對一存儲器區塊的多個地址的多個存取要求，每一存取要求對應上述存儲器區塊的地址中的一個，並且上述存取要求的地址是隨著時間函數非單調性地增加或減少；當接收到上述存取要求時，維持上述存儲器區塊中的一最大以及一最小地址，並且計算上述最大以及最小地址的變化的計數值；當接收到上述存取要求時，維持上述存儲器區塊中最近被存取的快取線的一歷史記錄，上述最近被存取的快取線是與上述存取要求的地址相關；根據上述計數值決定一存取方向；根據上述歷史紀錄決定一存取樣態；以及根據上述存取樣態並沿著上述存取方向，將上述快取存儲器內尚未被上述歷史記錄指示為已存取的快取線預取至上述存儲器區塊中。19.如權利要求18所述的數據預取方法，還包括在上述存儲器區塊中最近被存取的快取線的數量大於一既定值之前，暫緩上述預取的操作。20.如權利要求19所述的數據預取方法，其中上述既定值至少為9。21.如權利要求19所述的數據預取方法，其中上述既定值至少為上述存儲器區塊中的快取線的數量的百分之十。22.如權利要求18所述的數據預取方法，其中為了上述的根據上述計數值決定上述存取方向還包括當上述最大地址的變化的計數值與上述最小地址的變化的計數值之間的差值大於一既定值時，決定上述存取方向是向上；以及當上述最小地址的變化的計數值與上述最大地址的變化的計數值之間的差值大於上述既定值時，決定上述存取方向是向下。23.如權利要求18所述的數據預取方法，還包括在上述最大地址的變化的計數值與上述最小地址的變化的計數值間的差值的絕對值大於一既定值之前，暫緩上述預取操作。24.如權利要求18所述的數據預取方法，其中上述歷史記錄包括一位遮罩，上述位遮罩用以指出上述最近被存取的快取線，並且上述最近被存取的快取線是與上述存儲器區塊的地址所相關；當已接收上述存取時，還包括計算在上述位遮罩中的上述最近被存取的快取線的一中間指標暫存器；以及當上述中間指標暫存器的左側的上述位遮罩的N位與上述中間指標暫存器的右側的上述位遮罩的N位匹配時，為多個個不同的位周期中的每一個，增加上述位周期所相關的一匹配計數器的計數值，其中N為上述位周期中位數。25.如權利要求M所述的數據預取方法，其中為了根據上述位遮罩決定上述存取樣態包括檢測上述位周期的一個所相關的上述匹配計數器與上述位周期的其它者所相關的上述匹配計數器之間的差值是否大於一既定值；以及決定被上述位遮罩的上述中間指標暫存器的其中一側的N位所指定的上述存取樣態，其中N為上述位周期之一中的位的號碼，上述位周期的上述一個所具有的相關匹配計數器與上述位周期的其它者所具有的相關匹配計數器之間的差值大於上述既定值的上述計數器關於上述所有其他清楚位周期之間的差。26.如權利要求25所述的數據預取方法，其中為了根據上述存取樣態並沿著上述存取方向，將上述存儲器區塊中被上述位遮罩標指為最近尚未被存取的快取線預取至上述快取存儲器中，上述控制邏輯用以沿著上述存取方向，分派一搜尋指標器以及距離上述中間指標器N位的上述存取樣態；以及當上述搜尋指標器上的上述存取樣態中的位指示一存取時，預取上述搜尋指標器上的上述位遮罩中的上述位所相關的快取線。27.如權利要求26所述的數據預取方法，其中為了根據上述存取樣態並沿著上述存取方向，將上述存儲器區塊中被上述位遮罩標指為最近尚未被存取的快取線預取至上述快取存儲器中，還包括根據上述存取方向，增加/減少上述搜尋指標器的值；以及當增加/減少後的上述搜尋指標器上的上述存取樣態中的位指示一存取時，預取上述已增加/減少的上述搜尋指標器上的上述位遮罩中的上述位所相關的快取線。28.如權利要求27所述的數據預取方法，還包括重複上述增加上述搜尋指標器的值以及進行預取的操作，直到一狀況出現，其中上述狀況包括當上述存取方向是向上時，上述搜尋指標器上的上述位遮罩之中的位與在上述最大地址所相關的上述位遮罩之中的位之間的距離是大於一第二既定值；以及當上述存取方向是向下時，上述搜尋指標器上的上述位遮罩之中的位與上述最小地址所相關的上述位遮罩之中的位之間的距離是大於上述第二既定值。29.如權利要求M所述的數據預取方法，還包括在上述不同位周期的一個所相關的上述匹配計數器與上述不同位周期的其它者所相關的上述匹配計數器之間的差值大於一既定值之前，暫緩上述預取操作。30.如權利要求18所述的數據預取方法，其中上述位周期為3、4以及5位。31.如權利要求18所述的數據預取方法，還包括當上述快取線已出現在上述微處理器的任一快取存儲器時，放棄預取上述快取線。32.如權利要求18所述的數據預取方法，其中上述存儲器區塊的大小是4千字節。33.一種數據預取方法，用以預取數據進入一微處理器的一快取存儲器，上述數據預取方法包括接收對一存儲器區塊的一地址的一存取要求；設定一位遮罩中與一快取線所相關的一位，其中上述快取線是與上述存儲器區塊的上述地址相關；於接收到上述存取要求之後，增加一總計數器的計數值當上述地址大於一最大指標暫存器的值，用上述地址更新上述最大指標暫存器，並且增加一最大改變計數器的計數值；當上述地址小於一最小指標暫存器，用上述地址更新上述最小指標暫存器，並且增加一最小改變計數器的計數值；計算一中間指標暫存器，作為上述最大以及最小改變計數器的平均值；當上述中間指標暫存器的左側的上述位遮罩的N位與上述中間指標暫存器的右側的上述位遮罩的N位匹配時，為多個個不同的位周期中的每一個，增加上述位周期所相關的一匹配計數器的計數值，其中N為上述位周期中的位數；決定一狀況是否出現，其中上述狀況包括(A)上述存取總計數器大於一第一既定值；(B)上述最大改變計數器與最小改變計數器相減取絕對值後的差大於一第二既定值；以及(C)上述匹配計數器的一個與其它者間的計數值間的差值的絕對值大於一第三既定值；以及當上述狀況存在時當上述最大改變計數器大於上述最小改變計數器時，決定上述存取方向是向上，並且當上述最大改變計數器小於上述最小改變計數器時，決定上述存取方向是向下；決定被上述位遮罩的上述中間指標暫存器的其中一側的N位所指定的上述存取樣態，其中N為上述位周期中與上述最大匹配計數器相關的一個的位數；以及根據所決定的上述存取方向與上述存取樣態，將上述存儲器區塊的多個快取線預取至上述快取存儲器中。34.如權利要求33所述的數據預取方法，其中上述根據所決定的上述存取方向與上述存取樣態，將上述快取線預取至上述快取存儲器中的步驟包括(1)沿著上述存取方向，初始化一搜尋指標器以及距離上述中間指標器N位的上述存取樣態；(2)決定一第二狀況是否存在，其中上述第二狀況包括(D)在上述搜尋指標器的上述存取樣態的位已設定；(E)在上述搜尋指標器的上述位遮罩的位已清除；以及(F)在上述存取方向上，上述最大/最小指標器與上述搜尋指標器的上述位遮罩中的位間的差距小於一第四既定值；以及(3)當上述第二狀況存在，預取上述搜尋指標器的上述位遮罩中的位所相關的上述快取線。35.如權利要求33所述的數據預取方法，其中上述根據所決定的上述存取方向與存取樣態，將上述快取線預取至上述快取存儲器的步驟還包括於上述第二狀況存在時，在決定上述第二狀況存在以及存取之後，根據上述存取方向，增加/減少上述搜尋指標器的值；以及重複上述步驟O)以及⑶。36.如權利要求35所述的數據預取方法，其中上述根據所決定的上述存取方向與存取樣態，將上述快取線預取至上述快取存儲器的步驟還包括當上述狀況(F)為真，停止上述重複步驟。37.如權利要求35所述的數據預取方法，其中上述根據所決定的上述存取方向與存取樣態，將上述快取線預取至上述快取存儲器的步驟還包括當上述位遮罩的所有位都已測試完，停止上述重複步驟。38.一種微處理器，包括多個核心；一快取存儲器，由上述核心所共享，用以接收對一存儲器區塊的多個地址的多個存取要求，每一存取要求對應上述存儲器區塊的地址中的一個，上述存取要求的地址隨著時間函數非單調性地增加或減少；以及一預取單元，用以監視上述存取要求，並維持上述存儲器區塊中的一最大地址以及一最小地址，以及上述最大地址以及最小地址的變化的計數值；根據上述計數值，決定一存取方向；以及沿著上述存取方向，將上述存儲器區塊中未命中的快取線預取至上述快取存儲器中。39.如權利要求38所述的微處理器，其中上述預取單元還用以維持上述存儲器區塊中最近被存取的快取線的一歷史記錄，上述最近被存取的快取線是與上述存取要求的地址相關；根據上述歷史記錄，決定一存取樣態；以及根據上述存取樣態並沿著上述存取方向，將上述快取存儲器內被上述歷史記錄指示為最近尚未被存取且在上述存儲器區塊中是未命中的多個快取線預取至上述存儲器區塊中。40.一種微處理器，包括一第一級快取存儲器；一第二級快取存儲器；以及一預取單元，用以檢測出現在上述第二級快取存儲器中的最近存取要求的一方向以及樣態，以及根據上述方向以及樣態，將多個快取線預取至上述第二級快取存儲器中；從上述第一級快取存儲器，接收上述第一級快取存儲器所接收的一存取要求的一地址，其中上述地址與一快取線相關；決定在上述方向中所相關的快取線之後被上述樣態所指出的一個或多個快取線；以及導致上述一個或多個快取線被預取至上述第一級快取存儲器中。41.如權利要求40所述的微處理器，其中為了檢測出現在上述第二級快取存儲器中上述最近存取要求的上述方向以及樣態，上述預取單元用以檢測一存儲器區塊的上述方向以及樣態，上述存儲器區塊是可被上述微處理器存取的存儲器範圍的一小集合；為了決定在上述方向中所相關的快取線之後被上述樣態所指出的一個或多個快取線，上述預取單元用以放置上述樣態至上述存儲器區塊，使得上述地址位於上述樣態中；以及沿著上述方向，由上述地址開始搜尋，直到遇到上述樣態所指出的一快取線。42.如權利要求41所述的微處理器，其中上述樣態包括快取線的一順序；其中為了放置上述樣態至上述存儲器區塊，使得上述地址位於上述樣態中，上述預取單元用以藉由上述順序將上述樣態轉移至上述存儲器區塊。43.如權利要求41所述的微處理器，其中出現在上述第二級快取存儲器中的上述存儲器區塊的上述最近存取要求的上述地址隨著時間函數而非單調性地增加以及減少。44.如權利要求43所述的微處理器，其中出現在上述第二級快取存儲器中的上述存儲器區塊的上述最近存取要求的上述地址可為非連續的。45.如權利要求40所述的微處理器，還包括多個核心；其中上述第二級快取存儲器以及預取單元是由上述核心所共享；以及每一上述核心包括上述第一級快取存儲器的一不同的範例。46.如權利要求40所述的微處理器，其中為了導致上述一個或多個快取線被預取至上述第一級快取存儲器中，上述預取單元用以提供上述一個或多個快取線的地址至上述第一級快取存儲器，其中上述第一級快取存儲器用以從上述第二級快取存儲器中要求上述一個或多個快取線。47.如權利要求46所述的微處理器，其中上述第一級快取存儲器包括一隊列，用以儲存從上述預取單元所接收的上述地址。48.如權利要求40所述的微處理器，其中為了導致上述一個或多個快取線被預取至上述第一級快取存儲器中，上述預取單元是從上述微處理器的一總線接口單元要求一個或多個快取線，並且隨後將提供上述所要求到的快取線提供至上述第一級快取存儲器。49.如權利要求40所述的微處理器，其中為了導致上述一個或多個快取線被預取至上述第一級快取存儲器中，上述預取單元用以自上述第二級快取存儲器中要求上述一個或多個快取線。50.如權利要求49所述的微處理器，其中上述預取單元用以將上述被所要求到的快取線隨後提供至上述第一級快取線。51.如權利要求49所述的微處理器，其中上述第二級快取存儲器用以所要求的快取線隨後提供至上述第一級快取線。52.如權利要求40所述的微處理器，其中上述預取單元檢測上述方向以及樣態的步驟，包括當接收到上述最近存取要求時，維持一存儲器區塊的一最大地址以及一最小地址，以及上述最大地址以及上述最小地址的改變的計數值；當接收到上述最近存取要求時，維持上述存儲器區塊的上述存取地址所相關的最近存取的快取線的一歷史記錄；以及根據上述計數值，決定上述方向；以及根據上述歷史記錄，決定上述樣態。53.如權利要求52所述的微處理器，上述根據上述計數值決定上述方向的步驟包括當上述最大地址的變化的計數值與上述最小地址的變化的計數值間的差值大於一既定值時，決定上述方向是向上；以及當上述最小地址的變化的計數值與上述最大地址的變化的計數值間的差值大於上述既定值時，決定上述方向是向下。54.如權利要求40所述的微處理器，其中上述歷史記錄包括一位遮罩，用以指出上述存儲器區塊的上述存取地址所相關的最近存取的快取線；當接收到上述存取要求時，上述預取單元還包括進行下列步驟計算上述位遮罩中的上述最近存取的快取線的一中間指標暫存器；以及當上述中間指標暫存器的左側的上述位遮罩的N位與上述中間指標暫存器的右則的上述位遮罩的N位匹配時，為多個個不同的位周期中的每一個，增加上述位周期所相關的一匹配計數器的計數值，其中N為上述位周期中的位數。55.如權利要求M所述的微處理器，其中上述根據上述位遮罩決定上述存取樣態的步驟包括檢測上述位周期的一個所相關的上述匹配計數器與上述位周期的其它者所相關的上述匹配計數器之間的差值是否大於一既定值；以及決定被上述位遮罩的上述中間指標暫存器的其中一側的N位所指定的上述存取樣態，其中N為上述位周期的一個的位數，上述位周期的上述一個所具有的相關匹配計數器與上述位周期的其它者所具有的相關匹配計數器之間的差值大於上述既定值。56.一種數據預取方法，用以預取數據至具有一第二級快取存儲器的一微處理器的一第一級快取存儲器，上述數據預取方法包括檢測出現在上述第二級快取存儲器中的最近存取要求的一方向以及樣態，以及根據上述方向以及樣態，將多個快取線預取至上述第二級快取存儲器中；從上述第一級快取存儲器，接收上述第一級快取存儲器所接收的一存取要求的一地址，其中上述地址與一快取線相關；決定在上述方向中所相關的快取線之後被上述樣態所指出的一個或多個快取線；以及導致上述一個或多個快取線被預取至上述第一級快取存儲器中。57.如權利要求56所述的數據預取方法，其中上述檢測出現在上述第二級快取存儲器中上述最近存取要求的上述方向以及樣態的步驟，包括檢測一存儲器區塊的上述方向以及樣態，上述存儲器區塊是可被上述微處理器存取的存儲器範圍的一小集合；決定在上述方向中所相關的快取線之後被上述樣態所指出的一個或多個快取線的步驟，包括放置上述樣態至上述存儲器區塊，使得上述地址位於上述樣態中；以及沿著在上述方向，由上述地址開始搜尋，直到遇到上述樣態所指出的一快取線。58.如權利要求57所述的數據預取方法，其中上述樣態包括快取線的一順序，並且放置上述樣態至上述存儲器區塊，使得上述地址位於上述樣態中的步驟，包括藉由上述順序將上述樣態轉移至上述存儲器區塊。59.如權利要求57所述的數據預取方法，其中出現在上述第二級快取存儲器中的上述存儲器區塊的上述最近存取要求的上述地址是隨著時間函數而非單調性地增加以及減少。60.如權利要求59所述的數據預取方法，其中出現在上述第二級快取存儲器中的上述存儲器區塊的上述最近存取要求的上述地址可為非連續的。61.如權利要求56所述的數據預取方法，其中上述微處理器還包括多個核心，並且上述第二級快取存儲器以及預取單元是由上述核心所共享，並且每一上述核心包括上述第一級快取存儲器的一不同的範例。62.如權利要求56所述的數據預取方法，其中導致上述一個或多個快取線被預取至上述第一級快取存儲器的步驟，包括上述微處理器的一預取單元用以提供上述一個或多個快取線的地址至上述第一級快取存儲器，其中上述第一級快取存儲器用以從上述第二級快取存儲器中要求上述一個或多個快取線。63.如權利要求56所述的數據預取方法，其中導致上述一個或多個快取線被預取至上述第一級快取存儲器的步驟，包括上述微處理器的一預取單元用以提供上述一個或多個快取線的地址至上述第一級快取存儲器中，其中上述第一級快取存儲器自上述微處理器的一總線接口單元用以要求上述一個或多個快取線，並且隨後將上述要求的一個或多個快取線提供至上述第一級快取存儲器。64.如權利要求56所述的數據預取方法，其中導致上述一個或多個快取線被預取至上述第一級快取存儲器的步驟，包括上述預取單元用以自上述第二級快取存儲器中要求上述一個或多個快取線。65.如權利要求64所述的數據預取方法，其中導致上述一個或多個快取線被預取至上述第一級快取存儲器的步驟，包括上述預取單元用以將所要求的一個或多個快取線隨後提供至上述第一級快取線。66.如權利要求64所述的數據預取方法，還包括上述第二級快取存儲器用以將所要求的一個或多個快取線隨後提供至上述第一級快取線。67.一種微處理器，包括一快取存儲器；以及一預取單元，用以檢測具有一第一存儲器區塊的多個存儲器存取要求的一樣態，並且根據上述樣態從上述第一存儲器區塊預取多個快取線至上述快取存儲器中；監視一第二存儲器區塊的一新的存儲器存取要求；決定上述第一存儲器區塊是否虛擬鄰近於上述第二存儲器區塊，並且當自上述第一存儲器區塊延續至上述第二存儲器區塊時，則決定上述樣態是否預測到上述第二存儲器區塊的新的存儲器存取要求所相關的一快取線在上述第二存儲器區塊中；以及根據上述樣態，響應地從上述第二存儲器區塊將上述快取線預取至上述快取存儲器中。68.如權利要求67所述的微處理器，其中上述第一以及第二存儲器區塊的大小對應於一實體存儲器分頁的大小。69.如權利要求67所述的微處理器，其中上述微處理器包括一第二級快取存儲器，其中上述新的存儲器存取要求包括自上述微處理器的一第一級快取存儲器至上述第二級快取存儲器的要求，用以分派上述第二存儲器區塊的上述快取線。70.如權利要求67所述的微處理器，其中為了檢測上述第一存儲器區塊的上述存儲器存取要求的上述樣態，上述預取單元用以檢測上述存儲器存取要求的一方向；並且為了決定上述第一存儲器區塊是否虛擬鄰近於上述第二存儲器區塊，上述預取單元用以決定上述第一存儲器區塊在上述方向中是否虛擬鄰近於上述第二存儲器區塊。71.如權利要求70所述的微處理器，其中上述第一存儲器區塊的上述存儲器存取要求的上述地址隨著時間函數非單調性地增加或者減少。72.如權利要求70所述的微處理器，其中當自上述第一存儲器區塊延續至上述第二存儲器區塊時，為了決定上述樣態是否預測到上述第二存儲器區塊的上述新的存儲器存取要求所相關的上述快取線在上述第二存儲器區塊中，上述預取單元用以在沿著上述方向自上述第一存儲器區塊延續至上述第二存儲器區塊時，決定上述樣態是否預測上述第二存儲器區塊的上述新的存儲器存取要求所相關的上述快取線在上述第二存儲器區塊中。73.如權利要求70所述的微處理器，其中為了根據上述樣態自上述第二存儲器區塊將上述快取線預取至上述快取存儲器中，上述預取單元用以根據上述樣態且沿著上述方向，自上述第二存儲器區塊將上述快取線預取至上述快取存儲器中。74.如權利要求67所述的微處理器，其中上述樣態包括上述第一存儲器區塊的多個快取線的一順序，其中當自上述第一存儲器區塊延續至上述第二存儲器區塊時，為了決定上述樣態是否預測到上述第二存儲器區塊的上述新的存儲器存取要求所相關的上述快取線在上述第二存儲器區塊中，上述預取單元用以在根據上述快取線的一順序自上述第一存儲器區塊延續至上述第二存儲器區塊時，決定上述樣態是否預測到上述第二存儲器區塊的上述新的存儲器存取要求所相關的上述快取線在上述第二存儲器區塊中。75.如權利要求67所述的微處理器，其中上述快取單元還用以等待根據上述樣態從上述第二存儲器區塊上述快取線預取至上述快取存儲器中，直到當自上述第一存儲器區塊延續至上述第二存儲器區塊時，決定上述樣態是否預測到在上述新的存儲器存取要求之後有上述第二存儲器區塊的至少一既定值的存儲器存取要求的每一個所相關的一快取線。76.如權利要求67所述的微處理器，其中上述後續的存儲器存取要求的既定數量為2。77.如權利要求67所述的微處理器，其中預取單元還用以維持由多個項目所構成的一項目表，其中上述項目表的每一項目包括第一、第二以及第三欄位，其中上述第二欄位保持一最近存取的存儲器區塊的虛擬地址的代表值，其中上述第一欄位保持在一方向與上述最近存取的存儲器區塊虛擬相鄰的一存儲器區塊的虛擬地址的代表值，其中上述第三欄位保持在另一方向與上述最近存取的存儲器區塊虛擬相鄰的一存儲器區塊的虛擬地址的代表值。78.如權利要求77所述的微處理器，其中為了決定上述第一存儲器區塊是否虛擬相鄰於上述第二存儲器區塊，上述預取單元用以決定上述第二存儲器區塊的虛擬地址的代表值是否匹配於上述項目表的項目的一個的上述第一欄位或者第三欄位；以及決定在所匹配的上述項目的上述第二欄是否匹配於上述第一存儲器區塊的虛擬地址的代表值。79.如權利要求77所述的微處理器，其中為了維持上述表，上述預取單元用以根據一先進先出的方式，將上述項目推進上述項目表中，以回應上述微處理器的一載入/儲存單元所產生的存儲器存取要求。80.如權利要求77所述的微處理器，其中上述存儲器區塊的上述虛擬地址的代表值包括上述存儲器區塊的虛擬地址的一雜湊的位。81.如權利要求80所述的微處理器，其中上述存儲器區塊的虛擬地址的上述雜湊的位根據下列演算法則的一雜湊，其中hash[j]表示第j個雜湊的位，以及VA[k]表示第k個上述存儲器區塊的虛擬地址的位hash[5]=VA[29]"VA[18]"VA[17]；hash[4]=VA[28]"VA[19]"VA[16]；hash[3]=VA[27]"VA[20]"VA[15]；hash[2]=VA[26]"VA[21]"VA[14]；hash[l]=VA[25]"VA[22]"VA[13]；hash=VA[24]"VA[23]"VA[12]082.如權利要求67所述的微處理器，還包括多個核心，其中上述快取存儲器以及預取單元由上述核心所共享。83.一種數據預取方法，用以預取數據至一微處理器的一快取存儲器，上述數據預取方法包括檢測具有一第一存儲器區塊的多個存儲器存取要求的一樣態，並且根據上述樣態從上述第一存儲器區塊預取快取線至上至上述快取存儲器中；監視一第二存儲器區塊的一新的存儲器存取要求；決定上述第一存儲器區塊是否虛擬鄰近於上述第二存儲器區塊，並且當自上述第一存儲器區塊延續至上述第二存儲器區塊時，決定上述樣態是否預測到上述第二存儲器區塊的新的存儲器存取要求所相關的一快取線在上述第二存儲器區塊中；以及根據上述樣態，從上述第二存儲器區塊將多個快取線預取至上述快取存儲器中，以回應上述決定步驟。84.如權利要求83所述的數據預取方法，其中上述第一以及第二存儲器區塊的大小對應於一實體存儲器分頁的大小。85.如權利要求83所述的數據預取方法，其中上述微處理器包括一第二級快取存儲器，其中上述新的存儲器存取要求包括自上述微處理器的一第一級快取存儲器至上述第二級快取存儲器的要求，用以分派上述第二存儲器區塊的上述快取線。86.如權利要求83所述的數據預取方法，其中檢測上述第一存儲器區塊的多個存儲器存取要求的上述樣態的步驟，還包括檢測上述存儲器存取存取的一方向，其中決定上述第一存儲器區塊是否虛擬鄰近於上述第二存儲器區塊的步驟，還包括決定上述第一存儲器區塊是否在上述方向中虛擬鄰近於上述第二存儲器區塊。87.如權利要求86所述的數據預取方法，其中具有上述第一存儲器區塊的上述存儲器存取存取的上述地址隨著時間函數非單調性地增加或者減少。88.如權利要求86所述的數據預取方法，其中當自上述第一存儲器區塊延續至上述第二存儲器區塊時，決定上述樣態是否預測到上述第二存儲器區塊的上述新的存儲器存取要求所相關的上述快取線在上述第二存儲器區塊中的步驟包括在沿著上述方向自上述第一存儲器區塊延續至上述第二存儲器區塊時，決定上述樣態是否預測上述第二存儲器區塊的上述新的存儲器存取要求所相關的一快取線在上述第二存儲器區塊中。89.如權利要求86所述的數據預取方法，其中根據上述樣態自上述第二存儲器區塊將多個快取線預取至上述快取存儲器中的步驟包括根據上述樣態且沿著上述方向，自上述第二存儲器區塊將上述快取線預取至上述快取存儲器中。90.如權利要求83所述的數據預取方法，其中上述樣態包括具有上述第一存儲器區塊的多個快取線的一順序，其中當自上述第一存儲器區塊延續至上述第二存儲器區塊時，為了決定上述樣態是否預測到上述第二存儲器區塊的上述新的存儲器存取要求所相關的上述快取線在上述第二存儲器區塊中，上述預取單元用以在根據上述快取線的一順序自上述第一存儲器區塊延續至上述第二存儲器區塊時，決定上述樣態是否預測上述第二存儲器區塊的上述新的存儲器存取要求所相關的上述快取線在上述第二存儲器區塊中。91.如權利要求83所述的數據預取方法，還包括暫緩根據上述樣態從上述第二存儲器區塊上述快取線預取至上述快取存儲器中，直到當自上述第一存儲器區塊延續至上述第二存儲器區塊時，決定上述樣態是否預測到在上述新的存儲器存取要求之後有上述第二存儲器區塊的至少一既定數量的存儲器存取要求的每一個所相關的一快取線。92.如權利要求83所述的數據預取方法，其中上述後續的存儲器存取要求的既定數量為2。93.如權利要求83所述的數據預取方法，還包括維持由多個項目所構的的一項目表，其中上述項目表的每一項目包括第一、第二以及第三欄位，其中上述第二欄位保持一最近存取的存儲器區塊的虛擬地址的代表值，其中上述第一欄位保持在一方向與上述最近存取的存儲器區塊虛擬相鄰的一存儲器區塊的虛擬地址的代表值，其中上述第三欄位保持在另一方向與上述最近存取的存儲器區塊虛擬相鄰的一存儲器區塊的虛擬地址的代表值。94.如權利要求93所述的數據預取方法，其中決定上述第一存儲器區塊是否虛擬相鄰於上述第二存儲器區塊的步驟，還包括決定上述第二存儲器區塊的虛擬地址的代表值是否匹配於上述項目表的項目的一個的上述第一欄位或者第三欄位；以及決定在所匹配的上述項目的上述第二欄位是否匹配於上述第一存儲器區塊的虛擬地址的代表值。95.如權利要求93所述的數據預取方法，其中維持上述項目表的步驟，還包括以先進先出的方式，將上述項目推進上述項目表中，以便回應上述微處理器的一載入/儲存單元所產生的存儲器存取要求。96.如權利要求93所述的數據預取方法，其中上述存儲器區塊的上述虛擬地址的代表值包括上述存儲器區塊的虛擬地址的一雜湊的位。97.如權利要求96所述的數據預取方法，其中上述存儲器區塊的虛擬地址的上述雜湊的位是根據下列演算法則的一雜湊，其中hash[j]表示第j個雜湊的位，以及VA[k]表示第k個上述存儲器區塊的虛擬地址的位hash[5]=VA[29]"VA[18]"VA[17]hash[4]=VA[28]"VA[19]"VA[16]hash[3]=VA[27]"VA[20]"VA[15]hash[2]=VA[26]"VA[21]"VA[14]hash[l]=VA[25]"VA[22]"VA[13]hash=VA[24]"VA[23]"VA[12]0全文摘要一種預取單元、數據預取方法以及微處理器。該預取單元用以接收對一存儲器區塊的多個地址的多個存取要求，每一存取要求對應存儲器區塊的地址中的一個，並且存取要求的地址隨著時間函數非單調性地增加或減少。當接收到存取要求時，預取單元將維持儲存裝置中的存取要求的一最大地址以及一最小地址，以及最大地址以及最小地址的變化的計數值、維持存儲器區塊中最近被存取的快取線的一歷史記錄，其與最近被存取的快取線以存取要求的地址相關。預取單元亦依據計數值決定一存取方向、根據歷史記錄決定一存取樣態、並且根據存取樣態並沿著存取方向，將快取存儲器內尚未被歷史記錄指示為已存取的快取線預取至存儲器區塊中。文檔編號G06F9/38GK102169429SQ201110077108公開日2011年8月31日申請日期2011年3月29日優先權日2010年3月29日發明者約翰.M.吉爾,羅德尼.E.虎克申請人:威盛電子股份有限公司