Research On Scalable Parallel Data Driven Algorithms And Applications

For the scientific computation, the computational domain is usually discretized into grids, and the differential equations are discretized on the grids. According to the data dependency of neighboring grid cells, the computational methods are classified into two types: one is undirectional and the other is directional. For the former type, the computation on a grid cell can be executed using "old" data from the neighbor cells, however, for the the latter type, the computation on a grid cell depends on the new results of neighbor cells, i.e., the computation on a cell will not be executed until all its dependent neighbor cells are executed.For the undirectional methods, the computational domain can be decomposed into subdomains and distributed to different processors, and parallel algorithms can be designed in a natural way as described by the well-known BSP model. But such idea is not suitable for the computational methods with directional data dependency. In fact, for the directional methods, parallel computational models and fine-granularity parallel algorithms should be firstly considered. Lower communication latency is required for the high performance of such parallel algorithms. It is fortunately that the fast development of modern high performance computer can provide such lower communication latency.Oriented to the parallel computing of the well-known discrete-ordinate methods for particle transport equations and other directional methods, this dissertation mainly focuses on the parallel computing models, parallel algorithms, parallel performance optimization and realistic applications for the directional data dependency problems. The main contributions of this dissertation are summarized as follows:①Firstly, as an analysis result of directional data dependency in typically scientific applications, a data driven parallel computing model is presented to depict directional data dependency based on digraphs. Then, the parallel computing of numerical methods are transformed into the parallel computing of models.②Based on the data driven parallel computing models, a data-driven parallel algorithms framework is proposed. It consists of three components: the partitioning methods of digraph, the parallel sweeping algorithms for the parallel execution of a partitioned digraph, and the priority strategies for vertices scheduling towards larger parallelism.③Based on above framework, we realize the data-driven parallel computing for a 2D radiation transport application denoted by LARED-R-1. The parallel computing shows scalable parallel performance on hundreds of processors.④Based on above framework, a new universal vertices priority strategy is presented. This strategy can obviously improve the parallel efficency. The theoretical deductions and realistic applications on hundreds of processors verify its efficiency.⑤Three-hierarchy software architecture for the data-driven parallel algorithms framework is proposed and realized in JASMIN infrastructure. This architecture releases application researchers from the complicated data-driven parallel algorithms and their programming. Typical performance benchmarks on 2048 processors show that the realization is very effective.