本文選題：多核　切入點(diǎn)：任務(wù)隊(duì)列模型　出處：《昆明理工大學(xué)》2012年碩士論文　論文類型：學(xué)位論文

【摘要】：隨著國(guó)民經(jīng)濟(jì)信息化步伐的加快,空間信息的處理在人類社會(huì)經(jīng)濟(jì)發(fā)展和國(guó)防安全等眾多領(lǐng)域發(fā)揮著越來越重要的作用。數(shù)字城市、數(shù)字流域、數(shù)字企業(yè)、數(shù)字文化遺產(chǎn)、移動(dòng)定位服務(wù)、虛擬現(xiàn)實(shí)與三維動(dòng)態(tài)可視化等應(yīng)用的實(shí)現(xiàn)均離不開海量空間信息的快速存取與處理。而海量空間信息的存取和處理即是數(shù)據(jù)密集型操作也是CPU密集型操作,隨著摩爾定律在CPU主頻提高上遭遇失效后,雙核CPU出現(xiàn)了,在一個(gè)芯片內(nèi)集成多個(gè)運(yùn)算核的技術(shù)得到了迅猛發(fā)展。在多核平臺(tái)上,線程將是真正的并行執(zhí)行,而不是單核平臺(tái)上的時(shí)間片輪轉(zhuǎn),各線程的負(fù)載平衡(也即CPU的負(fù)載平衡)及緩存的利用效率將成為程序能否充分發(fā)揮多核性能的關(guān)鍵。但傳統(tǒng)的串行算法并不能很好地滿足這個(gè)要求�；诙嗪似脚_(tái)的并行算法研究正形成一個(gè)新的熱點(diǎn)。 本文正是在這個(gè)背景下系統(tǒng)地分析了多核技術(shù)與R樹索引發(fā)展的概況以及趨勢(shì),對(duì)比了多核平臺(tái)與單核平臺(tái)的區(qū)別、基于多核的多線程技術(shù)與基于單核的多線程技術(shù)的區(qū)別,以及未來多核技術(shù)在算法發(fā)展過程中的地位和作用。同時(shí)對(duì)針對(duì)于多核的并行模型進(jìn)行了分析,闡述了剛成為OpenMP3.0標(biāo)準(zhǔn)的任務(wù)隊(duì)列模型的原理,該模型的任務(wù)調(diào)度策略能夠?qū)鹘y(tǒng)難以并行化的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)和遞歸算法等復(fù)雜結(jié)構(gòu)的進(jìn)行并行化,并且得到比較好的負(fù)載平衡。本文在分析該模型原理的基礎(chǔ)上對(duì)其應(yīng)用于R樹的窗口查詢算法的可行性進(jìn)行了一個(gè)探討。并提出了基于OpenMP隊(duì)列模型的R樹窗口查詢算法的改進(jìn)優(yōu)化。最后在雙核平臺(tái)上對(duì)提出的改進(jìn)算法進(jìn)行實(shí)驗(yàn)。得出了在各種不同的數(shù)據(jù)量及查詢窗口下,改進(jìn)算法的性能一般能比原來提高20%左右的結(jié)論。
[Abstract]:With the rapid development of the national economy, the processing of spatial information is playing an increasingly important role in many fields, such as the development of human society and economy, national defense security, etc. Digital cities, digital watersheds, digital enterprises, digital cultural heritage, etc. The realization of mobile location service, virtual reality and 3D dynamic visualization is inseparable from the fast access and processing of massive spatial information, which is not only data-intensive but also CPU intensive. With the failure of Moore's law in the main frequency of CPU, the dual-core CPU has emerged, and the technology of integrating multiple operational cores into one chip has developed rapidly. On a multi-core platform, threads will be truly parallel execution. Instead of a time slice rotation on a single core platform, The load balancing of each thread (that is, the load balance of CPU) and the efficiency of cache utilization will be the key to whether the program can give full play to the multi-core performance, but the traditional serial algorithm can not meet this requirement very well. The parallel algorithm of the platform is becoming a new hotspot. Under this background, this paper systematically analyzes the general situation and trend of multi-kernel and R-tree index development, compares the difference between multi-core platform and single-core platform, the difference between multi-core multi-thread technology and single-core multi-threading technology. At the same time, the paper analyzes the parallel model for multi-kernel, and expounds the principle of task queue model which has just become the standard of OpenMP3.0. The task scheduling strategy of the model can parallelize complex structures such as dynamic data structures and recursive algorithms, which are difficult to parallelize. On the basis of analyzing the principle of the model, this paper discusses the feasibility of the window query algorithm applied to R-tree, and puts forward the R-tree window checking based on OpenMP queue model. Finally, the improved algorithm is tested on the dual-core platform. The performance of the improved algorithm is generally 20% higher than the original conclusion.
【學(xué)位授予單位】：昆明理工大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2012
【分類號(hào)】：TP332;TP301.6

【參考文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前3條

1 陳海波,王申康;R-tree的查詢代價(jià)模型分析及算法改進(jìn)[J];計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào);2003年03期

2 張明波,陸鋒,申排偉,程昌秀;R樹家族的演變和發(fā)展[J];計(jì)算機(jī)學(xué)報(bào);2005年03期

3 談曉軍,涂建光;一種自適應(yīng)的兩階段R樹批生成算法[J];武漢大學(xué)學(xué)報(bào)(信息科學(xué)版);2003年01期

中國(guó)博士學(xué)位論文全文數(shù)據(jù)庫(kù) 前1條

1 趙春宇;高性能并行GIS中矢量空間數(shù)據(jù)存取與處理關(guān)鍵技術(shù)研究[D];武漢大學(xué);2006年

，

本文編號(hào)：1652528