TY - GEN
T1 - Average-case communication-optimal parallel parenthesis matching
AU - Huang, Chun Hsi
AU - He, Xin
PY - 2002
Y1 - 2002
N2 - We provide the first non-trivial lower bound, p-3/p·n/p, wherep 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.
AB - We provide the first non-trivial lower bound, p-3/p·n/p, wherep 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.
UR - https://www.scopus.com/pages/publications/84878664174
U2 - 10.1007/3-540-36136-7_28
DO - 10.1007/3-540-36136-7_28
M3 - Conference contribution
SN - 3540001425
SN - 9783540001423
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 308
EP - 319
BT - Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings
T2 - 13th Annual International Symposium on Algorithms and Computation, ISAAC 2002
Y2 - 21 November 2002 through 23 November 2002
ER -