SHF: Small: Embedded Graph Software-Hardware Models and Maps for Scalable Sparse Computations

大量的“大数据”和“大模拟”应用，如确定网络模型或模拟偏微分方程模型，涉及的是稀疏的高维数据。稀疏数据结构和算法在存储和计算成本方面具有显著的优势。然而，由于每个数据元素只有很少的操作，在当前和新兴的高性能计算系统上很难实现高效和可扩展的实现，这些系统具有非常高的核心级并行性，复杂的节点互连拓扑和具有非统一内存架构（NUMA）的多核/多核节点。本提案开发和评估á-embedded图形硬件软件模型和相应的数据位置保持和numa感知应用到核心/线程映射，以提高性能和并行可扩展性。考虑一个应用程序任务图A，对工作和数据共享的度量进行加权，该度量近似嵌入到二维或三维中，以获得á-embedded图A。考虑一个HPC系统的加权图，该图被自然分配坐标以获得á-embedded主机图模型H。该建议开发并行算法来计算a到H的互连拓扑感知映射，以便在保持负载平衡的同时优化诸如拥塞和扩张之类的性能度量。此外，在H中的多核节点上，分配了a的子图，(i)稀疏数据重新排序以增强并行性和局部性，（ii）应用动态细粒度numa感知任务调度，通过工作窃取来响应资源冲突，节流等核心性能变化。最后，通过á-embedded图模型获得的见解，重新制定稀疏矩阵算法，以增强通信避免，软错误恢复和数据预处理。结果包括通过提取细颗粒、中颗粒和大颗粒的并行性，实现对大量核的弱缩放，并通过局部保存显着提高固定和缩放问题的效率。互连拓扑感知模型和映射通过潜在地集成到消息传递接口中以增强稀疏通信，具有对超大规模HPC工作负载产生影响的潜力。此外，建议的位置感知映射和numa感知调度可以潜在地使运行在小型多核集群上的大量建模和仿真应用程序受益。在计算科学与工程的跨学科课程中，研究生的训练通过“放大”挑战部分得到加强。高中学生通过暑期住宿项目了解并行计算，旨在扩大未被充分代表的社区对科学和工程的参与。

A large number of "big data" and "big simulation" applications, such as those for determining network models or simulations of partial differential equation models, concern high dimensional data that are sparse. Sparse data structures and algorithms present significant advantages in terms of storage and computational costs. However, with only a few operations per data element, efficient and scalable implementations are difficult to achieve on current and emerging high performance computing systems with very high degrees of core level parallelism, complex node interconnect topology and multicore/manycore nodes with non-uniform memory architectures (NUMA). This proposal develops and evaluates á-embedded graph hardware-software models and attendant data locality-preserving and NUMA-aware application to core/thread mappings to enhance performance and parallel scalability. Consider an application task graph A, weighted with measures of work and data sharing that is approximately embedded in two or three dimensions, to obtain an á-embedded graph A. Additionally, consider a weighted graph of a HPC system that is naturally assigned coordinates to obtain an á-embedded host graph model H. This proposal develops parallel algorithms to compute interconnect topology-aware mappings of A to H in order to optimize performance measures such as congestion and dilation while preserving load balance. Additionally, at a multicore node in H that is assigned a subgraph of A, (i) sparse data are reordered to enhance parallelism and locality, and (ii) a dynamic fine-grain NUMA-aware task scheduling is applied to respond through work-stealing to core variations in performance from resource conflicts, throttling etc. Finally, through insights gained from á-embedded graph models, sparse matrix algorithms are reformulated to enhance communication avoidance, soft error resilience and data preconditioning. Outcomes include enabling weak scaling to a very large number of cores by extracting parallelism at fine, medium and large-grains, and significantly enhanced fixed and scaled problem efficiencies through locality preservation. The interconnect topology-aware models and maps hold the potential for impact on very large scale HPC workloads through potential incorporation into the Message Passing Interface for enhanced sparse communications. Additionally, the proposed locality-aware mappings and NUMA-aware scheduling can potentially benefit the very large base of modeling and simulation applications that run on small multicore clusters. Graduate student training is enhanced through a "scale-up" challenge component in an interdisciplinary course on computational science and engineering. High school students are introduced to parallel computing through summer in-residence programs seeking to broaden participation in science and engineering from underrepresented communities.