Research On GPU-based Computation Method For Line-of-sight Queries

In recent years, the GPU has become an increasingly attractive architecture forsolving compute-intensive problems because of its increased computation power. Inaddition, LOS computation is a compute-intensive work, which possesses strongparallel characteristic. However, in most of existing efficient researches on acceleratingLOS computation using GPU based on culling method, GPU does simple cullingcomputation and CPU does exact LOS computation. So, they cannot take full advantageof GPU power, and CPU cannot concentrate on other urgent task in the simulation.To solve this problem, this paper analysed and studied their GPU parallelismtechnology intensively, with the LOS blockage algorithms in the regular Grid-Postterrain application. The paper main work and innovation includes:1. In most of existing efficient researches, about accelerating LOS computationusing GPU based on culling method, GPU does culling computation and CPU doesexact LOS computation. This not only makes CPU have some load about LOScomputation, but also makes the entity scale is limited in the simulation. To solve thisproblem, this paper discusses basic thought and GPU-parallelism of LOS algorithm(including DYNTACS, ModSAF, and BRESENHAM.) related with the regularGrid-Post terrain, and make GPU do the exact LOS computation. According to theresult of experiments, the GPU execution, compared to CPU execution, may get aspeedup from1.5x to14x.2. There are characteristics of high speed and low accuracy in Bresenhamalgorithm, and there are characteristics of low speed and high accuracy in algorithmsincluding DYNTACS and ModSAF. To balance speed and accuracy, a LOS algorithmis proposed, which is a method of creating two sets of the near points and remote pointsof LOS based on the thought of finding a set of nearest points by Bresenham algorithmand executing linear interpolating and LOS determination by comparing slope. Theresults of experiments, compared to the computation based on CPU, demonstrate: itstime performance is between Bresenham and DYNTACS, and its accuracy is equivalentwith DYNTACS; it may get a speedup beyond4x compared to its CPU computationand it may get a speedup beyond18x compared to ModSAF CPU computation when theterrain resolution is high and LOS ratio is high.3. Entities often trigger many concurrent LOS queries in one simulation step, and aLOS query implies a LOS computation in GPU. The communication latency amongLOS queries cannot be hidden, which make the ratio between communication time andcomputation time become high usually. Therefore, the computation power of GPUcannot be used intensively. And different query has defferent point-to-point count. So, if executing LOS computation in GPU based on query granularity, GPU load cannot bebalanced. To solve this problem, an asynchronous combine&partition algorithm isproposed. According to concurrent characteristic of multiple LOS query, a combinationmethod is proposed to aggregate multiple concurrent LOS queries into a LOS query setincuding many viewpoints and target points, and a partition method is proposed topartition the LOS query set into a GPU-based computation with a point-to-pointcomputations’ number of threads. The results of experiments, compared to theCPU-GPU hybrid algorithm based on culling, demonstrate it may get a speedup beyond2x in the best situation.