CRII: OAC: Scalable Cyberinfrastructure for Big Graph and Matrix/Tensor Analytics

现有的分布式图和矩阵分析框架在设计时考虑了数据密集型工作负载，使得它们对于计算密集型应用（如图挖掘和科学计算）效率低下。该项目的目标是分别为两个计算密集型任务（图挖掘和矩阵/张量计算）开发新的大数据框架。这两个框架通过激励未来的计算密集型分析系统，并促进其在各个科学领域的应用，以提高研究生产力，从而推动大数据分析领域的发展。这两个系统将可供公众使用，并可以服务于计算机取证，计算物理和生物信息学的几个跨学科项目。该项目包括通过暑期实习指导研究生和培训K-12学生，以及相关的新课程材料和外联活动，以帮助公众学习大数据技术。因此，该项目符合美国国家科学基金会的使命，以促进科学的进步和促进国家的健康和繁荣。图挖掘系统和矩阵/张量平台共享的设计（i）一个定制的存储子系统，提供高效和灵活的数据访问，和（ii）一个计算子系统，具有细粒度的任务控制，数据重用意识的任务分配和负载平衡。图挖掘系统，称为G-thinker，旨在促进分布式程序的编写，从一个大图中挖掘满足某些要求的子图。这样的挖掘问题在社区检测和子图匹配等许多应用中是有用的。这些问题通常具有很高的计算复杂度，现有的串行算法通过在无重复的顶点集计数树中回溯来解决这些问题，该计数树递归地划分搜索空间。G-thinker采用直观的编程界面，最大限度地减少了将现有串行子图挖掘算法用于分布式执行的工作。要挖掘的子图是从各个顶点产生的，它们根据需要增长边界，并且在需要时通过将子图溢出到磁盘来避免内存溢出。在每台机器中，由多个子图共享的顶点和边只需要传输和缓存一次，这最大限度地减少了通信（以及数据等待），从而更好地利用CPU内核。为了解决幂律图的负载平衡问题，G-thinker探索了递归分解和工作窃取，允许空闲机器从负载沉重的机器中窃取子图进行挖掘。该项目还探索了分布式矩阵/张量存储和计算框架，其中矩阵/张量分区使用不同的存储方案存储在多个副本中，以有效地支持各种子矩阵访问操作。这种灵活的存储方案为上层计算提供了更多的细粒度优化机会，包括更智能的任务调度和原位更新。这个框架的使用是由矩阵乘法和LU分解的例子。这两个拟议的框架都有助于建立一个网络基础设施，以便与科学、医学和工业领域的科学家进行合作。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

The existing distributed graph and matrix analytics frameworks are designed with data-intensive workloads in mind, rendering them inefficient for compute-intensive applications such as graph mining and scientific computing. The goal of this project is to develop novel big data frameworks for two compute-intensive tasks, graph mining and matrix/tensor computations, respectively. The two frameworks advance the field of big data analytics by motivating future systems for compute-intensive analytics, and promoting their application in various scientific areas to improve research productivity. The two systems will be available for public use, and can serve several cross-disciplinary projects in computer forensics, computational physics, and bioinformatics. The project includes mentoring graduate students and training K-12 students through summer internships, as well as related new course materials and outreach activities to help the public learn big data technologies. Thus, the project aligns with the NSF's mission to promote the progress of science and to advance the national health and prosperity.The graph mining system and the matrix/tensor platform share the design of (i) a tailor-made storage subsystem providing efficient and flexible data access, and (ii) a computation subsystem with fine-grained task control for data-reuse-aware task assignment and load balancing. The graph mining system, called G-thinker, aims to facilitate the writing of distributed programs which mine from a big graph those subgraphs that satisfy certain requirements. Such mining problems are useful in many applications like community detection and subgraph matching. These problems usually have a high computational complexity, and existing serial algorithms tackle these problems by backtracking in a duplication-free vertex-set numeration tree, which recursively partitions the search space. G-thinker adopts an intuitive programming interface that minimizes the effort of adapting an existing serial subgraph mining algorithm for distributed execution. The subgraphs to mine are spawned from individual vertices and they grow their frontiers as needed, and memory overflow is avoided by spilling subgraphs to disks when needed. In each machine, vertices and edges shared by multiple subgraphs need only be transmitted and cached once, which minimizes communication (and hence data waiting) so that CPU cores are better utilized. To address the load-balancing problem of power-law graphs, G-thinker explores recursive decomposition and work stealing to allow idle machines to steal subgraphs for mining from heavily-loaded machines. The project also explores a distributed matrix/tensor storage and computing framework, where matrix/tensor partitions are stored in multiple replicas using different storage schemes to efficiently support all kinds of submatrix access operations. This flexible storage scheme offers the upper-layer computations much more opportunities for fine-grained optimizations, including smarter task scheduling and in-situ updates. The use of this framework is exemplified by matrix multiplication and LU factorization. Both of the proposed frameworks can help build a cyberinfrastructure for collaborations with scientists in science, medicine, and industry.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.