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

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

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

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

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

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

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