|
Abstract:
Mapping an algorithm on a configurable architecture containing several types of function units requires an efficient allocation of the available computational resources to the various operations in order to exploit the parallelism and minimize the execution time. This resource scheduling/allocation problem consists of determining when and on which unit to schedule a given task with the objective of minimizing total execution time, while respecting precedence relations and resource constraints. In this paper, we use a branch and bound search method with a non-deterministic heuristic to find quasi optimal solution to the allocation problem. Partial schedules are built up starting at time 0 and proceed systematically by adding at each decision point subsets of activities until a complete feasible schedule is obtained. At each decision point m, the procedure identifies all operations that can be put in progress according to precedence rules. If it is impossible to schedule all eligible activites at time m, a heuristic is used to determine which operations are to be scheduled and which are to be delayed. The key idea of the heuristic is that, gaiven the set of available resources (AR) and the set of candidate operations (SC) that meet precedence constraints, the criteria for matching operation j with resource k is a probabilistic decision based on quantifying the opportunity cost of k and the scheduling urgency of j.
|
