We devise a scheme to allocate periodic task modules
in a planning cycle with the objective of maximizing the probability
of completing each task with both logical and timing
correctness, subject to task precedence and timing constraints.
- We decompose periodic tasks into a set of communicating modules
and represent them by a task flow graph.
- We use the branch-and-bound method to search for an optimal
module allocation. To reduce the computational complexity, we derived
a tight upper bound of the objective function with which we determine
whether to expand or to prune intermediate vertices in the search
tree.
- To incorporate the timing aspects in the objective function, we
devise a module scheduling algorithm (of polynomial time complexity)
to schedule all modules assigned to a node in both partial and
complete allocations.
The research results have been reported in the following papers:
- Chao-Ju Hou and Kang G. Shin, "Allocation
of periodic task modules with precedence and deadline constraints in
distributed real-time systems,"
IEEE Trans. on Computers, Vol. 46, No. 12, December, 1997.
An initial version of the paper appeared in IEEE Proc. 13th Real-Time
Systems Symposium, pp. 146-155, Phoenix, Arizona, December 2-4, 1992.
- Chao-Ju Hou and Kang G. Shin, "Replication
and allocation of task modules in distributed real-time systems,"
IEEE 24th Annual Int'l Symposium on Fault-tolerant Computing,
pp. 26-35, Austin, Texas, June 15-17, 1995.
Return
to Project Home Page
Date last modified -- August 15, 1998
Direct comments concerning this WWW site to:
jhou@ece.osu.edu
