On the scalability of loop tiling techniques

The challenge of extreme scale computing will test the limits of our ability to scale computa-tional infrastructure. While much attention has been given to the scalability of hardware designs and of the novel algorithms to be run thereon, and significant practical success has been achieved with data-flow-based automatic parallelization of dense array codes, current automatic parallelizers focus almost exclusively on transformations that are inherently not fully scalable. We discuss the limitations on asymptotic scalability of the transformations applied by successful automatic parallelizers like PLuTo, and review the literature of other approaches to this problem. As part of this survey, we discuss both the scalability and imple-mentation status of each current technique. Finally, we identify ongoing work that may resolve this issue