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.
A mathematical analysis of the run-time mapping problem shows that each of its subproblems, i.e. task assignment and communication routing, is computationally complex due to the constraints representing the limited resource capacities of the embedded platform. Even if one of these subproblems is solved to optimality, the second optimization problem is still N P-hard. Therefore, two different heuristic techniques are presented to tackle the run-time mapping problem.
The first approach discussed in this thesis is a deterministic technique. Both the resources requested by applications, and the resources provided by the platform are modeled as graphs. A divide-and-conquer algorithm exploits the graph structures in order to generate many small resource allocation problems. Each resource allocation problem is a knapsack problem, where the resource requests (the items) are assigned to a subset of the available resources (the bins). In case of an insufficient number of bins, the algorithm increases the set of bins by considering more platform resources, until it runs out of resources. A prototype run-time mapping system which uses this algorithm is evaluated on a many-core processing platform developed in the CRISP project. Multiple real-life applications (various beam forming applications, a GPS receiver, and a dependability monitor) have been tested successfully with the run-time mapper which determines the resource assignment and configuration. For these applications, the majority of the simulated hardware faults can be circumvented by means of run-time mapping. Empirical evaluation shows, however, that deterministic mapping algorithms do have their weaknesses when it comes to robustness and the ability to provide feedback information. The symmetric structures typically found in both hardware architecture and applications may cause combinatorial searches to spend time evaluating many similar sub problems in a small part of the search space, unable to continue the search in an effective manner. This implies, that the computation time increases vastly without being able to provide a solution or a cause for the failure to provide one.
The second approach discussed in this thesis is a randomized technique. Specifically, the meta-heuristic known as guided local search is able to improve upon the shortcomings of the first technique. Existing work that applies the guided local search technique to assignment problems only can be used for the task allocation part of our problem. In this thesis, the method is extended to take communication routing into account as well. Guided local search avoids topological orderings of either application or platform graphs. This gives both improvements on robustness in finding solutions and improvements in the quality of feedback information. It is shown that at any time, due to the iterative nature of the method, information can be provided on the relative scarcity of specific resources and the location in the platform that are most critical to the application being mapped. This information may be used for coordination between layers of a hierarchical organized system. Such a system is developed in the context of the STARS project, resulting in a demonstrator consisting of multiple processing boards.
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.
Starting-time 10.45h in Building Waaier - Prof. G. van Berkhoff-zaal
