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

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

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.