Task allocation based on precedence relations for distributed real-time systems

Abstract

A modeling approach for solving the task assignment problem encountered in distributed realtime computing systems is proposed in this paper. In this approach, a program task is modeled as a Petri net called Program net and a network configuration is modeled as a graph called Network graph. A Program net represents all the possible relations between tasks such as concurrency, conflicts, synchronisity, asynchronisity and precedence relations because it was represented by Petri net. To guarantee the completion time, it is necessary to find the maximal parallelism between tasks. Before the algorithm begins to find the optimal allocation, Task net is executed to find the maximal parallelism. And timing information such as the early time and the latest times are calculated for each task also by executing the Task net by topological order. This information is used to check timing constraints during the search process. After collecting this information, the problem is solved by applying the A* algorithm well-known in artificial intelligence after proper heuristic information for speeding up the search is suggested. The cost function is formulated as the sum of task execution time and interprocessor communication time. Hence the search algorithm satisfies also the timing constraints, which was impossible by previous methods. This search algorithm minimizes the previous cost function which tries to minimize resource utilization. An illustrative example and some experimental results are also included to illustrate the effectiveness of the heuristic search.