SHF: Medium: Collaborative Research: ANACIN-X: Analysis and modeling of Nondeterminism and Associated Costs in eXtreme scale applications

不确定性(即，科学应用程序在多次执行期间在数值结果和执行模式中表现出不同行为的特性)是高性能计算(HPC)应用程序日益根深蒂固的特性，因为科学界正在将它们的模拟转移到更大且高度异质的计算系统上。就开发人员的时间和计算资源而言，不确定性可能会极大地增加科学可重复性的成本，在从较小规模移动到较大规模或从一个平台移动到另一个平台时调试应用程序，并在执行可能需要从系统故障中恢复时确保容错。通过计算机模拟，这三个挑战最终可能会影响科学发现的数量和质量。用于解决不确定性问题的各方面的工具已经出现，包括记录和重放(R&amp；R)技术，其监视和记录在应用程序的一次执行(即，所记录的执行)上的程序状态的改变；并且再现这些改变，从而再现在随后的执行(即，重放的执行)期间的应用程序的行为。然而，这些工具对底层应用程序施加了开销，因此给HPC用户带来了平衡工具效用和工具开销的问题。HPC用户可能会选择根本不使用该工具，而不是处理不可预测的管理费用。该项目通过对应用程序的不确定性和工具开销的可变性之间的关系建模来支持HPC用户，并使用该知识来识别工具成本方面的热点以及在执行中触发应用程序中的不确定性行为的区域。该项目的目的是通过确定高性能计算应用程序执行中的不确定点(Motif)来建模不确定性执行，并应用R&amp；R技术的Motif建模，研究某些Motif的R&A；R技术的成本。该项目的成果影响到四个社区：应用程序开发人员，其识别意外不确定性的来源及其管理；致力于艾级级容错、弹性和再现性的HPC研究社区；为应用程序开发人员使用评估工具的数据中心管理员；以及在资源受限的环境中推广HPC的教育和培训人员，而无需访问高端、昂贵的计算机。该项目通过研究记录和重放(R&AMP；R)工具的记录成本并通过定义策略以使这些工具可以扩展到艾级域来推动对非确定性HPC应用程序的研究。除了更常研究的时间和内存开销因素外，该项目还在建模中集成了电力使用。该项目依赖图论来开发程序中事件之间的依赖关系的可表达和可伸缩的基于图的表示，并开发算法来识别图中指示不确定性点的主题。这些主题被用来量化不确定性的相关成本，包括开发衡量不同执行之间差异的度量标准，对记录执行的成本进行建模，以及评估记录的开销。基于这些主题，这个项目的工作产生了？指纹？(2)图形分析(例如，Graph500基准)；(3)生物信息学(例如，mpiBLAST)；以及(4)基于任务的数据分析应用(例如，字数、连接、基于MPI框架的MapReduceOver上的八叉树集群)。这些指纹揭示了以前被忽视的跨多个应用程序类别的不确定性之间的相似之处，并允许用户探索进程通信模式、实际结果执行的主题以及这些执行中工具开销累积的区域之间的关系。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Nondeterminism (i.e., the properties of a scientific application to exhibit different behaviors in numerical results and execution patterns during multiple executions) is an increasingly entrenched property of high performance computing (HPC) applications as the scientific community is moving their simulations on larger and highly heterogeneous computing systems. Nondeterminism can drastically increase the cost of scientific reproducibility in terms of developer time and computational resources, debugging applications when moving from a smaller to a larger scale or from one platform to another, and ensuring fault-tolerance when executions may need to recover from a system fault. These three challenges can ultimately compromise the amount and quality of scientific discovery through computer simulations. Tools for addressing aspects of the nondeterministic problem have emerged, including Record-and-replay (R&R) techniques that monitor and record changes in program states over one execution (i.e., the recorded execution) of an application; and reproduce those changes, and thus, the behavior of the application during a subsequent execution (i.e., the replayed execution). However, these tools impose overheads on the underlying application and thus present HPC users with the problem of balancing tool utility against tool overhead. HPC users may opt to not use the tool at all rather than deal with unpredictable overheads. This project supports HPC users by modeling the relationship between application nondeterminism and variability in tool overhead, and uses this knowledge to identify hot spots in terms of tool cost as well as regions in executions that trigger nondeterministic behaviors in the applications. The aim of the project is to model nondeterministic executions by determining points (motif) of nondeterminism in executions of HPC applications and to apply the motif modeling with R&R techniques, to study the cost on R&R techniques of certain motifs. The outcome of this project impacts four communities of application developers with the identification of sources of unintended nondeterminism and their management; the HPC research community working on fault-tolerance, resilience, and reproducibility at exascale; data center administrators who use evaluation tools for and with application developers; and educators and trainers in resource constrained environments to promote HPC without the need of accessing high-end, expensive computers.This project advances the study of nondeterministic HPC applications by studying the recording costs of Record-and-replay (R&R) tools and by defining strategy so that these tools can scale to the exascale domain. In addition to the more commonly studied factors of time and memory overhead, the project integrates power usage in the modeling. The project relies on graph theory to develop expressive and scalable graph-based representations of the dependencies between events in a program, and develops algorithms to identify motifs in the graph that indicate points of nondeterminism. These motifs are applied to quantify the associated costs of nondeterminism, including developing metrics to measure dissimilarities between different executions, modeling the costs of recording executions and assessing the overhead of recordings. Based on these motifs, work on this project generates ?fingerprints? (i.e., a holistic characterization of how and where nondeterminism manifests during the application executions) of real world HPC applications including N-Body problems (e.g., simulating particle, atomic, and planetary interactions); (2) Graph analytics (e.g., Graph500 benchmark); (3) Bioinformatics (e.g., mpiBLAST); and (4) Task-based data analysis application (e.g., WordCount, Join, Octree Clustering on top of MapReduce Over MPI frameworks). The fingerprints illuminate previously-overlooked similarities between the nondeterminism that manifests across multiple classes of applications and allow users to probe the relationship between process communication patterns, the motifs of the actual resulting executions, and the regions of those executions in which tool overhead accumulates for nondeterministic HPC applications.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.