Allocating hard real-time tasks: An NP-Hard problem made easy
✍ Scribed by K. W. Tindell; A. Burns; A. J. Wellings
- Publisher
- Springer US
- Year
- 1992
- Tongue
- English
- Weight
- 1004 KB
- Volume
- 4
- Category
- Article
- ISSN
- 0922-6443
No coin nor oath required. For personal study only.
✦ Synopsis
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 pr ways of allocating Ttasks 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 bard real-time architecture and presents new analysis which enables timing requirements to be guaranteed.