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.