A UNIFYING LOOK AT SEMIGROUP COMPUTATIONS ON MESHES WITH MULTIPLE BROADCASTING

Given a sequence of m items α₁, α₂,…, α_m from a semigroup S with an associative operation ⊕, the semigroup computation problem involves computing α₁ ⊕ α₂ ⊕…⊕ α_m. We consider the semigroup computation problem involving m (2≤m≤n) items on a mesh with multiple broadcasting of size . Our contribution is to present the first lower bound and the first time-optimal algorithm which apply to the entire range of m (2≤m≤n). Specifically, we show that any algorithm that solves the semigroup computation problem must take Ω(log m) time if and time for . We then show that our bound is tight by designing an algorithm whose running time matches the lower bound. These results unify and generalize all semigroup lower bounds and algorithms known to the authors.