CAREER: Determining Parallel Complexity of Numerical Computation Problems via Dependency Graphs

这个项目的研究目标是通过依赖图抽象各种数值计算问题的共同性质，从而确定在并行分布式存储机器上解决这些问题的一般时间复杂性。为此，我们考虑了两个重要的问题：(1)并行数值算法的设计与分析；(2)复杂性下界的推导。在最近引入的并行计算模型LogP中，将通过考虑三个重要因素来分析并行复杂性：(I)初始数据放置，(Ii)通信调度，和(Iii)本地操作。在LogP上高效的算法可以从一台并行机移植到另一台并行机上，并且在任何并行机上都是有效的。首先，将考虑几个不同的数值计算问题，并确定每个特定问题的并行复杂性。总体结果将被用来帮助提取依赖图的重要准则，从而通过这些准则对数值计算问题进行分类。此外，还将确定每类数值计算问题的并行复杂性。所获得的结果的重要性在于能够精确地确定需要什么类型的数据放置和通信调度以实现大类数值问题的有效或最佳运行时间。显然，这项研究可能会影响目前难以解决的各个领域的广泛应用和计算问题。为了成功地完成这项研究并将其应用于这些领域，必须对并行和数值计算领域的人员进行教育和培训。为此，将开发一个并行和数值计算程序，从本科生水平的课程准备开始，最终达到博士水平的研究计划。***

The research objective of this project is to determine the time complexity of solving various numerical computation problems on parallel distributed-memory machines in general by abstracting the common properties of these problems via dependency graphs. To that effect, two important topics are considered: (1) the design and analysis of parallel numerical algorithms and (2) the derivation of lower bounds on complexity. Working within LogP, a recently-introduced model for parallel computation, parallel complexity will be analyzed by taking into account three important factors: (i) initial data placement, (ii) communication scheduling, and (iii) local operations. Algorithms which are efficient on LogP are portable from one parallel machine to another and will be efficient on any parallel machine. Initially several different numerical computation problems will be considered and the parallel complexity for each specific problem will be determined. The overall results will be used to help extract the important criteria of dependency graphs and thereby classify numerical computation problems via these criteria. Furthermore, the parallel complexity for each classification of numerical computation problems will be determined. The importance of the results obtained lies in the ability to pinpoint what types of data placements and communication schedulings are needed in order to achieve efficient or optimal running times for large classes of numerical problems. Clearly, this research potentially impacts a wide variety of applications and computational problems from various domains which are currently difficult to address. In order to successfully accomplish this research and apply it to these domains, there must be education and training of people in the parallel and numerical computing field. To that effect, a program in parallel and numerical computing will be developed beginning with course preparation at the undergraduate level and culminating in a research program at the doctoral level. ***