ALLOCATING HARD REAL-TIME TASKS - AN NP-HARD PROBLEM MADE EASY

A distributed hard real time system can be composed from a number of communicating tasks. One of the difficulties with building such systems is the problem of where to place the tasks. In general there are P(T) ways of allocating T tasks to P processors, and the problem of finding an optimal feasible allocation (where all tasks meet physical and timing constraints) is known to be NP-Hard. This paper describes an approach to solving the task allocation problem using a technique known as simulated annealing. It also defines a distributed hard real-time architecture and presents new analysis which enables timing requirements to be guaranteed.