SIMD K-nearest-neighbors implementation

Patent metadata

Field	Value
Publication number	US-10042813-B2
Application number	US-201414570413-A
Country	US
Kind code	B2
Filing date	Dec 15, 2014
Priority date	Dec 15, 2014
Publication date	Aug 7, 2018
Grant date	Aug 7, 2018

Abstract

Methods and apparatus relating to improved SIMD (Single Instruction, Multiple Data) K-nearest-neighbors implementations are described. An embodiment provides a technique for improving SIMD implementations of the multidimensional K-Nearest-Neighbors (KNN) techniques. One embodiment replaces the non-SIMD friendly part of the KNN algorithm with a sequence of SIMD operations. For example, in order to avoid branches in the algorithm hotspot (e.g., the inner loop), SIMD operations may be used to update the list of nearest distances (and neighbors) after each iteration. Other embodiments are also disclosed and claimed.

First claim

The invention claimed is:

1. An apparatus comprising:
logic to cause replacement of one or more non-SIMD (Single Instruction, Multiple Data) portions of a K-Nearest-Neighbors (KNN) technique with one or more SIMD operations at least in part based on comparison of a first distance, corresponding to a current iteration of the KNN technique, and a second distance, corresponding to a shortest distance of a previous iteration of the KNN technique.

2. The apparatus of claim 1 , wherein the logic is to cause replacement of the one or more non-SIMD portions of the KNN technique to avoid branches in an inner loop of the KNN technique.

3. The apparatus of claim 1 , wherein the one or more non-SIMD portions of the KNN technique are to comprise one or more scalar operations.

4. The apparatus of claim 1 , wherein the one or more SIMD operations are to update a list of nearest distances after each iteration of the KNN technique.

5. The apparatus of claim 4 , further comprising memory to store the list.

6. The apparatus of claim 1 , wherein one of a VLIW (Very Long Instruction Word) Digital Signal Processor (DSP) or a GPU (Graphics Processing Unit) is to comprise the logic.

7. The apparatus of claim 1 , wherein a processor, having one or more processor cores, is to comprise the logic.

8. The apparatus of claim 1 , wherein the logic, a processor having one or more processor cores, and memory are on a same integrated device.

9. A method comprising:
causing replacement of one or more non-SIMD (Single Instruction, Multiple Data) portions of a K-Nearest-Neighbors (KNN) technique with one or more SIMD operations at least in part based on comparison of a first distance, corresponding to a current iteration of the KNN technique, and a second distance, corresponding to a shortest distance of a previous iteration of the KNN technique.

10. The method of claim 9 , further comprising causing replacement of the one or more non-SIMD portions of the KNN technique to avoid branches in an inner loop of the KNN technique.

11. The method of claim 9 , wherein the one or more non-SIMD portions of the KNN technique comprise one or more scalar operations.

12. The method of claim 9 , further comprising the one or more SIMD operations updating a list of nearest distances after each iteration of the KNN technique.

13. The method of claim 12 , further comprising storing the list in memory.

14. The method of claim 9 , wherein the replacement operation is performed by one of a VLIW (Very Long Instruction Word) Digital Signal Processor (DSP) or a GPU (Graphics Processing Unit).

15. A non-transitory computer-readable medium comprising one or more instructions that when executed on a processor configure the processor to perform one or more operations to:
cause replacement of one or more non-SIMD (Single Instruction, Multiple Data) portions of a K-Nearest-Neighbors (KNN) technique with one or more SIMD operations at least in part based on comparison of a first distance, corresponding to a current iteration of the KNN technique, and a second distance, corresponding to a shortest distance of a previous iteration of the KNN technique.

16. The non-transitory computer-readable medium of claim 15 , further comprising one or more instructions that when executed on the processor configure the processor to perform one or more operations to cause replacement of the one or more non-SIMD portions of the KNN technique to avoid branches in an inner loop of the KNN technique.

17. The non-transitory computer-readable medium of claim 15 , wherein the one or more non-SIMD portions of the KNN technique comprise one or more scalar operations.

18. The non-transitory computer-readable medium of claim 15 , further comprising one or more instructions that when executed on the processor configure the processor to perform one or more operations to cause the one or more SIMD operations to update a list of nearest distances after each iteration of the KNN technique.

19. The non-transitory computer-readable medium of claim 15 , further comprising one or more instructions that when executed on the processor configure the processor to perform one or more operations to cause storing the list in memory.

20. The non-transitory computer-readable medium of claim 15 , wherein the replacement operation is performed by one of a VLIW (Very Long Instruction Word) Digital Signal Processor (DSP) or a GPU (Graphics Processing Unit).

21. A system comprising:
a processor having one or more processor cores;
a display device, coupled to the processor, to display one or more images; and
logic to cause replacement of one or more non-SIMD (Single Instruction, Multiple Data) portions of a K-Nearest-Neighbors (KNN) technique with one or more SIMD operations at least in part based on comparison of a first distance, corresponding to a current iteration of the KNN technique, and a second distance, corresponding to a shortest distance of a previous iteration of the KNN technique.

22. The system of claim 21 , wherein the logic is to cause replacement of the one or more non-SIMD portions of the KNN technique to avoid branches in an inner loop of the KNN technique.

23. The system of claim 21 , wherein the one or more non-SIMD portions of the KNN technique are to comprise one or more scalar operations.

24. The system of claim 21 , wherein the one or more SIMD operations are to update a list of nearest distances after each iteration of the KNN technique.

25. The system of claim 24 , further comprising memory to store the list.

Assignees

• Intel Corp

Inventors

• Goldman Amos

Classifications

• G06F7/026

  Magnitude comparison, i.e. determining the relative order of operands based on their numerical value, e.g. window comparator · CPC title

• G06F15/8007 Primary

  single instruction multiple data [SIMD] multiprocessors · CPC title

• G06F15/17375

  One dimensional, e.g. linear array, ring · CPC title

• G06F7/023

  adaptive, e.g. self learning · CPC title