An evolutionary scheme for cosynthesis of real-time systems

We consider the problem of hardware-software cosynthesis of application-specific embedded real-time systems. We assume that these systems are based on a heterogeneous multiprocessor architecture. One of the key problems in the synthesis of such systems is that of scheduling the real-time tasks. The conventional approach to the problem has been to use a task graph to describe the dependencies among tasks and to assign constant weights to the nodes and edges of the graph. The node weights represent task execution times and the edge weights represent communication times. However, in many real-time applications, the execution time and communication times cannot be determined a-priori. One can use the conventional task graph model in such situations by taking the worst-case times, but such an approach is necessarily pessimistic and wasteful in terms of resource utilization. We propose a model which treats the task execution times and communication times as stochastic variables with beta distributions. A stochastic task scheduling algorithm is presented which maximizes the probability of meeting all real-time constraints. A genetic algorithm, which employs the stochastic scheduling algorithm, is used for the synthesis of a high performance embedded system at minimum cost. We present experimental results for three task graphs