ISSN 1000-1239 CN 11-1777/TP

• 系统结构 •

### 基于频繁序列挖掘的预取算法研究与实现

1. 1(武汉光电国家实验室(华中科技大学) 武汉 430074); 2(华中科技大学计算机科学与技术学院 武汉 430074) (wangpeiqun@hust.edu.cn)
• 出版日期: 2016-02-01
• 基金资助:
国家“八六三”高技术研究发展计划基金项目(2013AA013203)；华中科技大学自主创新研究基金项目(2014QN010)

### Study and Implementation of Frequent Sequences Mining Based Prefetching Algorithm

Wang Fang1,2, Wang Peiqun2, Zhu Chunjie1

1. 1(Wuhan National Laboratory for Optoetectronics (Huazhong University of Science and Technology), Wuhan 430074); 2(School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074)
• Online: 2016-02-01

Abstract: Prefetching technology is widely used as an efficient means to improve the performance of storage systems. However, traditional prefetching algorithms are mostly based on detecting sequential access features, which makes them hard to work in the environment with less or no sequential access features. Whats worse, the storage system may even suffer from negative effects with poor prefetching accuracy. Whereas the proposed prefetching algorithm based on frequent sequences mining can make some contributions to the storage system in such environment by analyzing the behavior of the data accessing to find the potential rules. Meanwhile, in some application scenarios where the cache capacity may be limited, such as the embedded system, the proposed prefetching algorithm improves the prefetching accuracy to avoid some adverse impacts which may be caused by prefetching. The new proposed prefetching algorithm is based on the frequent sequences mining technology, and the prefetching rules derived from the mined frequent sequences are organized in a Trie tree. To improve the accuracy of the prefetching, the multistep matching technology and the subtree partitioning technology are introduced, which can subtly control the using of prefetching rules, so that the prefetching algorithm with relatively high prefetching accuracy can efficiently improve the performance of the storage system.