Я планирую реализовать Verilog KNN. Но проблема заключается в евклидовом термине измерения расстояния, связанном с KNN, поскольку он требует вычитания, возведения в квадрат, сложения. Я думаю, что код станет сложным, когда я закодирую knn с евклидовым расстоянием. Есть ли какой-нибудь простой метод (аппаратно-дружественный) для нахождения расстояния, чтобы уменьшить сложность кода и, следовательно, сложность синтезированной схемы. Моя идея состоит в том, чтобы хранить кодовую книгу в памяти, и когда мы вводим входные данные, в качестве вывода будет сгенерирован индекс k ближайших соседей.
k-алгоритм ближайшего соседа в Verilog
comment
Инструменты синтеза способны синтезировать операции сложения, вычитания, умножения и степени двойки. Таким образом, простое (xx-yy) может быть синтезировано. Ты это пробовал?
- person Ari schedule 30.01.2014
comment
В зависимости от вашей конкретной проблемы вы также можете рассмотреть другие, неевклидовы нормы. В частности, норма l1 (такси) может работать в некоторых случаях и намного проще в вычислительном отношении, особенно если ваши данные имеют большую размерность. Однако мне кажется, что фактический алгоритм (в частности, сортировку по расстоянию) гораздо сложнее эффективно реализовать в Verilog, чем сумму произведений для евклидовой нормы.
- person mbschenkel schedule 01.02.2014
Ответы (1)
Поиск k-ближайших соседей состоит из двух частей: 1) вычислить расстояние между вашим входным вектором и каждым опорным вектором и 2) найти k наименьших расстояний.
Для части 1) вы можете разработать конвейерную функцию евклидова расстояния, состоящую из вычитателя, множителя и аккумулятора. Вычитание и накопление (сложение) требуют относительно небольшого такта по сравнению с умножением. В зависимости от битовой ширины может быть целесообразно их конвейеризировать. Однотактный умножитель потребует непомерно большого тактового периода, поэтому его обязательно придется конвейеризировать.
Здесь я предположил, что вы работаете с целыми числами; если вам приходится работать с плавающей запятой, то вам не повезло, поскольку умножение с плавающей запятой и сложение не могут быть конвейерными из-за их расходящегося ветвления.
В части 2 вам нужно сравнить все расстояния, чтобы найти наименьшее k. Это можно сделать несколькими способами; один из возможных способов - это дерево компараторов, которое находит единственное наименьшее расстояние. Как только это найдено, вы можете удалить это расстояние из набора расстояний и повторить k раз.
Обратите внимание, что в части 1 вы в основном реализуете функциональный блок CPU/GPU; и это почти наверняка будет быстрее, чем ваша реализация Verilog. Самое большое улучшение, которое вы получите по сравнению с процессором / графическим процессором, — это часть 2) нахождение k минимальных расстояний.
person
mtveezy
schedule
15.03.2017
