Assignment and scheduling communicating periodic tasks in distributed real-time systems
- 1 December 1997
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Software Engineering
- Vol. 23 (12), 745-758
- https://doi.org/10.1109/32.637388
Abstract
Presents an optimal solution to the problem of allocating communicating periodic tasks to heterogeneous processing nodes (PNs) in 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 the precedence constraints resulting from intercommunication among the tasks to be allocated. Minimization of the system hazard ensures that the solution algorithm allocates tasks so as to meet all task deadlines under an optimal schedule, whenever such an allocation exists. The task system is modeled with a task graph (TG), in which computation and communication modules, communication delays and intertask precedence constraints are clearly described. Tasks described by this TG are assigned to PNs by using a branch-and-bound (B&B) search algorithm. The algorithm traverses a search tree whose leaves correspond to potential solutions to the task allocation problem. We use a bounding method that prunes, in polynomial time, nonleaf vertices that cannot lead to an optimal solution, while ensuring that the search path leading to an optimal solution will never be pruned. For each generated leaf vertex, we compute the exact cost using the algorithm developed by Peng and Shin (1993). The lowest-cost leaf vertex (one with the least system hazard) represents an optimal task allocation. Computational experiences and examples are provided to demonstrate the concept, utility and power of the proposed approach.Keywords
This publication has 41 references indexed in Scilit:
- Heuristic algorithms for task assignment in distributed systemsIEEE Transactions on Computers, 1988
- Efficient computation of optimal assignments for distributed tasksJournal of Parallel and Distributed Computing, 1987
- Task Allocation and Precedence Relations for Distributed Real-Time SystemsIEEE Transactions on Computers, 1987
- Module replication and assignment for real-time distributed processing systemsProceedings of the IEEE, 1987
- A Graph Matching Approach to Optimal Task Assignment in Distributed Computing Systems Using a Minimax CriterionIEEE Transactions on Computers, 1985
- Practical Multiprocessor Scheduling Algorithms for Efficient Parallel ProcessingIEEE Transactions on Computers, 1984
- Recent Developments in Deterministic Sequencing and Scheduling: A SurveyPublished by Springer Nature ,1982
- A Task Allocation Model for Distributed Computing SystemsIEEE Transactions on Computers, 1982
- Task Allocation in Distributed Data ProcessingComputer, 1980
- Complexity of Scheduling under Precedence ConstraintsOperations Research, 1978