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

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

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.