CCS: A Motif-Based Storage Format for Micro-execution Dependence Graph

Micro-execution dependence graphs model the program execution on a microprocessor as relationships of micro-execution events intra- and inter-instructions for performance analysis. Each instruction constitutes a motif whose structure is defined by the dependence graph model. With the size of the application increasing dramatically, storing a large-scale dependence graph with billions of instructions becomes difficult. However, popular graph storage formats, such as CSR and CSC, are inefficient for motifs. And the current motif-based compression methods involve the time-consuming process of subgraph isomorphism checking, which is NP-hard. To reduce redundancy, we propose a novel motif-based lossless storage format called compressed common subgraph (CCS) for micro-execution dependence graphs. The key idea is to divide the graph into the intra- and inter-motif parts and compress the common subgraph structures in the intra-motif part by storing the same structures only once. Our method avoids subgraph isomorphism checking because the motifs (instructions) are regularly arranged. Furthermore, the CCS format has two variant implementations, compressed common single subgraph (CCSS) and compressed common multiple subgraphs (CCMS) to adapt to various dependence graph models. Experimental results show that our CCSS and CCMS formats use 16.66% and 8.67% less memory size than the CSC graph format, respectively.