Application of graph alignment techniques for identifying sources of non-determinism in MPI simulations

Abstract

Scientific high performance computing (HPC) applications employ asynchronous executions of MPI calls to improve scalability and performance. The asynchronous calls can lead to non-determinism (ND) in execution, particularly for large exascale simulations. In order to ensure reproducibility and facilitate error detection, it is imperative to identify the sources of non-determinism. Message ND that occurs when the order in which a process sends or receives MPI communication, or executes MPI calls varies across different runs of the same application. We model the MPI calls in the execution as an event graph. The regions of dissimilarity between two event graphs indicate the sources of non-determinism in the MPI calls. Thus by aligning the nodes of the event graphs, we can identify sources of ND. We show that traditional alignment techniques such as NetAlign and learning methodologies such as Graph Autoencoders are not able to align graphs with high accuracy due to the nearly regular degree and large diameter of event graphs. Therefore, we propose a meta graph heuristic that exploits structural properties of event graphs, by combining the set of nodes representing sequences of MPI calls within the same processor as a meta node. We align the meta graphs formed from these meta nodes, and then align the individual nodes within the meta nodes. Our results over three different MPI applications highlight that our meta graph heuristic has better accuracy and scales to large graphs compared to network alignment and graph auto encder methods.

Keywords

non-determinism MPI communications event graphs graph alignment

Get full access to this article

View all access options for this article.

References

Bayati

Gerritsen

Gleich

, et al. (2009) Algorithms for large, sparse network alignment problems. In: 2009 Ninth IEEE international conference on data mining, Miami, Florida, 06–09 December 2009, pp. 705–710.

Bell

Suarez

Chapp

, et al. (2021) ANACIN-X: a software framework for studying non-determinism in MPI applications. Software Impacts 10: 100151.

Chapp

Tan

Bhowmick

, et al. (2021) Identifying degree and sources of non-determinism in MPI applications via graph kernels. IEEE Transactions on Parallel and Distributed Systems 32(12): 2936–2952.

Gentile

Miller

(2010) Monte Carlo Benchmark (MCB). Livermore, CA, USA: Lawrence Livermore Nat. Lab. Tech. Rep. TR-LLNL-CODE-507091.

Milenković

Memisević

, et al. (2010) Protein interaction network topology uncovers melanogenesis regulatory network components within functional genomics datasets. BMC Systems Biology 4: 84.

Hočevar

Demšar

(2017) Combinatorial algorithm for counting small induced graphs and orbits. PONE 12(2): e0171428.

Khan

Gleich

Pothen

, et al (2012) A multithreaded algorithm for network alignment via approximate matching. In: SC’12: Proceedings of the international conference on high performance computing, networking, storage and analysis. IEEE, Salt Lake city, UT, USA, 2012, pp. 1–11.

Kipf

Welling

(2016) Variational graph auto-encoders. arXiv:1611.07308. doi: 10.48550/arXiv.1611.07308.

Klau

(2009) A new graph-based method for pairwise global network alignment. BMC Bioinformatics 10(Suppl 1): S59.

10.

LLNL (2014) CORAL benchmark suite. Available at: https://asc.llnl.gov/coral-benchmarks.

11.

Pang

Kasabov

(2004) Inductive vs transductive inference, global vs local models: Svm, Tsvm, And Svmt for gene expression classification problems. 2004 IEEE International Joint Conference on Neural Networks (IEEE Cat. No.04CH37541) 2: 1197–1202.

12.

Park

M-Y

Shim

Jun

Y-K

, et al. (2007) Mpirace-check: detection of message races in MPI programs. In: Advances in grid and pervasive computing: Second international conference, GPC 2007, Paris, France, 2–4 May 2007. Springer, pp. 322–333.

13.

Park

Smelyanskiy

Yang

, et al. (2015) High-performance algebraic multigrid solver optimized for multi-core based distributed parallel systems. In: Proceedings of the international conference for high performance computing, networking, storage and analysis, Austin, USA, 15–20 November 2015, pp. 1–12.

14.

Paszke

Gross

Massa

, et al. (2019) Pytorch: an imperative style, high-performance deep learning library. Proceedings of the 33rd International Conference on Neural Information Processing Systems.

15.

Rossi

Ahmed

(2015) The network data repository with interactive graph analytics and visualization. AAAI.

16.

Zhang

Tong

(2016) FINAL: fast attributed network alignment. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’16. New York, NY, USA, 13–17 August 2016. Association for Computing Machinery, pp. 1345–1354.

17.

Zhang

Zhou

, et al. (2024) Transduction enhanced inductive inference for imbalanced classification in medical images. In: 2024 IEEE International Symposium on Biomedical Imaging (ISBI). IEEE, pp. 1–5.