[發明專利]基于增量式閉合序列挖掘的高速緩存數據預取方法

無效

• 申請號: 200810059854.1
• 申請日: 2008-02-22
• 公開（公告）號: CN101266578A
• 公開（公告）日: 2008-09-17
• 發明（設計）人: 陳剛;蔡銘;李山亭
• 申請（專利權）人: 浙江大學
• 主分類號: G06F12/08
• 分類號: G06F12/08;G06F17/30
• 代理公司: 杭州求是專利事務所有限公司
• 代理人: 林懷禹

技術領域

本發明涉及高速緩存數據預取技術，尤其是涉及一種基于增量式閉合序列挖掘的高速緩存數據預取方法。

背景技術

近年來，為了減少處理器等待讀取數據的時間，提出了使用高速緩存的技術。采用高速緩存的系統芯片的相關部分如圖1所示，該系統芯片包括處理器、高速緩存、高速緩存預取模塊、內存，系統總線。其中處理器從高速緩存中讀取數據并進行計算以及向高速緩存預取模塊發送預取數據的控制信息；高速緩存中保存的是處理器將要使用的數據；高速緩存預取模塊用于從系統內存讀取處理器即將使用的數據，并將數據傳輸到高速緩存；內存中保存著各種數據；系統芯片總線連接所述高數緩存預取模塊和內存，并傳遞各種控制信息。

為提高高速緩存的效率(提高命中率)，在高速緩存未命中發生之前，需要高速緩存預取模塊進行數據預加載(pre-load)(或預取(pre-fetch))，即把將要使用的數據預先填充到高速緩存中。存在幾種公知的數據預取技術。一種是順序預取，即預取地址空間的下一順序行。另一種是分支預測技術，使用分支目標緩存器，當一個高速緩存行被引用時，它的相關聯的分支目標地址是預取的良好候選者。

這些公知的數據預取技術，都采用簡單的預取模式，高速緩存的命中率不高，預取沒有利用數據塊之間的語義聯系，不具有智能性。因此，在高數緩存預取模塊中引入語義模式，充分挖掘數據塊之間的語義聯系，提高高速緩存的命中率是十分有必要的。

序列模式挖掘是數據挖掘中的一項重要任務.其目的是在給定的序列數據庫中挖掘出所有的滿足最小支持度要求的頻繁序列，以產生相應的規則或模式.這類模式有著廣泛的應用，如分析顧客的購物習慣、Web頁面的訪問順序、DNA序列等等。而頻繁閉合序列擁有與完全頻繁序列集相同的表達能力，卻有著更加簡潔的形式和少得多的數量，充分減少了結果集的冗余度。

將閉合序列挖掘引入高速緩存的數據預取模塊中，通過對存儲數據存取系列挖掘出相應的頻繁閉合序列，產生數據預取的規則，從而使得數據塊之間具有語義聯系，數據預取智能化，這是有實際意義的。UIUC的Zhenmin等使用閉合序列模式挖掘算法Clospan的變種CMiner挖掘存儲系統的數據存取序列的數據相關性，明顯地提高了I/O平均響應時間。CMiner挖掘方法是針對靜態數據庫進行的，不能針對實時的環境進行挖掘，而存儲數據的存取序列是動態更新的，特點是變化幅度小，頻率高，因此需要一種更加高效的實時閉合序此列挖掘方法來滿足需求。

發明內容

本發明的目的在于提供一種基于增量式閉合序列挖掘的高速緩存數據預取方法。

本發明解決其技術問題所采用的技術方案是：

1、用于存儲系統的高速緩存數據預取模塊中的數據預取步驟中的，通過采集CPU向內存請求的數據存取序列，將其轉換為序列輸入數據庫，采用增量式閉合序列挖掘算法挖掘頻繁閉合序列，提取出高速緩存數據預取規則，用于指導高速緩存的數據預取，提高高速緩存的命中率；

(1)采集CPU訪問內存存取序列：實時記錄CPU請求訪問的文件系統中的邏輯塊號組成的序列，每一個文件系統的邏輯塊號為序列中的一個項目；

(2)預處理：處理步驟(1)得到的CPU訪問內存存取序列，將步驟(1)得到的CPU訪問內存存取序列劃分為固定長度的序列，此序列為一個窗口，此序列長度為窗口大小，一個窗口作為一條輸入序列，存入輸入序列數據庫中；

(3)訓練：對步驟(2)得到的序列輸入數據庫采用增量式的閉合序列挖掘方法進行挖掘得到頻繁閉合序列集合，每當步驟(2)有新的輸入序列時，在已有的閉合序列挖掘的結果基礎上，結合新增輸入序列，增量式挖掘新的頻繁閉合序列模式集合；

(4)規則生成：對步驟(3)得到的頻繁閉合序列進行分解得到所蘊含的所有規則，并通過規則評估函數對規則進行評估，去除不符合要求的規則，最后得到高效的用于高速緩存數據預取的指導規則。

2.步驟(2)設置一個計數器，初始值為零，步驟(1)每采集一個項目，計數器增加1，當計數器值等于窗口大小時，把步驟(1)采集得到的序列作為一條記錄存入序列輸入數據庫中，并清除步驟(1)的記錄。計數器重置為0，取下一條存入序列輸入數據庫的記錄，如此循環下去；

3.步驟(3)對步驟(2)得到的序列輸入數據庫，簡稱為SDB采用增量式的閉合序列挖掘方法進行挖掘得到頻繁閉合序列集合的具體步驟如下：