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

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

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

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