ASSIGNMENT AND SCHEDULING COMMUNICATING PERIODIC TASKS IN DISTRIBUTEDREAL-TIME SYSTEMS

We present an optimal solution to the problem of allocating communicat ing periodic tasks to heterogeneous processing nodes (PNs) in a distri buted real-time system. The solution is optimal in the sense of minimi zing the maximum normalized task response time, called the system haza rd, subject to the precedence constraints resulting from intercommunic ation among the tasks to be allocated. Minimization of the system haza rd ensures that the solution algorithm will allocate tasks so as to me et all task deadlines under an optimal schedule, whenever such an allo cation exists. The task system is modeled with a task graph (TG), in w hich computation and communication modules, communication delays, and intertask precedence constraints are clearly described. Tasks describe d by this TG are assigned to PNs by using a branch-and-bound (B&B) sea rch algorithm. The algorithm traverses a search tree whose leaves corr espond to potential solutions to the task allocation problem. We use a bounding method that prunes, in polynomial time, nonleaf vertices tha t cannot lead to an optimal solution, while ensuring that the search p ath leading to an optimal solution will never be pruned. For each gene rated leaf vertex we compute the exact cost using the algorithm develo ped in [1]. The lowest-cost leaf vertex (one with the least system haz ard) represents an optimal task allocation. Computational experiences and examples are provided to demonstrate the concept, utility, and pow er of the proposed approach.