k-ближайший соседний алгоритм в verilog

Question

Im планирует выполнить реализацию Verilog KNN. Но проблема заключается в евклидовом измерении расстояния, связанного с KNN, так как для этого требуется вычитание, возведение в квадрат, добавление. Я думаю, что код станет сложным, когда я код knn с эвклидовым distance.Is есть простой метод (аппаратно дружественный), чтобы найти расстояние, так что сложность кода и, следовательно, сложность синтезированной схемы будет уменьшаться. Моя идея состоит в том, чтобы хранить кодовую книгу в памяти, и когда мы даем ввод, k ближайших соседей будет генерироваться как результат.

Answer 1

Поиск k-ближайших соседей включает в себя две части: 1) Рассчитайте расстояние между вашим входным вектором и каждым опорным вектором и 2) Найдите k наименьших расстояний.

Для части 1) вы можете спроектировать конвейерную функцию евклидова расстояния, состоящую из вычитателя, множителя и аккумулятора. Для вычитания и накопления (добавления) требуется относительно небольшой период синхронизации относительно умножения. В зависимости от битовой ширины может оказаться целесообразным и конвейер. Для однотактного множителя потребуется непомерно высокий тактовый период, поэтому он, безусловно, должен быть конвейерным.

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

Для части 2), вы должны сравнить все расстояния, чтобы найти k наименьшее. Это можно сделать несколькими способами; один из возможных способов - это дерево компараторов, которое находит единственное наименьшее расстояние. Как только это будет найдено, вы можете удалить это расстояние от множества расстояний и повторить k раз.

Обратите внимание, что для части 1 вы в основном используете функциональный блок CPU/GPU; и это почти наверняка будет быстрее, чем реализация Verilog. Самое большое улучшение, которое вы получите над процессором/графическим процессором, - это часть 2), нахождение k минимальных расстояний.