本文關(guān)鍵詞：針對(duì)廣度優(yōu)先搜索算法的多核處理器定制優(yōu)化

  更多相關(guān)文章： 廣度優(yōu)先搜索 多核處理器 定制處理器

【摘要】：目前，高能耗已經(jīng)嚴(yán)重制約了高性能計(jì)算機(jī)的發(fā)展，因此處理器體系結(jié)構(gòu)的設(shè)計(jì)越來(lái)越注重性能功耗比的提升，針對(duì)關(guān)鍵應(yīng)用進(jìn)行體系結(jié)構(gòu)的定制已成為技術(shù)發(fā)展趨勢(shì)之一。另一方面，圖數(shù)據(jù)處理的應(yīng)用越來(lái)越廣泛，廣度優(yōu)先搜索（BFS）算法作為圖數(shù)據(jù)處理的基礎(chǔ)算法之一，重要性日益凸顯。 隨著多核/眾核處理器體系結(jié)構(gòu)的發(fā)展，越來(lái)越多的處理器核心將被集成到一個(gè)芯片上。在片上多核處理器（CMP）中運(yùn)行廣度優(yōu)先搜索算法，面臨的主要挑戰(zhàn)有：數(shù)據(jù)局部性差帶來(lái)的訪存延時(shí)，并行執(zhí)行帶來(lái)的任務(wù)間負(fù)載不均以及同步開(kāi)銷等。對(duì)此，本文采用軟硬件協(xié)同設(shè)計(jì)的方法，提出了一個(gè)在較大規(guī)模片上多核處理器上實(shí)現(xiàn)高能效、可擴(kuò)展的廣度優(yōu)先搜索的方案。1）將廣度優(yōu)先搜索算法訪存密集部分和計(jì)算密集部分劃分為兩個(gè)階段，用較多的內(nèi)核或線程來(lái)執(zhí)行相對(duì)較慢的訪存，掩蓋訪存延時(shí)并實(shí)現(xiàn)訪存與計(jì)算的并行；同時(shí)，對(duì)訪存和計(jì)算兩個(gè)部分分別采用不同的數(shù)據(jù)劃分方法，在避免鎖的同時(shí)達(dá)到較好的負(fù)載均衡性。2）針對(duì)廣度優(yōu)先搜索算法對(duì)處理器核心進(jìn)行定制，用可快速訪問(wèn)的片上存儲(chǔ)取代最后一級(jí)緩存，用于存儲(chǔ)頻繁訪問(wèn)的離散數(shù)據(jù)，在提高性能的同時(shí)降低了功耗。3）構(gòu)建快速的片上網(wǎng)絡(luò)實(shí)現(xiàn)數(shù)據(jù)在處理器核心之間的快速傳輸。 實(shí)驗(yàn)結(jié)果表明，在體系結(jié)構(gòu)的支持下，經(jīng)過(guò)適當(dāng)?shù)乃惴ㄔO(shè)計(jì)，可以在低功耗CMP上實(shí)現(xiàn)高效率的圖數(shù)據(jù)處理。使用16個(gè)Xtensa處理器核心構(gòu)建的片上多核處理器模型進(jìn)行仿真測(cè)試，執(zhí)行2階段并行BFS算法，相對(duì)于Intel Xeon X5560處理器(相同的CMOS工藝)運(yùn)行Graph500OpenMP基準(zhǔn)測(cè)試程序，以10%的面積、1.6%的功耗，可以達(dá)到90%的圖遍歷性能，，性能功耗比提高了41.98倍。
【關(guān)鍵詞】：廣度優(yōu)先搜索 多核處理器 定制處理器
【學(xué)位授予單位】：清華大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2014
【分類號(hào)】：TP332
【目錄】：

• 摘要3-4
• Abstract4-7
• 第1章 引言7-13
• 1.1 能耗成為制約高性能計(jì)算機(jī)發(fā)展的重要因素7
• 1.2 使用定制處理器構(gòu)建高性能計(jì)算機(jī)系統(tǒng)7-9
• 1.3 圖數(shù)據(jù)處理日益重要9-10
• 1.4 大規(guī)模圖數(shù)據(jù)處理對(duì)高性能計(jì)算機(jī)的挑戰(zhàn)10-11
• 1.5 本文貢獻(xiàn)11
• 1.6 論文結(jié)構(gòu)11-13
• 第2章 相關(guān)工作介紹13-20
• 2.1 幾種針對(duì)特定應(yīng)用的定制處理器系統(tǒng)介紹13-17
• 2.1.1 Blue Gene13-14
• 2.1.2 Green Flash14-15
• 2.1.3 Anton15-16
• 2.1.4 MD Grape16-17
• 2.2 圍繞廣度優(yōu)先搜索算法進(jìn)行的研究17-19
• 2.2.1 針對(duì)多核處理器的研究17
• 2.2.2 在 Cray MTA 2 平臺(tái)上的研究17-18
• 2.2.3 在 GPU 上進(jìn)行圖數(shù)據(jù)處理18
• 2.2.4 在 Intel MIC 平臺(tái)上的研究18-19
• 2.3 本章小結(jié)19-20
• 第3章 基于 Xtensa 的定制處理器工具和環(huán)境20-33
• 3.1 Xtensa 處理器定制工具20-26
• 3.1.1 Xtensa 處理器指令集基本配置22-24
• 3.1.2 Xtensa 處理器的流水線24-25
• 3.1.3 Xtensa 處理器的存儲(chǔ)系統(tǒng)25-26
• 3.2 Tensilica 指令擴(kuò)展（TIE）語(yǔ)言介紹26-32
• 3.2.1 指令部分的擴(kuò)展和定制27-30
• 3.2.2 接口部分的定制30-32
• 3.3 本章小結(jié)32-33
• 第4章 并行廣度優(yōu)先搜索算法設(shè)計(jì)優(yōu)化33-45
• 4.1 廣度優(yōu)先搜索算法33-34
• 4.1.1 圖數(shù)據(jù)處理的特點(diǎn)33-34
• 4.1.2 廣度優(yōu)先搜索（BFS）算法34
• 4.2 針對(duì)廣度優(yōu)先搜索的優(yōu)化策略及算法設(shè)計(jì)34-44
• 4.2.1 算法使用的主要數(shù)據(jù)結(jié)構(gòu)35
• 4.2.2 并行 BFS 算法35-37
• 4.2.3 分段并行 BFS 算法37-42
• 4.2.4 負(fù)載均衡42-44
• 4.3 本章小結(jié)44-45
• 第5章 處理器定制優(yōu)化及多核互聯(lián)環(huán)境45-65
• 5.1 影響算法的因素45-47
• 5.1.1 內(nèi)存延遲的影響45-46
• 5.1.2 取數(shù)與計(jì)算的平衡46-47
• 5.2 多核互聯(lián)仿真47-54
• 5.2.1 SystemC47-48
• 5.2.2 XTSC 工具集48-51
• 5.2.3 多核處理器的存儲(chǔ)系統(tǒng)實(shí)現(xiàn)51-52
• 5.2.4 處理器核間互聯(lián)網(wǎng)絡(luò)實(shí)現(xiàn)52-54
• 5.3 處理器核心設(shè)計(jì)54-61
• 5.3.1 指令集定制55-56
• 5.3.2 存儲(chǔ)系統(tǒng)定制56-58
• 5.3.3 流水線定制58-59
• 5.3.4 指令擴(kuò)展（TIE）59-61
• 5.4 多核處理器性能評(píng)估61-63
• 5.5 本章小結(jié)63-65
• 第6章 總結(jié)與展望65-67
• 6.1 總結(jié)65-66
• 6.2 展望66-67
• 參考文獻(xiàn)67-69
• 致謝69-70
• 個(gè)人簡(jiǎn)歷、在學(xué)期間發(fā)表的學(xué)術(shù)論文與研究成果70

【共引文獻(xiàn)】

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

1 黎軍;張賢惠;;鋰離子電池技術(shù)中的計(jì)算設(shè)計(jì)方法進(jìn)展[J];科研信息化技術(shù)與應(yīng)用;2012年01期

2 吳超;馬路遙;黃牛;;高性能分子動(dòng)力學(xué)模擬在生物大分子結(jié)構(gòu)和功能研究中的應(yīng)用[J];科研信息化技術(shù)與應(yīng)用;2010年04期

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

1 楊矯云;大規(guī)模生物序列分析的高性能算法和模型[D];中國(guó)科學(xué)技術(shù)大學(xué);2014年

2 吳云劍;分子動(dòng)力學(xué)模擬在幾類重要蛋白研究中的應(yīng)用[D];吉林大學(xué);2014年

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

1 牟麗蓉;改進(jìn)的AMBER力場(chǎng)研究Trp-cage的折疊機(jī)理[D];華東師范大學(xué);2014年

2 程亦超;GPU上圖處理并行框架的設(shè)計(jì)與實(shí)現(xiàn)[D];中國(guó)科學(xué)技術(shù)大學(xué);2015年

本文編號(hào)：1088996