XPS: FULL: Collaborative Research: PARAGRAPH: Parallel, Scalable Graph Analytics

许多现实世界的问题可以有效地建模为复杂的关系网络或图，其中节点表示感兴趣的实体，边缘模拟它们之间的交互或关系。这类问题的数量和产生这些问题的领域的多样性正在增加。然而，开发高性能应用程序来从这些数据集中提取有用的信息是非常具有挑战性的。图形处理单元对于此类应用程序非常有吸引力，因为它们比标准的多核处理器提供更高的计算性能和能源效率。然而，目前为它们开发高性能应用程序比为标准多核处理器开发并行程序更具挑战性。使用图形处理单元的有效应用程序开发通常要求开发人员对其体系结构特征具有相当的专业知识，并使用专门的编程模型和性能优化技术。因此，同时为这些设备的数据分析应用程序实现高性能和高用户生产力是一项艰巨的挑战。该项目提出了一个可扩展的高级软件框架，以实现图形处理单元的高性能应用程序的生产性开发。它具有两个不同的抽象，以解决开发图/数据分析应用程序中的性能和生产力挑战：1)以边界为中心的抽象，基于许多这些应用程序的共同迭代特征，具有动态移动的活动顶点（或边）边界，计算为中心；2)基于稀疏线性代数原语的抽象，利用稀疏矩阵和图之间的对偶关系。将使用这两种抽象开发和评估图形分析应用程序的基准套件，从而能够深入了解这些替代的高级抽象对一系列分析应用程序的有效性。基准套件和软件框架将会公开发布。

Many real world problems can be effectively modeled as complex relationship networks or graphs where nodes represent entities of interest and edges mimic the interactions or relationships among them. The number of such problems and the diversity of domains from which they arise is growing. However developing high-performance applications to extract useful information from such datasets is very challenging. Graphical processing units are very attractive for such applications because they offer higher computational performance and energy efficiency than standard multi-core processors. However, the development of high-performance applications for them is currently much more challenging than parallel program development for standard multi-core processors. Effective application development to use graphical processing units generally requires that developers possess considerable expertise on their architectural characteristics and use specialized programming models and performance optimization techniques. Thus, simultaneously achieving high performance and high user productivity for data analytics applications for such devices is a daunting challenge.This project proposes a scalable high-level software framework to enable the productive development of high-performance applications for graphical processing units. It features two distinct abstractions to address the performance and productivity challenges in developing graph/data analytics applications: 1) a frontier-centric abstraction that is based on a common iterative characteristic of many of these applications, with a dynamically moving active frontier of vertices (or edges) where computation is centered, and 2) an abstraction based on sparse linear algebra primitives, exploiting the dual relationship between sparse matrices and graphs. A benchmark suite of graph analytics applications will be developed and evaluated using both abstractions, enabling insights into the effectiveness of these alternate high-level abstractions for a range of analytics applications. The benchmark suite and the software framework will be publicly released.