基于多核平台的R树窗口查询算法优化探讨

发布时间：2018-03-23 07:45

  本文选题：多核　切入点：任务队列模型　出处：《昆明理工大学》2012年硕士论文　论文类型：学位论文

【摘要】：随着国民经济信息化步伐的加快,空间信息的处理在人类社会经济发展和国防安全等众多领域发挥着越来越重要的作用。数字城市、数字流域、数字企业、数字文化遗产、移动定位服务、虚拟现实与三维动态可视化等应用的实现均离不开海量空间信息的快速存取与处理。而海量空间信息的存取和处理即是数据密集型操作也是CPU密集型操作,随着摩尔定律在CPU主频提高上遭遇失效后,双核CPU出现了,在一个芯片内集成多个运算核的技术得到了迅猛发展。在多核平台上,线程将是真正的并行执行,而不是单核平台上的时间片轮转,各线程的负载平衡(也即CPU的负载平衡)及缓存的利用效率将成为程序能否充分发挥多核性能的关键。但传统的串行算法并不能很好地满足这个要求。基于多核平台的并行算法研究正形成一个新的热点。 本文正是在这个背景下系统地分析了多核技术与R树索引发展的概况以及趋势,对比了多核平台与单核平台的区别、基于多核的多线程技术与基于单核的多线程技术的区别,以及未来多核技术在算法发展过程中的地位和作用。同时对针对于多核的并行模型进行了分析,阐述了刚成为OpenMP3.0标准的任务队列模型的原理,该模型的任务调度策略能够对传统难以并行化的动态数据结构和递归算法等复杂结构的进行并行化,并且得到比较好的负载平衡。本文在分析该模型原理的基础上对其应用于R树的窗口查询算法的可行性进行了一个探讨。并提出了基于OpenMP队列模型的R树窗口查询算法的改进优化。最后在双核平台上对提出的改进算法进行实验。得出了在各种不同的数据量及查询窗口下,改进算法的性能一般能比原来提高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

【参考文献】

中国期刊全文数据库 前3条

1 陈海波,王申康;R-tree的查询代价模型分析及算法改进[J];计算机辅助设计与图形学学报;2003年03期

2 张明波,陆锋,申排伟,程昌秀;R树家族的演变和发展[J];计算机学报;2005年03期

3 谈晓军,涂建光;一种自适应的两阶段R树批生成算法[J];武汉大学学报(信息科学版);2003年01期

中国博士学位论文全文数据库 前1条

1 赵春宇;高性能并行GIS中矢量空间数据存取与处理关键技术研究[D];武汉大学;2006年

，

本文编号：1652528