The problem of parallel thread mapping is studied for the case of discrete orthogonal @math -simplices. The possibility of a @math time recursive block-space map @math is analyzed from the point of view of parallel space efficiency and potential performance improvement. The @math -simplex and @math -simplex are analyzed as special cases, where constant time maps are found, providing a potential improvement of up to @math and @math more efficient than a bounding-box approach, respectively. For the general case it is shown that finding an efficient recursive parallel space for an @math -simplex depends of the choice of two parameters, for which some insights are provided which can lead to a volume that matches the @math -simplex for @math , making parallel space approximately @math times more efficient than a bounding-box.
@cite_11: This paper presents a novel and efficient GPU-based parallel algorithm to cull non-colliding object pairs in very large-scale dynamic simulations. It allows to cull objects in less than 25ms with more than 100K objects. It is designed for many-core GPU and fully exploits multi-threaded capabilities and data-parallelism. In order to take advantage of the high number of cores, a new mapping function is defined that enables GPU threads to determine the objects pair to compute without any global memory access. These new optimized GPU kernel functions use the thread indexes and turn them into a unique pair of objects to test. A square root approximation technique is used based on Newton's estimation, enabling the threads to only perform a few atomic operations. A first characterization of the approximation errors is presented, enabling the fixing of incorrect computations. The I O GPU streams are optimized using binary masks. The implementation and evaluation is made on largescale dynamic rigid body simulations. The increase in speed is highlighted over other recently proposed CPU and GPU-based techniques. The comparison shows that our system is, in most cases, faster than previous approaches.
Q. Avril proposed a GPU mapping function for collision detection based on the properties of the @cite_11 . The map is a thread-space function @math , where @math is the linear index of a thread @math and the pair @math is a unique two-dimensional coordinate in the upper triangular matrix. Since the map works in thread space, the map is accurate only in the range @math of linear problem size.