Non-linear scheduling and allocation in regular arrays: a genetic algorithm approach

Graham Megson

(University of Newcastle)

The mapping of so called regular algorithms specificed as recurrence equations in euclidean lattice via unformization and pipelining techniques is now well understood. Essentially the lattice is enclosed in a convex polytope determined by loop bounds of the algorithm and conditions based on an embedding of the polytope into a (pointed) convex cone can be used to derived linear programming problems to determine optimal linear (conflict free) schedules for evaluating the computation at integer co-ordinate positions in the polytope. A similar technique can be used to determine a placement (or allocation) of computation to processors. Thus we have methods for determining systematically the best timing and allocation pair and consequently optimal architectures for the recurrence equations. In this lecture we consider ways of extending the framework of algorithm mapping into the non-linear domain. In particular we propose new algorithms to generate non-linear timing and allocation functions based on genetic algorithm techniques. Such techniques increase the range of systematic methods considerable and overcome one of the major restrictions in the field.
Tuesday 14th March 1995, 14:30
Seminar Room 322
Department of Computer Science