Run-time mapping: dynamic resource allocation in embedded systems

Many desired features of computing platforms, such as increased fault tolerance, variable quality of service, and improved energy efficiency, can be achieved by postponing resource management decisions from design-time to run-time. While multiprocessing has been widespread in embedded systems for quite some time, allocation of (shared) resources is typically done at design-time to meet the constraints of applications. The inherent flexibility of large-scale embedded systems is then reduced to a fixed, static resource allocation derived at design-time. At run-time, unanticipated situations in either the system itself or in its environment may render resources inaccessible that were assumed to be available at design-time. The increased flexibility obtained by run-time resource allocation can be exploited to increase the degree of fault tolerance, quality of service, energy efficiency and to support a higher variability in use-cases. The term run-time mapping is used to refer to resource allocation at run-time to meet the dynamic requirements of applications. The introduction of full-fledged run-time mapping systems in the domain of embedded systems has long been delayed due to the inherent complexity of the problems to be solved. While similar mapping problems have been solved at design-time for a long time already, different analysis and problem solving techniques are required at run-time. The guided local search technique presented in this thesis provides a balance between robustness and overhead. The results of guided local search and the required computation time on synthetic datasets are competitive with industry standard solvers, while the memory footprint is one or two orders of magnitude lower. Therefore, the algorithm can be implemented on an embedded platform. The computation time required for solving the resource allocation problems at run-time may be further reduced by a hybrid form between design-time allocation and run-time adaptation.