We provide the first non-trivial lower bound, (p-3)/p·n/p, where p is the number of the processors and n is the data size, on the average-case communication volume, σ, required to solve the parenthesis matching problem and present a parallel algorithm that takes linear (optimal) computation time and optimal expected message volume, σ + p. The kernel of the algorithm is to solve the all nearest smaller values problem. Provided n/p = Ω(p), we present an algorithm that achieves optimal sequential computation time and uses only a constant number of communication phases, with the message volume in each phase bounded above by (n/p + p) in the worst case and p in the average case, assuming the input instances are uniformly distributed.
展开▼
机译：我们提供第一个非平凡的下限，（p-3）/ p·n / p，其中p是处理器的数量，n是数据大小，在平均案例通信容量，σ所需的情况下括号匹配问题并呈现一个并行算法，该算法采用线性（最佳）计算时间和最佳预期消息卷σ+ p。算法的内核是解决所有最接近的较小值问题。提供了n / p =ω（p），我们介绍了一种实现最佳顺序计算时间的算法，并仅使用恒定数量的通信阶段，并且在最坏的情况下通过（n / p + p）界定的每个阶段中的消息卷案例和p在平均案例中，假设输入实例是均匀分布的。
展开▼
