面向大規(guī)模查詢處理的GPU緩存框架設(shè)計(jì).pdf

1、隨著搜索引擎面臨越來(lái)越大的性能壓力，使用現(xiàn)代圖形處理器(Graphic Processing Units)進(jìn)行搜索引擎查詢處理加速被證明是一個(gè)有效提高搜索引擎效率的途徑。GPU的眾核架構(gòu)十分有利于加速查詢處理算法。但是，由于搜索引擎需要處理的數(shù)據(jù)量日益增長(zhǎng)，GPU有限的顯存空間限制了它在這個(gè)領(lǐng)域的應(yīng)用。在本文中，我們提出一種面向大規(guī)模查詢處理的GPU緩存框架。該框架使得在GPU上處理遠(yuǎn)大于顯存空間的倒排索引成為可能。另一方面，我們注意到

2、，在查詢處理中應(yīng)用提前停止算法（early termination）后，大部分倒排鏈表只被部分地訪問(wèn)到?；诖?，我們提出了一種基于倒排鏈表剪枝的GPU靜態(tài)緩存算法。該算法只緩存倒排鏈表中被頻繁訪問(wèn)到的部分，使得顯存中能夠容納更多的鏈表。
　　為了提高在剪枝索引上的查詢效率，我們?cè)?GPU上實(shí)現(xiàn)了數(shù)據(jù)并行的查詢處理算法，包括鏈表求交、top-k排序和提前停止算法等多個(gè)步驟。對(duì)比于CPU查詢處理算法，GPU算法達(dá)到11倍的加速比。此外

3、，為了保證在剪枝索引上進(jìn)行的查詢處理的結(jié)果是正確、完整的，我們提出了一種GPU-CPU協(xié)同查詢處理的方案。
　　作為一種靜態(tài)緩存策略，我們提出的緩存算法需要將一部分的顯存預(yù)留作為存儲(chǔ)緩存失效數(shù)據(jù)的臨時(shí)存儲(chǔ)空間（緩沖區(qū)空間）。實(shí)驗(yàn)表明，緩存空間和緩沖區(qū)空間的大小比例對(duì)于查詢處理的性能至關(guān)重要。因此，我們從理論上討論并分析了顯存空間的劃分問(wèn)題并提出了兩種尋找最優(yōu)劃分經(jīng)驗(yàn)值的方法。
　　實(shí)驗(yàn)表明，我們提出的 GPU查詢處理緩存框架