我打算做 KNN 的 verilog 实现。但问题是与 KNN 相关的欧几里德距离测量项，因为它需要减法、平方、加法。我认为，当我用欧几里德距离编码knn时，代码会变得复杂。有没有简单的方法（硬件友好）来找到距离，从而降低代码的复杂性，从而降低合成电路的复杂性。我的想法是将密码本存储在内存中，当我们提供输入时，将生成 k 个最近邻索引作为输出。
问问题
1243 次
1 回答
1
找到 k 最近邻涉及两个部分：1）计算输入向量和每个参考向量之间的距离，以及 2）找到 k 个最小距离。
对于第 1) 部分，您可以设计一个由减法器、乘法器和累加器组成的流水线欧几里得距离函数。减法和累加（加法）相对于乘法需要相对较小的时钟周期。根据位宽，也可能值得将它们流水线化。单周期乘法器将需要非常高的时钟周期，因此肯定必须流水线化。
在这里，我假设您正在使用整数；如果您必须使用浮点，那么您就不走运了，因为浮点乘法和加法由于它们的分歧分支而无法流水线化。
对于第 2 部分），您必须比较所有距离以找到 k 最小的。这可以通过多种方式完成；一种可能的方法是使用查找单个最小距离的比较器树。一旦找到，您可以从距离集中删除该距离并重复 k 次。
请注意，对于第 1 部分，您基本上是在实现 CPU/GPU 的功能单元；这几乎肯定会比您的 Verilog 实现更快。您将在 CPU/GPU 上获得的最大改进是第 2 部分）找到 k 个最小距离。
于 2017-03-15T17:07:40.720 回答