本文關(guān)鍵詞：基于FPGA的聚類(lèi)算法的加速平臺(tái)的研究與設(shè)計(jì)

  更多相關(guān)文章： 聚類(lèi)算法 加速平臺(tái) 片外訪存 加速比 能效比

【摘要】：聚類(lèi)分析在人類(lèi)工作生活中扮演著越來(lái)越重要的角色,目前已被廣泛運(yùn)用于許多不同的領(lǐng)域,如市場(chǎng)調(diào)研、模式識(shí)別、數(shù)據(jù)挖掘、圖像處理、客戶(hù)分割、Web文檔分類(lèi)等。隨著互聯(lián)網(wǎng)和電子商務(wù)的飛速發(fā)展,各行各業(yè)采集、積累或急需處理的數(shù)據(jù)呈現(xiàn)海量式的增長(zhǎng)。海量的數(shù)據(jù)大大降低了聚類(lèi)分析的效率,針對(duì)各種聚類(lèi)算法加速的研究成為了人們探討的重要課題。不同的應(yīng)用領(lǐng)域以及不同類(lèi)型的數(shù)據(jù)集需要使用不同的聚類(lèi)算法才能夠獲得較好的聚類(lèi)效果,由此可見(jiàn)高效實(shí)現(xiàn)多種聚類(lèi)算法是很有必要的。目前聚類(lèi)算法的加速平臺(tái)主要有云計(jì)算平臺(tái)和硬件加速平臺(tái),其中硬件加速平臺(tái)主要有GPU、FPGA以及ASIC。云計(jì)算平臺(tái)采用集群的方式將應(yīng)用進(jìn)行劃分,然后將劃分后的任務(wù)分配到各個(gè)PC節(jié)點(diǎn),各個(gè)節(jié)點(diǎn)處理任務(wù)并將計(jì)算結(jié)果匯總到總機(jī)。這種加速方式需要多個(gè)PC機(jī),而且算法的加速最終受限于網(wǎng)絡(luò)帶寬；硬件加速平臺(tái)利用硬件自身速度快的特點(diǎn),使用硬件來(lái)代替軟件或者CPU來(lái)實(shí)現(xiàn)具體功能邏輯,而且大量的內(nèi)置硬件邏輯部件使得硬件加速平臺(tái)可以更好地采用并行和流水的方式加速算法的執(zhí)行。硬件加速平臺(tái)的加速效果好、不受限于帶寬而且相比云計(jì)算平臺(tái)加速成本更低。綜上,硬件加速平臺(tái)是算法加速的一種有效的加速平臺(tái)。目前,硬件加速器的設(shè)計(jì)大多針對(duì)單一特定的算法,對(duì)加速器的通用性和靈活性的研究很少。雖然GPU提供了解決通用性和靈活性的方法,但是對(duì)通用性和靈活性的支持使得GPU帶來(lái)了高能耗的問(wèn)題,而FPGA會(huì)獲得更好的節(jié)能效果。但是目前基于FPGA的加速器都是針對(duì)特定算法設(shè)計(jì)特定的硬件加速模塊的,使得該硬件加速器僅支持一種算法,大大限制了硬件加速器的通用性和靈活性。能否設(shè)計(jì)一種基于FPGA的硬件加速器,使之能夠支持多種聚類(lèi)算法呢?本文采用軟硬件結(jié)合的方式實(shí)現(xiàn)了一個(gè)基于FPGA的硬件加速系統(tǒng)平臺(tái),它能夠支持K-means、PAM、SLINK、DBSCAN四種聚類(lèi)算法和兩種相似度度量標(biāo)準(zhǔn)。基于對(duì)算法的熱點(diǎn)代碼和局部性的分析,加速器解決了頻繁的片外訪存問(wèn)題,最后通過(guò)提取熱點(diǎn)代碼的公共算子,最大化地平衡了加速器的通用性以及靈活性和加速性能之間的關(guān)系,使得加速器支持通用性和靈活性的同時(shí)又兼顧了加速器的加速性能。為了評(píng)估加速器的性能,將加速器分別與CPU和GPU作了比較,給出了相應(yīng)的加速比和能效比,并測(cè)試與分析了影響加速器加速性能的因素。
【關(guān)鍵詞】：聚類(lèi)算法 加速平臺(tái) 片外訪存 加速比 能效比
【學(xué)位授予單位】：中國(guó)科學(xué)技術(shù)大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類(lèi)號(hào)】：TP311.13
【目錄】：

• 摘要5-6
• ABSTRACT6-15
• 第1章 緒論15-21
• 1.1 課題背景及意義15-16
• 1.2 國(guó)內(nèi)外研究現(xiàn)狀16-18
• 1.3 本文研究?jī)?nèi)容18-19
• 1.4 論文的組織安排19-21
• 第2章 相關(guān)基礎(chǔ)知識(shí)簡(jiǎn)介21-27
• 2.1 算法介紹21-25
• 2.1.1 K-means算法21-22
• 2.1.2 PAM算法22-23
• 2.1.3 SLINK算法23-24
• 2.1.4 DBSCAN算法24-25
• 2.2 硬件加速技術(shù)介紹25-26
• 2.3 本章小結(jié)26-27
• 第3章 加速系統(tǒng)的軟硬件功能劃分27-37
• 3.1 軟硬件協(xié)同設(shè)計(jì)的設(shè)計(jì)流程27-29
• 3.2 熱點(diǎn)代碼分析29-35
• 3.2.1 K-means算法的熱點(diǎn)分析30
• 3.2.2 PAM算法的熱點(diǎn)分析30-31
• 3.2.3 SLINK算法的熱點(diǎn)分析31-32
• 3.2.4 DBSCAN算法的熱點(diǎn)分析32
• 3.2.5 算法軟硬件劃分的結(jié)果32-35
• 3.3 相同代碼的提取和局部性分析35-36
• 3.3.1 相同代碼的提取35
• 3.3.2 局部性分析35-36
• 3.4 本章小結(jié)36-37
• 第4章 硬件加速器的設(shè)計(jì)與實(shí)現(xiàn)37-51
• 4.1 加速器的框架結(jié)構(gòu)介紹37-39
• 4.1.1 加速器的基本框架37-38
• 4.1.2 執(zhí)行單元的內(nèi)部結(jié)構(gòu)38-39
• 4.2 加速方案的選擇39-42
• 4.2.1 并行方式的加速方案39-40
• 4.2.2 流水方式的加速方案40-41
• 4.2.3 加速方案的分析與比較41-42
• 4.3 硬件邏輯單元的設(shè)計(jì)42-48
• 4.3.1 指令集的設(shè)計(jì)42-45
• 4.3.2 指令集的硬件實(shí)現(xiàn)45-48
• 4.4 頻繁片外訪存的解決方案48-50
• 4.5 本章小結(jié)50-51
• 第5章 軟件子系統(tǒng)的設(shè)計(jì)51-57
• 5.1 加速器的操作系統(tǒng)模式51-54
• 5.1.1 操作系統(tǒng)模式下加速器的工作流程51-53
• 5.1.2 數(shù)據(jù)填充53-54
• 5.2 面向用戶(hù)的接口設(shè)計(jì)54-56
• 5.3 本章小結(jié)56-57
• 第6章 加速平臺(tái)的性能測(cè)試與分析57-69
• 6.1 實(shí)驗(yàn)環(huán)境57-58
• 6.2 加速器的性能評(píng)估58-64
• 6.2.1 硬件加速器的加速效果58-62
• 6.2.2 加速器的能耗評(píng)估62-64
• 6.3 影響加速器加速比的因素的測(cè)試與分析64-67
• 6.3.1 數(shù)據(jù)集規(guī)模VS加速效果64-66
• 6.3.2 向量維度VS加速效果66
• 6.3.3 簇的個(gè)數(shù)VS加速效果66-67
• 6.4 誤差分析67-68
• 6.5 本章小結(jié)68-69
• 第7章 總結(jié)和展望69-73
• 7.1 工作總結(jié)69-70
• 7.2 未來(lái)工作展望70-73
• 參考文獻(xiàn)73-77
• 致謝77-79
• 在讀期間參加的科研項(xiàng)目79-81
• 在讀期間的學(xué)術(shù)論文81

【參考文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前5條

1 郎為民;陳凱;張國(guó)峰;;無(wú)監(jiān)督學(xué)習(xí)在認(rèn)知網(wǎng)絡(luò)中的應(yīng)用研究[J];電信快報(bào);2014年02期

2 周濤;陸惠玲;;數(shù)據(jù)挖掘中聚類(lèi)算法研究進(jìn)展[J];計(jì)算機(jī)工程與應(yīng)用;2012年12期

3 趙旭;郝莉;;基于FPGA的實(shí)時(shí)視頻采樣控制器設(shè)計(jì)[J];成都信息工程學(xué)院學(xué)報(bào);2008年03期

4 孫吉貴;劉杰;趙連宇;;聚類(lèi)算法研究[J];軟件學(xué)報(bào);2008年01期

5 賀玲;吳玲達(dá);蔡益朝;;數(shù)據(jù)挖掘中的聚類(lèi)算法綜述[J];計(jì)算機(jī)應(yīng)用研究;2007年01期

中國(guó)碩士學(xué)位論文全文數(shù)據(jù)庫(kù) 前1條

1 白冬艷;數(shù)據(jù)挖掘在煤炭綜合統(tǒng)計(jì)系統(tǒng)的應(yīng)用研究[D];河北工程大學(xué);2010年

，

本文編號(hào)：881344