圖形處理器對(duì)倒排索引求交運(yùn)算的優(yōu)化

1、中圖分類(lèi)號(hào)：學(xué)校代碼：密級(jí)：公開(kāi)高蕊犬淫碩士學(xué)位論文圖形處理器對(duì)倒排索引求交運(yùn)算的優(yōu)化。答辯委員會(huì)主席評(píng)閱人南開(kāi)大學(xué)研究生院二。一一年五月南開(kāi)大學(xué)學(xué)位論文原創(chuàng)性聲明本人鄭重聲明：所呈交的學(xué)位論文，是本人在導(dǎo)師指導(dǎo)下進(jìn)行研究工作所取得的研究成果。除文中已經(jīng)注明引用的內(nèi)容外，本學(xué)位論文的研究成果不包含任何他人創(chuàng)作的、已公開(kāi)發(fā)表或者沒(méi)有公開(kāi)發(fā)表的作品的內(nèi)容。對(duì)本論文所涉及的研究工作做出貢獻(xiàn)的其他個(gè)人和集體，均已在文中以明確方式標(biāo)明。本學(xué)位論文原創(chuàng)性聲明的法律責(zé)任由本人承擔(dān)。學(xué)位論文作者簽名：昱遮年月日非公開(kāi)學(xué)位論文標(biāo)注說(shuō)明（本頁(yè)表中填寫(xiě)內(nèi)容須打?。└鶕?jù)南開(kāi)大學(xué)有關(guān)規(guī)定，非公開(kāi)學(xué)位論文須經(jīng)指導(dǎo)教師同意

2、、作者本人申請(qǐng)和相關(guān)部門(mén)批準(zhǔn)方能標(biāo)注。未經(jīng)批準(zhǔn)的均為公開(kāi)學(xué)位論文，公開(kāi)學(xué)位論文本說(shuō)明為空白。論文題目圖形處理器對(duì)倒排索引求交運(yùn)算的優(yōu)化申請(qǐng)密級(jí)口限制（年）口秘密（年）口機(jī)密（年）保密期限年月日至年月日審批表編號(hào)批準(zhǔn)日期年月日南開(kāi)大學(xué)學(xué)位評(píng)定委員會(huì)辦公室蓋章（有效）注：限制年（可少于年）：秘密年（可少于年）：機(jī)密年（可少于年）中文摘要中文摘要大型搜索引擎系統(tǒng)每秒鐘都在響應(yīng)著大量的用戶請(qǐng)求。這些查詢請(qǐng)求希望從上百億張網(wǎng)頁(yè)中檢索出最相關(guān)的網(wǎng)頁(yè)集合。隨著互聯(lián)網(wǎng)業(yè)務(wù)的迅猛發(fā)展，搜索引擎系統(tǒng)檢索的信息量和承擔(dān)的計(jì)算負(fù)載正以指數(shù)增長(zhǎng)速度膨脹。為了快速完成這些沉重的任務(wù)壓力，我們利用圖形處理器（）來(lái)完成部分計(jì)

3、算任務(wù)。在本文中，我們探討了幾種新的算法來(lái)加速搜索引擎中的一個(gè)重要且頻繁的操作：倒排索引求交。本文的主要工作包括：為了充分發(fā)揮的計(jì)算潛力，本文設(shè)計(jì)了批次處理模式。在批次模式下，若干個(gè)查詢被綁定為一個(gè)批次發(fā)送到上進(jìn)行并行處理，以此取得較高的系統(tǒng)吞吐率。本文設(shè)計(jì)了查詢線程塊并行策略（）來(lái)實(shí)現(xiàn)這個(gè)批次模型。為了改善負(fù)載均衡的情況，我們?cè)O(shè)計(jì)了線程并行策略（）。在系統(tǒng)負(fù)載較低的情況下，或者應(yīng)該立即處理當(dāng)前到達(dá)的查詢請(qǐng)求，以取得最低的響應(yīng)時(shí)間。為此，本文設(shè)計(jì)了一個(gè)在線調(diào)度算法，用于將當(dāng)前到達(dá)的查詢派發(fā)到能夠最快完成任務(wù)的處理器上。本文將應(yīng)用到倒排索引求交領(lǐng)域。雖然具有一定的誤稱(chēng)率，但本文通過(guò)選擇合適的哈希

4、函數(shù)，將錯(cuò)誤結(jié)果比例控制在很低的水平。實(shí)驗(yàn)顯示，方法符合的并行特征，能夠大幅度提升系統(tǒng)吞吐率。本文分析了倒排索引的數(shù)據(jù)分布特征，總結(jié)出了大部分倒排索引都具備明顯線性形態(tài)的重要結(jié)論。這種線性性質(zhì)來(lái)源于搜索引擎抓取網(wǎng)頁(yè)和分配過(guò)程中的隨機(jī)性和不確定性。為了增強(qiáng)這種線性特征，我們?cè)O(shè)計(jì)了利用隨機(jī)算法進(jìn)行倒排索引重排的策略。在線性性質(zhì)明顯的數(shù)據(jù)集合上，一元線性回歸能夠取得較好的擬合效果。本文在倒排索引數(shù)據(jù)分布的基礎(chǔ)上，設(shè)計(jì)了線性回歸搜索算法。良好的線性性質(zhì)等價(jià)于在倒排索引中的較均勻分布。因此，本文設(shè)計(jì)了哈希分段搜索算法。實(shí)驗(yàn)顯示，線性回歸搜索和哈希分段搜索均能夠?qū)崿F(xiàn)可觀的加速比。關(guān)鍵詞：；搜索引擎；倒排索

5、引，（）：，曲，曲，：；了目錄目錄中文摘要目錄第一章緒論第一節(jié)研究背景第二節(jié)本文主要工作第三節(jié)本文組織結(jié)構(gòu)第二章背景知識(shí)介紹第一節(jié)硬件體系結(jié)構(gòu)。第二節(jié)存儲(chǔ)模型。寄存器（）共享存儲(chǔ)空間（）。只讀存儲(chǔ)空間（）紋理存儲(chǔ)空間（）一全局存儲(chǔ)空間（）第三節(jié)線程模型一第四節(jié)倒排索引的交運(yùn)算第五節(jié)實(shí)驗(yàn)環(huán)境和數(shù)據(jù)集實(shí)驗(yàn)環(huán)境數(shù)據(jù)集百度數(shù)據(jù)集數(shù)據(jù)集特征第三章并行求交計(jì)算框架第一節(jié)查詢的處理模式異步模式同步模式。：目錄第二節(jié)按查詢劃分的粗粒度并行框架第三節(jié)按劃分的細(xì)粒度并行框架第四節(jié)低負(fù)載情況下的動(dòng)態(tài)處理器選擇第四章搜索算法的分析與改造第一節(jié)搜索算法的分析和比較第二節(jié)搜索算法介紹在上的應(yīng)用。哈希函數(shù)的選擇搜索算法的性

6、能第五章倒排索引數(shù)據(jù)分布的分析和利用第一節(jié)倒排索引重排和隨機(jī)化方法第二節(jié)數(shù)據(jù)分布特征。第三節(jié)一元線性回歸第四節(jié)線性回歸加速搜索第五節(jié)哈希分段加速搜索矗第六節(jié)實(shí)驗(yàn)分析第六章總結(jié)和展望第一節(jié)總結(jié)第二節(jié)工作展望參考文獻(xiàn)致謝一個(gè)人簡(jiǎn)歷學(xué)術(shù)論文第一章緒論第一章緒論第一節(jié)研究背景如今的大型商用搜索引擎系統(tǒng)，正處理著日益繁重的計(jì)算任務(wù)。例如，作為全球最大的中文搜索引擎，百度每天接受幾十億次的用戶查詢請(qǐng)求；而垂直搜索領(lǐng)域的翹楚一淘寶，每天處理的查詢數(shù)量也已超過(guò)了十億次。隨著業(yè)務(wù)的迅猛增長(zhǎng)以及對(duì)多元化查詢請(qǐng)求的進(jìn)一步滿足，搜索引擎后臺(tái)的服務(wù)集群，正承受著巨大的壓力。系統(tǒng)效率和結(jié)果質(zhì)量是衡量搜索引擎系統(tǒng)的主要指標(biāo)，而“平均查詢響應(yīng)時(shí)間”則是衡量系統(tǒng)效率的重要指標(biāo)。如果響應(yīng)時(shí)間過(guò)長(zhǎng)則會(huì)傷害到用戶體驗(yàn)，并限制了系統(tǒng)能夠同時(shí)處理的查詢數(shù)量。結(jié)果質(zhì)量的衡量標(biāo)準(zhǔn)是“召回率和“精確度【，前者是搜索結(jié)果中有價(jià)值的相關(guān)網(wǎng)頁(yè)的數(shù)量占互聯(lián)網(wǎng)上所有相關(guān)文檔數(shù)量的比例，它衡量了搜索引擎的查全率；后者