本文選題：多核　切入點：任務隊列模型　出處：《昆明理工大學》2012年碩士論文　論文類型：學位論文

【摘要】：隨著國民經(jīng)濟信息化步伐的加快,空間信息的處理在人類社會經(jīng)濟發(fā)展和國防安全等眾多領域發(fā)揮著越來越重要的作用。數(shù)字城市、數(shù)字流域、數(shù)字企業(yè)、數(shù)字文化遺產、移動定位服務、虛擬現(xiàn)實與三維動態(tài)可視化等應用的實現(xiàn)均離不開海量空間信息的快速存取與處理。而海量空間信息的存取和處理即是數(shù)據(jù)密集型操作也是CPU密集型操作,隨著摩爾定律在CPU主頻提高上遭遇失效后,雙核CPU出現(xiàn)了,在一個芯片內集成多個運算核的技術得到了迅猛發(fā)展。在多核平臺上,線程將是真正的并行執(zhí)行,而不是單核平臺上的時間片輪轉,各線程的負載平衡(也即CPU的負載平衡)及緩存的利用效率將成為程序能否充分發(fā)揮多核性能的關鍵。但傳統(tǒng)的串行算法并不能很好地滿足這個要求�；诙嗪似脚_的并行算法研究正形成一個新的熱點。 本文正是在這個背景下系統(tǒng)地分析了多核技術與R樹索引發(fā)展的概況以及趨勢,對比了多核平臺與單核平臺的區(qū)別、基于多核的多線程技術與基于單核的多線程技術的區(qū)別,以及未來多核技術在算法發(fā)展過程中的地位和作用。同時對針對于多核的并行模型進行了分析,闡述了剛成為OpenMP3.0標準的任務隊列模型的原理,該模型的任務調度策略能夠對傳統(tǒng)難以并行化的動態(tài)數(shù)據(jù)結構和遞歸算法等復雜結構的進行并行化,并且得到比較好的負載平衡。本文在分析該模型原理的基礎上對其應用于R樹的窗口查詢算法的可行性進行了一個探討。并提出了基于OpenMP隊列模型的R樹窗口查詢算法的改進優(yōu)化。最后在雙核平臺上對提出的改進算法進行實驗。得出了在各種不同的數(shù)據(jù)量及查詢窗口下,改進算法的性能一般能比原來提高20%左右的結論。
[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.
【學位授予單位】：昆明理工大學
【學位級別】：碩士
【學位授予年份】：2012
【分類號】：TP332;TP301.6

【參考文獻】

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

1 陳海波,王申康;R-tree的查詢代價模型分析及算法改進[J];計算機輔助設計與圖形學學報;2003年03期

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

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

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

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

，

本文編號：1652528