CAREER: Algorithm-Centric High Performance Graph Processing

职业：以算法为中心的高性能图形处理

• 批准号: 1750656
• 负责人: Xuehai Qian
• 金额: $ 45万
• 依托单位: University of Southern California
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-02-01 至 2023-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1750656&HistoricalAwards=false
• 关键词: CAREER; Algorithm; Centric; Performance; Graph

With the advent of big data, large amounts of data are collected from numerous sources, such as social media, sensor feeds, and scientific experiments. Graph analytics has emerged as an important way to understand the relationships between heterogeneous types of data, allowing data analysts to draw valuable insights from patterns in the data for a wide range of applications, including machine learning tasks, natural language processing, anomaly detection, clustering, recommendation, social influence analysis, bioinformatics. Due to the broad applications, the research community tackled graph processing from multiple angles, including distributed, disk-based systems and in-memory graph processing. There are four key problems of today's graph processing research: 1) the gap between programming model and algorithm; 2) the lack of diversity in applications studied; 3) insufficient research on dynamic graphs and graph database; and 4) architectural supports focus only on classical problems. This proposal attempts to advance the graph processing systems by solving these major challenges.This research proposes a novel approach ALCHEM, algorithm-centric high performance graph processing, which involves the collaborative designs of algorithms, programming model, systems, and architecture. This interdisciplinary research program takes the opportunity to explore or enhance the interactions between different layers, with the emphasis on algorithm efficiency. It contains four research thrusts: (1) Using graph abstraction as a bridge between programming model and algorithm to speed up the convergence; (2) Developing efficient execution model with specialization; (3) Building a graph database as a unified engine for relational and dynamic graph data; (4) Enhancing architecture with novel features to support new graph algorithms (e.g., random walk). The research will trigger close interactions between researchers in theory, system, and architecture. The project will engage women, minorities and undergraduates. Uniquely, it will not only train the students' system building skills, but also strengthen their algorithm understanding. The research outcomes will benefit the society by improving everyday life with better and faster recommendations, enhanced security, and better social relationships.

随着大数据的出现，大量数据是从社交媒体，传感器提要和科学实验等众多来源收集的。 Graph Analytics已成为理解异质类型数据之间关系的一种重要方法，从而使数据分析师能够从数据中的模式中获取多种应用程序的有价值的见解，包括机器学习任务，自然语言处理，自然语言处理，异常检测，聚类，聚类，建议，社交影响分析，生物影响学。由于广泛的应用，研究社区从多个角度（包括分布式，基于磁盘的系统和内存图形处理）处理了图形处理。当今的图形处理研究有四个关键问题：1）编程模型和算法之间的差距； 2）所研究的应用中缺乏多样性； 3）对动态图和图形数据库的研究不足； 4）建筑支持仅关注经典问题。该建议试图通过解决这些主要挑战来推进图形处理系统。这项研究提出了一种新颖的方法炼金术，以算法为中心的高性能图形处理，其中涉及算法，编程模型，系统和体系结构的协作设计。该跨学科研究计划借此机会探索或增强了不同层之间的相互作用，重点是算法效率。它包含四个研究推力：（1）使用图形抽象作为编程模型和算法之间的桥梁，以加快收敛性； （2）开发具有专业化的有效执行模型； （3）将图形数据库构建为统一的引擎，用于关系和动态图数据； （4）增强具有新功能的建筑，以支持新的图形算法（例如随机步行）。该研究将触发理论，系统和建筑中研究人员之间的紧密相互作用。该项目将吸引妇女，少数民族和本科生。独特的是，它不仅会训练学生的系统建筑技能，还可以增强其算法的理解。研究成果将通过更好，更快的建议，增强的安全性和更好的社会关系来改善日常生活，从而使社会受益。