{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T23:37:01Z","timestamp":1648769821514},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"01n02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Parallel Process. Lett."],"published-print":{"date-parts":[[1994,6]]},"abstract":"<jats:p> Given a sequence of m items \u03b1<jats:sub>1<\/jats:sub>, \u03b1<jats:sub>2<\/jats:sub>,\u2026, \u03b1<jats:sub>m<\/jats:sub> from a semigroup S with an associative operation \u2295, the semigroup computation problem involves computing \u03b1<jats:sub>1<\/jats:sub> \u2295 \u03b1<jats:sub>2<\/jats:sub> \u2295\u2026\u2295 \u03b1<jats:sub>m<\/jats:sub>. We consider the semigroup computation problem involving m (2\u2264m\u2264n) items on a mesh with multiple broadcasting of size [Formula: see text]. Our contribution is to present the first lower bound and the first time-optimal algorithm which apply to the entire range of m (2\u2264m\u2264n). Specifically, we show that any algorithm that solves the semigroup computation problem must take \u03a9( log m) time if [Formula: see text] and [Formula: see text] time for [Formula: see text]. 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. <\/jats:p>","DOI":"10.1142\/s0129626494000090","type":"journal-article","created":{"date-parts":[[2004,11,18]],"date-time":"2004-11-18T21:21:13Z","timestamp":1100812873000},"page":"73-82","source":"Crossref","is-referenced-by-count":3,"title":["A UNIFYING LOOK AT SEMIGROUP COMPUTATIONS ON MESHES WITH MULTIPLE BROADCASTING"],"prefix":"10.1142","volume":"04","author":[{"given":"D.","family":"BHAGAVATHI","sequence":"first","affiliation":[{"name":"Department of Computer Science, Southern Illinois University, Edwardsville, IL 62026, USA"}]},{"given":"S.","family":"OLARIU","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Old Dominion University, Norfolk, VA 23529, USA"}]},{"given":"W.","family":"SHEN","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Old Dominion University, Norfolk, VA 23529, USA"}]},{"given":"L.","family":"WILSON","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Old Dominion University, Norfolk, VA 23529, USA"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"container-title":["Parallel Processing Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129626494000090","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T09:31:49Z","timestamp":1565170309000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129626494000090"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,6]]},"references-count":0,"journal-issue":{"issue":"01n02","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[1994,6]]}},"alternative-id":["10.1142\/S0129626494000090"],"URL":"https:\/\/doi.org\/10.1142\/s0129626494000090","relation":{},"ISSN":["0129-6264","1793-642X"],"issn-type":[{"value":"0129-6264","type":"print"},{"value":"1793-642X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,6]]}}}