On run-time exploitation of concurrency

The `free' speed-up stemming from ever increasing processor speed is over. Performance increase in computer systems can now only be achieved through parallelism. One of the biggest challenges in computer science is how to map applications onto parallel computers.\ud \ud Concurrency, seen as the set of valid traces through a program, is utilized by translating it into actual parallelism, i.e. into the simultaneous execution of multiple computations. With higher degrees of unpredictability---both with regards to the actual workload and to the availability of resources---more can be gained from making scheduling and resource management decisions at run-time, when more information (such as resource availability and required QoS level) is available. In cases where concurrency is data-dependent, programming models and their supporting run-time systems also benefit from exposing concurrency when that data is known, viz. at run-time. In this thesis, two systems for run-time exploitation of concurrency are discussed.\ud \ud The first system discussed in this thesis is an on-line spatial resource manager for real-time streaming applications, especially in energy constrained environments. In embedded systems, these applications typically require QoS guarantees, are structurally stable (do not change over time) and are active for a (relatively) long period of time. With increasing complexity, embedded systems consist increasingly of many independent processors with varying degrees of specialization. Designing systems in such a way is beneficial for flexibility, yield increase and energy conservation. However, exploiting such a heterogeneous multi-processor system in order to realize these benefits requires that the resources it provides are dynamically assigned to applications.\ud \ud A formal and precise definition of this on-line spatial resource management problem is given in this thesis and qualitative evaluation criteria by which on-line spatial resource managers can be compared are introduced. Constraints on applications and techniques for their modelling are discussed. Since the complexity of this problem is prohibitive and the time constraints to make choices are tight, a heuristic approach is introduced. In this approach, the complete problem of spatial resource management is partitioned into the subproblems of binding, mapping, routing, and QoS validation.\ud \ud The subproblems are ordered in the sense that choices made for the solutions to earlier subproblems are considered fixed when solving later subproblems. Since the subproblems still have a high complexity, algorithms and approaches from literature are adapted to partition them further. The adapted algorithms are implemented in Kairos, a proof-of-concept on-line spatial resource manager for heterogeneous multi-processor systems. A large use case, taken from a state-of-the-art industrial application, is used to explore Kairos' capabilities. With this use case and a with synthetic benchmark, Kairos is shown to be a successful proof-of-concept implementation for on-line spatial resource management and, thus, the problem is shown to be solvable with acceptable concessions.\ud \ud The second system discussed in this thesis deals with applications for which it is hard or even impossible to predict their behaviour to the extent that is necessary to fulfil real-time requirements. In particular, this holds for applications for which the amount of concurrency is highly data-dependent and the work done by different tasks in an application is unbalanced, variable and unpredictable. For these applications, performance can not be guaranteed, but by exposing (data-dependent) concurrency at run-time, an application's performance and the total system's utilization can be improved.\ud \ud The system discussed here is SNet. It is developed at the University of Hertfordshire and comprises a coordination language, a programming model and a run-time system. A great strength of SNet is that it allows for the separation of concerns between application engineering and concurrency engineering. The application engineer does not program individual threads with their synchronization and communication, but decomposes the application into small units of work on a stream of input data. In this thesis, a denotational semantics for SNet is presented with proof that under those semantics, SNet is prefix monotonic, i.e. for every finite prefix of the input stream, a prefix of the output stream exists that is unchanged by further input. Furthermore, a novel execution model is presented that exposes significantly more concurrency than the former execution model. A strong indication is given that a schedule exists, such that the novel execution model does not introduce non-termination