Time Optimal Supernode Shape For Algorithms With n Extreme Dependence Directions

With the objective of minimizing the total execution time of a parallel program on a distributed memory parallel computer, this paper discusses how to find an optimal supernode shape of a supernode transformation (also known as tiling). We assume the communication cost to be dominated by the startup penalty and therefore, can be approximated by a constant. We identify three parameters of supernode transformation: supernode size, relative side lengths, and cutting hyperplane directions. For algorithms with perfectly nested loops and uniform dependencies, we give a closed form for an optimal linear schedule vector, a necessary and sufficient condition for an optimal relative side lengths, and for dependence cones with n extreme directions, we prove that the total running time is minimized for the cutting hyperplane directions corresponding to the n extreme directions of the dependence cone. The results are derived in continuous space and should for that reason be considered approximate. ..