Quantitative performance modeling of scientific computations and creating locality in numerical algorithms
Quantitative performance modeling of scientific computations and creating locality in numerical algorithms
复制标题
科学计算的定量性能建模和在数值算法中创建局部性
DOI：
--
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
Sivan Toledo
中科院分区：
文献类型：
--
作者：
Sivan Toledo
如何在不实际运行程序的情况下确定其运行时间？如何设计一种高效的核外迭代算法？这是本文要回答的两个问题。
本文的第一部分表明，使用一种称为基准映射（benchmapping）的方法可以准确、自动且快速地预测程序的性能。基准映射的关键方面包括：自动创建详细的性能模型，使用这些模型预测运行时系统调用的性能，以及将一个数据并行程序自动分解为一系列运行时系统调用。通过两个称为PscERFS scIM和B scENCHC scVL的性能预测系统确立了基准映射的可行性和实用性。实证研究表明，PscERFS scIM的相对预测误差在21%以内，B scENCHC scVL的相对预测误差几乎总是在33%以内。
本文的第二部分介绍了在数值算法中创建局部性的方法。计算机、编译器和运行时系统的设计者努力创建能够利用某些程序中引用的时间局部性的设计。不幸的是，许多迭代数值算法缺乏时间局部性。在当前高性能计算机上执行此类算法的特点是某些通信通道（如总线或I/O通道）饱和，而CPU大部分时间处于空闲状态。
本文表明，一种创建局部性的新方法，即阻塞覆盖方法（blocking covers method），可以提高包括多重网格、共轭梯度和隐式时间步长在内的迭代算法的性能。本文证明该方法减少了这些算法中的输入 - 输出操作量，并表明该方法可将工作站上的求解时间最多缩短5倍。
本文还描述了一种基于局部致密化（local densification）方法的并行线性方程求解器。该方法增加了单个处理器可处理的依赖关系数量，但没有增加产生处理器间通信的依赖关系数量。所得算法的一种实现比传统算法快达2.5倍。（副本仅可从麻省理工学院图书馆获取，地址：马萨诸塞州剑桥市14 - 0551室，邮编02139 - 4307。电话：617 - 253 - 5668；传真：617 - 253 - 1690。）
How do you determine the running time of a program without actually running it? How do you design an efficient out-of-core iterative algorithm? These are the two questions answered in this thesis.
The first part of the thesis demonstrates that the performance of programs can be predicted accurately, automatically, and rapidly using a method called benchmapping. The key aspects benchmapping are: automatic creation of detailed performance models, prediction of the performance of runtime system calls using these models, and automatic decomposition of a data-parallel program into a sequence of runtime system calls. The feasibility and utility of benchmapping are established using two performance-prediction systems called P scERFS scIM and B scENCHC scVL. Empirical studies show that P scERFS scIM's relative prediction errors are within 21% and that B scENCHC scVL's relative prediction errors are almost always within 33%.
The second part of the thesis presents methods for creating locality in numerical algorithms. Designers of computers, compilers, and runtime systems strive to create designs that exploit the temporal locality of reference found in some programs. Unfortunately, many iterative numerical algorithms lack temporal locality. Executions of such algorithms on current high-performance computers are characterized by saturation of some communication channel (such as a bus or an I/O channel) whereas the CPU is idle most of the time.
The thesis demonstrates that a new method for creating locality, called the blocking covers method, can improve the performance of iterative algorithms including multigrid, conjugate gradient, and implicit time stepping. The thesis proves that the method reduces the amount of input-output operations in these algorithms and demonstrates that the method reduces the solution time on workstations by up to a factor of 5.
The thesis also describes a parallel linear equation solver which is based on a method called local densification. The method increases the amount of dependencies that can be handled by individual processors but not the amount of dependencies that generate interprocessor communication. An implementation of the resulting algorithm is up to 2.5 times faster than conventional algorithms. (Copies available exclusively from MIT Libraries, Rm. 14-0551, Cambridge, MA 02139-4307. Ph. 617-253-5668; Fax 617-253-1690.)
系统性能建模
DOI：
--
发表时间：
2021
期刊：
影响因子：
--
作者：
三坂孝志 ; 久保世志 ; 淺海典男 ; 出田武臣 ; 大林茂;Y. Tamura and S. Yamada
通讯作者：
Y. Tamura and S. Yamada