Spatial Data Indexing And Performance Optimixation On Shared Memory Architecture

For a long time, scientific computing, Internet data processing, multimedia, and other fields promote parallel computing to the higher performance, lower cost, more flexible and diverse to satisfy the needs of different parallel applications. The amount of data which is related to IR applications is increasing all the time, with the increas-ing of query difficulty and the number of queries which are to response in realtime. Therefore, these application systems and services must have a strong supporting par-allel computing platform. Spatial data information retrieval is a hot topic in IR field. With the widely applying of cell phones, PDAs, GPS devices and other moving sen-sors, more and more applications have to manage moving objects. In the near future, computing will be ubiquitous, will need to manage a large amount of location related objects, both moving objects and objects that keep stationary. There are various Loca-tion Based Services(LBS), such as location-based cell phone services, intelhgent traffic control system, intelligent monitor system, wireless sensor network systems and so on. In these application systems, the data scale of most systems is far beyond the single CPU processing power, and is increasing rapidly. This thesis is mainly on spatial indexing and querying on parallel platforms, and related parallel optimization methods, especially parallel optimization with both thread level parallelization(TLP) and instruction level parallelization(ILP), concurrent access-ing index of large scale moving objects, concurrent continuous query, and concurrent controls with different locks and lock-free methods. These studies can effectively in-crease application’s performance on parallel computer, which are valuable in theory and practice.Specifically, the main contents and contributions of this dissertation are as follows.(1) GKd-tree index on shared memory systems This dissertation surveys the related works about moving objects indexing algorithms, and toward the deficiencies of gird and kd-tree index in main memory, this dissertation purpose a grid and Kd-tree hybrid index structure, GKd-tree, which gives better computing complexity and improves the performance of regional-based indexing for moving object indexing. Meanwhile, we designed concurrency control in GKd-tree.(2)"Query As Index" method in spatial continuous query In the application which involves moving object management and querying, many query is continuous, and this continuity can be used to optimize the query performance. We studied that in the previous works about continuous query, index and query results are separated, which can bring redundancy and synchronization overhead. So, this dissertation proposes a "Query As Index" method, which unit index and query in the same index structure. This new index, together with an auxiliary index on object ID, can reduce the computing complexity of update and query operations, and make concurrency control more convenient. Experiments show that this method gives obvious improvement on query performance and throughput.(3) fine-grain lock and lock-free concurrent control method on moving object management In the original index of concurrent mobile objects, a significant problem is the coarse-grain lock granularity, which is not very suitable for large-scale concurrent operations. The use of fine-grained locking can reduce the scope of concurrent confliction so that improve the degree of concurrency; By using CPU CAS instruc-tion, this dissertation designed a lock-free concurrency control for object location updating between different index regions. Using fine-grain lock and lock-free con-currency control, as well coarse-grain lock when the index structure is changed, we can get more flexible concurrency control, and more suitable to the various applications.(4) The parallelization method with both TLP and SIMD ILP In this dissertation we studied thread-level parallelism(TLP) and instruction-level parallelism(ILP), and their optimizations. Using both TLP and ILP, we can fully utilize the CPU multi-core parallelism and CPU SIMD instruction parallelism. Es-pecially in ILP, SIMD instruction can eliminate the random branches which cannot be predicted efficiently by CPU branch prediction, and convert the branch instruc-tion into SIMD arithmetic instruction. The method is applied to large-scale image features extraction, with TLP in high-level and ILP in low level, and we creatively eliminate a number of program hot spots by SIMD. The experiments show that TLP and ILP with specificate optimization give a much better performance together.