Histogram computation on distributed memory architectures

Autor: D. C. Gerogiannis, S. C. Orphanoudakis, S. L. Johnsson
Rok vydání: 1989
Předmět:
Zdroj: Concurrency: Practice and Experience. 1:219-237
ISSN: 1096-9128
1040-3108
DOI: 10.1002/cpe.4330010205
Popis: 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.
Databáze: OpenAIRE
Externí odkaz: