Network-Theoretic Classification of Parallel Computation Patterns


S. Whalen, S. Peisert, and M. Bishop, “Network-Theoretic Classification of Parallel Computation Patterns,” Proceedings of the First International Workshop on Characterizing Applications for Heterogeneous Exascale Systems pp. 159–169 (June 2011).



Parallel computation in a high performance computing environment can be characterized by the distributed memory access patterns of the underlying algorithm. During execution, networks of compute nodes exchange messages that indirectly exhibit these access patterns. Thus, identifying the algorithm underlying these observable messages is the problem of latent class analysis over information flows in a computational network. Towards this end, our work applies methods from graph and network theory to classify parallel computations solely from network communication patterns. We also introduce an approximate pattern matching algorithm using statistical hypothesis testing and compare these approaches using massive datasets collected at Lawrence Berkeley National Laboratory.

Bibliographic Information: [BibTeX] [EndNote] [RIS]
DOI: 10.1177/1094342012436618