Frequent instruction sequential pattern mining in hardware sample data

Abstract

When parallelism and heterogeneity has become the trend for computer system design, both the size and the complexity of the hardware sample data generated by Performance Monitoring Unit (PMU) increase fast, thus automatic analysis methods, i.e. data mining methods, are urgently needed to accelerate hardware sample data analysis. We are the first to study instruction sequential pattern mining for hardware sample data. It is a challenging task due to the implicit sequential relationship contained in the data and due to the importance of low frequency patterns. As a solution, we i) provide a novel algorithm Prof Span; ii) adapt two existing algorithms, which are based on candidate generation and projected database generation, to hardware sample data. Our evaluation results show Prof Span can reduce up to 75% and 80% of execution time compared with other two algorithms. Particularly, up to 50% of frequent patterns mined by Prof Span in hardware sample data are crossing basic block boundaries and can not be found by existing methods for source code or disassembly code. We also analyze three example patterns identified by Prof Span: consecutive loads, JIT entry sequence, and conditional code dependency sequence, to illustrate how Prof Span can benefit performance analysis. Finally, we apply patterns to module classification and obtain promising results. © 2010 IEEE.