High-Productivity and High-Performance Analysis of Filtered Semantic Graphs
High-Productivity and High-Performance Analysis of Filtered Semantic Graphs
复制标题
DOI：
10.1109/ipdps.2013.52
复制
发表时间：
2013-05
期刊：
影响因子：
--
通讯作者：
A. Buluç;Erika Duriakova;A. Fox;J. Gilbert;Shoaib Kamil;A. Lugowski;L. Oliker;Samuel Williams
中科院分区：
文献类型：
--
作者：
A. Buluç;Erika Duriakova;A. Fox;J. Gilbert;Shoaib Kamil;A. Lugowski;L. Oliker;Samuel Williams
在对大规模语义图执行复杂的分析查询时，高性能是一个至关重要的考虑因素。在语义图中，顶点和边携带各种类型的属性。语义图上的分析查询通常取决于这些属性的值;因此，计算必须通过仅通过感兴趣的那些单个顶点和边的过滤器来查看图。知识发现库（KDT）是一个用于并行图计算的Python库，可以通过两种方式进行定制。首先，用户可以通过指定边和顶点之间的操作来编写自定义图形算法。由于KDT的基本线性代数抽象，这些程序员指定的操作被称为半环操作。其次，用户可以通过编写过滤器来定制现有的图形算法，该过滤器对于用户想要在算法执行期间保留的那些顶点和边返回true。为了提高生产率，半环操作和过滤器都是用高级语言编写的，由于必须为每个顶点和边调用Python虚拟机的瓶颈，导致性能相对较低。在这项工作中，我们使用选择性嵌入式JIT专业化（SEJITS）方法来自动将程序员定义的半环操作和过滤器转换为较低级别的效率语言，从而绕过Python的upcall。我们通过与高性能组合BLAS引擎进行比较来评估我们的方法，并显示我们的方法使用户能够用高级语言编写，并且仍然获得低级别代码的高性能。我们还提出了一个新的屋顶模型图遍历，并表明我们的高性能实现不显着偏离屋顶。总的来说，我们展示了第一个已知的解决方案，从生产力语言获得高性能的问题时，选择性地应用图算法的语义图。
High performance is a crucial consideration when executing a complex analytic query on a massive semantic graph. In a semantic graph, vertices and edges carry attributes of various types. Analytic queries on semantic graphs typically depend on the values of these attributes; thus, the computation must view the graph through a filter that passes only those individual vertices and edges of interest. Knowledge Discovery Toolbox (KDT), a Python library for parallel graph computations, is customizable in two ways. First, the user can write custom graph algorithms by specifying operations between edges and vertices. These programmer-specified operations are called semiring operations due to KDT's underlying linear-algebraic abstractions. Second, the user can customize existing graph algorithms by writing filters that return true for those vertices and edges the user wants to retain during algorithm execution. For high productivity, both semiring operations and filters are written in a high-level language, resulting in relatively low performance due to the bottleneck of having to call into the Python virtual machine for each vertex and edge. In this work, we use the Selective Embedded JIT Specialization (SEJITS) approach to automatically translate semiring operations and filters defined by programmers into a lower-level efficiency language, bypassing the upcall into Python. We evaluate our approach by comparing it with the high-performance Combinatorial BLAS engine, and show our approach enables users to write in high-level languages and still obtain the high performance of low-level code. We also present a new roofline model for graph traversals, and show that our high-performance implementations do not significantly deviate from the roofline. Overall, we demonstrate the first known solution to the problem of obtaining high performance from a productivity language when applying graph algorithms selectively on semantic graphs.