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.