Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components
Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components
复制标题
DOI：
10.1145/3210257
复制
发表时间：
2018-08-01
影响因子：
1.3
通讯作者：
Pavlogiannis, Andreas
中科院分区：
文献类型：
--
作者：
Chatterjee, Krishnendu;Ibsen-Jensen, Rasmus;Pavlogiannis, Andreas
我们研究了并发系统中关于代数路径性质的算法问题，其中系统的迁移是从一个完全闭半环标记的。代数路径属性可以对数据流分析问题、最短路径问题以及程序分析中出现的许多其他自然问题进行建模。我们认为并发系统的每个组成部分都是一个具有恒定树宽的图，这是大多数程序的控制流图所满足的性质。我们允许多种可能的查询，这些查询在需求驱动的数据流分析中自然出现。对多个查询的研究允许我们考虑一次性预处理和每个单独查询的资源使用之间的权衡。传统的方法是构造所有组件的乘积图，并在乘积上应用最著名的图算法。在这种方法中，即使是单个查询的答案也需要传递闭包（即所有可能查询的结果），这就没有在预处理和查询时间之间进行权衡的余地。我们的主要贡献是显著改善传统方法的最坏情况运行时间的算法，并根据查询的数量提供各种权衡。例如，在两个组件的并发系统中，传统方法在最坏的情况下需要六次时间来回答一个查询并计算传递闭包，而我们表明，在几乎三次的时间内进行一次预处理，每个后续查询最多可以在线性时间内回答，甚至可以在几乎四次的时间内计算传递闭包。此外，我们建立了条件最优性结果，表明如果不实现图算法的重大突破（即改进一般图中最短路径问题的最坏情况边界），我们的算法的最坏情况运行时间就无法改进。初步的实验结果表明，我们的算法在几个基准测试中表现良好。
We study algorithmic questions wrt algebraic path properties in concurrent systems, where the transitions of the system are labeled from a complete, closed semiring. The algebraic path properties can model dataflow analysis problems, the shortest path problem, and many other natural problems that arise in program analysis. We consider that each component of the concurrent system is a graph with constant treewidth, a property satisfied by the controlflow graphs of most programs. We allow for multiple possible queries, which arise naturally in demand driven dataflow analysis. The study of multiple queries allows us to consider the tradeoff between the resource usage of the one-time preprocessing and for each individual query. The traditional approach constructs the product graph of all components and applies the best-known graph algorithm on the product. In this approach, even the answer to a single query requires the transitive closure (i.e., the results of all possible queries), which provides no room for tradeoff between preprocessing and query time.Our main contributions are algorithms that significantly improve the worst-case running time of the traditional approach, and provide various tradeoffs depending on the number of queries. For example, in a concurrent system of two components, the traditional approach requires hexic time in the worst case for answering one query as well as computing the transitive closure, whereas we show that with one-time preprocessing in almost cubic time, each subsequent query can be answered in at most linear time, and even the transitive closure can be computed in almost quartic time. Furthermore, we establish conditional optimality results showing that the worst-case running time of our algorithms cannot be improved without achieving major breakthroughs in graph algorithms (i.e., improving the worst-case bound for the shortest path problem in general graphs). Preliminary experimental results show that our algorithms perform favorably on several benchmarks.