Abstract
This paper extends the algorithms which were developed in Part I
to cases in which there is no affine schedule, i.e. to problems
whose parallel complexity is polynomial but not linear. The
natural generalization is to multidimensional schedules with
lexicographic ordering as temporal succession. Multidimensional
affine schedules, are, in a sense, equivalent to polynomial
schedules, and are much easier to handle automatically.
Furthermore, there is a strong connection between
multidimensional schedules and loop nests, which allows one to
prove that a static control program always has a
multidimensional schedule. Roughly, a larger dimension indicates
less parallelism. In the algorithm which is presented here, this
dimension is computed dynamically, and is just sufficient for
scheduling the source program. The algorithm lends itself to a
``divide and conquer'' strategy. The paper gives some
experimental evidence for the applicability, performances and
limitations of the algorithm.
Users
Please
log in to take part in the discussion (add own reviews or comments).