TitleA High Performance Systolic Architecture for k-NN Classification
Publication TypeConference Papers
2014
AuthorsK. Townsend, P. Jones and J. Zambreno
Conference NameProceedings of the International Conference on Formal Methods and Models for Codesign (MEMOCODE)
Date PublishedOctober

This paper describes the architecture of the winning entry to the 2014 Memocode Design Contest, in the maximum performance category. This year’s Memocode design contest asks contestants to find the 10 nearest neighbors between 1,000 testing points and 10,000,000 training points. Instead of using Euclidean distance, the contest uses Mahalanobis distance. The contest has 2 awards: the maximum performance award and the cost adjusted performance award.

Our implementation uses a brute force approach that calculates the distance between every testing point to every training point. We use the Convey HC-2ex, a FPGA-based platform. However, the theory applies to software implementations as well. At the time of publication, our runtime is 0.54 seconds.

Paper attachments: