Communication-optimal parallel parenthesis matching

We provide the first non-trivial lower bound, p-3p·np, 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, assuming problem instances are uniformly distributed, 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 np=Ω(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 (np+p) in the worst case and p in the average case. Experiments have been performed on two clusters: an SGI Intel Linux Cluster and a Sun cluster of workstations, both showing low communication overhead and good speedups.