Space-time Parallelization of Numerical Methods for Partial Differential Equations

高性能科学计算领域正处于计算机体系结构变化带来的颠覆性范式转变之中。增加计算吞吐量现在主要是通过增加并发性来实现的，每个处理器的核心数量呈指数级增长，并计划为第一个百万亿级系统提供大量核心。此外，对系统功率的限制、增加的存储器层次结构和基本的物理障碍将使存储器访问和通信比浮点操作相对更昂贵。这些变化需要重新考虑几乎每一种类型的数值算法的新兴架构所需的新的效率指标。受日益增加的并发性的挑战，本研究围绕新算法的分析，实现和应用，使偏微分方程的数值方法在空间和时间上的并行化。他的方法建立在并行全近似方案的空间和时间（PFASST）算法最近开发的PI。PFASST结合了迭代时间积分方案和空间和时间离散化的层次结构，允许同时完成PDE的多个时间步长的工作。PI对PFASST算法的初步研究表明，在一系列不同类型的代表性模型PDE上，时间并行效率超过50%，然而，时空并行性在很大程度上尚未被探索，当然也没有在更广泛的社区中被广泛采用。该项目概述了一个必要的研究计划，将时空并行的使用从概念阶段的证明转移到在计算科学的大规模应用中提高计算速度的有效方法。在研究中解决的具体主要问题包括数学分析的PFASST收敛在各种离散化制度，负载平衡和优化的权衡空间和时间的并行化，适应PFASST非结构化网格和基于粒子的模拟，并使用多个物理模型内的离散化层次结构。该研究有可能增加几乎所有时间相关数值方法的计算并发性。因此，该研究项目可能会影响计算化学，生物学，物理学，工程学和计算机科学等广泛的领域。在教育和外联领域，方案倡议包括在研究生和本科生一级开展的活动，其中一个组成部分是针对高中教师和学生的。

The field of high-performance scientific computing is in the midst of a disruptive paradigm shift brought about by changes in computer architecture. Increased computational through-put is now achieved mainly by increasing concurrency with the number of cores per processor increasing exponentially and plans for the first exascale system suggesting massive cores. In addition, limitations to system power, increased memory hierarchy, and fundamental physical barriers will make memory access and communication relatively more expensive than floating point operations. These changes are necessitating the reconsideration of numerical algorithms of nearly every type in terms of the new efficiency metrics emerging architectures require. Motivated by the challenge of increasing concurrency, this research centers around the analysis, implementation, and application of new algorithms to enable parallelization of numerical methods for partial differential equations in both space and time. His approach builds on the parallel full approximation scheme in space and time (PFASST) algorithm recently developed by the PIs. PFASST combines iterative temporal integration schemes and a hierarchy of spatial and temporal discretizations to allow work on multiple time steps of a PDE to be done concurrently. Preliminary studies of the PFASST algorithm by the PIs have demonstrated temporal parallel efficiencies in excess of fifty percent on a range of representative model PDEs of differing type, however, space-time parallelism to this point is largely unexplored and certainly not widely adopted in the broader community. This project outlines a program of research necessary to move the use of space-time parallelism from the proof of concept stage to an effective way of increasing computational speed in large scale applications across computational science. Specific major issues addressed in the research include mathematical analysis of the convergence of PFASST in various discretization regimes, load-balancing and optimization of the trade-off between space and time parallelization, adapting PFASST to unstructured grids and particle based simulations, and the use of multiple physical models within the discretization hierarchies. The research has the potential to increase the available computational concurrency in virtually all time-dependent numerical methods. Hence this research project could impact a broad spectrum of fields such as computational chemistry, biology, physics, engineering, and computer science. In the area of education and outreach, the PI includes activities at the graduate and undergraduate level, with a component designed to reach high-school teachers and students.