Runtime Support for Irregular Computation in MPI-Based Applications

Abstract—In recent years more and more applications have been using irregular computation models in various domains such as bioinformatics and social network analysis. Traditional data movement approaches are not well suited for such applications because of the irregular communication patterns, sparse data structures, fast growth rate of data movement as system size or problem size rises, and so forth. Active Messages (AM) is an alternative programming paradigm that is more suitable for irregular computations. It allows small pieces of data to be dynamically moved to the remote process and certain computation to be triggered, and the remote process does not need to explicitly receive the data. In this paper, an outline of the first author’s Ph.D. thesis, focusing on runtime support for irregular computation, is presented. In the first part, we combine the capability of AM with traditional MPI data movement patterns; and we propose a generalized MPI-interoperable AM framework (MPI-AM). In the second part, we extend the MPI-AM framework to provide a model of dynamic task parallelism for data-driven computation. In each part we describe critical issues, demonstrate the current status of the work and performance gain, and discuss remaining challenges to be solved. I