On optimal size and shape of supernode transformations

Supernode transformation has been proposed to reduce the communication startup cost by grouping a number of iterations in a perfectly nested loop with uniform dependencies as a supernode which is assigned to a processor as a single unit. A supernode transformation is specified by n families of hyperplanes which slice the iteration space into parallelepiped supernodes, the grain size of a supernode, and the relative side lengths of the parallelepiped supernode. The total running time is affected by the three factors. The paper considers the problem of finding an optimal grain size and an optimal relative side length vector, with the goal of minimizing total running time. The results show that the optimal grain size is proportional to the ratio of the communication startup cost and the computation speed of the processor, and that the optimal supernode shape is similar to the shape of the index space, in the case of hypercube index spaces and supernodes.