Characterizing Phase Behavior Through Time-Varying Microarchitecture Independent Characteristics Clustering

• Rafael Soares UNICAMP
• Rodolfo Azevedo UNICAMP

DOI: https://doi.org/10.5753/wscad.2020.14075

Resumo

Programs often exhibit repeating behaviors, which are known as program phases. The automatic discovery of such structured behavior has benefited many applications. However, many existing phase signatures lack the ability to reason about what are the key factors of each phase. Also, programs exhibit phase behavior at many different granularities, and some exhibit hierarchical phase behavior. Many techniques focus on a single granularity, which can cause an out of sync classification with the actual phase behavior. We solve these problems by adopting a recently proposed method of subsequence clustering of multivariate time series. Using this method, the phases started to have a much more interpretable signature (MRF). We graphically showed that the method partitions the execution into a temporally consistent way. We showed the effectiveness of MRF's signature by using a centrality measure to identify the most important characteristics within a program phase. Finally, we present a case study to show the relationship between the MRF signature and source code.

Referências

Carlson, T. E., Heirman, W., and Eeckhout, L. (2011). Sniper: Exploring the level of abstraction for scalable and accurate parallel multi-core simulation. In Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis, SC '11, pages 52:1–52:12, New York, NY, USA. ACM.

Eeckhout, L., Sampson, J., and Calder, B. (2005). Exploiting program microarchitecture independent characteristics and phase behavior for reduced benchmark suite simula- tion. In IEEE International. 2005 Proceedings of the IEEE Workload Characterization Symposium, 2005., pages 2–12.

Eeckhout, L., Vandierendonck, H., and Bosschere, K. D. (2002). Workload design: Se- lecting representative program-input pairs. In Proceedings of the 2002 International Conference on Parallel Architectures and Compilation Techniques, PACT '02, pages 83–94, Washington, DC, USA. IEEE Computer Society.

Hallac, D., Vare, S., Boyd, S., and Leskovec, J. (2017). Toeplitz inverse covariance-based clustering of multivariate time series data. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '17, pages 215–223, New York, NY, USA. ACM.

Hoste, K. and Eeckhout, L. (2007a). MICA. https://github.com/boegel/MICA.

Hoste, K. and Eeckhout, L. (2007b). Microarchitecture-independent workload character- ization. IEEE Micro, 27(3):63–72.

Isci, C. and Martonosi, M. (2006). Phase characterization for power: evaluating control- ow-based and event-counter-based techniques. In The Twelfth International Sympo- sium on High-Performance Computer Architecture, 2006., pages 121–132.

LaMarca, A. and Ladner, R. E. (1999). The inuence of caches on the performance of sorting. Journal of Algorithms, 31(1):66 – 104.

Lau, J., Perelman, E., and Calder, B. (2006). Selecting software phase markers with code structure analysis. In Proceedings of the International Symposium on Code Generation and Optimization, CGO '06, Washington, DC, USA. IEEE Computer Society.

Lau, J., Perelman, E., Hamerly, G., Sherwood, T., and Calder, B. (2005). Motivation for variable length intervals and hierarchical phase behavior. In Proceedings of the IEEE International Symposium on Performance Analysis of Systems and Software, 2005, ISPASS '05, pages 135–146, Washington, DC, USA. IEEE Computer Society.

Luk, C.-K., Cohn, R., Muth, R., Patil, H., Klauser, A., Lowney, G., Wallace, S., Reddi, V. J., and Hazelwood, K. (2005). Pin: Building customized program analysis tools with dynamic instrumentation. SIGPLAN Not., 40(6):190–200.

Newman, M. E. J. (2003). A measure of betweenness centrality based on random walks. arXiv e-prints, pages cond–mat/0309045.

Shen, X., Zhong, Y., and Ding, C. (2004). Locality phase prediction. In Proceedings of the 11th International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS XI, pages 165–176, New York, NY, USA. ACM.

Sherwood, T., Perelman, E., Hamerly, G., and Calder, B. (2002). Automatically charac- terizing large scale program behavior. SIGOPS Oper. Syst. Rev., 36(5):45–57.

Sherwood, T., Perelman, E., Hamerly, G., Sair, S., and Calder, B. (2003). Discovering and exploiting program phases. IEEE Micro, 23(6):84–93.

Zhang, W., Li, J., Li, Y., and Chen, H. (2015). Multilevel phase analysis. ACM Trans. Embed. Comput. Syst., 14(2):31:1–31:29.