{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,21]],"date-time":"2025-05-21T06:55:07Z","timestamp":1747810507357},"reference-count":11,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2006,10,20]],"date-time":"2006-10-20T00:00:00Z","timestamp":1161302400000},"content-version":"vor","delay-in-days":6167,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Concurrency: Pract. Exper."],"published-print":{"date-parts":[[1989,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>One data\u2010independent and one data\u2010dependent algorithm for the computation of image histograms on parallel computers are presented, analysed and implemented on the Connection Machine system CM\u20102. The data\u2010dependent algorithm has a lower requirement on communication bandwidth by only transferring bins with a non\u2010zero count. Both algorithms perform <jats:italic>all\u2010to\u2010all reduction<\/jats:italic>, which is implemented through a sequence of exchanges as defined by a butterfly network. The two algorithms are compared based on predicted and actual performance on the Connection Machine CM\u20102. With few pixels per processor the data\u2010dependent algorithm requires in the order of \u221a<jats:italic>B<\/jats:italic> data transfers for <jats:italic>B<\/jats:italic> bins compared to <jats:italic>B<\/jats:italic> data transfers for the data\u2010independent algorithm. As the number of pixels per processor grows the advantage of the data\u2010dependent algorithm decreases. The advantage of the data\u2010dependent algorithm increases with the number of bins of the histogram.<\/jats:p>","DOI":"10.1002\/cpe.4330010205","type":"journal-article","created":{"date-parts":[[2006,11,18]],"date-time":"2006-11-18T06:14:23Z","timestamp":1163830463000},"page":"219-237","source":"Crossref","is-referenced-by-count":5,"title":["Histogram computation on distributed memory architectures"],"prefix":"10.1002","volume":"1","author":[{"given":"D. C.","family":"Gerogiannis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S. C.","family":"Orphanoudakis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S. L.","family":"Johnsson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,10,20]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1982.235426"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/0031-3203(85)90002-0"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(87)90030-X"},{"key":"e_1_2_1_5_2","unstructured":"C. M.Brown \u2018Low level image analysis on an MIMD architecture\u2019 inInternational Conference on Computer Vision London England 1987 pp.468\u2013475."},{"key":"e_1_2_1_6_2","first-page":"444","volume-title":"1984 International Conference on Parallel Processing","author":"Johnsson S. L.","year":"1984"},{"key":"e_1_2_1_7_2","unstructured":"S. L.JohnssonandC.\u2010T.Ho \u2018Spanning graphs for optimum broadcasting and personalized communication in hypercubes\u2019 Technical Report YALEU\/DCS\/RR\u2010500 Dept. of Computer Science Yale University New Haven CT November 1986. Revised November 1987 YALEU\/DCS\/RR\u2010610. To appear inIEEE Trans. Computers."},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1973.5009159"},{"key":"e_1_2_1_9_2","volume-title":"The Connection Machine","author":"Hillis W. D.","year":"1985"},{"key":"e_1_2_1_10_2","unstructured":"Thinking Machines Corporation \u2018Connection machine model CM\u20102 technical summary\u2019 Technical Report HA87\u20104 Thinking Machines Corporation 1987."},{"key":"e_1_2_1_11_2","unstructured":"*Lisp release notes. Thinking Machines Corporation 1987."},{"key":"e_1_2_1_12_2","first-page":"223","volume-title":"Advanced Algorithms and Architectures for Signal Processing II","author":"Johnsson S. L.","year":"1987"}],"container-title":["Concurrency: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fcpe.4330010205","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/cpe.4330010205","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,21]],"date-time":"2023-10-21T23:22:54Z","timestamp":1697930574000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/cpe.4330010205"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,12]]},"references-count":11,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1989,12]]}},"alternative-id":["10.1002\/cpe.4330010205"],"URL":"https:\/\/doi.org\/10.1002\/cpe.4330010205","archive":["Portico"],"relation":{},"ISSN":["1040-3108","1096-9128"],"issn-type":[{"value":"1040-3108","type":"print"},{"value":"1096-9128","type":"electronic"}],"subject":[],"published":{"date-parts":[[1989,12]]}}}