Cj. Hou et Kg. Shin, ALLOCATION OF PERIODIC TASK MODULES WITH PRECEDENCE AND DEADLINE CONSTRAINTS IN DISTRIBUTED REAL-TIME SYSTEMS, I.E.E.E. transactions on computers, 46(12), 1997, pp. 1338-1356
This paper addresses the problem of allocating (assigning and scheduli
ng) periodic task modules to processing nodes in distributed real-time
systems subject to task precedence and timing constraints. Using the
branch-and-bound technique, a module allocation scheme is proposed to
find an ''optimal'' allocation that maximizes the probability of meeti
ng task deadlines. The task system within a planning cycle is first mo
deled with a task flow graph which describes computation and communica
tion modules, as well as the precedence constraints among them. To inc
orporate both timing and logical correctness into module allocation, t
he probability of meeting task deadlines is used as the objective func
tion. The module allocation scheme is then applied to find an optimal
allocation of task modules in a distributed system. The timing aspects
embedded in the objective function drive the scheme not only to assig
n task modules to processing nodes, but also to use a module schedulin
g algorithm (with polynomial time complexity) for scheduling all modul
es assigned to each node, so that all tasks may be completed in time.
In order to speed up the branch-and-bound process and to reduce the co
mputational complexity, a dominance relation is derived from the requi
rement of timely completion of tasks and use to eliminate the possibil
ity of generating vertices in the state-space search tree, which never
lead to an optimal solution, and an upper bound of the objective func
tion is derived for every partial allocation with which the scheme det
ermines whether or not to prune the corresponding intermediate vertex
in the search tree. Several numerical examples are presented to demons
trate the effectiveness and practicality of the proposed scheme.