Constraints and Mutexflows for Scalable Block-Sparse Matrix Multiplication Using Template Task Graphs

Block-sparse matrix operations are a special case of general sparse algebra where the matrix is sparsely populated with dense blocks, e.g., in sparse tensor algebra for quantum chemistry. One of the challenges of implementing distributed matrix multiplication in general is the management of communication flows since both input matrices A and B are readily available and must be distributed to the processes computing the relevant blocks of C. In this extended article, we propose two additions to the Template Task Graph (TTG) data flow programming model that allows applications to constrain the execution of tasks and to relax the strict order of tasks that results from tasks forwarding data to successor tasks in the TTG model. We show that constraint can be used in a pure dataflow model to replace artificial control flow with a more structured approach and that mutexflows can be used to allow reordering of tasks operating on the same data, while ensuring mutual exclusion. In the context of sparse matrix multiplication, we found that the combination of constraints and mutexflows allow us to limit the number of concurrent communications and thus avoid creating a bottleneck in the network while improving communication/computation overlap through reordering of ready tasks.