本文關(guān)鍵詞：大規(guī)模并行排序?qū)W習(xí)算法研究，由筆耕文化傳播整理發(fā)布。

【摘要】：搜索引擎可以幫助用戶查找相關(guān)的信息,搜索引擎返回的搜索結(jié)果決定了搜索引擎的質(zhì)量,因此,如何獲得最優(yōu)的搜索結(jié)果,以使得用戶得到與自己所請(qǐng)求的數(shù)據(jù)最相關(guān)的結(jié)果就顯得尤其重要,排序?qū)W習(xí)的出現(xiàn)為解決這一問題提供了新的思路,它可以通過對(duì)用戶所要檢索的信息進(jìn)行必要的排序,按與用戶的請(qǐng)求的相關(guān)度輸出相關(guān)信息。雖然傳統(tǒng)的排序?qū)W習(xí)算法可以很好地解決小規(guī)模文本的排序問題,然而由于互聯(lián)網(wǎng)行業(yè)的快速發(fā)展,互聯(lián)網(wǎng)信息總量不斷地膨脹,傳統(tǒng)的排序?qū)W習(xí)算法無法有效實(shí)時(shí)地處理大規(guī)模數(shù)據(jù),因此,本文使用兩種并行編程模式分別對(duì)排序?qū)W習(xí)算法進(jìn)行加速。本文的主要研究內(nèi)容如下:(1)選擇OpenCL(Open Computing Language)并行計(jì)算模型來加速本文算法,同時(shí)介紹了排序支撐矢量機(jī)算法(Ranking Support Vector Machine,RSVM)以及序貫最小化算法(Sequential Minimal Optimization,SMO)的相關(guān)知識(shí)并詳細(xì)分析SMO算法的具體步驟,根據(jù)GPU(Graphic Processing Unit)硬件架構(gòu)的特點(diǎn)分析串行算法,設(shè)計(jì)了相應(yīng)的并行算法流程,對(duì)算法中的可并行部分采用OpenCL進(jìn)行編程加速,實(shí)驗(yàn)結(jié)果表明與串行排序支撐矢量機(jī)算法相比,并行排序支撐矢量機(jī)算法的加速性能最高提升了90多倍。同時(shí)為了驗(yàn)證OpenCL程序的可移植性,將OpenCL并行程序移植到多種異構(gòu)設(shè)備中,并對(duì)基于OpenCL的并行排序?qū)W習(xí)算法在各個(gè)設(shè)備的性能差異進(jìn)行了詳細(xì)分析。(2)將基于OpenCL的并行排序支撐矢量機(jī)算法擴(kuò)展到多GPU下運(yùn)行,同時(shí)對(duì)多GPU實(shí)施過程中的同步問題進(jìn)行了詳細(xì)分析,運(yùn)用一種有效的同步方式減少了多個(gè)設(shè)備之間的同步開銷,在多GPU上運(yùn)行的結(jié)果表明并行算法的加速性能相對(duì)于單GPU又有了進(jìn)一步的提升。(3)利用多線程并行編程模式OpenMP(Open Multiple Processing)將排序支撐矢量機(jī)算法并行化,并在多核CPU和Intel MIC(Many Integrated Core)上進(jìn)行實(shí)驗(yàn),結(jié)果表明基于OpenMP的并行排序支撐矢量機(jī)算法在多核CPU與MIC上都取得了優(yōu)異的加速效果。同時(shí)比較了基于OpenCL和OpenMP的并行排序支撐矢量機(jī)算法在多核CPU與MIC上的性能,分析了兩種編程模式的差異。
【關(guān)鍵詞】：排序?qū)W習(xí) 并行計(jì)算 OpenCL OpenMP 可移植性
【學(xué)位授予單位】：西安電子科技大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2014
【分類號(hào)】：TP391.3;TP18
【目錄】：

• 摘要5-6
• ABSTRACT6-10
• 符號(hào)對(duì)照表10-11
• 縮略語對(duì)照表11-14
• 第一章 緒論14-20
• 1.1 相關(guān)研究背景14-15
• 1.2 國內(nèi)外研究現(xiàn)狀15-18
• 1.2.1 排序?qū)W習(xí)算法的研究現(xiàn)狀15-16
• 1.2.2 國內(nèi)外并行計(jì)算研究現(xiàn)狀16-18
• 1.3 本文主要研究內(nèi)容18-19
• 1.4 本文組織架構(gòu)19-20
• 第二章 并行排序?qū)W習(xí)算法相關(guān)知識(shí)概述20-32
• 2.1 排序?qū)W習(xí)算法20-25
• 2.1.1 排序?qū)W習(xí)概念20-22
• 2.1.2 排序支撐矢量機(jī)22-24
• 2.1.3 排序?qū)W習(xí)評(píng)價(jià)指標(biāo)24-25
• 2.2 并行硬件架構(gòu)25-27
• 2.2.1 GPU架構(gòu)25-26
• 2.2.2 Intel MIC眾核架構(gòu)26-27
• 2.3 并行編程模型27-29
• 2.3.1 OpenCL模型27-29
• 2.3.2 OpenMP模型29
• 2.4 本章小結(jié)29-32
• 第三章 基于GPU的OpenCL并行排序?qū)W習(xí)算法32-52
• 3.1 序貫最小化算法的并行性分析32-35
• 3.2 基于單GPU的并行排序支撐矢量機(jī)算法35-38
• 3.3 基于單GPU的PRSVM算法實(shí)驗(yàn)結(jié)果與分析38-44
• 3.3.1 LETOR數(shù)據(jù)集38-39
• 3.3.2 實(shí)驗(yàn)環(huán)境39-40
• 3.3.3 單GPU上的實(shí)驗(yàn)結(jié)果分析40-41
• 3.3.4 OpenCL程序可移植性實(shí)驗(yàn)分析41-44
• 3.4 基于多GPU的并行排序支撐矢量機(jī)44-50
• 3.4.1 基于多GPU的PRSVM算法實(shí)施細(xì)節(jié)44-47
• 3.4.2 多設(shè)備間的線程同步47-48
• 3.4.3 多GPU上的實(shí)驗(yàn)結(jié)果分析48-50
• 3.5 本章小結(jié)50-52
• 第四章 基于多核與眾核的OpenMP并行排序?qū)W習(xí)算法52-62
• 4.1 基于多核CPU的OpenMP并行排序支撐矢量機(jī)實(shí)施細(xì)節(jié)52-54
• 4.2 基于MIC的Open MP并行排序支撐矢量機(jī)實(shí)現(xiàn)與優(yōu)化54-55
• 4.3 實(shí)驗(yàn)結(jié)果與分析55-61
• 4.3.1 實(shí)驗(yàn)環(huán)境55-56
• 4.3.2 基于多核CPU與MIC的實(shí)驗(yàn)結(jié)果分析56-59
• 4.3.3 基于OpenCL和OpenMP的PRSVM算法性能比較分析59-61
• 4.4 本章小結(jié)61-62
• 第五章 總結(jié)與展望62-64
• 5.1 本文工作總結(jié)62-63
• 5.2 未來工作展望63-64
• 參考文獻(xiàn)64-68
• 致謝68-70
• 作者簡介70-71

【相似文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前10條

1 朱銳;徐友云;蔡躍明;;低密度奇偶校驗(yàn)碼的構(gòu)造[J];軍事通信技術(shù);2005年04期

2 劉星成;程浩輝;;基于PEG算法的準(zhǔn)循環(huán)LDPC碼構(gòu)造方法研究[J];電路與系統(tǒng)學(xué)報(bào);2009年04期

3 鄭斌;李涓子;;一種基于FP-Growth的改進(jìn)算法[J];平頂山工學(xué)院學(xué)報(bào);2008年04期

4 朱延廣;梅珊;趙雯;朱一凡;;支持復(fù)雜產(chǎn)品總體優(yōu)化設(shè)計(jì)的多算法協(xié)作優(yōu)化框架研究[J];系統(tǒng)仿真學(xué)報(bào);2007年11期

5 白洪濤,孫吉貴,焦洋,徐長青;網(wǎng)絡(luò)優(yōu)化算法的實(shí)現(xiàn)與比較[J];吉林大學(xué)學(xué)報(bào)(信息科學(xué)版);2002年02期

6 劉康,余玲;蟻群算法及其連續(xù)優(yōu)化算法初析[J];四川輕化工學(xué)院學(xué)報(bào);2004年01期

7 黃琪;李丹;汪洋;張欽宇;;一種優(yōu)化LDPC碼環(huán)分布的改進(jìn)算法[J];通信技術(shù);2010年05期

8 徐艷;董濤;;一種防火墻規(guī)則沖突快速檢測(cè)算法[J];計(jì)算機(jī)技術(shù) 與發(fā)展;2013年09期

9 張磊;沈夏炯;韓道軍;安廣偉;;基于同義概念的概念格縱向合并算法[J];計(jì)算機(jī)工程與應(yīng)用;2007年02期

10 謝廷婷;;頻繁集挖掘算法研究[J];計(jì)算機(jī)與現(xiàn)代化;2007年03期

中國重要會(huì)議論文全文數(shù)據(jù)庫 前2條

1 潘志明;鄭駿;錢衛(wèi)寧;周傲英;;構(gòu)造XML相似相關(guān)結(jié)構(gòu)庫的一種有效方法[A];第二十屆全國數(shù)據(jù)庫學(xué)術(shù)會(huì)議論文集（技術(shù)報(bào)告篇）[C];2003年

2 林景亮;董槐林;姜青山;吳書;;一種基于新增閾值的頻繁模式挖掘算法[A];第二十三屆中國數(shù)據(jù)庫學(xué)術(shù)會(huì)議論文集（研究報(bào)告篇）[C];2006年

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

1 張磊;基于概念格的角色工程相關(guān)算法研究[D];哈爾濱工業(yè)大學(xué);2015年

2 孟靜;新型Krylov子空間算法及其應(yīng)用研究[D];電子科技大學(xué);2015年

3 唐益明;（1，，2，2）型異蘊(yùn)涵泛三I算法及其應(yīng)用研究[D];合肥工業(yè)大學(xué);2011年

4 牛云云;求解計(jì)算困難問題的膜計(jì)算模型與算法研究[D];華中科技大學(xué);2012年

5 李冬冬;基因組序列標(biāo)注的算法與理論研究[D];國防科學(xué)技術(shù)大學(xué);2004年

6 周琨;航空公司航班運(yùn)行調(diào)度模型與算法研究[D];南京航空航天大學(xué);2012年

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

1 閆銘;基于度量學(xué)習(xí)的不完整數(shù)據(jù)聚類方法研究[D];哈爾濱工業(yè)大學(xué);2015年

2 張小瓊;基于改進(jìn)螢火蟲群優(yōu)化算法的BP神經(jīng)網(wǎng)絡(luò)研究[D];廣西大學(xué);2015年

3 李俊杰;基于蟻群算法的聚類區(qū)分器設(shè)計(jì)研究[D];電子科技大學(xué);2014年

4 艾慧;天波雷達(dá)電離層污染校正與測(cè)高算法研究[D];電子科技大學(xué);2015年

5 陳紅強(qiáng);大規(guī)模并行排序?qū)W習(xí)算法研究[D];西安電子科技大學(xué);2014年

6 白鷺;基于自適應(yīng)人工免疫進(jìn)化的網(wǎng)格聚類算法研究[D];沈陽大學(xué);2010年

7 紀(jì)彤坤;概念格Chein算法的研究與改進(jìn)[D];華南理工大學(xué);2012年

8 錢偉強(qiáng);一種基于改進(jìn)粒子群和K均值結(jié)合的聚類算法[D];西安電子科技大學(xué);2011年

9 張菲;蜂群混合算法[D];西安電子科技大學(xué);2013年

10 陸麗娟;強(qiáng)跳躍顯露模式挖掘算法及其應(yīng)用[D];湖南大學(xué);2011年

  本文關(guān)鍵詞：大規(guī)模并行排序?qū)W習(xí)算法研究，由筆耕文化傳播整理發(fā)布。

本文編號(hào)：333373