.png){kind=icon}
.png){kind=icon}
Return
Optimal semi-oblique tiling
.png){kind=icon}
PRE
AI
DOI：10.1109/TPDS.2003.1233716.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
For 2D iteration space tiling, we address the problem of determining the tile parameter's that minimize the total execution time on a parallel machine. We consider uniform dependency computations tiled so that (at least) one of the tile boundaries is parallel to the domain boundaries. 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 results are based on the BSP model, which assures the portability of the results. Our predictions are justified on a sequence global alignment problem specialized to similar sequences using Fickett's k-band algorithm, for which our optimal semi-oblique tiling yields an improvement of a factor of 2.5 over orthogonal tiling. 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 three times slower. Furthermore, our best running time is within 10 percent of the predicted theoretical peak performance of the machine!
Keywords:
2D uniform recurrences
biological sequence alignment
BSP model
communication-compuation granularity
distributed memory machines
locality
loop blocking
MPI
perfect loop nests
SPMD
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
6
Papers:
5.2K
Citations:
1.1W
Organization
No organization information available