Static Allocation of Periodic Tasks with Precedence Restraints in Distributed Systems

TitleStatic Allocation of Periodic Tasks with Precedence Restraints in Distributed Systems
Publication TypeTechnical Report
Year of Publication1988
AuthorsShin, K. G., & Peng D-T.
Other Numbers1218

Using two branch-and-bound (B&B) algorithms, we propose an optimal solution to the problem of allocating (or assigning with subsequent scheduling considered) periodic tasks to a set of heterogeneous processing nodes (PNs) of a distributed real-time system. The solution is optimal in the sense of minimizing the maximum normalized task response time, called the system hazard, subject to precedence constraints among the tasks to be allocated. First, the task system is described as a task graph (TG), which represents computation and communication modules as well as the precedence constraints among them. Second, the exact system hazard of a complete assignment is determined so that an optimal (rather than suboptimal) assignment can be derived. This exact cost is obtained by optimally scheduling the modules assigned to each PN with a B&B algorithm guided by the dominance relationship between simultaneously schedulable modules. Thirdly, to reduce the amount of computation needed for an optimal assignment, we derive a lower-bound system hazard that is obtainable with a polynomial time algorithm. This lower-bound cost, together with the exact cost of a complete assignment, is used to efficiently guide the search for an optimal assignment. Finally, examples are provided to demonstrate the concept, utility and power of our approach.

Bibliographic Notes

ICSI Technical Report TR-88-005

Abbreviated Authors

K. Shin and D.-T. Peng

ICSI Publication Type

Technical Report