Optimization On Queries Of Moving-objects In Heterogeneous Environment

Parallel grid(PGrid)is an effective main-memory indexing technique widely used in location based service(LBS).With the increasing number of moving objects in LBS,the location-related update and query workloads put rigorous challenge to the server-side infrastructures,especially the query workload for its amount of query request and the workload of single request.General purpose graphic processing unit(GPGPU),as a parallel platform that offers tremendous computing power has been used in many fields,including the PGrid queries.The proposed implementation of PGrid queries for GPU has achieved a performance improvement compared with traditional implementations for CPU.However,it suffers from severe workload imbalance when moving objects distribute uneven,besides,thread divergence and poorly coalesced memory access still exist.This paper presents COPGrid(Cell-Oriented PGrid),an efficient PGrid query implementation for GPU based on a new task organization form(Cell-Oriented)and three different strategies,which solves the thread divergence and coalesces the memory accesses within virtual warp threads by the Cell-Oriented task organization form and virtual warp technique and leads to workload balance by dynamic parallelism and thread preemption scheduling.Experiment results show that,as compared to the traditional GPU implementation,the proposed adaptive scheduling strategies improve the query throughput by one order of magnitude.