论文标题
快速且最佳的平行算法用于谓词检测
Fast and Work-Optimal Parallel Algorithms for Predicate Detection
论文作者
论文摘要
最近，谓词检测问题显示在平行复杂性类NC中。在本文中，我们给出了第一个最佳的并行算法，以在用$ n $过程的分布式计算上解决谓词检测问题，每个过程最多$ $ m $状态。以前最著名的并行谓词检测算法ParallelCut具有时间复杂性$ O（\ log Mn）$和工作复杂性$ O（m^3n^3 \ log Mn）$。我们提供了两种算法，一种确定性算法，具有时间复杂性$ o（mn）$和工作复杂性$ O（Mn^2）$，以及一种随机算法，具有时间复杂性$ $（Mn）^{1/2 + O（1）} $和工作复杂性$ \ tilde $ \ tilde $ \ tilde {O} {o}（o}（Mn^2）$。此外，我们的算法对并行曲线的空间复杂性有所改善。我们的这两种算法都具有空间复杂性$ O（Mn^2）$，而ParallelCut具有空间复杂性$ O（m^2n^2）$。
Recently, the predicate detection problem was shown to be in the parallel complexity class NC. In this paper, we give the first work-optimal parallel algorithm to solve the predicate detection problem on a distributed computation with $n$ processes and at most $m$ states per process. The previous best known parallel predicate detection algorithm, ParallelCut, has time complexity $O(\log mn)$ and work complexity $O(m^3n^3\log mn)$. We give two algorithms, a deterministic algorithm with time complexity $O(mn)$ and work complexity $O(mn^2)$, and a randomized algorithm with time complexity $(mn)^{1/2 + o(1)}$ and work complexity $\tilde{O}(mn^2)$. Furthermore, our algorithms improve upon the space complexity of ParallelCut. Both of our algorithms have space complexity $O(mn^2)$ whereas ParallelCut has space complexity $O(m^2n^2)$.
