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; 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）的核心级别互连拓扑以及多核/多门节点的当前和新兴高性能计算系统上，难以实现高效且可扩展的实现。该提案开发并评估了á包装的图形硬件软件模型，以及随之而来的数据localital-warmital-wardital-nocal-Application Application to Core/thread Mappings，以增强性能和并行的可扩展性。考虑一个申请任务图A，并通过大约嵌入两个或三个维度的工作和数据共享的测量值进行加权，以获得A安装图A的图A。为了优化绩效指标，例如拥塞和扩散，同时保持负载平衡。 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重新进行了重新调整，以增强沟通避免，软误差能力和数据预处理。结果包括通过在细，中和大元素上提取并行性，从而使弱缩放率达到大量核心，并通过保存可以显着提高固定和缩放的问题效率。互连拓扑感知的模型和地图通过潜在的就业方式进入消息传递界面，以增强稀疏通信，从而对非常大规模的HPC工作负载产生影响。此外，提议的局部感知映射和数字感知的调度可能会使在小型多核心簇上运行的建模和仿真应用程序的大量基础受益。通过在计算科学与工程跨学科课程中，通过“扩大”挑战组成部分来增强研究生培训。在夏季居民计划中，介绍了高中生进行平行计算，旨在扩大代表性不足社区的科学和工程的参与。