[發明專利]一種基于MapReduce的K-means聚類算法FPGA加速系統

有效

• 申請號: 201610308843.7
• 申請日: 2016-05-11
• 公開（公告）號: CN107368375B
• 公開（公告）日: 2019-11-12
• 發明（設計）人: 李開;曹計昌;鄒復好;陽美玲;黃浩
• 申請（專利權）人: 華中科技大學
• 主分類號: G06F9/54
• 分類號: G06F9/54;G06F13/40;G06K9/62
• 代理公司: 華中科技大學專利中心 42201
• 代理人: 梁鵬

本發明提出了一種基于MapReduce的K?means聚類算法FPGA加速系統，該加速系統主要包括Map任務數據收發子系統、Map任務加速子系統、Reduce任務數據收發子系統和Reduce任務加速子系統，Map任務數據收發子系統傳送來自PCIe端的相應數據給Map任務加速子系統，并將Map任務加速子系統的最終計算結果回傳給PCIe端；Reduce任務數據收發子系統傳送來自PCIe端的相應數據給Reduce任務加速子系統，并將Reduce任務加速子系統的最終計算結果回傳給PCIe端。按照本發明實現的加速系統，將所需要進行的耗時計算過程從上層中分離出來，采用專用的硬件系統來進行相應的計算，并且系統中的各模塊采用流水線設計和并行處理方法，大大提高了運算處理速度。

技術領域

本發明屬于復雜算法硬件加速系統，具體涉及一種大數據量下基于MapReduce的K-means聚類算法FPGA加速系統。

背景技術

隨著大數據時代的來臨，大數據的應用越來越彰顯它的優勢，它占領的領域也越來越大；但大數據時代仍然面臨著一些亟待解決的難題，比如數據量大、價值密度低、處理速度快、時序性要求高等，因此機器學習和數據挖掘技術正日益獲得計算領域的關注。

聚類分析是數據挖掘中的重要內容，在工業、商業和科研等領域發揮著越來越重要的作用。K-means算法屬于聚類分析中的一種基本劃分方法，常采用誤差平方和準則函數作為聚類準則，該算法在處理數據集上相對可伸縮且效率高。但面對大規模數據集時，其串行計算方法的時間復雜度比較高，處理能力存在局限性，其在計算數據對象間的距離上遇到瓶頸。

發明內容

本發明提供一種大數據量下基于MapReduce的K-means聚類算法FPGA加速系統，其目的在于克服現有PC機或服務器串行方式執行K-means算法計算復雜度高，速度慢，算法時間開銷大的缺陷，以獲取更快的計算處理速度。

本發明所提供的一種基于MapReduce的K-means聚類算法FPGA加速系統，其特征在于，

該加速系統可模塊化設計，可多個獨立并行設置于集群中實現加速；

所述加速系統包括Map任務數據收發子系統、Map任務加速子系統、Reduce任務數據收發子系統和Reduce任務加速子系統；

所述Map任務數據收發子系統傳送來自PCIe端的對應數據給所述Map任務加速子系統，并將所述Map任務加速子系統的計算結果數據回傳給PCIe端；

所述Reduce任務數據收發子系統傳送來自所述PCIe端的對應數據給所述Reduce任務加速子系統，并將所述Reduce任務加速子系統最終計算結果回傳給PCIe端；

所述Reduce任務加速子系統完成K-means算法中單個MapReduce任務的Reduce計算階段，即計算K個類簇的聚類中心；

所述Map任務加速子系統完成所述K-means算法中單個MapReduce任務的Map計算階段，即計算數據對象與K個所述聚類中心的距離，并將所述數據對象指派到一個距離其最近的聚類中心所在的類簇。

進一步地，所述Map任務數據收發子系統和所述Reduce任務數據收發子系統的組成都包括各自的交互接口模塊、數據讀取模塊和數據發送模塊；

所述Map任務數據收發子系統中的數據讀取模塊、數據發送模塊與所述外部PCIe端相連，所述Map任務加速子系統與所述Map任務數據收發子系統中的數據讀取模塊相連，所述Map任務數據收發子系統中的數據發送模塊與所述Map任務加速子系統相連；所述Map任務數據收發子系統中的交互接口模塊與所述外部PCIe端相連，所述Map任務加速子系統與所述Map任務數據收發子系統中的交互接口模塊相連；