optimal semi-oblique tiling
For 2-D iteration space tiling, we address the problem of determining the tile parameters that minimize the total execution time under the BSP model. We consider uniform dependency computations, tiled so that (at least) one of the tile boundaries is parallel to the domain boundary. We determine the optimal tile size as a closed form solution. In addition, we determine the optimal number of processors and also the optimal slope of the oblique tile boundary. Our predictions are validated, among other examples, on a sequence alignment problem specialized to similar sequences using Ficket's  k -band algorithm, for which, our optimal semi-oblique tiling yields an improvement over orthogonal tiling by a factor of 2.5. Our optimal solution requires a block-cyclic distribution of tiles to processors. The best one can obtain with only block distribution (as many authors require) is 3 times slower.
optimality tile iter space addressing timing model dependencies parallel size processor predict examples sequence alignment sequence algorithm blocking distributed author