Mo, Zeyao; Zhang, Aiqing; Wittum, Gabriel Scalable heuristic algorithms for the parallel execution of data flow acyclic digraphs. (English) Zbl 1204.68266 SIAM J. Sci. Comput. 31, No. 5, 3626-3642 (2009). Summary: Data flow acyclic directed graphs (digraphs) can be applied to accurately describe the data dependency for a wide range of grid-based scientific computing applications ranging from numerical algebra to realistic applications of radiation or neutron transport. The parallel computing of these applications is equivalent to the parallel execution of digraphs. This paper presents a framework of scalable heuristic algorithms for the parallel execution of digraphs. This framework consists of three components: the heuristic partitioning method of a digraph, the parallel sweeping algorithm for a partitioned digraph, and the heuristic strategy for vertex scheduling and vertex packing. Evaluation rules of heuristic algorithms are presented for better theoretical understanding and performance optimization. Parallel benchmarks for the multigroup neutron or radiation \(S_n\) transport using processors from 100 to 2048 on two massively parallel machines show that these heuristic algorithms scale well. MSC: 68W10 Parallel algorithms in computer science 68R10 Graph theory (including graph drawing) in computer science 05C85 Graph algorithms (graph-theoretic aspects) Keywords:parallel algorithm; acyclic digraph; grid-based scientific computing; \(Sn\) transport Software:Ardra; Sweep3d; MPI; ParMETIS; Chaco PDFBibTeX XMLCite \textit{Z. Mo} et al., SIAM J. Sci. Comput. 31, No. 5, 3626--3642 (2009; Zbl 1204.68266) Full Text: DOI Link