Histogram Computation on Distributed Memory Architectures
1989 (English)In: Concurrency: Practice and Experience, Vol. 1, no 2, 219-237 p.Article in journal (Refereed) Published
One data-independent and one data-dependent algorithm for the computation of image histograms on parallel computers are presented, analysed and implemented on the Connection Machine system CM-2. The data-dependent algorithm has a lower requirement on communication bandwidth by only transferring bins with a non-zero count. Both algorithms perform all-to-all reduction, 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-2. With few pixels per processor the data-dependent algorithm requires in the order of √B data transfers for B bins compared to B data transfers for the data-independent algorithm. As the number of pixels per processor grows the advantage of the data-dependent algorithm decreases. The advantage of the data-dependent algorithm increases with the number of bins of the histogram.
Place, publisher, year, edition, pages
1989. Vol. 1, no 2, 219-237 p.
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-91058DOI: 10.1002/cpe.4330010205OAI: oai:DiVA.org:kth-91058DiVA: diva2:507908
NR 201408052012-03-062012-03-062012-03-06Bibliographically approved