Event-based parareal: A data-flow based implementation of parareal
Event-based parareal: A data-flow based implementation of parareal
复制标题
基于事件的 parareal：基于数据流的 parareal 实现
DOI：
10.1016/j.jcp.2012.05.016
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
D. Newman
中科院分区：
文献类型：
--
作者：
L. Berry;W. Elwasif;J. Reynolds;D. Samaddar;R. Sánchez;D. Newman
Parareal是一种迭代算法，实际上，它实现了微分或偏微分方程的时间依赖系统的时间分解。在较短的挂钟时间内获得解决方案，但以增加计算周期为代价。该算法结合了一个精细的求解器，解决了系统的可接受的精度与一个近似的粗求解器。在任何系统上成功实现parareal的关键任务是开发一个粗略的求解器，与完整时间间隔中的时间片数量相比，该求解器可以在少量迭代中收敛，同时比精细求解器快得多。非常快的粗解算器可能不会导致足够快的收敛，并且缓慢的粗解算器可能不会导致显著的增益，即使收敛的迭代次数是令人满意的。我们发现，通过使用数据驱动的、基于事件的parareal实现，可以大大缓解满足这些相互冲突的需求的困难。因此，一次迭代的任务不会等待前一次迭代完成，而是在所需数据可用时启动。对于给定的收敛属性，基于事件的方法通过因子K/K来放松对粗略求解器的速度要求，其中K是收敛解所需的迭代次数。对于许多问题，这可能导致高效的并行实现，否则这是不可能的，或者需要大量的粗略求解器开发。此外，用于该实现的框架在满足数据依赖性并且计算资源可用时执行任务。这导致与将任务组流水线化或调度到特定处理器或处理器组的先前方法相比提高的计算效率。
Parareal is an iterative algorithm that, in effect, achieves temporal decomposition for a time-dependent system of differential or partial differential equations. A solution is obtained in a shorter wall-clock time, but at the expense of increased compute cycles. The algorithm combines a fine solver that solves the system to acceptable accuracy with an approximate coarse solver. The critical task for the successful implementation of parareal on any system is the development of a coarse solver that leads to convergence in a small number of iterations compared to the number of time slices in the full time interval, and is, at the same time, much faster than the fine solver. Very fast coarse solvers may not lead to sufficiently rapid convergence, and slow coarse solvers may not lead to significant gains even if the number of iterations to convergence is satisfactory. We find that the difficulty of meeting these conflicting demands can be substantially eased by using a data-driven, event-based implementation of parareal. As a result, tasks for one iteration do not wait for the previous iteration to complete, but are started when the needed data are available. For given convergence properties, the event-based approach relaxes the speed requirements on the coarse solver by a factor of ∼K, where K is the number of iterations required for a converged solution. This may, for many problems, lead to an efficient parareal implementation that would otherwise not be possible or would require substantial coarse solver development. In addition, the framework used for this implementation executes a task when the data dependencies are satisfied and computational resources are available. This leads to improved computational efficiency over previous approaches that pipeline or schedule groups of tasks to a particular processor or group of processors.