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。此外，考虑自然分配坐标以获得α嵌入的主机图模型H的HPC系统的加权图。该建议开发并行算法来计算互连拓扑感知A到H的映射，以便在保持负载平衡的同时优化诸如拥塞和扩张的性能度量。此外，在被分配了A的子图的H中的多核节点，(I)稀疏数据被重新排序以增强并行性和局部性，以及(Ii)动态细粒度NUMA感知任务调度被应用以通过窃取工作来响应资源冲突、节流等导致的核心性能变化。最后，通过从嵌入图模型中获得的见解，重新制定稀疏矩阵算法以增强通信避免、软错误恢复和数据预处理。结果包括通过在细、中和大颗粒上提取并行性，使弱伸缩能够扩展到非常大量的核心，并通过位置保留显著提高固定和规模化问题的效率。互连拓扑感知模型和映射通过潜在地整合到消息传递接口以增强稀疏通信，可能会对超大规模HPC工作负载产生影响。此外，建议的位置感知映射和NUMA感知调度可能会使运行在小型多核集群上的非常大的建模和模拟应用程序基础受益。研究生培训通过计算科学和工程跨学科课程中的“扩大规模”挑战部分得到加强。高中生通过暑期入驻项目向他们介绍并行计算，这些项目旨在扩大代表不足的社区对科学和工程的参与。