Possibilities of Recursive GPU Mapping for Discrete Orthogonal Simplices

2016/10/24 by Cristóbal A. Navarro, Navarro, Cristóbal A., Benjamín Bustos +3
Computer Science · #Graph Theory and Algorithms #Digital Image Processing Techniques #Computational Geometry and Mesh Generation

paper · pdf · doi:10.48550/arxiv.1610.07394

Abstract

The problem of parallel thread mapping is studied for the case of discrete orthogonal m-simplices. The possibility of a O(1) time recursive block-space map λ: ℤ^m ↦ ℤ^m is analyzed from the point of view of parallel space efficiency and potential performance improvement. The 2-simplex and 3-simplex are analyzed as special cases, where constant time maps are found, providing a potential improvement of up to 2× and 6× more efficient than a bounding-box approach, respectively. For the general case it is shown that finding an efficient recursive parallel space for an m-simplex depends of the choice of two parameters, for which some insights are provided which can lead to a volume that matches the m-simplex for n>n₀, making parallel space approximately m! times more efficient than a bounding-box.

Related

• A Non-linear GPU Thread Map for Triangular Domains
• Efficient GPU Thread Mapping on Embedded 2D Fractals
• Block-space GPU Mapping for Embedded Sierpiński Gasket Fractals
• A Scalable and Energy Efficient GPU Thread Map for m-Simplex Domains
• Potential benefits of a block-space GPU approach for discrete\n tetrahedral domains