[發明專利]一種基于可重構方式的KNN算法的硬件實現系統和方法

在審

• 申請號: 201911037856.5
• 申請日: 2019-10-29
• 公開（公告）號: CN110796193A
• 公開（公告）日: 2020-02-14
• 發明（設計）人: 李麗;張衡;傅玉祥;何書專
• 申請（專利權）人: 南京寧麒智能計算芯片研究院有限公司
• 主分類號: G06K9/62
• 分類號: G06K9/62;G06K9/00
• 代理公司: 32346 江蘇瑞途律師事務所
• 代理人: 金龍

1.一種基于可重構方式的KNN算法的硬件實現系統，其特征在于：包括控制器模塊、距離計算模塊、排序模塊、決策模塊、地址產生模塊和數據分發模塊；地址產生模塊包括寫結果地址產生模塊；數據分發模塊包括結果分發模塊；

其中，控制器模塊用于配置運算所需要的參數并將參數送入到地址產生模塊和數據分發模塊；

地址產生模塊生成地址數據然后通過數據分發模塊送入距離計算模塊；

距離計算模塊接收數據分發模塊發送的數據并將計算后的距離數據送入排序模塊，所述距離計算模塊計算每個測試集樣本與所有訓練集樣本的對應歐式距離，距離計算模塊為一個實數乘法器和三個實數加法器組成的乘累加單元；

排序模塊對距離計算模塊發送的數據進行排序后得到最小的K個值然后發送給決策模塊，決策模塊尋找標簽地址以得到最終標簽；

結果地址產生模塊產生對應地址同時將數據通過結果分發模塊寫入到SRAM相應位置。

2.根據權利要求1所述的基于可重構方式的KNN算法的硬件實現系統，其特征在于：若M>[logK]+1，則距離計算模塊的計算時間覆蓋排序模塊和決策模塊的計算時間；若M≤[logK]+1，則排序模塊的計算時間覆蓋距離計算模塊和決策模塊的計算時間，其中，M為距離計算模塊計算一個樣本距離的時間，[K]+1為排序模塊的計算時間，即對于距離計算結果已經排序的的K個距離，插入一個距離計算結果重新排序所需的時間，其中，3≤K≤20，2≤M≤64。

3.根據權利要求1所述的基于可重構方式的KNN算法的硬件實現系統，其特征在于：根據存儲資源按照訓練集數據、測試集數據、訓練集標簽和結果數據的比例分配存儲資源。

4.根據權利要求1所述的基于可重構方式的KNN算法的硬件實現系統，其特征在于：所述排序模塊獲取每個測試集和所有訓練集樣本中要選取距離最小的K個樣本，每計算得到一個距離數值，若該距離數值小于現有的K個樣本中距離最大的值，則將此值與剩下的K-1個值重新排序，排序模塊的計算時間為[logK]+1，其中，3≤K≤20。

5.根據權利要求4所述的基于可重構方式的KNN算法的硬件實現系統，其特征在于：決策模塊根據最終得到的最小的K個值通過尋址方式找到訓練集樣本對應的標簽，然后通過計數的方式K個值中數量最多的標簽，確定測試集分類結果并將結果存回SRAM。

6.一種基于可重構方式的KNN算法的硬件實現方法，其特征在于：包括以下步驟：

S1：通過地址產生模塊和數據分發模塊從bank中分別取X個測試集樣本數據和一個訓練集樣本數據，送入到距離計算模塊進行X路乘累加計算；

S2：距離計算結果進入排序模塊進行判斷并進行排序，若M>[logK]+1，則距離計算模塊的計算時間覆蓋排序模塊和決策模塊的計算時間；若M≤[logK]+1，則排序模塊的計算時間覆蓋距離計算模塊和決策模塊的計算時間，其中，M為距離計算模塊計算一個樣本距離的時間，[K]+1為排序模塊的計算時間，其中，3≤K≤20，2≤M≤64；

S3：通過排序模塊得到每個測試集和所有訓練集樣本中要選取距離最小的K個樣本，每計算得到一個距離，若該距離小于現有的K個樣本中距離最大的值，則將此值與剩下的K-1個值重新排序，其中，3≤K≤20；

S4：距離計算模塊計算完一個測試集樣本與所有訓練集的距離后發給決策模塊，決策模塊得到距離最小的K個值；

S5：在決策模塊中通過尋址的方式確定K個樣本的分類，然后選擇K個樣本中出現次數最多的分類，作為測試集樣本分類；

S6：得到分類類別，通過數據分發模塊和地址產生模塊將結果存回bank中。

7.根據權利要求6所述的基于可重構方式的KNN算法的硬件實現方法，其特征在于：步驟S1具體包括以下步驟：

S11：根據計算資源，決定并行計算為X路并行計算，因此從測試集中同時取X個樣本，連續不斷供數；

S12：從訓練集中取出一個樣本并連續不斷供數，訓練集數據和測試集數據通過加法器做減法，得到中間結果數據分兩路送入乘法器，乘法器將計算的結果數據送入加法器；

S13：第一個加法器將乘法器輸出的結果數據減少為Y個并送入第二個加法器，第二個加法器將接收的數據減少為Y/2個，最后一個加法器將上述兩個數據相加，得到結果數據；其中，加法器有Y個延時的周期。