Book Image

OpenCL Programming by Example

Book Image

OpenCL Programming by Example

Overview of this book

Research in parallel programming has been a mainstream topic for a decade, and will continue to be so for many decades to come. Many parallel programming standards and frameworks exist, but only take into account one type of hardware architecture. Today computing platforms come with many heterogeneous devices. OpenCL provides royalty free standard to program heterogeneous hardware. This guide offers you a compact coverage of all the major topics of OpenCL programming. It explains optimization techniques and strategies in-depth, using illustrative examples and also provides case studies from diverse fields. Beginners and advanced application developers will find this book very useful. Beginning with the discussion of the OpenCL models, this book explores their architectural view, programming interfaces and primitives. It slowly demystifies the process of identifying the data and task parallelism in diverse algorithms. It presents examples from different domains to show how the problems within different domains can be solved more efficiently using OpenCL. You will learn about parallel sorting, histogram generation, JPEG compression, linear and parabolic regression and k-nearest neighborhood, a clustering algorithm in pattern recognition. Following on from this, optimization strategies are explained with matrix multiplication examples. You will also learn how to do an interoperation of OpenGL and OpenCL. "OpenCL Programming by Example" explains OpenCL in the simplest possible language, which beginners will find it easy to understand. Developers and programmers from different domains who want to achieve acceleration for their applications will find this book very useful.
Table of Contents (18 chapters)
OpenCL Programming by Example
Credits
About the Authors
About the Reviewers
www.PacktPub.com
Preface
Index

k-Nearest Neighborhood (k-NN) algorithm


In machine learning classification is the problem of identifying class/type of a given input quantity. Formally the problem can be stated like, we have a set of classes/types represented by:

C={t(1), t(2),…, t(m)}. 

We have a set P of objects, each of which is described by a vector. All the objects of P have a unique class from C. From P we are given n objects (that is their representative vectors) p(1), p(2), …, p(n) (each p(i) is d-dimensional vector) and for each one of them p(i) the class is also given c(i). These n vectors with their classes ( p(i) , c(i)) are called as the training data. We are given a distance measure d( p1 , p2) that gives the relevant distance between two vectors of P. Now, we are presented an arbitrary point from P say p whose class is not known. The problem is to find the class of p (using each given data and distance).

To find the class of x we use the following algorithm called k-nearest neighborhood algorithm.

  1. Fix a positive...