k-Nearest Neighbour Algorithm in verilog

Question

Im planning to do KNN's verilog implementation. But the problem is the euclidean distance measurement term associated with KNN,since it needs Subtraction,squaring,adding. I think,the code will become complex when i code knn with euclidean distance.Is there any simple method(hardware friendly) to find the distance, so that the complexity of the code and hence complexity of synthesized circuit will reduce. My idea is to store the codebook in memory and when we give input, k nearest neighbours index will generated as output.

Answer 1

Finding the k-Nearest Neighbors involves two parts: 1) Calculate the distance between your input vector and every reference vector and 2) Find the k smallest distances.

For the part 1), you can design a pipelined Euclidean distance function that consists of a subtractor, multiplier, and accumulator. Subtraction and accumulation (addition) require a relatively small clock period relative to multiplication. Depending on the bitwidth it may be worthwhile to pipeline those as well. A single-cycle multiplier will require a prohibitively high clock period, so it will certainly have to be pipelined.

Here I've assumed you're working with integers; if you have to work with floating point then you're out of luck since floating point multiply and addition cannot be pipelined due to their divergent branching.

For part 2), you have to compare all of the distances to find the k smallest. This can be done several ways; one possible way is with a tree of comparators that finds the single smallest distance. Once that is found, you can remove that distance from the set of distances and repeat k times.

Notice that for part 1, you're basically implementing a CPU/GPU's functional unit; and that's almost certainly going to be faster than your Verilog implementation. The biggest improvement you'll get over a CPU/GPU is with part 2) finding the k minimum distances.