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

点击翻译按钮获取中文摘要

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. ***