With the objective of minimizing the total execution time of a parallel program on a distributed memory parallel computer, this paper discusses the selection of an optimal supernode shape of a supernode transformation (also known as tiling). We identify three parameters of a supernode transformation: supernode size, relative side lengths, and cutting hyperplane directions. For supernode transformations on algorithms with perfectly nested loops and uniform dependencies, we prove the optimality of a constant linear schedule vector and give a necessary and sufficient condition for optimal relative side lengths. We also prove that the total running time is minimized by a cutting hyperplane direction matrix from a particular subset of all valid directions and we discuss the cases where this subset is unique. The results are derived in continuous space and should be considered approximate. Our model does not include cache effects and assumes an unbounded number of available processors, the communication cost approximated by a constant, uniform dependences, and loop bounds known at compile time. A comprehensive example is discussed with an application of the results to the Jacobi algorithm.

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 size and optimal supernode relative side lengths of a supernode transformation (also known as tiling). 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, for sufficiently large supernodes and number of processors, and for the case where multiple supernodes are mapped to a single processor, we give an order n polynomial whose real positive roots include the optimal supernode size. For two special cases, 1) two-dimensional algorithm problems and 2) n-dimensional algorithm problems, where the communication cost is dominated by the startup penalty and, therefore, can be approximated by a constant, we give a closed form expression for the optimal supernode size, which is independent of the supernode relative side lengths and cutting hyperplanes. For the case where the algorithm iteration index space and the supernodes are hyperrectangular, we give closed form expressions for the optimal supernode relative side lengths. Our experiment shows a good match of the closed form expressions with experimental data.

Supernode transformation has been proposed to reduce the communication startup cost by grouping a number of iterations in a loop 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 mentioned above. In this paper, how to find an optimal grain size and an optimal relative side length vector, with the goal of minimizing total running time, is addressed. Two communication cost models are considered. In the first one, communication cost is approximated by a constant startup penalty and in the second, communication cost is a function of the startup penalty and the message size. We derive closed form analytical expressions for the optimal supernode size for the one parameter model and the two parameter model with doubly nested loops. A closed form expression for the optimal relative length vector is also provided for the one parameter model with constant bounded loop iteration space.

The paper deals with the problem of transforming irregular data dependence structures of algorithms with nested loops into more regular ones. Algorithms under consideration are n-dimensional algorithms (algorithms with n nested loops) with affine dependences where dependences are affine functions of index variables of the loop. Methods are proposed to uniformize affine dependence algorithms, i.e., to transform affine dependence algorithms into uniform dependence algorithms where dependences are independent of the index variables (constant). Objectives are considered to guide the selection of feasible uniformizations. The first one is to reduce the number of dependences after uniformization. The second one is to maximize parallelism preserved by the uniformization. Some parallelism might be lost due to the uniformization. The parallelism preserved by the uniformization is measured by: the total execution time by the optimal linear schedule which assigns each computation in the algorithm an execution time according to a linear function of the index of the computation; and the size of the cone spanned by the dependence vectors after uniformization.