PGrid(Parallel Grid,并行格网)是一种基于空间划分并被广泛应用到基于位置的服务(Location-Based Service,LBS)的主存索引结构。随着对象数量的增加,与位置相关的更新负荷和查询负荷给LBS的服务器端性能提出严重的挑战。尤其是查询负荷,因查询请求的增多和查询范围的扩大两方面的作用,造成巨大的工作量。用于通用计算GPU(GPGPU)因其强大的并行计算能力而被应用于越来越广泛的大规模计算任务,其中包括PGrid查询。已提出的利用GPU处理PGrid查询的方法相较以往的用CPU处理PGrid查询的串行或并行方法有显著的性能提升。然而因为传统的基于查询的任务划分方式未能迎合GPU的线程执行以及内存访问特性,存在大量线程分歧,使得在查询范围较大时执行速度缓慢;并且没有提供负载均衡策略,使得在面临不规则查询负荷时GPU性能恶化。本文提出一种基于Cell进行任务划分的GPU执行PGrid查询的算法(Cell-Oriented PGrid,COPGrid),这种新型的任务组织框架配合虚拟分组方法消除线程分歧,并且聚集分组内线程的内存访问,从而提高GPU的执行效率;并且通过抢占式线程调度和动态并行化方法有效的解决了线程的负载均衡问题。实验结果表明,与传统的GPU执行方式相比,本文提出的调度策略可以取得一个数量级的性能优势。