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

Abstract

This work studies the problem of GPU thread mapping for a Sierpiński gasket fractal embedded in a discrete Euclidean space of $n\times n$. A block-space map $\lambda :{\mathbb{Z}}_{\mathbb{E}}^2\mapsto {\mathbb{Z}}_{\mathbb{F}}^2$ is proposed, from Euclidean parallel space $\mathbb{E}$ to embedded fractal space $\mathbb{F}$, that maps in $\mathcal{O}({\log }_2{\log }_2(n))$ time and uses no more than $\mathcal{O}(n^{\mathbb{H}})$ threads with $\mathbb{H}\approx \mathrm{1.58...}$ being the Hausdorff dimension, making it parallel space efficient. When compared to a bounding-box map, $\lambda (\omega )$ offers a sub-exponential improvement in parallel space and a monotonically increasing speedup once $n>n_0$. Experimental performance tests show that in practice $\lambda (\omega )$ can produce performance improvement at any block-size once $n>n_0=2^8$, reaching approximately $10\times$ of speedup for $n=2^{16}$ under optimal block configurations.

7 pages, 8 Figures