On the optimality of linear schedules

Authors: Weijia Shang Jose A B Fortes

Publish Date: 1989/09/01

Volume: 1, Issue: 3, Pages: 209-220

PDF Link

Abstract

An algorithm can be modeled as a set of indexed computations and a schedule is a mapping of the algorithm index space into timeLinear schedules are a special class of schedules that are described by a linear mapping and are commonly used in many systolic algorithmsFree schedules cause computations of an algorithm to execute as soon as their operands are available If one computation uses data generated by another computation then a data dependence exists between these two computations which can be represented by the difference of their indices calleddependence vector Many important algorithms are characterized by the fact that data dependencies areuniform ie the values of the dependence vectors are independent of the indices of computations There are applications where it is of interest to find an optimal linear schedule with respect to the time of execution ofa specific computation of the given algorithm This paper addresses the problem of identifying optimal linear schedules for uniform dependence algorithms so that the execution time ofa specific computation of the algorithm is minimized and proposes a procedure to solve this problem based on the mathematical solution of a linear optimization problem Also linear schedules are compared with free schedules The comparison indicates that optimal linear schedules can be as efficient as free schedules the best schedules possible and identifies a class of algorithms for which this is always trueThis research was supported in part by the National Science Foundation under Grant DCI8419745 and in part by the Innovative Science and Technology Office of the Strategic Defense Initiative Organization and was administered through the Office of Naval Research under contracts No 0001485k0588 and No 0001488k0723

Keywords: