  There is a stage in the GPU computing pipeline where a grid of thread-blocks
is mapped to the problem domain. Normally, this grid is a k-dimensional
bounding box that covers a k-dimensional problem no matter its shape. Threads
that fall inside the problem domain perform computations, otherwise they are
discarded at runtime. For problems with non-square geometry, this is not always
the best idea because part of the space of computation is executed without any
practical use. Two- dimensional triangular domain problems, alias td-problems,
are a particular case of interest. Problems such as the Euclidean distance map,
LU decomposition, collision detection and simula- tions over triangular tiled
domains are all td-problems and they appear frequently in many areas of
science. In this work, we propose an improved GPU mapping function g(lambda),
that maps any lambda block to a unique location (i, j) in the triangular
domain. The mapping is based on the properties of the lower triangular matrix
and it works at a block level, thus not compromising thread organization within
a block. The theoretical improvement from using g(lambda) is upper bounded as I
< 2 and the number of wasted blocks is reduced from O(n^2) to O(n). We compare
our strategy with other proposed methods; the upper-triangular mapping (UTM),
the rectangular box (RB) and the recursive partition (REC). Our experimental
results on Nvidias Kepler GPU architecture show that g(lambda) is between 12%
and 15% faster than the bounding box (BB) strategy. When compared to the other
strategies, our mapping runs significantly faster than UTM and it is as fast as
RB in practical use, with the advantage that thread organization is not
compromised, as in RB. This work also contributes at presenting, for the first
time, a fair comparison of all existing strategies running the same experiments
under the same hardware.
