k-алгоритъм за най-близък съсед във Verilog

Планирам да направя изпълнението на Verilog на KNN. Но проблемът е терминът за измерване на евклидовото разстояние, свързан с KNN, тъй като се нуждае от изваждане, повдигане на квадрат, събиране. Мисля, че кодът ще стане сложен, когато кодирам knn с евклидово distance.Is има някакъв прост метод (удобен за хардуер) за намиране на разстоянието, така че сложността на кода и следователно сложността на синтезираната верига ще намалее. Идеята ми е да съхраня кодовата книга в паметта и когато дадем вход, индексът на k най-близките съседи ще се генерира като изход.


euclidean-distance knn fpga verilog vlsi
person Viz    schedule 30.01.2014    source източник
comment
Инструментите за синтез са в състояние да синтезират операции събиране, изваждане, умножение и степен две. Така че простото (xx-yy) може да бъде синтезирано. Опитвали ли сте го?   -  person Ari    schedule 30.01.2014
comment
В зависимост от точния ви проблем можете да вземете предвид и други, неевклидови норми. По-специално нормата l1 (такси) може да работи за някои случаи и е много по-проста от изчислителна гледна точка, особено ако вашите данни имат голяма размерност. Усещането ми обаче е, че действителният алгоритъм (по-специално сортирането по разстояние) е много по-труден за ефективно прилагане във Verilog, отколкото сборът на продуктите за евклидова норма.   -  person mbschenkel    schedule 01.02.2014

Отговори (1)


arrow_upward
1
arrow_downward

Намирането на k-най-близките съседи включва две части: 1) Изчислете разстоянието между вашия входен вектор и всеки референтен вектор и 2) Намерете k най-малките разстояния.

За част 1) можете да проектирате конвейерна функция за евклидово разстояние, която се състои от изваждане, множител и акумулатор. Изваждането и натрупването (събирането) изискват относително малък тактов период спрямо умножението. В зависимост от широчината на битовете, може да си струва да ги тръбопроводите също. Умножителят с един цикъл ще изисква прекалено висок тактов период, така че със сигурност ще трябва да бъде конвейеризиран.

Тук предположих, че работите с цели числа; ако трябва да работите с плаваща запетая, тогава нямате късмет, тъй като умножението и събирането с плаваща запетая не могат да бъдат конвейерни поради тяхното различно разклоняване.

За част 2) трябва да сравните всички разстояния, за да намерите най-малкото k. Това може да стане по няколко начина; един възможен начин е с дърво от компаратори, което намира най-малкото разстояние. След като това бъде намерено, можете да премахнете това разстояние от набора от разстояния и да повторите k пъти.

Забележете, че за част 1 вие основно внедрявате функционалната единица на CPU/GPU; и това почти сигурно ще бъде по-бързо от внедряването на Verilog. Най-голямото подобрение, което ще получите спрямо CPU/GPU, е с част 2) намиране на k минимални разстояния.

person mtveezy    schedule 15.03.2017