Software support for parallel processing of irregular and dynamic computations

Many real world scientific computing problems are irregular and dynamic, which pose great challenge to the effort of parallelization. In this thesis, we study the efficient mapping of a subclass of these problems, namely the "Stepwise slowly changing" irregular computations, onto distributed memory multiprocessors using the task graph scheduling approach. There exists a large class of applications which belong to this category. Intuitively, the irregularity requires sophisticated mapping algorithms, and the "slowness" in the changes of the computational structures between steps allows the scheduling cost to be amortized, justifying the approach. We study three representative and widely-used applications in this thesis:The N-body simulation in particle physics, the Vortex-Sheet Roll-Up and the Contour Dynamics Computation from Computational Fluid Dynamics. We start with an initial global compile-time scheduling using PYRROS, and as this schedule degenerates over the iterative process, we apply new rescheduling algorithms to improve performance. We develop rescheduling algorithms for two important dynamic patterns: task graph weight variation, and dynamic spawning of new subgraphs. These algorithms are implemented and tested on irregular applications such as the N-body and Vortex-Sheet. Our experiments show that global scheduling using sophisticated methods can be beneficial for these problems, and our fast rescheduling algorithms can correct run-time imbalance with very low cost. In summary, we introduce two new rescheduling heuristics and discuss several central issues such as schedule reuse, performance/scheduling overhead trade-off and the guidelines for choosing an appropriate rescheduling method. We identify classes of problems where rescheduling algorithms are applicable, and finally present experimental evidence to justify our approach. Throughout the thesis, performance results are obtained from particular problems but presented in the general framework of software supporting systems. In addition, we examine an automatic task graph generation tool that can handle restricted cases of sequential code, and carry out its integration with PYRROS system. The new system is capable of realizing automatic parallelization of simple programs, a step forward to the grand challenge of fully automatic parallelization of regular and irregular code.Technical report LCSR-TR-27