Team member: Lin, Wei-Yang
             Chin, Tai-Lin

Title: On the time scheduling problem of uniform recurrence equations

Time scheduling is an important issue for supercompilers/parallelizers
in parallel computing. Finding the optimal execution schedules is known
to be difficult for general problems. However, for uniform recurrence
equations, which possesse a high degree of implicit parallelism, it is
possible to analytically calculate the scheduling vectors. Uniform
recurrence equations can be expressed as a sequential nested loop and
all the nodes in the iteration space have the same dependence structure.
Since the regular and repetitive structure of the nested loop,
dependence analysis can be exploited to schedule the execution using
various scheduling strategies.

This project is dealing with finding the optimal scheduling vectors for
uniform recurrence equations using different scheduling methods. First,
we study the hyperplane based scheduling method and the related variants.
For instance, linear scheduling, uniform scheduling, and affine
scheduling. Then, a more powerful and complicated method called
multi-dimensional scheduling is investigated. The optimal scheduling
vectors based on these scheduling methods can be obtained by solving the
corresponding linear program problems. Various scheduling methods are
implemented on several applications, such as selection sort, a FIR filter,
and a complex loop. The scheduling results will be presented.