NDLI: A new method for GPU based irregular reductions and its application to k-means clustering

Please wait, while we are loading the content...

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

Reducing branch divergence in GPU programs

Fast Mersenne prime testing on the GPU

A framework for dynamically instrumenting GPU compute applications within GPU Ocelot

Automatically generating and tuning GPU code for sparse matrix-vector multiplication from a high-level representation

A new method for GPU based irregular reductions and its application to k-means clustering

Register packing for cyclic reduction: a case study

Floating-point data compression at 75 Gb/s on a GPU

Analyzing program flow within a many-kernel OpenCL application

Unstructured grid applications on GPU: performance analysis and improvement

Caracal: dynamic translation of runtime environments for GPUs

Real-time rendering and dynamic updating of 3-d volumetric data

Quantifying NUMA and contention effects in multi-GPU systems

A new method for GPU based irregular reductions and its application to k-means clustering

Content Provider	ACM Digital Library
Author	Rubin, Norman Dhanasekaran, Balaji
Abstract	A frequently used method of clustering is a technique called k-means clustering. The k-means algorithm consists of two steps: A map step, which is simple to execute on a GPU, and a reduce step, which is more problematic. Previous researchers have used a hybrid approach in which the map step is computed on the GPU and the reduce step is performed on the CPU. In this work, we present a new algorithm for irregular reductions and apply it to k-means such that the GPU executes both the map and reduce steps. We provide experimental comparisons using OpenCL. Our results show that our scheme is 3.2 times faster than the hybrid scheme for k = 10, an average 1.5 times faster when the number of clusters, k = 100 and on average equal for k = 400, on an ATI Radeon® HD 5870 (best speedup was 3.5 times) compared to the hybrid approach. In addition, we compare the GPU code with the standard OpenMP benchmark, MineBench. In that implementation, both the map and reduce steps are computed on the CPU. For large data sizes, the new GPU scheme shows great promise, with performance up to 35 times faster than MineBench on a four core Intel i7 CPU.
Starting Page	1
Ending Page	8
Page Count	8
File Format	PDF
ISBN	9781450305693
DOI	10.1145/1964179.1964182
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2011-03-05
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	K-means Data-mining Clustering Heterogeneous computing Gpgpu
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in