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

图形表示不同实体之间的关系，并且是不同领域中的选择的表示，例如网页排名、社交网络、药物相互作用和传染病传播。由于这些重要领域中的图的庞大规模，数十亿个顶点和数百亿条边，图处理是一项数据密集型任务。图形的大小预计将远远超过许多计算机系统中可用的主存储器的大小。因此，图形分析将因无法从计算机存储中快速访问图形顶点和边而受到阻碍。当前的存储系统大多是基于块的，因此将图形数据视为组织成页面的字节集合。可负担得起的固态驱动器（SSD）的出现允许人们设想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.