High performance predictable histogramming on GPUs : exploring and evaluating algorithm trade-offs

C. Nugteren, G.J.W. Braak, van den, H. Corporaal, B. Mesman

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

6 Citations (Scopus)
2 Downloads (Pure)

Abstract

Graphics Processing Units (GPUs) are suitable for highly data parallel algorithms such as image processing, due to their massive parallel processing power. Many image processing applications use the histogramming algorithm, which fills a set of bins according to the frequency of occurrence of pixel values taken from an input image. Histogramming has been mapped on a GPU prior to this work. Although significant research effort has been spent in optimizing the mapping, we show that the performance and performance predictability of existing methods can still be improved. In this paper, we present two novel histogramming methods, both achieving a higher performance and predictability than existing methods. We discuss performance limitations for both novel methods by exploring algorithm trade-offs. Both the novel and the existing histogramming methods are evaluated for performance. The first novel method gives an average performance increase of 33% over existing methods for non-synthetic benchmarks. The second novel method gives an average performance increase of 56% over existing methods and guarantees to be fully data independent. While the second method is specifically designed for newer GPU architectures, the first method is also suitable for older ar- chitectures.
Original languageEnglish
Title of host publicationProceedings of the Fourth Workshop on General Purpose Processing on Graphics Processing Units (GPGPU) at ASPLOS'11. 5 March 2011, Newport Beach, California
Place of PublicationNew York
PublisherAssociation for Computing Machinery, Inc
ISBN (Print)978-1-4503-0569-3
DOIs
Publication statusPublished - 2011
Eventconference; ASPLOS'11, Newport Beach, CA, USA; 2011-03-05; 2011-03-05 -
Duration: 5 Mar 20115 Mar 2011

Conference

Conferenceconference; ASPLOS'11, Newport Beach, CA, USA; 2011-03-05; 2011-03-05
Period5/03/115/03/11
OtherASPLOS'11, Newport Beach, CA, USA

Fingerprint Dive into the research topics of 'High performance predictable histogramming on GPUs : exploring and evaluating algorithm trade-offs'. Together they form a unique fingerprint.

Cite this