CAREER: Associative In-Memory Graph Processing Paradigm: Towards Tera-TEPS Graph Traversal In a Box

职业：关联内存图处理范式：在盒子中实现 Tera-TEPS 图遍历

基本信息

批准号：
1748988
负责人：
Jing Li
金额：
$ 50万
依托单位：
University of Wisconsin-Madison
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2018
资助国家：
美国
起止时间：
2018-02-01 至 2020-10-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1748988&HistoricalAwards=false
关键词：
CAREER Associative Memory Graph Processing

项目摘要

Large-scale graph analytics, the class of big data analytics that essentially explores the relationship among a vast collection of interconnected entities (e.g., "friends" in a social network), is becoming increasingly important due to its broad applicability, from machine learning to web search, precision medicine, and social sciences. However, the performance of graph processing systems is severely limited by the irregular data access patterns in graph computations. The existing solutions that have been developed for mainstream parallel computing are generally ineffective for massive, sparse real-world graphs due to the conventional computer architecture (i.e., von Neumann architecture) itself. In this project, new, fundamental methods will be explored in both theoretical and practical implementations to address this problem. It uniquely advances multiple fundamental cross-disciplinary areas in device, circuit, computer-aided design, and computer architecture and can be applied to address some of the most challenging "big data" problems ranging from fundamental research to everyday life. The research framework will be extended into an educational platform, providing a user-friendly framework for a laboratory-based curriculum and will serve the educational objectives for K-12 students, undergraduate and graduate students.In this research, a new computing paradigm will be developed to fundamentally address the challenge in processing large-scale graphs and to achieve ultra-high computing efficiency, orders of magnitude higher in performance per watt than state-of-art mainstream computer. To this end, a holistic co-design and optimization of algorithm, software and hardware will be developed to leverage the great potential of emerging nonvolatile memory technology. A new computing model will be proposed and theoretically proven to be more efficient in runtime/area/energy than traditional von Neumann architecture in performing graph computation. Detailed micro-architectures and circuits will be designed and evaluated to best implement the proposed computing model for concept proof.

大规模图形分析是一类大数据分析，本质上是探索大量互连实体（例如社交网络中的“朋友”）之间的关系，由于其广泛的适用性（从机器学习到网络搜索、精准医学和社会科学。然而，图处理系统的性能受到图计算中不规则数据访问模式的严重限制。由于传统计算机架构（即冯·诺依曼架构）本身的原因，为主流并行计算开发的现有解决方案对于大规模、稀疏的现实世界图通常无效。在这个项目中，将在理论和实践中探索新的、基本的方法来解决这个问题。它独特地推进了设备、电路、计算机辅助设计和计算机体系结构等多个基础跨学科领域的发展，可用于解决从基础研究到日常生活的一些最具挑战性的“大数据”问题。该研究框架将扩展到一个教育平台，为基于实验室的课程提供一个用户友好的框架，并将服务于 K-12 学生、本科生和研究生的教育目标。在这项研究中，将采用一种新的计算范式旨在从根本上解决大规模图形处理的挑战，实现超高计算效率，每瓦性能比最先进的主流计算机高出几个数量级。为此，将开发算法、软件和硬件的整体协同设计和优化，以充分利用新兴非易失性存储技术的巨大潜力。将提出一种新的计算模型，并在理论上证明在执行图计算时比传统的冯·诺依曼架构在运行时/面积/能量方面更高效。将设计和评估详细的微架构和电路，以最好地实现所提出的概念证明计算模型。