2014-01-30 8 views
0

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

+0

Инструменты синтеза могут синтезировать операции добавления, вычитания, умножения и силы-два. Таким образом, простой (x * x-y * y) может быть синтезирован. Ты это пробовал? – Ari

+0

В зависимости от вашей конкретной проблемы вы также можете рассмотреть другие, неевклидианские нормы. В частности, норма l1 («taxicab») может работать в некоторых случаях и намного проще вычислить, особенно если ваши данные имеют большую размерность. Однако я чувствую, что фактический алгоритм (в частности, сортировка по расстоянию) гораздо сложнее эффективно реализовать в Verilog, чем сумма продуктов для евклидовой нормы. – mbschenkel

ответ

0

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

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

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

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

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