Real World Example – Fast K-Nearest Neighbor Search
Celestech has been developing a revolutionary method for hyperspectral image processing. The computational load of this sort of application is daunting, but provides some concrete data points on the types of performance improvement that can be achieved with GPU processing. Our GPU software development team has mastered the art of extracting maximum performance from the NVIDIA hardware.
As part of our hyperspectral image processing effort, Celestech developed a proprietary K-Nearest Neighbors (KNN) algorithm with world-class speed. We have benchmarked this algorithm against other published approaches and believe it to be the fastest nearest neighbor search algorithm available.
The chart shows the performance of Celestech's Fast Nearest Neighbors algorithm. Highly optimized KNN algorithms were developed for traditional CPU-based architectures and the GPU. The chart illustrates the difference between a highly optimized CPU approach and a highly optimized GPU approach. Please note, a separate architecture-optimized implementation of the overall technique was run on the CPU and GPU. While the algorithms differed, the answers did not. Both the CPU and GPU achieved the same accuracy in all significant digits of precision. The algorithms were run on a 2.4GHz Quad Core Intel with 8 GB of RAM under 64-bit Linux vs. an NVIDIA 8800 GTX GPU under Windows XP. As the chart shows, the over all GPU-optimized application is more than 45 times faster than the optimized CPU application. The Fast KNN search algorithm portion of the software executes hundreds of times faster than a conventional implementation.
Part of the challenge in developing efficient GPU applications lies in the sheer magnitude of their processing capabilities. One trillion floating-point operations per second is a number so large that it defies comprehension. In this realm, counter-intuitive approaches sometimes yield superior results.