Frequent Instruction Sequential Pattern Mining in Hardware Sample Data

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 ProfSpan, ii) adapt two existing algorithms, which are based on candidate generation and projected database generation, to hardware sample data. Our evaluation results show ProfSpan can reduce up to 75% and 80% of execution time compared with other two algorithms. Particularly, up to 50% of frequent patterns mined by ProfSpan 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 ProfSpan: consecutive loads, JIT entry sequence, and conditional code dependency sequence, to illustrate how ProfSpan can benefit performance analysis. Finally, we apply patterns to module classification and obtain promising results.