SHF: Small: Transformations for Synergistic Analysis of Large Evolving Graphs

图形处理的重要性随着图形分析的普及而增长。真实世界图的一个重要特征是它们不断地演变（例如，社交网络、模拟疾病传播的网络等）。对演进图的图分析需要对在不同时间点拍摄的图的快照进行重复分析，以观察感兴趣的特征如何随时间变化。对于具有数百亿条边的大型真实世界图，进化图分析是高度计算密集型和内存密集型的。通过开发重新组织计算和数据的转换，正在考虑在现代计算平台上快速发展图形分析的技术。许多学生正在接受这一重要领域的培训和教育。图分析可以从现代并行机上可用的内核和存储中受益匪浅。然而，有效地利用资源仍然是一个巨大的挑战，由于不规则的并行性和缺乏数据的局部性图计算。这项工作利用了两个关键特征，重叠的工作集和计算值稳定性，以开发加速图形分析的技术。正在考虑的技术包括：优化磁盘上大型图形的阅读和写入，优化集群上的节点间通信，以及优化多个版本的演进图形的计算。这些优化被用于极大地提高多个流行的图形处理系统的性能。还计划向公众宣传这些软件的改进。

The importance of graph processing has grown with the popularity of graph analytics. An important feature of real-world graphs is that they are constantly evolving (e.g., social networks, networks modeling spreading of a disease etc.). Graph analytics over an evolving graph entails repeating analysis over snapshots of a graph taken at different points in time to observe how features of interest change over time. For large real-world graphs with tens of billions of edges, evolving graph analysis is both highly compute- and memory-intensive. By developing transformations that reorganize the computation and data, techniques for rapid evolving graph analytics on modern computing platforms are being considered. Many students are being trained and educated in this important field.Graph analysis can greatly benefit from cores and storage available on modern parallel machines. However, effectively exploiting the resources remains an enormous challenge due to irregular nature of parallelism and lack of data locality in graph computations. This work is leveraging two key characteristics, overlapping working sets and computed value stability, to develop techniques for speeding up graph analytics. The techniques being considered include: optimization of reading and writing of large graphs on disk, optimizing inter-node communication on a cluster, and optimizing computation over multiple versions of an evolving graph. These optimizations are being used to greatly enhance the performance of multiple popular graph processing systems. Public dissemination of these software enhancements are also planned.