Abstract. With the disproportional improvements of computational and communication efficiency in computing architectures, data movement remains as the most important challenge in efficient execution. A good trade-off between load balance and data locality is necessary when scheduling computations. Directed Acyclic Graphs (DAGs) have been the de-facto abstraction to model computational tasks and their dependencies. Acyclicity provides many benefits on the ordering and mapping of vertices of the DAG (i.e., tasks) to computational resources. Thus, it is desirable to preserve acyclicity at different granularities of computation. In this talk, we show how acyclic partitioning of DAGs, i.e. partitioning in which the inter-part edges between the vertices from different parts should preserve an acyclic dependency structure among the parts, can be explored to minimize redundant data movement in two different computational models: on a single processor with two-level memory setting and on distributed memory setting. We demonstrate the usefulness of our acyclic partitioning using a high-performance distributed quantum circuit simulation application. To address the limitations of the graph model, we also develop and analyze the performance of acyclic partitioning approaches for directed hypergraphs and discuss and evaluate the scenarios where each can be preferable.
| PP22 Home 2022 | Program | Speaker Index |