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

SHF：小型：用于可扩展稀疏计算的嵌入式图软件硬件模型和映射

• 批准号: 1319448
• 负责人: Padma Raghavan
• 金额: $ 42.5万
• 依托单位: Pennsylvania State Univ University Park
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-08-01 至 2017-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1319448&HistoricalAwards=false
• 关键词: SHF; Small; Embedded; Graph; Software

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.

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