TWI420311B - 基於集合分模組之快取記憶體之分割方法 - Google Patents

Description

基於集合分模組之快取記憶體之分割方法

本發明係關於一種快取記憶體分割方法，尤其是一種基於集合分模組之基於集合分模組之快取記憶體之分割方法。

目前，單核心處理器因功率及頻率之限制，顯然已無法滿足於現今計算機系統之操作需求及應用，因此，發展具有更高操作性能之多核心處理器技術遂逐漸取代單核心處理器之應用。然而，由於計算機系統之多核心處理器具有快取記憶體共享之特性，衍伸而來的，如何妥善且有效的分割快取記憶體，使得在各核心上執行的程式均能獲得適量的快取記憶體，並容納各該程式的內容，以增進存取效能與降低功率消耗，顯然已成為該領域中之業者亟欲達成之目標。

現有的快取記憶體動態分割方式主要有基於結合度的分割方式、基於集合的分割方式及共享方式等三種。許多文獻及專利已揭示一種基於結合度的快取記憶體之分割方式，如：

1. 2006年發表在39th IEEE/ACM Int’l Symp. On Microarchitecture之研討會論文第423至432頁「Utility-based cache partitioning:a low-overhead,high-performance runtime mechanism to partition shared caches」；

2. 2007年發表在13th Int’l Symp. on High Performance computer Architecture之研討會論文第2至12頁「An adaptive shared/private NUCA cache partitioning scheme for chip multiprocessors」；

3. 2004年刊載在J. of Supercomputing之期刊論文第2至12頁「Dynamic partitioning of shared cache memory」；

4. 2008年發表在Int’l Conf. on Embedded Computer Systems:Architectures,Modeling,and Simulation之研討會論文第25至32頁「An adaptive bloom filter cache partitioning scheme for multicore architectures」；及

5.　中華民國公告第I285810號「晶片多處理器之分享快取記憶體之分割方法、裝置、系統以及儲存有相關指令的電腦可讀取之記錄媒體」發明專利。

上述前案揭示一種習知基於結合度的動態快取記憶體分割，其結構請參照第1圖所示，其將一快取記憶結構區分成數個快取記憶模組，各該模組包含數個快取記憶集合(set)，且各快取記憶集合更包含有數個固定數量之快取線通道(way)。當多個程序執行時，各快取記憶模組的快取線通道依各程序的需求量被分割給不同程序，因此，需要設置更多的快取線，該類快取記憶分割方式在快取記憶體進行存取時需操作全部或多條快取線，因而需要較高的功率，並且多核心處理器之多個程式易競爭同一個快取記憶模組，造成額外的存取等待時間，進而降低系統效能。

有鑑於此，該基於集合的動態快取記憶體之分割方式被提出，由於在該類快取記憶體之分割方式中，該快取記憶模組具有較低的結合度，且對於多個快取存取操作僅需要存取各自對應的快取記憶模組，因而可解決上述該基於結合度的動態快取記憶體分割之缺點。關於該基於集合的動態快取記憶體之分割方式，如2008年發表在14th Int’l Symp. on High Performance computer Architecture之研討會論文第367至378頁「Gaining insights into multicore cache partitioning:bridging the gap between simulation and real systems」，其揭示快取區塊係均勻配置於所分配的快取記憶模組中，在快取記憶重新分割時，各快取存取操作係分開進行，因此可減少等待時間，惟其在快取記憶重新配置時需要整體的快取記憶內容的移動，因此相對產生移動時耗費的功率與時間，在進行快取記憶存取時，需要進行除法運算，亦即需要除法電路之設置，相對的，其將導致邏輯電路及運算複雜度增加，因此亦需耗費較多功率與時間。

另外，關於共享方式的快取記憶體之分割，如2006年發表在39th IEEE/ACM Int’l Symp. on Microarchitecture之研討會論文第433至442頁「Molecular caches:a caching structure for dynamic creation of application-specific heterogeneous cache regions」，其揭示採用隨機分佈的方式，選擇快取記憶模組儲存之記憶區塊，在進行存取時，平均皆需要搜尋多個可能分佈的記憶區塊，因此需要較多搜尋時間與功率消耗。

又，如2004年發表在10th Int’l Symp. on High Performance computer Architecture之研討會論文第176至185頁「Organizing the last line of defense before hitting the memory wall for CMPs」，其揭示將快取記憶模組分配給一至多個程式，在進行快取記憶存取時需要搜尋可能存在的快取記憶模組，因此同樣需要較多搜尋時間與功率消耗。

再者，如中華民國公告第I297832號「多核心處理器中之非均勻快取記憶體的系統方法」發明專利，其揭示一種將記憶區塊以由遠至近的方式分佈於各快取記憶模組，可以依使用狀況動態移動該記憶區塊，調整其與使用之處理器的距離，因此，快取記憶在存取時亦需由近至遠搜尋多個快取記憶模組，故需要較多時間與功率之消耗。

另外，中華民國公告第I317065號「適用於平行處理器之快取記憶體資料存取的方法」發明專利，其亦揭示採取由近至遠搜尋快取記憶模組的方式進行快取記憶存取，因此同樣亦需較多的時間與功率消耗。

本發明主要目的係提供一種基於集合分模組之快取記憶體之分割方法，以減少存取的等待時間、搜尋時間及消耗功率。

本發明次一目的係提供一種基於集合分模組之快取記憶體之分割方法，可以減少重新配置的動作，進一步降低重新分配所需的功率與時間。

本發明另一目的係提供一種基於集合分模組之快取記憶體之分割方法，省去重新配置快取記憶時造成該程序進行快取記憶存取的等待時間。

根據本發明基於集合分模組之快取記憶體之分割方法，係包含步驟：一程式實體位址對應步驟，係將至少一程式實體位址對應到數個虛擬快取記憶模組之至少一個；一虛擬快取記憶模組對應步驟，利用一虛擬至實體快取記憶模組區域編號對應計算與一區域至全域實體快取記憶模組對應表查詢將該數個虛擬快取記憶模組之內容對應至數個實體快取記憶模組，其中該實體快取記憶模組分配數量之選取及該區域至全域實體快取記憶模組對應表之設定係由一作業系統內之軟體演算法或一硬體演算法依據目前進行快取存取之程式之命中率所決定，且其中該虛擬至實體快取記憶模組區域編號對應計算係包含步驟：依據選取之實體快取記憶模組之數量P，以公式計算一k值；將該數個虛擬快取記憶模組依序編號s_1N ，N為0至u-1，其中u為一個程序所對應之虛擬快取記憶模組的數量，且該虛擬快取記憶模組的數量為2的次方，以及將該數個實體快取記憶模組依序做區域編號s_PN ，N為0至v-1，其中v為一個程序動態配置的實體快取記憶模組的數量，將各該虛擬快取記憶模組以其編號s_1N 對2^k 進行如下式之取餘數之運算：s_1N '=s_1N mod2^k ；判斷求得之餘數s_1N ’是否小於P；依據該判斷結果執行一實體快取記憶模組之區域編號s_PN 對應步驟，其中，若餘數s_1N ’小於P，則該餘數s_1N ’即為對應之該實體快取記憶模組之全域編號s_PN ’若餘數s_1N ’不小於P，則將該虛擬快取記憶模組以其編號再進行如下式之取餘數之運算：s_1N '=s_1N mod2^k-1 ，該餘數s_1N ’即為對應之該實體快取記憶模組之區域編號s_PN ；及回覆該虛擬快取記憶模組所欲存取之實體快取記憶模組之區域編號s_PN ；及一實體快取記憶模組之存取步驟，係將各該虛擬快取記憶模組的快取存取，依據該對應到的實體快取記憶模組進行一實體快取記憶體之快取存取。

為讓本發明之上述及其他目的、特徵及優點能更明顯易懂，下文特舉本發明之較佳實施例，並配合所附圖式，作詳細說明如下：

請參照第2圖所示，其揭示本發明較佳實施例之基於集合分模組之快取記憶體之分割方法，包含步驟：一程式實體位址對應步驟S1，係將至少一程式實體位址對應到數個虛擬快取記憶模組之一個；一虛擬快取記憶模組對應步驟S2，利用一虛擬至實體快取記憶模組區域編號對應計算與一區域至全域實體快取記憶模組對應表查詢將數個虛擬快取記憶模組之內容對應至數個實體快取記憶模組，其中該實體快取記憶模組分配數量之選取及該對應表之設定係由一作業系統內之軟體演算法或一硬體演算法依據目前進行快取存取之程式之命中率所決定；及一實體快取記憶模組之存取步驟，係將各該虛擬快取記憶模組的快取存取，依據該對應之實體快取記憶模組進行一實體快取記憶體之快取存取。

其中所謂實體快取記憶模組區域編號的定義為：一程序被分配到若干數量之實體快取記模組(數量為P)，針對該些實體快取記模組進行0~P-1之編號，則該些編號即代表實體快取記憶模組區域編號。

請參照第3A、3B及3C圖所示，在該程式實體位址對應步驟S1中，各該程式段(program segment)均有一程式實體位址，多個程式段可共用同一虛擬快取記憶空間，各該程式實體位址中包含三個位址內容D1、D2及D3，該程式段可利用第3B圖之流程依據該二位址內容D1、D2對應到該虛擬快取記憶體。而當該程式實體位址需要位移時，可利用第3C圖之流程進行虛擬快取記憶模組位址對應之轉換機制，其係將一個或多個程式的個別或整體程式段對應到虛擬快取記憶體中相同或不同的虛擬快取記憶模組，其目的為將低使用率及互補使用的程式段對應到同一個虛擬快取記憶空間，有高度競爭性的程式段對應到不同的虛擬快取記憶空間，以消除其間因快取記憶存取競爭造成的快取記憶污染(cache pollution)的效應。

關於在同一虛擬快取記憶空間之位址對應，可利用記憶體交錯(memory interleaving)的安排方式進行對應，或者如本發明第3A及3C圖所示由數個程式段對應在一虛擬快取記憶空間內位移的技術，以錯開對應到同一虛擬快取空間的其他程式段，以避免快取記憶存取時進行相互競爭。

請參照第4圖所示，該程式內容D1用以提供一索引資料，進行虛擬對應與實體對應而獲得所對應之實體快取記憶模組之全域編號，再使用該程式內容D2及D3至該實體快取記憶模組進行快取存取。

其主要目的為在各虛擬快取記憶空間，依動態需要分配若干數量的實體快取記憶模組，並提供從虛擬到實體快取記憶模組的對應方式。如此，該作業系統內之軟體演算法或硬體演算法依據各程式動態需要調整其使用的實體快取記憶容量，以獲得快取命中率的改進。更進一步言之，一個虛擬快取記憶空間形成一個位址空間整合單位，之後再分配實體快取記憶給各個虛擬快取記憶空間使用，可以依快取命中率與總失誤次數調整各程式所使用實體快取記憶的容量，並使得在相同位址空間可能會相互競爭的程式可對應到不同實體快取記憶模組，而不會造成快取污染。

其中所謂實體快取記憶模組全域編號的定義為：一作業系統或硬體演算法藉由該區域至全域實體快取記憶模組對應表查詢出實際的實體快取記憶體模組之真實位置，該真實位置即為該實際的實體快取記憶體模組之全域編號。

關於本發明之基於集合分模組之快取記憶體之分割方法將細述如下：請參照第5圖所示，其揭示將一程式實體位址空間(physical address space)對應到一虛擬快取記憶體(virtual cache)再對應至一實體快取記憶體(physical cache)之間的對應流程圖。

該程式實體位址空間以一虛擬快取記憶對應之方式對應至該虛擬快取記憶體，其中該虛擬快取記憶體具有數個虛擬快取記憶模組，且該虛擬快取記憶模組之數量為2的次方，該程式實體位址空間之至少一程式實體位址係分配至一個該對應到的虛擬快取記憶模組；藉由該區域至全域實體快取記憶模組對應表之查詢結果，將該對應到的虛擬快取記憶模組內之資料，對應到一實體快取記憶體中的一個對應到的實體快取記憶模組中進行儲存，其中該作業系統內之軟體演算法或硬體演算法依據目前程式需求決定實體快取記憶模組之分配數量，因此該所分配實體快取記憶模組之數量可能為2的次方或非2的次方的任意正整數，且該實體快取記憶模組數量係不大於該虛擬快取記憶模組數量。在一般的狀況下，因局部調整計算的關係，該實體快取記憶模組分配之數量常不為2的次方。

本發明藉由該對應表記載各實體快取記憶模組所進行之動態快取記憶分割，使得各程式可以獲得分配合適數量的實體記憶體，促進其個別與整體的快取命中率。

為清楚介紹如何以該記憶體位址經運算獲得該對應表的索引值，以及如何利用該對應表之索引值決定各該虛擬快取記憶模組與各實體快取記憶模組之間的對應實施方式，請配合參照本發明第6及7圖。

本發明第6圖係揭示一個規律性以模組為單位的虛擬快取記憶空間對應到實體快取記憶空間的計算方法，此方法僅需要快速低功率的計算。該方法包含步驟：一冪級值計算步驟S21，係依據選取之實體快取記憶模組之數量P，以公式計算該冪級值k值；一將各虛擬快取記憶模組對2^k 進行取餘數運算之步驟S22，係將該數個欲進行快取存取之虛擬快取記憶模組依序編號s_1N 為0至u-1(即s₁₀ ,s₁₁ ,...,s_1u-1 )，以及將該數個實體快取記憶模組依序做區域編號s_PN 為0至v-1(即s_P0 ,s_P1 ,...,s_Pv-1 )，並將各該虛擬快取記憶模組以其編號s_1N 對2^k 進行如下式之取餘數之運算：s_1N '=s_1N mod2^k ；一判斷步驟S23，係判斷求得之餘數s_1N ’是否小於P；依據該判斷結果執行一實體快取記憶模組之區域編號s_PN 對應步驟S24，其中，若餘數s_1N ’小於P，則執行一對應步驟，即該餘數s_1N ’為對應之該實體快取記憶模組之區域編號s_PN ，若餘數s_1N ’不小於P，則將各虛擬快取記憶模組再對2^k-1 次方進行取餘數之運算步驟：s_1N '=s_1N mod2^k-1 ，再執行一對應步驟，即該餘數s_1N ’為對應之該實體快取記憶模組之區域編號s_PN ；及一回覆步驟S25，係回覆該虛擬快取記憶模組所欲存取之實體快取記憶模組之區域編號s_PN 。

如上步驟所述，藉由輸入該虛擬快取記憶空間所分配到的實體快取記憶模組數量P與所欲查詢的虛擬快取記憶模組編號s_1N ，經過簡單快速的硬體計算可以回覆出所欲存取的分配之實體快取記憶模組的區域編號s_PN 。在該實體快取記憶模組之存取步驟中，各該虛擬快取記憶模組可依據其對應到的實體快取記憶模組之區域編號s_PN 進行快取存取。而且，在第6圖的電路實現上，由於其不需要除法器，因此可藉由簡單的計算電路架構進行該虛擬快取記憶模組與實體快取記憶模組之間的對應作業。

請參照第7圖所示，其係可用以說明利用第6圖之虛擬至實體快取記憶模組區域編號對應計算方法進行虛擬快取記憶空間與實體快取記憶空間之間的對應關係。假設該虛擬快取記憶空間具有8個虛擬快取記憶模組，其數量係為2的次方，並加以依序編號為0~7；另外，假設作業系統內之軟體演算法或一硬體演算法所選取欲分配之該實體快取記憶模組之數量為P，並加以依序做區域編號為0~P-1，其中P為任意正整數，於此，以該實體快取記憶模組之數量P為1至8為例，列出選取八種不同數量P之表項之對應狀況。

關於第7圖中該虛擬快取記憶模組如何利用第6圖之計算流程對應至該實體快取記憶模組之對應方式，茲舉例說明如下：假設以第7圖中第五表項進行說明，該表項中實體快取記憶模組被分配之數量為5個，其介於，因此，將該虛擬快取記憶模組編號s_1N 分別對2³ =8進行取餘數之計算，若求得的餘數s_1N ’小於5(於此例子中，該虛擬快取記憶模組編號s_1N =0~4之餘數皆小於5)，則該餘數s_1N ’即為對應之該實體快取記憶模組之區域編號s_PN ，即該虛擬快取記憶模組編號s_1N =0~4分別對應到的實體快取記憶模組區域編號s_PN 為0~4。

惟，若求得的餘數s_1N ’不小於P(於此例子中，該虛擬快取記憶模組編號s_1N =5~7分別對2³ =8取餘數後所求得之餘數皆不小於5)，則將該些虛擬快取記憶模組以其編號再分別對2² =4進行取餘數之計算，此時求得的該餘數s_1N ’即為對應之該實體快取記憶模組之區域編號s_PN ，即該虛擬快取記憶模組編號s_1N =5~7此時對應到的實體快取記憶模組區域編號s_PN 為1~3。

綜上所述，請再參照第6及7圖所示，當依照程式動態需求分配實體快取記憶模組給虛擬快取記憶空間時，可將藉由程式實體位址計算出的虛擬快取記憶模組編號與所分配實體快取記憶模組個數作為該虛擬至實體快取記憶模組區域編號對應計算之參考值，並以前述對應計算方法得到所分配的實體快取記憶模組區域編號，再以此區域編號作為索引值進行第8圖所示區域至全域實體快取記憶模組對應表的查詢，進行所對應實體快取記憶模組的快取存取。

請再參照第8圖所示，其揭示程式實體位址及虛擬至實體快取記憶體之間的對應流程圖，該程式實體位址轉換出虛擬快取記憶體模組編號s_1N ，再計算出實體快取記憶模組區域編號s_p ，以此為索引值到區域至全域實體快取記憶模組對應表上查詢出要存取之實體快取記憶模組的全域編號(c_i ,m_i )，而此區域至全域的對應表上由作業系統內之軟體演算法或硬體演算法預存有依序分配到的實體快取記憶模組的全域編號。此方法可達到兩個重要的特性，其一為可將虛擬快取記憶模組編號s_1N 對應到實體快取記憶模組區域編號s_PN ，因此可以局部的重新配置各執行程式所使用到的實體快取記憶大小。其二為在重新配置實體快取記憶模組時，可以以最少量的實體快取記憶模組的重新配置，進行牽涉的快取線集合的移動，因此所需重新配置的時間與功率消耗可以控制在儘量少量的程度。

請再參照第8圖所示，其中由程式實體位址至該虛擬快取記憶模組之轉換可參照第3A、3B及3C圖之對應方式。另外，以該對應表進行該虛擬快取記憶模組至該實體快取記憶模組之對應方式及其對應之硬體架構茲舉例如下：

請參照第9圖所示，該虛擬快取記憶體具有數個虛擬快取記模組，並加以編號0~7，該虛擬快取記模組用以對應轉換程式實體位址；該實體快取記憶體具有數個實體快取記憶叢集(cluster)c0~c3，各該實體快取記憶叢集c0~c3包含四個實體快取記憶模組m0~m3。

請再參照第9圖所示，其中該虛擬快取記憶體及該實體快取記憶體之間係配合該虛擬至實體快取記憶模組區域編號對應計算及區域至全域實體快取記憶模組對應表進行對應。前述對應計算係如第6及7圖之計算；而該區域至全域實體快取記憶模組對應表則係預存於硬體中，由作業系統內之軟體演算法或硬體演算法依據目前程式快取存取之命中率與失誤次數，決定需要分配之實體快取記憶模組之數量，如第9圖所示，該實體快取記憶體共用非2次方數量的實體快取記憶模組進行分配運作(於此，該分配的實體快取記憶模組之數量為5，並被依序索引為0~4)；其中該對應表中索引值為0的實體快取記憶模組係被配置到實體快取記憶叢集c0之實體快取記憶模組m0，如此，該虛擬快取記憶模組編號為0之資料可依路徑快取存取至該實體快取記憶叢集c0之實體快取記憶模組m0；由於該分配之實體快取記憶模組之數量為5，參照第7圖之第五表項可知，編號為1及5之該二虛擬快取記憶模組內之資料可依路徑快取存取至該實體快取記憶叢集c0之實體快取記憶模組m1；其餘虛擬快取記憶模組可參照第7圖之第五表項進行對應配置。

再者，該作業系統內之軟體演算法或硬體演算法依據各該程序P1、P2等目前所處理之快取存取是否有符合其命中率之預定要求，若有，則維持該實體快取記憶模組之分配數量；若無，則重新配置該實體快取記憶模組之分配數量。如第10圖所示，其為假設該程序P1目前所處理之快取存取無法符合命中率之預定要求，而程序P2被判定快取命中率過高，而可將P2所分配之一實體快取記憶模組重新配置給P1使用的快取重新配置(cache reconfiguration)處理過程。

請參照第11圖所示，其揭示經由實體快取記憶模組之位址掃瞄、重新配置，以及利用搬移快取線集合進行實體快取記憶模組之間的重新配置作業，以達到如第10圖所示快取重新配置之目標的操作方式。利用該搬移快取線集合之方法在重新配置之實體快取記憶模組中逐步清除與移入快取線之重新配置操作，係可以一個硬體計數器達到掃瞄的控制。在掃瞄移動快取線集合的過程，對於重新配置的實體快取記憶模組而言，已掃瞄過的快取線集合屬於重新配置完成後的虛擬快取記憶空間，此一情況之實體快取記憶模組的快取存取應使用新的位址對應設定；而尚未掃瞄的快取線集合屬於原來的虛擬快取記憶空間，因此，此一情況之實體快取記憶模組的快取存取應使用原來的位址對應設定。

請參照第12圖所示，其揭示第8圖中再加入二判斷步驟，其一判斷步驟為加入一重新配置旗標，該重新配置旗標係由該作業系統內之軟體演算法或硬體演算法進行控制，以決定該實體快取記憶模組是否正在進行重新配置，即決定獲取該實體快取記憶模組的程序P1的快取存取是要到正重新配置的實體快取記憶模組，或是要到未重新配置的實體快取記憶模組進行存取之作業，並決定釋出該實體快取記憶模組的程序P2的快取存取是要到正重新配置的實體快取記憶模組，或是搬移至其他的實體快取記憶模組進行存取之作業；另一判斷步驟為比較該實體快取記憶模組內存取之集合位址是否不大於快取線集合之掃描位址，以決定該實體快取記憶模組目前應存取新對應的實體快取記憶位址或原來對應的實體快取記憶位址。

請再參照第12圖所示，當該作業系統內之軟體演算法或硬體演算法設定該重新配置旗標為1時，即表示該實體快取記憶模組需重新配置，若某一虛擬快取記憶模組一次獲得增加n(或減少n)個實體快取記憶模組的分配，可以同時以P及P+n(或P-n)計算出對應表上的實體快取記憶模組區域編號s_PN 及s_PN ’，再使用實體快取記憶模組內存取集合位址與快取線集合之掃描位址進行比較，若實體快取記憶模組內存取集合位址不大於快取線集合之掃描位址，則s_PN ’選擇對應到已重新配置的實體快取記憶模組；反之，則s_PN 選擇未重新配置的實體快取記憶模組，進行快取記憶存取。

藉由以上的重新配置與快取記憶位址對應方法，在正被重新配置的虛擬快取記憶模組上所進行的快取記憶存取，均可以正確對應到相關實體快取記憶模組上進行存取。其特點有二：其一為在相關快取記憶重新配置的設定後即可在背景中趁處理器不使用該快取記憶時，進行逐步累進的重新配置工作，牽涉重新配置實體快取記憶模組的執行程式不需等待其重新配置完成，即可繼續執行，此有助於各程式執行的速度。另一特點為在任何時刻的快取存取均只需要做一次的實體快取記憶模組存取，此有利於降低功率與減少快取模組的競爭，其亦可導致效能的增進。

綜上所述，本發明藉由上述步驟之操作，以克服習用基於集合分模組之快取記憶體之分割方法具有在效能上的問題，因此本發明相較於上述習用技術可進一步減少存取的等待與搜尋的時間，並降低存取時電路的消耗功率等功效。

雖然本發明已利用上述較佳實施例揭示，然其並非用以限定本發明，任何熟習此技藝者在不脫離本發明之精神和範圍之內，相對上述實施例進行各種更動與修改仍屬本發明所保護之技術範疇，因此本發明之保護範圍當視後附之申請專利範圍所界定者為準。

第1圖：習知基於結合度的動態快取記憶體分割結構示意圖。

第2圖：本發明較佳實施例之基於集合分模組之快取記憶體之分割方法流程圖。

第3A圖：為多程式段對應至一虛擬快取記憶空間示意圖。

第3B圖：為一程式之程式實體位址對應至一虛擬快取記憶空間示意圖。

第3C圖：為一程式之程式實體位址進行位移對應至另一虛擬快取記憶空間示意圖。

第4圖：為一程式之程式實體位址藉由一虛擬對應與實體對應處理對應至一實體快取記憶模組的示意圖。

第5圖：本發明較佳實施例之一程式實體位址空間、一虛擬快取記憶體及一實體快取記憶體之間的對應示意圖。

第6圖：本發明較佳實施例之虛擬快取記憶空間至所分配實體快取記憶空間的運算流程圖。

第7圖：當該虛擬快取記憶空間具有8個虛擬快取記憶模組時，其利用第6圖之運算流程對應到八種不同實體快取記憶模組數量之情況。

第8圖：本發明較佳實施例之程式實體位址依據第3圖之運算流程對應至虛擬快取記憶模組，再依據第6圖計算出實體快取記憶模組的區域編號，再以此區域編號查詢區域至全域實體快取記憶模組對應表對應至實體快取記憶模組全域編號，此流程顯示於此示意圖。

第9圖：本發明較佳實施例之虛擬快取記憶模組與實體快取記憶模組之間藉由一虛擬至實體快取記憶模組區域編號對應計算及一作業系統內之軟體演算法或硬體演算法所支配的一區域至全域實體快取記憶模組對應表進行對應示意圖。

第10圖：為二程序間進行重新配置之示意圖。

第11圖：為經由實體快取記憶模組之位址掃瞄、重新配置，以及利用搬移快取線集合進行實體快取記憶模組之間的重新配置示意圖。

第12圖：為第8圖中再加入一重新配置旗標及一快取線集合之掃描位址的完整實體快取記憶位址轉換流程示意圖。

Claims (10)

1. 一種基於集合分模組之快取記憶體之分割方法，包含步驟：一程式實體位址對應步驟，係將至少一程式實體位址對應到數個虛擬快取記憶模組之至少一個；一虛擬快取記憶模組對應步驟，利用一虛擬至實體快取記憶模組區域編號對應計算與一區域至全域實體快取記憶模組對應表查詢將該數個虛擬快取記憶模組之內容對應至數個實體快取記憶模組，其中該實體快取記憶模組分配數量之選取及該區域至全域實體快取記憶模組對應表之設定係由一作業系統內之軟體演算法或一硬體演算法依據目前進行快取存取之程式之命中率所決定，且其中該虛擬至實體快取記憶模組區域編號對應計算係包含步驟：依據選取之實體快取記憶模組之數量P，以公式計算一k值；將該數個虛擬快取記憶模組依序編號s_1N ，N為0至u-1，其中u為一個程序所對應之虛擬快取記憶模組的數量，且該虛擬快取記憶模組的數量為2的次方，以及將該數個實體快取記憶模組依序做區域編號s_PN ，N為0至v-1，其中v為一個程序動態配置的實體快取記憶模組的數量，將各該虛擬快取記憶模組以其編號s_1N 對2^k 進行如下式之取餘數之運算：s_1N '=s_1N mod2^k ；判斷求得之餘數s_1N ’是否小於P；依據該判斷結果執行一實體快取記憶模組之區域編號s_PN 對應步驟，其中，若餘數s_1N ’小於P，則該餘數s_1N ’即為對應之該實體快取記憶模組之全域編號s_PN ，若餘數s_1N ’不小於P，則將該虛擬快取記憶模組以其編號再進行如下式之取餘數之運算：s_1N '=s_1N mod2^k-1 ，該餘數s_1N ’即為對應之該實體快取記憶模組之區域編號s_PN ；及回覆該虛擬快取記憶模組所欲存取之實體快取記憶模組之區域編號s_PN ；及一實體快取記憶模組之存取步驟，係將各該虛擬快取記憶模組的快取存取，依據該對應到的實體快取記憶模組，進行一實體快取記憶體之快取存取。
2. 依申請專利範圍第1項所述之基於集合分模組之快取記憶體之分割方法，其中該實體快取記憶模組數量不大於該虛擬快取記憶模組數量，且該實體快取記憶模組數量為任意整數。
3. 依申請專利範圍第1項所述之基於集合分模組之快取記憶體之分割方法，其中在該程式段實體位址對應步驟中，將低使用率及互補使用的程式段對應到同一個虛擬快取記憶空間，有高度競爭性的程式段對應到不同的虛擬快取記憶空間。
4. 依申請專利範圍第3項所述之基於集合分模組之快取記憶體之分割方法，其中在同一虛擬快取記憶空間內之位址對應，可利用記憶體交錯的安排方式進行對應，或者由數個程式段對應在一虛擬快取記憶空間內位移的技術，以錯開對應到同一虛擬快取空間的其他程式段。
5. 依申請專利範圍第1項所述之基於集合分模組之快取記憶體之分割方法，其中在該虛擬快取記憶空間對應步驟中，可對應至實體快取記憶空間為使用共用非2次方數量的實體快取記憶模組，進行快取存取運作。
6. 依申請專利範圍第1項所述之基於集合分模組之快取記憶體之分割方法，其中該作業系統內之軟體演算法依據目前所處理之快取存取是否符合其命中率與失誤次數之相對要求，若有，則維持該實體快取記憶模組之分配數量，若無，則以該作業系統內之軟體演算法或該硬體演算法重新配置該實體快取記憶模組之分配數量。
7. 依申請專利範圍第6項所述之基於集合分模組之快取記憶體之分割方法，其中在該重新配置過程中，利用搬移快取線集合進行實體快取記憶模組之間的重新配置作業。
8. 依申請專利範圍第7項所述之基於集合分模組之快取記憶體之分割方法，其中該搬移快取線集合之方法將實體快取記憶模組逐步清除與移入快取線之重新配置操作係以一個硬體計數器達到掃瞄的控制。
9. 依申請專利範圍第7項所述之基於集合分模組之快取記憶體之分割方法，其中在掃瞄移動快取線集合的過程中，對於重新配置的實體快取記憶模組而言，已掃瞄過的快取線集合，其實體快取記憶模組的快取存取使用新對應的實體快取記憶位址對應設定，而尚未掃瞄的快取線集合，其實體快取記憶模組的快取存取使用原來對應的實體快取記憶位址對應設定。
10. 依申請專利範圍第6項所述之基於集合分模組之快取記憶體之分割方法，其中在該重新配置過程中係包含二判斷步驟，其一判斷步驟為加入一重新配置旗標，該重新配置旗標係由該作業系統內之軟體演算法或該硬體演算法進行控制，以決定該實體快取記憶模組是否正在進行重新配置；另一判斷步驟為比較該實體快取記憶模組內存取之集合位址是否不大於快取線集合之掃描位址，以決定該實體快取記憶模組目前應存取新對應的實體快取記憶位址或原來對應的實體快取記憶位址。