SHF:Small: Accelerating Graph Analytics Through Coordinated Storage, Memory and Computing Advances

SHF:Small：通过协调存储、内存和计算进步加速图形分析

• 批准号: 1719074
• 负责人: Murali Annavaram
• 金额: $ 40万
• 依托单位: University of Southern California
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-09-15 至 2020-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1719074&HistoricalAwards=false
• 关键词: SHF; Small; Accelerating; Graph; Analytics

Graphs represent the relationship between different entities and are the representation of choice in diverse domains, such as web page ranking, social networks, drug interactions, and communicable disease spreading. Due to the sheer size of graphs in these important domains, billions of vertices with tens of billions of edges, graph processing is a data intensive task. The size of the graphs is expected to far exceed the size of the main memory available in many computer systems. As such graph analytics will be hobbled by their inability to quickly access graph vertices and edges from computer storage. Current storage systems are mostly block based and hence treat graph data as a collection of bytes organized into pages. The advent of affordable solid state drives (SSDs) allows one to envision a future where SSDs can be made semantically aware of the underlying graph storage. Rather than treating storage as a collection of blocks, semantic awareness enables SSDs to consider graph structure while deciding on how vertices and edges are laid out, and how to access the graph elements efficiently. This research advances the vision of semantic graph storage by proposing to make the SSD controller treat graph vertices and edges as first class objects. In particular, this research will design and implement a set of application programming interfaces (APIs) that allow application developers and algorithmic designers to specify graph layout and query storage systems using graph-oriented access requests, such as finding all the neighbors of a given vertex. A new runtime layer for SSDs will also be developed to exploit the semantic awareness to improve SSD endurance, garbage collection and caching. The benefits of semantic graph storage will be demonstrated by rethinking the implementation of graph signal processing algorithms to achieve an order magnitude improvement in performance. Such dramatic performance improvements in turn will enable a variety of compelling societal benefits such as accelerated drug discovery. This research also provides opportunities for a new generation of students to study, implement and optimize graph analytics on experimental SSD platforms and to study the tradeoffs between clean abstractions and the performance impact of abstractions.

图表代表了不同实体之间的关系，并且代表了不同领域中的选择，例如网页排名、社交网络、药物相互作用和传染病传播。由于这些重要领域中的图规模巨大，有数十亿个顶点和数百亿条边，因此图处理是一项数据密集型任务。图表的大小预计将远远超过许多计算机系统中可用的主存储器的大小。因此，图分析将因无法从计算机存储快速访问图顶点和边而受到阻碍。当前的存储系统主要是基于块的，因此将图数据视为组织成页面的字节集合。经济实惠的固态硬盘 (SSD) 的出现让人们可以想象这样一个未来：SSD 可以在语义上感知底层图形存储。语义感知使 SSD 能够考虑图结构，同时决定如何布置顶点和边，以及如何有效地访问图元素，而不是将存储视为块的集合。这项研究提出让 SSD 控制器将图顶点和边视为第一类对象，从而推进了语义图存储的愿景。 特别是，这项研究将设计和实现一组应用程序编程接口（API），允许应用程序开发人员和算法设计人员使用面向图的访问请求来指定图布局和查询存储系统，例如查找给定顶点的所有邻居。还将开发 SSD 的新运行时层，以利用语义感知来提高 SSD 的耐用性、垃圾收集和缓存。语义图存储的好处将通过重新思考图信号处理算法的实现来证明，以实现性能的数量级提高。如此巨大的性能改进反过来将带来各种引人注目的社会效益，例如加速药物发现。 这项研究还为新一代学生提供了在实验 SSD 平台上学习、实施和优化图形分析的机会，并研究干净抽象与抽象性能影响之间的权衡。