A fast algorithm for computing histograms on a reconfigurable mesh

Author

Jang, Ju-wool ; Park, Heonchul ; Prasanna, Viktor K.

Author_Institution

Univ. of Southern California, Los Angeles, CA, USA

fYear

1992

fDate

19-21 Oct 1992

Firstpage

244

Lastpage

251

Abstract

The authors present fast parallel algorithms for computing the histogram on PARBUS and RMESH models. Compared with the approach of J. Jeng and S. Sahni (1992), the proposed algorithm improves the time complexity by using a constant amount of memory in each processing element. In the histogram modification algorithm, the entire range of h is considered. The connections used by the proposed algorithm on the PARBUS model are same as those allowed in the MRN model. Thus, this algorithm runs on this model as well. The results obtained imply that the number of 1´s in a N×N 0/1 table can be counted in O(log* N) time on an N×N reconfigurable mesh and in O(log log N) time on an N×N RMESH

Keywords

computational complexity; parallel algorithms; reconfigurable architectures; MRN model; PARBUS; RMESH models; algorithm for computing histograms; parallel algorithms; reconfigurable mesh; time complexity; Automata; Broadcasting; Computational modeling; Computer networks; Computer vision; Concurrent computing; Contracts; Histograms; Image segmentation; Switches;

fLanguage

English

Publisher

ieee

Conference_Titel

Frontiers of Massively Parallel Computation, 1992., Fourth Symposium on the

Conference_Location

McLean, VA

Print_ISBN

0-8186-2772-7

Type

conf

DOI

10.1109/FMPC.1992.234952

Filename

234952