有效分區存儲緩存的製作方法

2023-07-06 17:11:01

專利名稱：有效分區存儲緩存的製作方法
有效分區存儲緩存
背景技術：
除非另有聲明，這一部分中描述的材料並非是針對該申請中權利要求的現有技術，並且並不承認包括在這一部分中就是現有技術。緩存(cache)可以用於存儲供一個或多個處理器或處理器內核訪問的數據。數據可以是較大存儲器中存儲的數據的副本，所述較大存儲器典型地位於具有緩存的晶片外部。在緩存中，可以將數據的副本按照數據陣列(data array)進行存儲。標籤陣列(tag array)可以維持數據陣列中存儲的數據的索引。處理器可以通過識別地址來請求緩存中存儲的特定數據。將地址與標籤陣列中的地址進行比較，以確定該特定數據的副本是否存儲在緩存的數據陣列中。

發明內容
在一個示例中，描述了一種用於將特定塊的特定扇區中的特定數據從存儲器複製到緩存中的方法。在一些示例中，緩存可以包括標籤陣列和數據陣列。在一些示例中，該方法可以包括通過處理器將特定扇區中的特定數據從起始扇區處開始從存儲器複製到數據陣列的路徑中。在一些示例中，該方法還可以包括通過處理器更新標籤陣列以標識特定扇區。在一些示例中，該方法還可以包括通過處理器更新標籤陣列以標識數據陣列中的路徑。在一些示例中，該方法還可以包括通過處理器更新標籤陣列以標識起始扇區。在另一個示例中，描述了一種用於複製特定塊的特定扇區中的特定數據的系統。在一些示例中，該系統包括緩存，緩存包括標籤陣列和數據陣列。在一些示例中，該系統還包括存儲器和處理器，處理器配置為與緩存和存儲器通信。在一些示例中，處理器可以配置為將特定扇區中的特定數據從起始扇區處開始從存儲器複製到數據陣列的路徑中。在一些示例中，處理器可以進一步配置為更新標籤陣列以標識特定扇區。在一些示例中，處理器可以進一步配置為更新標籤陣列以標識數據陣列的路徑。在一些示例中，處理器可以進一步配置為更新標籤陣列以標識起始扇區。在又一示例中，描述了一種基於地址來獲得緩存中存儲的特定扇區中的特定數據的副本的方法。在一些示例中，地址包括標籤欄位、集合索引欄位和扇區索引欄位。在一些示例中，緩存包括標籤陣列和數據陣列。在一些示例中，該方法包括通過處理器在集合索引欄位中所標識的集合中將標籤欄位中的第一標籤數據與標籤陣列中的另一標籤欄位中的第二標籤數據進行比較，以產生匹配標籤。在一些示例中，匹配標籤處於標籤結構中。在一些示例中，標籤結構包括扇區位向量欄位、路徑欄位和起始扇區欄位。在一些示例中，該方法還包括通過處理器將標籤結構的扇區位向量欄位中的扇區位向量數據與地址的扇區索引欄位中的數據進行比較，以確定特定扇區中的特定數據的副本存儲在緩存中。在一些示例中，該方法還包括通過處理器分析路徑欄位中的數據，以確定特定扇區中的特定數據的副本所存儲於的數據陣列中的路徑。在一些示例中，該方法還包括通過處理器分析起始扇區欄位中的數據，以確定特定扇區中的特定數據的副本所存儲於的數據陣列中的起始扇區。在一些示例中，該方法還包括通過處理器按照數據陣列的路徑、集合和起始扇區來獲得特定數據的副本。以上概述只是說明性的，絕非要進行任何限制。除了上述說明性的方面、實施例和特徵之外，通過參考附圖和以下詳細描述，其他方面、實施例和特徵將變得清楚明白。


圖I示出了可以用於實現有效分區存儲緩存的示例系統；圖2示出了可以用於實現有效分區存儲緩存的示例系統；圖3描述了用於實現有效分區存儲緩存的示例處理的流程圖；圖4示出了用於實現有效分區存儲緩存的電腦程式產品的示例；以及 圖5是示出了配置用於實現有效分區存儲緩存的示例計算設備的方框圖；所有這些都根據這裡展示的至少一些實施例來設置。
具體實施例方式在以下詳細說明中，參考了作為詳細說明的一部分的附圖。在附圖中，類似符號通常表示類似部件，除非上下文另行指明。
具體實施方式
部分、附圖和權利要求書中記載的示例性實施例並不是限制性的。在不脫離在此所呈現主題的精神或範圍的情況下，可以利用其他實施例，且可以進行其他改變。應當理解，在此一般性記載以及附圖中圖示的本公開的各方案可以按照在此明確和隱含公開的多種不同配置來設置、替換、組合、分割和設計。該公開一般地涉及實現有效分區存儲緩存(storage efficient sectoredcache)的方法、設備、系統、裝置和電腦程式產品。簡要來說，一般性地描述了這樣的技術用於將特定塊(block)的特定扇區(sector)中的特定數據從存儲器複製到緩存中的系統。在一些示例中，緩存包括標籤陣列和數據陣列。在一些示例中，處理器可以適用於將特定扇區中的數據從存儲器複製到數據陣列的路徑(way)中，數據在該路徑中的複製從起始扇區處開始。在一些示例中，處理器可以適用於更新標籤陣列以標識特定扇區。在一些示例中，處理器可以適用於更新標籤陣列以標識數據陣列中的路徑。在一些示例中，處理器可以適用於更新標籤陣列以標識起始扇區。圖I示出了可以用於實現根據這裡展示的至少一些實施例設置的有效分區存儲緩存的示例系統。示例系統100可以包括處理器102，處理器102配置為與緩存112和存儲器154通信。緩存112可以包括標籤陣列106和數據陣列104。在一些示例中，數據陣列104可以使用DRAM (動態隨機存取存儲器)實現，而標籤陣列106可以使用SRAM (靜態隨機存取存儲器)或者DRAM實現。標籤陣列106可以配置為包括按多個路徑(way)或列(column) 108以及多個集合(set)或行(row) 110排列的多個標籤結構116。在一些示例中，數據陣列104可以配置為包括按照相同數目的集合110和不同數目的路徑114排列的多個緩存線(緩存線路)(cacheline) 118。例如，如圖所示，標籤陣列106和數據陣列104均可以包括N個集合。在所示示例中，標籤陣列106包括8個路徑，而數據陣列104包括4個路徑。如下面更加詳細解釋的那樣，標籤結構116可以配置為對扇區120、122包括數據陣列104中存儲的數據的位置進行映射或者索引(如映射箭頭124所示)。扇區120、122可以包括來自存儲器154中不同數據塊的數據的副本。處理器102可以適用於將數據存儲在數據陣列104的緩存線118中，並且將標籤結構116存儲在標籤陣列106中。在示例中，當將來自不同數據塊的數據存儲在單個緩存線中時，標籤結構116可以適用於指示數據存儲在數據陣列104中的集合、路徑(列)和起始扇區的位置。類似地，處理器102可以配置為通過產生地址並且將地址與標籤陣列106中的標籤結構116相比較來產生對於在數據陣列104中存儲的數據的請求。除了其他優點之外，通過在相同緩存線中存儲和索引來自多個不同塊的數據的副本，可以實現高效的緩存存儲。圖2示出了可以用於實現根據這裡展示的至少一些實施例設置的有效分區存儲緩存的示例系統。圖2實質上與系統100類 似，但具有附加的細節。為了清楚的目的，將不再描述圖2中與圖I部件標記相同的那些部件。如圖2所示，處理器102可以配置為產生地址126，地址126標識可能存儲在緩存112中的數據的位置。地址126可以包括諸如標籤128、集合索引130、扇區索引132和扇區偏移134之類的欄位。標籤陣列中的每一個標籤結構116可以配置為包括諸如標籤136、狀態138、扇區位向量(bit vector) 140、路徑142、起始扇區144和/或長度145之類的欄位。下面將解釋這些欄位的一些用途。數據陣列104中的每一個緩存線118可以配置為包括如在146、148、150和152處所示的M個扇區。在一些示例中，可以在緩存線118中使用64個扇區。在處理器102請求特定塊的特定扇區中的特定數據的示例中，處理器102可以配置為產生針對該特定數據的地址126。地址126的集合索引130可以表示處理器102可能在標籤陣列106中讀取到標籤欄位128中所標識標籤的集合或行。在所示示例中,在地址126中標識集合S2。在該示例中，一旦識別了該集合，處理器102可以配置為對針對標籤欄位128中標識的標籤，對集合S2中的路徑(列)中的標籤進行比較。如果標籤欄位128中的數據與集合S2任一路徑中的標籤欄位136中的數據之間不存在匹配，則處理器102可以配置為確定存在塊未命中(miss)。然後可以從存儲器154中獲得所請求數據的扇區中的數據，並且將其存儲在緩存112中由替代策略(!^placement policy)定義的位置中。例如，可以利用所請求數據的副本覆蓋具有最老時間標籤的數據、在限定的時間段內沒有訪問的數據、或者近來最少使用的數據。在處理器102確定標籤欄位128中的數據與標籤欄位136之一中的數據匹配的示例中，處理器102可以配置為讀取狀態欄位138中的數據。狀態欄位138中的數據可以根據緩存相關性協議(cache cohererce protocol)表示數據的狀態是否是有效的。如果狀態不是有效的，則處理器102可以配置為確定發生了緩存未命中。如果狀態是有效的，則處理器102可以配置為將扇區索引欄位132中的數據與扇區位向量欄位140中的數據進行比較，以確定是否將特定扇區中的數據的副本存儲到數據陣列104中。例如，扇區位向量140中的比特可以表示是否將特定扇區中數據的副本存儲到數據陣列104中，如果扇區位向量140中的數據表示沒有將特定扇區中的數據的副本存儲到數據陣列104中，則處理器102可以配置為確定存在扇區未命中。響應於扇區未命中，處理器102可以配置為從存儲器154獲得特定扇區中的數據，並且基於(這裡所討論的)替代策略來將其複製到緩存112中。在確定特定扇區中的數據的副本存在於緩存112中的示例中，處理器102可以配置為讀取路徑欄位142中的數據。路徑欄位142可以表示數據陣列104中存儲特定扇區中數據的副本的路徑或者列。可以將具有不同標籤線路(tag line)的多個不同塊的扇區中的數據在標籤陣列106中映射到數據陣列104中的相同路徑114以及緩存線路118。處理器102可以配置為讀取起始扇區欄位144中的數據，以確定緩存線118中存儲特定扇區中數據的副本的起始扇區。處理器102可以配置為讀取長度欄位145中的數據，以確定特定數據可能佔用和/或預留多少扇區。例如，特定數據可以佔用數據陣列104中的兩個扇區，並且可以為相關數據預留總共四個扇區。可以在長度欄位145中標識佔用和預留的扇區。在該示例中，如果處理器102訪問相同塊的兩個新扇區，則可以使用在長度欄位145中定義的已有預留而不是引起不同塊的數據的逐出來存儲這兩個新扇區中的數據。在從起始扇區欄位144確定了起始扇區之後，處理器102可以配置為定位地址126的扇區偏移欄位134中的字節(byte) /字(word)。可以將來自存儲器154的數據有效地存儲在緩存112中。在處理器102確定塊或者扇區未命中(如上所述)的示例中，或者當首次用數據填充緩存112時，可以通過處理器102將數據從存儲器154複製到數據陣列114中。不必將數據的整個塊複製到數據陣列114 中，因為可以複製所請求的特定扇區本身。在可以將包括來自多個不同塊的數據的扇區適合到單獨的緩存線路的示例中，可以將具有數據的那些扇區存儲在相同的緩存線路中。例如，當通過處理器102訪問特定扇區時，可以複製該扇區或者下一個連續的扇區或接下來的幾個扇區。在另一示例中，處理器102可以配置為使用扇區預取。扇區預取可以配置為檢測針對扇區中數據的連續訪問，並且預取特定扇區和接下來的幾個扇區。接下來的幾個扇區可以是連續的，或者可以是分開一定的步長(stride)。在一些示例中，基於歷史數據，預取也可以配置為使用長度欄位145確定應該在數據陣列104中預留多少扇區。在另一示例中，處理器102可以配置為監測塊中數據的過去使用，例如針對該塊過去訪問了多少扇區。基於該信息，處理器102可以配置為針對該塊預留與過去訪問相同數目的扇區。在一些示例中，可以基於預測算法對除了特定扇區之外的具有數據的扇區進行預留或者從存儲器154複製到緩存112中。在這些示例中，處理器102可以配置為保持從存儲器154複製的扇區和塊中的數據的歷史信息。例如，在歷史上，包括數據的一些扇區(例如連續的扇區)典型地可以從存儲器154 —起複製到緩存112中，或者具有數據的一個扇區的複製可以暗示也應該複製相關的扇區。利用這種歷史信息，針對這些相關扇區之一的扇區未命中可以指示處理器102應該配置為複製具有數據的相關扇區。例如，處理器102可以配置為使用預測結構，所述預測結構可以跟蹤比緩存112能夠保存的塊更多的塊的使用。在示例中，預測結構可以包括以塊地址和計數值為索引的表，當塊從緩存逐出時，所述計數值用於記錄所述塊的扇區位向量140中的「I」的數目。當處理器102確定存在塊未命中時，處理器102可以配置為檢查上述表。可以通過處理器102使用計數值來確定要為該塊預留的扇區數目。在示例中，存儲器154可以包括塊156和162中的數據，在處理器102請求時可以將所述數據複製到緩存112的數據陣列114中。在該示例中，塊156具有標籤「456」，並且包括四個扇區158(X1、X2、X3和X4)。在該示例中，數據存儲在扇區Xl和X3中(如數據位向量160的比特1010所示)。在該示例中，塊162具有標籤「789」，並且包括四個扇區162(￥1、￥2、￥3和￥4)。在該示例中，數據存儲在扇區Y3和Y4中(如數據位向量166中的比特0011所示)。複製和存儲塊156和162的所有扇區將導致在數據陣列114中分配和使用總共8個扇區和多個緩存線路118。即使當前沒有數據存儲在扇區X2、X4、Y1和Y2中這也成立。處理器102可以適用於將這些扇區158、164中當前存儲有數據的扇區中的數據從存儲器154存儲到數據陣列114中。在該示例中，將塊156的扇區Xl和X3中的數據複製到數據線路118a。數據線路118a包括具有四個緩存扇區編號164(編號為00、01、10、11)的四個扇區。因為只將塊158的兩個扇區(XI和X3)中的數據從存儲器154複製到數據陣列114，所以數據線路118a具有供兩個其他扇區中的數據用的空間。也可以將塊162中的扇區Y3和Y4中的數據複製到數據線路118a中。在一些示例中，處理器102可以配置為預留塊可能需要的預定數目的連續扇區。例如，如果緩存線路118中存在64個扇區，並且標籤陣列106可以保持數據陣列104兩倍的線路，那麼處理器102可以預設地為每一個新的塊預留32個扇區。在另一示例中，如上所述，可以使用記錄有塊的過去使用的預測表。在該示例中，處理器102可以配置為預留過去為該塊所使用的扇區數目，將該數目取捨為可 以預留的最小數目扇區。例如，最小數目可以是16或32的倍數。在示例中，處理器102可以配置為更新標籤陣列108以反映塊156和162的複製。如該示例中所示，第一標籤結構116a可以用於對塊156進行索引。在示例中，處理器102可以配置為將標籤「456」存儲在標籤欄位136中，並且將有效狀態(例如「I」)存儲在狀態欄位138中。在示例中，處理器102可以配置為更新扇區位向量140中的數據，以包括位向量「1010」，表示塊156的哪個(些)扇區包括在數據陣列104中存儲的數據。在示例中，將塊156映射到數據陣列104的路徑《2。因為可以將來自多個不同塊的扇區中的數據映射到相同的緩存線路和路徑，所以標籤結構116a也包括起始扇區欄位144。在該示例中，具有標籤「456」的塊156在值為00的緩存線路扇區標號164處開始，並且因此處理器102可以配置為將「00」存儲在起始扇區欄位144中。在塊156的兩個扇區中存在數據，並且因此處理器102可以配置為將「10」存儲在長度欄位145中。類似地，在示例中，第二標籤結構116b可以用於對塊162進行索引。標籤結構116b可以存儲在不同的標籤條目中作為標籤結構116a。處理器102可以配置為將標籤「789」存儲在標籤欄位136中，並且將有效狀態(例如「I」)存儲在狀態欄位138中。在示例中，處理器102可以配置為更新扇區位向量140中的數據以包括位向量「0011」，表示塊162的哪個(些)扇區包括在數據陣列104中存儲的數據。在示例中，將塊162映射到路徑《2。因為可以將來自多個不同塊的扇區中的數據映射到相同的緩存線路和路徑，所以標籤結構116b也包括起始扇區欄位144。在該示例中，具有標籤「789」的塊162在值為10的緩存線路扇區編號164處開始，並且因此處理器102可以配置為將「10」存儲在起始扇區144中。在塊162的兩個扇區中存在數據，因此處理器102可以配置為將「10」存儲在長度欄位145中。在該示例中，如果數據存儲在塊156的扇區X2中，那麼塊156和162不能夠適合相同的緩存線路118a。在這種示例中，另一條緩存線路可以用於存儲塊156、162。例如，處理器102可以配置為讀取標籤陣列106，並且查找具有所需數目扇區的犧牲塊中的數據，以存儲來自塊156、162的數據。處理器102可以選擇將犧牲塊的數據從緩存112中逐出。在逐出犧牲塊的數據之後，處理器102可以配置為從塊156和/或162複製數據，以佔據在數據陣列104中由犧牲塊的數據釋放的空間。在另一示例中，處理器102可以配置為讀取標籤陣列106，以了解是否在與塊156、162中的數據連續地存儲在相同的緩存線路中的另一塊的數據。可以逐出這種數據，並且處理器102可以配置為將塊156、162的存儲擴展至連續的扇區。在其他示例中，基於處理器102使用的替代策略，可以逐出緩存線路118a中存儲的舊數據以允許新數據的存儲。處理器102可以配置為限制在單獨的緩存線路118中能夠存儲的不同數據塊的數目。例如，為了簡化標籤陣列106，處理器102可以配置為限制在單獨的緩存線路中能夠存儲的不同塊的數目(例如，2或4塊)。在這種示例中，可以基於緩存線路中允許的塊的數目，利用較少的比特對起始扇區欄位144中的數據進行編碼，所述比特標識允許的起始扇區之一。起始扇區欄位144中的數據可以表示特定塊是使用了 1/4、1/2、還是整個緩存線路。除了其他可能的益處之外，在系統100中，緩存112允許將來自多個不同塊的數據存儲在單獨的緩存線路中。單獨塊的數據的存儲不必要求在數據陣列104中分配整個緩存線路。在數據陣列中可以為存儲有數據的扇區分配空間，而非為塊中的所有扇區分配空間 (無論這些扇區中是否存在數據)。除了標籤結構116和緩存線路118之間的一對一映射之外，在一些示例中，系統100允許標籤結構116和緩存線路118之間的多(或者N)對一映射。例如，標籤陣列108中的路徑《2和路徑w5中的標籤結構116可以基於路徑欄位142中的數據，都映射到數據陣列104的路徑《2中的緩存線路118。因為多個不同塊的數據可以共享數據陣列104中的相同緩存線路，所以可以在標籤陣列108中使用比在數據陣列104中使用的更多路徑/列。在一些示例中，通過複製存儲有數據的扇區，即使在具有相對較大緩存尺寸的緩存中，也可以限制緩存中的存儲碎片(fragmentation)。在一些示例中，系統100避免了部分地填充數據陣列104中的緩存線路。除其他益處之外，上述措施可以導致更高的性能和更好的能量效率，如下所述。因此，至少部分地由於限制了存儲碎片，緩存可以保持更多的數據塊。通過增加有效緩存容量，可以減小緩存未命中率，因為更多的塊可以在緩存中找到而不是從另一存儲器中獲得。可以減小數據通信量，允許在不影響具有緩存的晶片的帶寬包絡的情況下實現更多的內核。因為來自不同塊的數據可以共享單獨的緩存線路，所以可能更加頻繁地訪問緩存線路。如果不進行刷新，DRAM緩存線路可能會丟失其電荷。對於緩存線路的多次訪問可能意味著可以使用較少的DRAM刷新。作為使用系統100增加效率的示例，在具有4KB線路和8個路徑組合規則(associativity)的32MB分區緩存中，可以與128KB的標籤陣列(64KB用於標籤，而64KB用於扇區位向量)一起使用8192條緩存線路。如果每一個4KB線路是半填充的，則有效緩存容量只是16MB。標籤結構116包括路徑欄位(在一些示例中可以是3比特)，表示緩存線路所處的位置。標籤結構116可以包括起始扇區欄位(在一些示例中可以是I比特)，表示起始扇區。標籤結構116可以包括長度欄位(在一些示例中可以是I比特)，表示可以允許塊佔用的扇區的最大數目。在該示例中，標籤結構116中的額外欄位總計為5個額外比特，在標籤陣列中合計為5KB的額外標籤存儲(增加了 4% )，但導致32MB的有效緩存容量(增加了 100% )。圖3描述了用於實現根據這裡展示的至少一些實施例設置的有效分區存儲緩存的示例處理的流程圖。在一些示例中，可以使用上述系統100實現圖3中的處理。示例處理可以包括由方框200、202、204、206、208、210、212、214和/或216中的一個或多個所示的一個或多個操作、動作或功能。儘管圖示為分離的方框，可以依賴於所需的實現將各種方框劃分為附加的方框、組合成更少的方框或者取消。處理可以在方框200處開始。在方框200處，處理器可以配置為從緩存請求特定塊中的特定扇區中的數據。處理可以從方框200繼續進行至方框202。在方框202處，處理器可以配置為確定該特定塊的數據的副本是否存儲在緩存中。在一些示例中，這可以通過對標籤陣列中的標籤和/或狀態欄位進行分析來執行。如果該塊不存在於緩存中(「否」)，則處理器可以配置為確定已經發生了緩存未命中，並且處理可以從方框202繼續進行至方框210。如果在方框202處，處理器確定該塊存在於緩存中(「是」)，則處理可以從方框202繼續進行至方框204。在方框204處，處理器可以配置為確定特定扇區中的數據的副本是否存儲在緩存中。在一些示例中，這可以通過對扇區位向量進行分析來執行。如果該特定扇區的數據沒有存儲在緩存中(「否」)，則處理器可以配置為確定已經發生了扇區緩存 未命中，並且處理可以從方框204繼續進行至方框210。如果在方框204處，處理器確定該特定扇區中的數據的副本存在於緩存中(「是」)，則處理可以從方框204繼續進行至方框206。在方框206處，處理器可以配置為確定該特定扇區中的數據的副本存儲在緩存的數據陣列中的路徑和起始扇區。在一些示例中，這可以通過對路徑和起始扇區欄位中的數據進行分析來執行。處理可以從方框206繼續進行至方框208。在方框208處，處理器可以配置為通過參考扇區位向量，來獲得在適當扇區處數據陣列的路徑和起始扇區中存儲的該特定扇區的數據的副本。在方框210，在方框202的塊未命中之後或者在方框204的扇區未命中之後，處理器可以配置為將該特定扇區中存儲的數據從另一存儲器複製到緩存的數據陣列的緩存線路中。可以將該特定扇區中存儲的數據複製到包括來自其他不同塊的數據的緩存線路中。處理可以從方框210繼續進行至方框212。在方框212，處理器可以配置為更新緩存的標籤陣列，以標識包括在數據陣列中存儲的數據的該特定扇區。在一些示例中，這可以通過更新扇區位向量欄位來執行。處理可以從方框212繼續進行至方框214。在方框214，處理器可以配置為更新緩存的標籤陣列，以標識包括數據的該特定扇區存儲在數據陣列中的路徑。在一些示例中，這可以通過更新路徑欄位來執行。處理可以從方框214繼續進行至方框216。在方框216，處理器可以配置為更新緩存的標籤陣列，以標識緩存線路中包括數據的該特定扇區存儲在數據陣列中的起始扇區。在一些示例中，這可以通過更新起始扇區欄位來執行。圖4示出了根據這裡展示的至少一些實施例設置的示例電腦程式產品300。程序產品300可以包括信號承載介質302。信號承載介質302可以包括一個或多個指令304,當通過例如處理器執行時，所述指令可以提供以上針對圖1-3描述的功能。因此例如參考系統100，處理器102可以響應於通過介質302轉達給系統100的指令來進行圖4所示的一個或多個模塊。在一些實現中，信號承載介質302可以涵蓋計算機可讀介質306，例如但不局限於硬碟驅動器、光碟(CD)、數位化視頻盤(DVD)、數字磁帶、存儲器等。在一些實現中，信號承載介質302可以涵蓋可記錄介質308，例如但不局限於存儲器、讀/寫(R/W)⑶、R/W DVD等。在一些實現中，信號承載介質302可以涵蓋通信介質310，例如但不局限於數字和/或模擬通信介質(例如光纜、波導、有線通信鏈路、無線通信鏈路等)。因此例如，程序產品300可以通過RF信號承載介質302向系統100的一個或多個模塊轉達，其中通過無線通信介質310 (例如符合IEEE 802. 11標準的無線通信介質)轉達信號承載介質302。圖5是示出了示例計算設備400的方框圖，該計算設備400設置用於實現根據這裡展示的至少一些實施例的有效分區存儲緩存。在非常基本的配置402中，計算設備400典型地包括一個或多個處理器404和系統存儲器406。存儲器總線408可用於在處理器404和系統存儲器406之間進行通信。根據所期望的配置，處理器4 04可以是任意類型的，包括但不限於微處理器(UP)、微控制器(UC)、數位訊號處理器(DSP)或其任意組合。處理器404可以包括一級或多級緩存(例如，一級高速緩存410和二級高速緩存412)、處理器核414、以及寄存器416。示例處理器核414可以包括算術邏輯單元(ALU)、浮點單元(FPU)、數位訊號處理核(DSP核)或其任意組合。示例存儲器控制器418也可以與處理器404 —起使用，或者在一些實施方式中，存儲器控制器418可以是處理器404的內部部件。根據所期望的配置，系統存儲器406可以是任意類型的，包括但不限於易失性存儲器(如RAM)、非易失性存儲器(如ROM、快閃記憶體等)或其任意組合。系統存儲器406可以包括作業系統420、一個或多個應用程式422和程序數據424。應用程式422可以包括有效分區存儲緩存算法426，其設置用於執行在此所述的功能，包括針對圖2的系統100描述的功能。程序數據424可以包括有效分區存儲緩存數據428，如上所述，其可以對於有效分區存儲緩存算法是有用的。在一些實施例中，應用程式422可以設置用於在作業系統420上利用程序數據424來操作，使得可以提供有效分區存儲緩存算法。這裡所描述的基本配置402在圖5中由虛線內的部件來圖示。計算設備400可以具有額外特徵或功能以及額外接口，以有助於基本配置402與任意所需設備和接口之間進行通信。例如，總線/接口控制器430可以有助於基本配置402與一個或多個數據存儲設備432之間經由存儲接口總線434進行通信。數據存儲設備432可以是可拆除存儲設備436、不可拆除存儲設備438或其組合。可拆除存儲設備和不可拆除存儲設備的示例包括磁碟設備(如軟盤驅動器和硬碟驅動器(HDD))、光碟驅動器(如緊緻盤(CD)驅動器或數字通用盤(DVD)驅動器)、固態驅動器(SSD)以及磁帶驅動器，這僅僅是極多例子中的一小部分。示例計算機存儲介質可以包括以任意信息存儲方法或技術實現的易失性和非易失性、可拆除和不可拆除介質，如計算機可讀指令、數據結構、程序模塊或其他數據。系統存儲器406、可拆除存儲設備436和不可拆除存儲設備438均是計算機存儲介質的示例。計算機存儲介質包括但不限於RAM、ROM、EEPR0M、快閃記憶體或其他存儲器技術，CD-ROM、數字多功能盤(DVD)或其他光存儲設備，磁盒、磁帶、磁碟存儲設備或其他磁存儲設備，或可以用於存儲所需信息並可以由計算設備400訪問的任意其他介質。任何這種計算機存儲介質可以是設備400的一部分。計算設備400還可以包括接口總線440，以有助於各種接口設備(例如，輸出設備442、外圍設備接口 444和通信設備116)經由總線/接口控制器430與基本配置402進行通信。示例輸出設備442包括圖形處理單元448和音頻處理單元450，其可被配置為經由一個或多個A/V埠 452與多種外部設備(如顯示器或揚聲器)進行通信。示例外圍設備接口 444包括串行接口控制器454或並行接口控制器456，它們可被配置為經由一個或多個I/O埠 458與外部設備(如輸入設備(例如，鍵盤、滑鼠、筆、語音輸入設備、觸摸輸入設備等))或其他外圍設備(例如，印表機、掃描儀等)進行通信。示例通信設備446包括網絡控制器460，其可以被設置為經由一個或多個通信埠 464與一個或多個其他計算設備462通過網絡通信鏈路進行通信。網絡通信鏈路可以是通信介質的一個示例。通信介質典型地可以由調製數據信號(如載波或其他傳輸機制)中的計算機可讀指令、數據結構、程序模塊或其他數據來體現，並可以包括任意信息傳送介質。「調製數據信號」可以是通過設置或改變一個或多個特性而在該信號中實現信息編碼的信號。例如，但並非限 制性地，通信介質可以包括有線介質(如有線網絡或直接布線連接)、以及無線介質(例如聲、射頻(RF)、微波、紅外(IR)和其他無線介質)。這裡所使用的術語計算機可讀介質可以包括存儲介質和通信介質。計算設備400可以實現為小體積可攜式(或移動)電子設備的一部分，如蜂窩電話、個人數據助理(PDA)、個人媒體播放設備、無線web瀏覽設備、個人耳機設備、專用設備或包括任意上述功能的混合設備。計算設備400也可以實現為個人計算機，包括膝上型計算機和非膝上型計算機配置。本公開不限於在本申請中描述的具體示例，這些具體示例意在說明不同方案。本領域技術人員清楚，不脫離本公開的精神和範圍，可以做出許多修改和變型。本領域技術人員根據之前的描述，除了在此所列舉的方法和裝置之外，還可以想到本公開範圍內功能上等價的其他方法和裝置。這種修改和變型應落在所附權利要求的範圍內。本公開應當由所附權利要求的術語及其等價描述的整個範圍來限定。應當理解，本公開不限於具體方法、試齊U、化合物組成或生物系統，這些都是可以改變的。還應理解，這裡所使用的術語僅用於描述具體示例的目的，而不應被認為是限制性的。至於本文中任何關於多數和/或單數術語的使用，本領域技術人員可以從多數形式轉換為單數形式，和/或從單數形式轉換為多數形式，以適合具體環境和應用。為清楚起見，在此明確聲明單數形式/多數形式可互換。本領域技術人員應當理解，一般而言，所使用的術語，特別是所附權利要求中(例如，在所附權利要求的主體部分中)使用的術語，一般地應理解為「開放」術語(例如，術語「包括」應解釋為「包括但不限於」，術語「具有」應解釋為「至少具有」等)。本領域技術人員還應理解，如果意在所引入的權利要求中標明具體數目，則這種意圖將在該權利要求中明確指出，而在沒有這種明確標明的情況下，則不存在這種意圖。例如，為幫助理解，所附權利要求可能使用了引導短語「至少一個」和「一個或多個」來引入權利要求中的特徵。然而，這種短語的使用不應被解釋為暗示著由不定冠詞「一」或「一個」引入的權利要求特徵將包含該特徵的任意特定權利要求限制為僅包含一個該特徵的實施例，即便是該權利要求既包括引導短語「一個或多個」或「至少一個」又包括不定冠詞如「一」或「一個」(例如，「一」和/或「一個」應當被解釋為意指「至少一個」或「一個或多個」)；在使用定冠詞來引入權利要求中的特徵時，同樣如此。另外，即使明確指出了所引入權利要求特徵的具體數目，本領域技術人員應認識到，這種列舉應解釋為意指至少是所列數目(例如，不存在其他修飾語的短語「兩個特徵」意指至少兩個該特徵，或者兩個或更多該特徵)。另外，在使用類似於「A、B和C等中至少一個」這樣的表述的情況下，一般來說應該按照本領域技術人員通常理解該表述的含義來予以解釋(例如，「具有A、B和C中至少一個的系統」應包括但不限於單獨具有A、單獨具有B、單獨具有C、具有A和B、具有A和C、具有B和C、和/或具有A、B、C的系統等)。在使用類似於「A、B或C等中至少一個」這樣的表述的情況下，一般來說應該按照本領域技術人員通常理解該表述的含義來予以解釋(例如，「具有A、B或C中至少一個的系統」應包括但不限於單獨具有A、單獨具有B、單獨具有C、具有A和B、具有A和C、具有B和C、和/或具有A、B、C的系統等)。本領域技術人員還應理解，實質上任意表示兩個或更多可選項目的轉折連詞和/或短語，無論是在說明書、權利要求書還是附圖中，都應被理解為給出了包括這些項目之一、這些項目任一方、或兩個項目的可能性。例如，短語「A或B」應當被理解為包括「A」或「B」、或「A和B」的可能性。另外，在以馬庫什組描述本公開的特徵或方案的情況下，本領域技術人員應認識 至IJ，本公開由此也是以該馬庫什組中的任意單獨成員或成員子組來描述的。本領域技術人員應當理解，出於任意和所有目的，例如為了提供書面說明，這裡公開的所有範圍也包含任意及全部可能的子範圍及其子範圍的組合。任意列出的範圍可以被容易地看作充分描述且實現了將該範圍至少進行二等分、三等分、四等分、五等分、十等分等。作為非限制性示例，在此所討論的每一範圍可以容易地分成下三分之一、中三分之一和上三分之一等。本領域技術人員應當理解，所有諸如「直至」、「至少」、「大於」、「小於」之類的語言包括所列數字，並且指代了隨後可以如上所述被分成子範圍的範圍。最後，本領域技術人員應當理解，範圍包括每一單獨數字。因此，例如具有I 3個單元的組是指具有1、2或3個單元的組。類似地,具有I 5個單元的組是指具有1、2、3、4或5個單元的組，以此類推。儘管已經在此公開了多個方案和實施例，但是本領域技術人員應當明白其他方案和實施例。這裡所公開的多個方案和實施例是出於說明性的目的，而不是限制性的，本公開的真實範圍和精神由所附權利要求表徵
權利要求
1.ー種用於將特定塊的特定扇區中的特定數據從存儲器複製到緩存中的方法，所述緩存包括標籤陣列和數據陣列，所述方法包括 通過處理器將特定扇區中的特定數據從存儲器複製到數據陣列的路徑中，所述特定數據在所述路徑中的複製從起始扇區處開始； 通過處理器更新標籤陣列以標識所述特定扇區； 通過處理器更新標籤陣列以標識數據陣列中的所述路徑；以及 通過處理器更新標籤陣列以標識所述起始扇區。
2.根據權利要求I所述的方法，還包括在複製之前，通過處理器確定所述特定塊中的數據的副本沒有存儲在緩存中。
3.根據權利要求2所述的方法，其中通過處理器確定所述特定塊中的數據的副本沒有存儲在緩存中包括將針對特定數據的請求的標籤欄位與標籤陣列中的標籤欄位進行比較。
4.根據權利要求3所述的方法，還包括在複製之前，通過處理器確定所述特定扇區中的特定數據的副本沒有存儲在緩存中。
5.根據權利要求4所述的方法，其中通過處理器確定所述特定扇區中的特定數據的副本沒有存儲在緩存中包括將所述請求的扇區索引欄位與標籤陣列中的扇區位向量欄位進行比較。
6.根據權利要求5所述的方法，其中標籤陣列中的扇區位向量欄位表示在數據陣列中存儲的特定塊的扇區的副本。
7.根據權利要求I所述的方法，其中 所述特定數據是第一特定數據，並且所述第一特定數據在存儲器中存儲在第一塊中； 所述特定扇區是第一特定扇區； 所述路徑是第一路徑； 所述起始扇區是第一起始扇區，並且所述方法還包括 通過處理器將第二特定扇區中的特定數據從存儲器複製到數據陣列的第二路徑中，所述第二特定扇區中的特定數據在所述第二路徑中的複製從第二起始扇區處開始，其中所述第二特定扇區在存儲器中存儲在第二塊中，並且其中所述第二塊與所述第一塊不同； 通過處理器更新標籤陣列以標識所述第二特定扇區； 通過處理器更新標籤陣列以標識數據陣列中的所述第二路徑；以及 通過處理器更新標籤陣列以標識所述第二起始扇區。
8.根據權利要求7所述的方法，其中所述第一和第二路徑不同。
9.根據權利要求I所述的方法，其中複製包括分析所述特定塊，對存儲器中存儲數據的所述特定塊的所述特定扇區中的數據進行複製，並且對存儲器中沒有存儲數據的所述特定塊的另ー扇區不分配數據陣列中的空間。
10.根據權利要求7所述的方法，其中 通過處理器複製第一特定扇區中的數據包括分析第一特定塊，對存儲器中存儲數據的第一特定塊的第一特定扇區中的數據進行複製，對存儲器中沒有存儲數據的第一特定塊的另ー扇區不分配數據陣列中的空間；以及 通過處理器複製第二特定扇區中的數據包括分析第二特定塊，對存儲器中存儲數據的第二特定塊的第二特定扇區中的數據進行複製，對存儲器中沒有存儲數據的第二特定塊的另一扇區不分配數據陣列中的空間。
11.根據權利要求I所述的方法，其中複製包括對所述特定扇區和相關扇區中的數據進行複製。
12.根據權利要求I所述的方法，還包括通過處理器更新標籤陣列以指示在數據陣列中為所述特定數據所預留的扇區的數目。
13.根據權利要求I所述的方法，還包括通過處理器基於替代策略來選擇所述路徑和起始扇區。
14.ー種用於複製特定塊的特定扇區中的特定數據的系統，所述系統包括 緩存，包括標籤陣列和數據陣列； 存儲器；以及 處理器，所述處理器配置為與所述緩存和存儲器通信，其中 所述處理器配置為 將特定扇區中的特定數據從存儲器複製到數據陣列的路徑中， 所述特定數據在所述路徑中的複製從起始扇區處開始； 更新標籤陣列以標識所述特定扇區； 更新標籤陣列以標識數據陣列中的所述路徑；以及 更新標籤陣列以標識所述起始扇區。
15.根據權利要求14所述的系統，其中 所述特定數據是第一特定數據，並且所述第一特定數據在存儲器中存儲在第一塊中； 所述特定扇區是第一特定扇區； 所述路徑是第一路徑； 所述起始扇區是第一起始扇區，以及所述處理器還配置為 將第二特定扇區中的數據從存儲器複製到數據陣列的第二路徑中，所述第二特定扇區中的數據在所述第二路徑中的複製從第二起始扇區處開始，其中所述第二特定數據在存儲器中存儲在第二塊中，並且其中所述第二塊與所述第一塊不同； 更新標籤陣列以標識所述第二特定扇區； 更新標籤陣列以標識數據陣列中的所述第二路徑；以及 更新標籤陣列以標識所述第二起始扇區。
16.根據權利要求15所述的系統，其中所述第一和第二路徑不同。
17.根據權利要求15所述的系統，其中 所述處理器配置為通過如下操作複製第一特定扇區中的數據分析第一特定塊，對存儲器中存儲數據的第一特定塊的第一特定扇區中的數據進行複製，對存儲器中沒有存儲數據的第一特定塊的另一扇區不分配數據陣列中的空間；以及 所述處理器配置為通過如下操作複製第二特定扇區中的數據分析第二特定塊，對存儲器中存儲數據的第二特定塊的第二特定扇區中的數據進行複製，對存儲器中沒有存儲數據的第二特定塊的另一扇區不分配數據陣列中的空間。
18.根據權利要求14所述的系統，其中使用DRAM實現數據陣列，並且使用SRAM或DRAM實現標籤陣列。
19.一種基於地址來獲得緩存中存儲的特定扇區中的特定數據的副本的方法，其中所述地址包括標籤欄位、集合索引欄位和扇區索引欄位，所述緩存包括標籤陣列和數據陣列，所述方法包括 通過處理器在所述集合索引欄位中所標識的集合中，將所述標籤欄位中的第一標籤數據與標籤陣列中的另ー標籤欄位中的第二標籤數據進行比較，以產生匹配標籤，其中所述匹配標籤具有標籤結構，並且其中所述標籤結構包括扇區位向量欄位、路徑欄位和起始扇區欄位； 通過處理器將在所述標籤結構的扇區位向量欄位中的扇區位向量數據與所述地址的扇區索引欄位中的數據進行比較，以確定所述特定扇區中的特定數據的副本存儲在所述緩存中； 通過處理器分析所述路徑欄位中的數據，以確定所述特定扇區中的特定數據的副本所存儲於的數據陣列中的路徑； 通過處理器分析所述起始扇區欄位中的數據，以確定所述特定扇區中的特定數據的副·本所存儲於的數據陣列中的起始扇區；以及 通過處理器按照數據陣列的所述路徑、集合和起始扇區來獲得所述特定數據的副本。
20.根據權利要求19所述的方法，其中所述地址還包括扇區偏移欄位，並且所述方法還包括使用所述扇區偏移欄位中的數據來獲得所述特定扇區的特定數據的副本。
全文摘要
一般性地描述了這樣的技術用於將特定塊的特定扇區中的特定數據從存儲器複製到緩存中的系統。在一些示例中，緩存包括標籤陣列和數據陣列。在一些示例中，處理器可以適用於將特定扇區中的數據從存儲器複製到數據陣列的路徑中，數據在所述路徑中的複製從起始扇區處開始。在一些示例中，處理器可以適用於更新標籤陣列以標識特定扇區。在一些示例中，處理器可以適用於更新標籤陣列以標識數據陣列中的路徑。在一些示例中，處理器可以適用於更新標籤陣列以標識起始扇區。
文檔編號G06F13/28GK102859504SQ201080066116
公開日2013年1月2日 申請日期2010年4月21日 優先權日2010年4月21日
發明者揚·索利希恩 申請人:英派爾科技開發有限公司