趙睿

摘要：K近鄰算法（KNN）是基于統(tǒng)計學(xué)的分類的方法，是數(shù)據(jù)挖掘分類的算法中比較常用的一種。該算法有更直觀且無需先驗統(tǒng)計知識等特點，已經(jīng)成為數(shù)據(jù)挖掘技術(shù)重要的理論和實際應(yīng)用研究方法之一。K近鄰計算需要快速處理數(shù)據(jù)，因此用硬件來實現(xiàn)加速。

關(guān)鍵詞：數(shù)據(jù)挖掘；K近鄰；FPGA

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2013）07-1572-03

FPGA（現(xiàn)場可編程邏輯器件）產(chǎn)品的應(yīng)用領(lǐng)域已經(jīng)從原來的通信擴展工業(yè)控制、電子等廣泛的領(lǐng)域。所以用FPGA（現(xiàn)場可編程邏輯器件）來實現(xiàn)K近鄰計算更符合市場需求，但是KNN算法仍然存在一定的缺陷，今后研究的重點仍然應(yīng)該放在速度與準(zhǔn)確度的提高上面。

1 K近鄰硬件結(jié)構(gòu)

本次設(shè)計采用的是VHDL語言編寫設(shè)計，仿真實驗時首先要進行程序分析，確認(rèn)程序沒有語法和邏輯錯誤之后再逐步實現(xiàn)其功能。試驗時先用兩張圖片分別生成兩個.mif和.coe文件，利用生成的兩個.mif文件創(chuàng)建兩個IP核備用。然后添加各個子模塊，運行程序進行K近鄰分類計算，調(diào)用IP核和由圖像生成的ROM文件進行數(shù)據(jù)分析處理，最后得出仿真試驗的結(jié)果。仿真測試如圖1所示。

其中，K近鄰計算程序值主要的調(diào)用程序，K近鄰測試程序中各種主要的參數(shù)基本都在K近鄰計算程序計算得出。

2 IP核的生成

IP核（Intellectual Property core）具有特定功能的電路模塊。IP核有時也稱為宏功能塊、虛擬元件。按提供方式分類：

1）硬核（hard core）具有特定功能的硬件電路。在FPGA中是已經(jīng)用硬件實現(xiàn)并可以直接應(yīng)用的功能模塊。

2）固核（firm core）是硬核與軟核的折中，他是將軟核固化為硬核并加入的IP庫中的產(chǎn)品。

3）軟核（soft core）是一段具有特定電路功能的硬件描述語言程序，該程序與集成電路工藝無關(guān)，可以移植到不同的半導(dǎo)體工藝中去生產(chǎn)集成電路芯片。

綜上所述，將硬核和固核作為硬IP核，而軟核作為軟IP核。

4）硬IP核與軟IP核的關(guān)系。硬IP核的缺點是對加工工藝依賴性大，優(yōu)點是節(jié)省設(shè)計時間；軟IP核的缺點是需要花費大量的時間進行功能和時序的驗證，有點是它的設(shè)計不依賴加工工藝。所以，當(dāng)新加工工藝出現(xiàn)時，芯片設(shè)計主要是軟IP核設(shè)計，當(dāng)其經(jīng)過功能和時序的測試后就將其固化為硬IP核并加入到IP庫中，隨著芯片設(shè)計的不斷改進，最后可能85%的芯片面積都由硬IP核占據(jù)。直到出現(xiàn)下一個循環(huán)。

分類：①嵌入式IP核，可編程IP核如CPU。

②通用IP核，如存儲器、通用接口電路。

常見的IP核有CUP核、DSP核、存儲器模塊、復(fù)雜接口模塊、完成復(fù)雜計算功能的模塊、外設(shè)接口（PCI）、通用串行總線（USB）。

IP核的價值：IP核重用（reuse）可以縮短設(shè)計周期、提高設(shè)計效率。

3 FIFO文件的使用

FIFO（first input first output，先進先出堆棧）是一種數(shù)據(jù)緩沖器，優(yōu)點沒有外部讀寫地址線，這樣使用起來非常方便；缺點是只能順序讀寫數(shù)據(jù)。通常FIFO的使用情況有兩種，一是FIFO用于不同時鐘域之間的數(shù)據(jù)傳輸；二是FIFO用于不同位寬的數(shù)據(jù)傳輸.根據(jù)FIFO的時鐘域，可以將FIFO分為同步FIFO和異步FIFO.異步FIFO的讀寫時鐘采用各自獨立的不同時鐘，廣泛應(yīng)用與網(wǎng)絡(luò)接口、圖像處理等方面；同步FIFO的讀寫時鐘相同。

FIFO的功能。

FIFO存儲器是系統(tǒng)的緩沖環(huán)節(jié)，如果沒有FIFO存儲器，整個系統(tǒng)就不可能正常工作.FIFO存儲器的主要功能如下：

1）對連續(xù)數(shù)據(jù)流進行緩存，防止進機和存儲操作時丟失數(shù)據(jù)。

2）數(shù)據(jù)集中起來進機和存儲，可避免頻繁的總線操作，減輕CPU的負(fù)擔(dān)。

3）允許系統(tǒng)進行DMA操作，提高數(shù)據(jù)的傳輸速度。

異步FIFO的結(jié)構(gòu)如圖2所示。

工作原理：

由于空標(biāo)志和滿標(biāo)志控制了FIFO的操作，因此標(biāo)志錯誤會引起操作的錯誤。標(biāo)志的產(chǎn)生是通過對讀寫地址的比較產(chǎn)生的。

空滿標(biāo)志產(chǎn)生的算法。構(gòu)造一個指針寬度為N+1，深度為2+N字節(jié)的FIFO（為便方比較將格雷碼指針轉(zhuǎn)換為二進制指針）。當(dāng)指針的二進制碼中最高位不～致而其它N位都相等時，F(xiàn)IFO為滿。當(dāng)指針完全相等時，F(xiàn)IFO為空。舉例說明：一個深度為8字節(jié)的FIFO怎樣工作（使用已轉(zhuǎn)換為二進制的指針）。FIFO_WlDTH=8，F(xiàn)IFO_DEPTH=2+N=8，N=3，指針寬度為N+1=4。起初rd和wr均為“0000”。此時FIFO中寫入8個字節(jié)的數(shù)據(jù)。wr=“1000”，rd=“0000”。當(dāng)然，這就是滿條件。現(xiàn)在，假設(shè)執(zhí)行了8次的讀操作，使得rd=“1000”，這就是空條件。另外的8次寫操作將使wr等于“0000”，但rd仍然等于“1000”，因此FIFO為滿條件。當(dāng)然實際使用中其實指針可以是任意一個。

4 LPM_ROM簡介

LPM是可變參數(shù)元件庫Library of Parameterized Modules的英語縮寫，Altera提供的可變參數(shù)元件均是基于Altera器件的結(jié)構(gòu)做的優(yōu)化設(shè)計。在許多實用情況中，必須使用可變參數(shù)元件才可以使用一些Altera特定器件的硬件功能。例如各類片上存儲器、DSP模塊、LVDS驅(qū)動器、嵌入式PLL以及SERDES和DDIO電路模塊等等。這些可變參數(shù)元件可以以圖形或硬件描述語言的方式進行調(diào)用，使得基于EDA技術(shù)的電子設(shè)計的效率和可靠性有了很大的提高。設(shè)計者可以根據(jù)實際電路的設(shè)計需要，選擇LPM庫中的適當(dāng)模塊，并為其設(shè)定適當(dāng)?shù)膮?shù)，就能滿足自己的設(shè)計需要，從而在自己的項目中十分方便地調(diào)用優(yōu)秀的電子工程技術(shù)人員的硬件設(shè)計成果。

5 小結(jié)

本文采用VHDL語言來實現(xiàn)K近鄰計算，VHDL語言功能強大、設(shè)計靈活，具有強大的系統(tǒng)硬件描述能力，支持廣泛、易于修改，獨立于器件的設(shè)計、與工藝無關(guān)等特點，因此用VHDL來實現(xiàn)K近鄰計算更加方便。

參考文獻(xiàn)：

[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] 余蓓，高軍，葉施仁.基于近鄰方法的高維數(shù)據(jù)可視化聚類發(fā)現(xiàn)[J].計算機研究與發(fā)展，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] 孫巖，呂世聘，王秀坤.基于結(jié)構(gòu)學(xué)習(xí)的KNN分類算法[J].計算機科學(xué)，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īng)網(wǎng)絡(luò)的文檔特征表示研究[J].情報學(xué)報，2003，22（1）：22-26.

[8] 李榮陸，胡運發(fā).基于密度的KNN文本分類器訓(xùn)練樣本裁剪方法[J].計算機研究與發(fā)展，2004，41（4）：539-545.