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.

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

项目成果

An Alternative Analytical Approach to Associative Processing

关联处理的另一种分析方法

• DOI: 10.1109/lca.2018.2789424
• 发表时间: 2018
• 期刊: IEEE Computer Architecture Letters
• 影响因子: 2.3
• 作者: Khoram, Soroosh;Zha, Yue;Li, Jing
• 通讯作者: Li, Jing