Block-space GPU Mapping for Embedded Sierpiński Gasket Fractals

2017/06/14 by Navarro, Cristóbal A., Bustos, Benjamín, Vega, Raimundo +1
#Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)

paper · doi:10.48550/arxiv.1706.04552

Abstract

This work studies the problem of GPU thread mapping for a Sierpiński gasket fractal embedded in a discrete Euclidean space of n × n. A block-space map λ: ℤ_𝔼² ↦ ℤ_\mathbbF² is proposed, from Euclidean parallel space 𝔼 to embedded fractal space \mathbbF, that maps in O(log₂ log₂(n)) time and uses no more than O(n^ℍ) threads with ℍ ≈ 1.58... being the Hausdorff dimension, making it parallel space efficient. When compared to a bounding-box map, λ(ω) offers a sub-exponential improvement in parallel space and a monotonically increasing speedup once n > n₀. Experimental performance tests show that in practice λ(ω) can produce performance improvement at any block-size once n > n₀ = 2⁸, reaching approximately 10× of speedup for n=2¹⁶ under optimal block configurations.

Related

• Efficient GPU Thread Mapping on Embedded 2D Fractals
• Accelerating Compact Fractals with Tensor Core GPUs
• Squeeze: Efficient Compact Fractals for Tensor Core GPUs
• Possibilities of Recursive GPU Mapping for Discrete Orthogonal Simplices
• A Non-linear GPU Thread Map for Triangular Domains