基于FPGA的K近邻计算的实现

赵睿

摘要：K近邻算法（KNN）是基于统计学的分类的方法，是数据挖掘分类的算法中比较常用的一种。该算法有更直观且无需先验统计知识等特点，已经成为数据挖掘技术重要的理论和实际应用研究方法之一。K近邻计算需要快速处理数据，因此用硬件来实现加速。

关键词：数据挖掘；K近邻；FPGA

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2013）07-1572-03

FPGA（现场可编程逻辑器件）产品的应用领域已经从原来的通信扩展工业控制、电子等广泛的领域。所以用FPGA（现场可编程逻辑器件）来实现K近邻计算更符合市场需求，但是KNN算法仍然存在一定的缺陷，今后研究的重点仍然应该放在速度与准确度的提高上面。

1 K近邻硬件结构

本次设计采用的是VHDL语言编写设计，仿真实验时首先要进行程序分析，确认程序没有语法和逻辑错误之后再逐步实现其功能。试验时先用两张图片分别生成两个.mif和.coe文件，利用生成的两个.mif文件创建两个IP核备用。然后添加各个子模块，运行程序进行K近邻分类计算，调用IP核和由图像生成的ROM文件进行数据分析处理，最后得出仿真试验的结果。仿真测试如图1所示。

其中，K近邻计算程序值主要的调用程序，K近邻测试程序中各种主要的参数基本都在K近邻计算程序计算得出。

2 IP核的生成

IP核（Intellectual Property core）具有特定功能的电路模块。IP核有时也称为宏功能块、虚拟元件。按提供方式分类：

1）硬核（hard core）具有特定功能的硬件电路。在FPGA中是已经用硬件实现并可以直接应用的功能模块。

2）固核（firm core）是硬核与软核的折中，他是将软核固化为硬核并加入的IP库中的产品。

3）软核（soft core）是一段具有特定电路功能的硬件描述语言程序，该程序与集成电路工艺无关，可以移植到不同的半导体工艺中去生产集成电路芯片。

综上所述，将硬核和固核作为硬IP核，而软核作为软IP核。

4）硬IP核与软IP核的关系。硬IP核的缺点是对加工工艺依赖性大，优点是节省设计时间；软IP核的缺点是需要花费大量的时间进行功能和时序的验证，有点是它的设计不依赖加工工艺。所以，当新加工工艺出现时，芯片设计主要是软IP核设计，当其经过功能和时序的测试后就将其固化为硬IP核并加入到IP库中，随着芯片设计的不断改进，最后可能85%的芯片面积都由硬IP核占据。直到出现下一个循环。

分类：①嵌入式IP核，可编程IP核如CPU。

②通用IP核，如存储器、通用接口电路。

常见的IP核有CUP核、DSP核、存储器模块、复杂接口模块、完成复杂计算功能的模块、外设接口（PCI）、通用串行总线（USB）。

IP核的价值：IP核重用（reuse）可以缩短设计周期、提高设计效率。

3 FIFO文件的使用

FIFO（first input first output，先进先出堆栈）是一种数据缓冲器，优点没有外部读写地址线，这样使用起来非常方便；缺点是只能顺序读写数据。通常FIFO的使用情况有两种，一是FIFO用于不同时钟域之间的数据传输；二是FIFO用于不同位宽的数据传输.根据FIFO的时钟域，可以将FIFO分为同步FIFO和异步FIFO.异步FIFO的读写时钟采用各自独立的不同时钟，广泛应用与网络接口、图像处理等方面；同步FIFO的读写时钟相同。

FIFO的功能。

FIFO存储器是系统的缓冲环节，如果没有FIFO存储器，整个系统就不可能正常工作.FIFO存储器的主要功能如下：

1）对连续数据流进行缓存，防止进机和存储操作时丢失数据。

2）数据集中起来进机和存储，可避免频繁的总线操作，减轻CPU的负担。

3）允许系统进行DMA操作，提高数据的传输速度。

异步FIFO的结构如图2所示。

工作原理：

由于空标志和满标志控制了FIFO的操作，因此标志错误会引起操作的错误。标志的产生是通过对读写地址的比较产生的。

空满标志产生的算法。构造一个指针宽度为N+1，深度为2+N字节的FIFO（为便方比较将格雷码指针转换为二进制指针）。当指针的二进制码中最高位不～致而其它N位都相等时，FIFO为满。当指针完全相等时，FIFO为空。举例说明：一个深度为8字节的FIFO怎样工作（使用已转换为二进制的指针）。FIFO_WlDTH=8，FIFO_DEPTH=2+N=8，N=3，指针宽度为N+1=4。起初rd和wr均为“0000”。此时FIFO中写入8个字节的数据。wr=“1000”，rd=“0000”。当然，这就是满条件。现在，假设执行了8次的读操作，使得rd=“1000”，这就是空条件。另外的8次写操作将使wr等于“0000”，但rd仍然等于“1000”，因此FIFO为满条件。当然实际使用中其实指针可以是任意一个。

4 LPM_ROM简介

LPM是可变参数元件库Library of Parameterized Modules的英语缩写，Altera提供的可变参数元件均是基于Altera器件的结构做的优化设计。在许多实用情况中，必须使用可变参数元件才可以使用一些Altera特定器件的硬件功能。例如各类片上存储器、DSP模块、LVDS驱动器、嵌入式PLL以及SERDES和DDIO电路模块等等。这些可变参数元件可以以图形或硬件描述语言的方式进行调用，使得基于EDA技术的电子设计的效率和可靠性有了很大的提高。设计者可以根据实际电路的设计需要，选择LPM库中的适当模块，并为其设定适当的参数，就能满足自己的设计需要，从而在自己的项目中十分方便地调用优秀的电子工程技术人员的硬件设计成果。

5 小结

本文采用VHDL语言来实现K近邻计算，VHDL语言功能强大、设计灵活，具有强大的系统硬件描述能力，支持广泛、易于修改，独立于器件的设计、与工艺无关等特点，因此用VHDL来实现K近邻计算更加方便。

参考文献：

[1] Tao Yufei，Dimitris Papadias，Nikos Mamoulis，et al. An efficient cost model for K-NNsearch technical report[J]. HKUST，2001，13（1）：1-14.

[2] Fayed H A，Atiya A F. A Novel Template Reduction Approach for the K-NearestNeighbor Method[J].IEEE Transactions on Neural Networks，2009，20（5）： 890-896.

[3] 余蓓，高军，叶施仁.基于近邻方法的高维数据可视化聚类发现[J].计算机研究与发展，2000，37（6）：714-720.

[4] Mitchell H B，Schaefer P A. A “soft” K-nearest neighbor voting scheme[J]. International journalof intelligent systems，2001，16：459-468.

[5] 孙岩，吕世聘，王秀坤.基于结构学习的KNN分类算法[J].计算机科学，2007，34（12）：184-187.

[6] Aghbari Z A.Array-index：a plug&search K nearest neighbors method for high-dimensional data[J]. Data & Knowledge Engineering，2005，52：333-352.

[7] 田萱，孟祥光，刘希玉.基于BP神经网络的文档特征表示研究[J].情报学报，2003，22（1）：22-26.

[8] 李荣陆，胡运发.基于密度的KNN文本分类器训练样本裁剪方法[J].计算机研究与发展，2004，41（4）：539-545.