Accelerating R-tree In Cluster Storage Structure Using GPU

Data size is growing rapidly with the development of software industry because software is penetrating the whole society with the low marginal cost.However,computer and platform technology is not developing as fast as software in terms of performance and volume.To meet the performance requirement in real-time applications,quite a few tree data structures are provided to meet the speed of response demands at the low I/O function condition.Meanwhile with the slowing down generic IC frequency development,SIMD is used in the field of heterogeneous computing and tends to more and more popular based on inherent data parallel processing pipeline.Compared with SISD device SIMD device has distinct advantage of consumption as well as speed when running some particular algorithms.Therefore through analyzing the relationship between SP and memory in GPU and studying the main functions algorithm and geometry of R-tree a kind of parallel R-tree has been proposed which can be accelerated by multi-core GPU running SIMD instruction.Then the data structure with accelerating strategy and the major tree operation algorithms including search/delete/insert/split functions have been paralleled by the definition of parallel R-tree.Theoretical speed up ratio of these paralleled algorithms has been calculated and parallel parameters have been set to get the practical speed up ratio.The major contribution of this paper is that the parallel R-tree are able to achieve about 80 of speedup ratio of search and delete functions as well as about 90 speedup ratio of insert and split functions compared with existing R-tree.In addition,the standard deviation of insert and splitfunctions timing has been improved greatly at about 450 speedup ratio.These features help R-tree to cost less file I/O performance and trend to a dynamic data structure.