Improved GPU near neighbours performance for multi-agent simulations

被引:4
作者
Chisholm, Robert [1 ]
Maddock, Steve [1 ]
Richmond, Paul [1 ]
机构
[1] Univ Sheffield, Dept Comp Sci, 211 Portobello, Sheffield S1 4DP, S Yorkshire, England
基金
英国工程与自然科学研究理事会;
关键词
GPU; CUDA; Parallel algorithms; Complex systems; FLUIDS; MODEL;
D O I
10.1016/j.jpdc.2019.11.002
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
Complex systems simulations are well suited to the SIMT paradigm of GPUs, enabling millions of actors to be processed in fractions of a second. At the core of many such simulations, fixed radius near neighbours (FRRN) search provides the actors with spatial awareness of their neighbours. The FRNN search process is frequently the limiting factor of performance, due to the disproportionate level of scattered memory reads demanded by the query stage, leading to FRNN search runtimes exceeding that of simulation logic. In this paper, we propose and evaluate two novel optimisations (Strips and Proportional Bin Width) for improving the performance of uniform spatially partitioned FRNN searches and apply them in combination to demonstrate the impact on the performance of multi-agent simulations. The two approaches aim to reduce latency in search and reduce the amount of data considered (i.e. more efficient searching), respectively. When the two optimisations are combined, the peak obtained speedups observed in a benchmark model are 1.27x and 1.34x in two and three dimensional implementations, respectively. Due to additional non FRNN search computation, the peak speedup obtained when applied to complex system simulations within FLAMEGPU is 1.21x. (C) 2019 The Authors. Published by Elsevier Inc.
引用
收藏
页码:53 / 64
页数:12
相关论文
共 31 条
[1]   Tree data structures for N-body simulation [J].
Anderson, RJ .
SIAM JOURNAL ON COMPUTING, 1999, 28 (06) :1923-1940
[2]  
[Anonymous], 2010, 2010 IEEE INT S PARA
[3]  
[Anonymous], 2018, FLUIDS V 3 LARGE SCA
[4]  
[Anonymous], 2015, CUB DOCUMENTATION
[5]  
[Anonymous], 2002, Proceedings of the ACM SIGMOD International Conference on Management of Data, DOI DOI 10.1145/564691.564755
[6]  
Chisholm R., 2016, EURO PAR 2016 PARALL, P311
[7]   SIMPLE ALGORITHMS FOR ENUMERATING INTERPOINT DISTANCES AND FINDING k NEAREST NEIGHBORS [J].
Dickerson, Matthew T. ;
Drysdale, R. L. Scot ;
Sack, Joerg-Ruediger .
INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 1992, 2 (03) :221-239
[8]   Efficient k-nearest neighbor searches for multi-source forest attribute mapping [J].
Finley, Andrew O. ;
McRoberts, Ronald E. .
REMOTE SENSING OF ENVIRONMENT, 2008, 112 (05) :2203-2211
[9]  
FLAMEGPU, 2018, FLAMEGPU FLEXIBLE LA
[10]  
Goswami P., 2010, P 2010 ACM SIGGRAPHE, P55