共享內(nèi)存并行系統(tǒng)上空間數(shù)據(jù)檢索及優(yōu)化研究.pdf

1、長久以來，科學(xué)計算、企業(yè)數(shù)據(jù)處理、多媒體等領(lǐng)域推動并行計算向更高性能、更低成本、更多樣地適應(yīng)需求的方向發(fā)展。隨著信息檢索相關(guān)應(yīng)用中數(shù)據(jù)量的增加，以及查詢難度和需要實時響應(yīng)的查詢數(shù)量的增加，提供相關(guān)信息檢索服務(wù)必須以強有力的并行計算平臺做支撐?？臻g數(shù)據(jù)檢索是信息檢索領(lǐng)域一個快速發(fā)展的領(lǐng)域。隨著手機，掌上電腦、GPS等移動計算設(shè)備及各種移動傳感器的普及使用，越來越多的應(yīng)用需要計算隨時間不斷變化的移動物體信息。在不遠(yuǎn)的未來，計算將無處不在；需

2、要管理大量的位置相關(guān)的物體，既有靜止的對象，也有大量位置不斷變化的移動對象?；谖恢玫姆?wù)相關(guān)應(yīng)用是正是利用了這些空間信息為用戶提供多種多樣的服務(wù)，比如基于位置的手機業(yè)務(wù)和電子商務(wù)；智能交通；智能監(jiān)控系統(tǒng)；無線傳感器網(wǎng)絡(luò)系統(tǒng)等。在多種多樣的應(yīng)用中，大多數(shù)的應(yīng)用的數(shù)據(jù)規(guī)模遠(yuǎn)遠(yuǎn)超出的單CPU的處理能力，而且還會不斷地增加。
　　 本論文主要研究并行平臺上的空間數(shù)據(jù)索引和檢索問題，以及相關(guān)的并行優(yōu)化方法。特別是線程級并行和指令級并行相

3、結(jié)合的并行優(yōu)化方法、共享內(nèi)存系統(tǒng)上支持并發(fā)訪問的大規(guī)模移動對象的索引、支持并發(fā)的移動點持續(xù)查詢、不同粒度的鎖協(xié)議及l(fā)ock-free并發(fā)控制方法。本文針對并行優(yōu)化以及空間數(shù)據(jù)索引的研究，可以有效改善并行平臺上的空間數(shù)據(jù)索引的相關(guān)應(yīng)用，具有重要的學(xué)術(shù)價值和廣泛的應(yīng)用前景。具體而言，本文的主要研究成果、貢獻和創(chuàng)新點可概括為以下幾點：
　　 (1)研究多核多線程并行和SIMD指令級并行相結(jié)合的方法本文研究了多核平臺上的線程級并行和指令

4、級并行的優(yōu)化方法。線程級并行和指令級并行相結(jié)合，可一以充分利用CPU的多核多線程資源和SIMD指令級并行資源。特別是在指令級并行中，使用SIMD指令，可以把占大量CPU時間的隨機條件分支轉(zhuǎn)化成算術(shù)邏輯指令，從而可以使用指令級并行。該方法應(yīng)用到大規(guī)模圖像特征提取中，并創(chuàng)造性地使用SIMD指令消除了在圖像特征提取中存在的若干程序熱點，使其性能有明顯提升。
　　 (2)提出共享內(nèi)存系統(tǒng)上GKd-樹索引結(jié)構(gòu)移動對象的空間數(shù)據(jù)索引是高效支

5、持移動對象更新和查詢的關(guān)鍵。本文研究了現(xiàn)有的移動對象索引算法，針對內(nèi)存中常用的網(wǎng)格索引和Kd-樹索引的不足，提出了GKd-樹索引結(jié)構(gòu)。對于空間索引的位置查詢操作、位置更新操作和區(qū)域查詢操作有更好的算法復(fù)雜度；并具有便于并行化和支持并發(fā)控制的特性。GKd-樹索引改善了現(xiàn)有的基于區(qū)域劃分的空間移動對象數(shù)據(jù)索引，可以高效地支持大規(guī)模移動對象的并發(fā)檢索。
　　 (3)提出共享內(nèi)存系統(tǒng)上“查詢即索引”的索引結(jié)構(gòu)在移動對象管理的相關(guān)的應(yīng)用中

6、，有很大部分應(yīng)用中查詢是持續(xù)的，可以利用查詢的持續(xù)性對查詢進行優(yōu)化。本文針對原有持續(xù)性索引中索引結(jié)構(gòu)和查詢結(jié)果相分立帶來的冗余和同步等開銷，提出“查詢即索引”的索引結(jié)構(gòu)。新的索引方法將索引和查詢結(jié)果相統(tǒng)一，并且通過使用基于對象ID的輔助索引和空間索引相結(jié)合的方式，降低了持續(xù)查詢的復(fù)雜度，便于并行化和支持并發(fā)控制，使數(shù)據(jù)更新和持續(xù)性查詢的吞吐量、查詢實時性等有明顯提升。
　　 (4)研究并優(yōu)化應(yīng)用于移動對象索引的細(xì)粒度鎖和無鎖化并