DidaWiki

Adaptivity is an essential feature whose importance has been assessed in many research fields (e.g. parallel programs, mobile computing and web applications). Especially for high-performance processing, this feature is of special interest in order to properly and promptly respond to time- variable QoS requirements, to react to uncontrollable environmental effects, and to efficiently deal with highly irregular parallel problems. In this scenario the Structured Parallel Programming approach is a cornerstone for expressing adaptive parallel programs: the high-degree of composability of parallelization schemes, their predictability formally expressed by performance models, are basic concepts in order to introduce dynamic reconfiguration processes of adaptive applications. These reconfigurations are not only limited to implementation aspects (e.g. parallelism degree modification), but also parallel versions with different structures can be expressed for the same computation, featuring different levels of expected performance, memory utilization, energy consumption, and the exploitation of the memory hierarchy of the underlying architecture. Over the last decade several programming models and research frameworks have been developed by our research group, with the purpose of defining tools and strategies for expressing adaptive applications. Relevant examples have been the ASSIST programming model and its extension ASSISTANT, and the Behavioural Skeleton methodology. Although these approaches represent a crucial experience, they are hampered by a substantial lacking in formal modeling of the control problem and in the definition of powerful adaptation strategies. This is especially true if we consider that reconfigurations imply a transient degradation (cost) over the system execution: a methodology able to quantify these costs, the steady-state behavior of system after a reconfiguration process, and to evaluate the “stability degree” of a reconfiguration decision represent a clear and challenging research effort. For the previous reasons, since the last two year of my Ph.D studies I have investigated a formal control-theoretic perspective for controlling the behavior of structured parallel computations. Assuming the predictability of the performance of well-known parallelization schemes, my research work has been consisted in verifying the applicability of Optimal Control techniques to the control of computational graphs of parallel modules. For each parallel module a predictive control strategy based upon the iterative model-predictive control procedure has been applied. Reconfigurations are decided by solving a combinatorial optimization problem for a finite prediction horizon, predicting future system states by using a formal description of the computation behavior, mathematically expressed as a Hybrid Dynamical System. This technique has been theoretically applied to several application scenarios and its feasibility must be still verified by experimental results. In order to provide a novel and complete methodology, the problem of distributed control has been faced. For controlling computational graphs of interconnected structured parallel elaborations, the overall control problem consists in a set of coupled control sub-problems for each application module. The nature of distributed control is twofold: first of all we need to model the coupling relationships between control problems, furthermore we need to introduce proper notions of negotiation and convergence in the control decisions collectively taken by the parallel modules of the application graph. Currently my first attempt to study this problem has been developed by employing a limited but significant background in Game Theory, formalizing the problem of distributed control as a finite strategic game, and studying proper protocols and constraints in the problem formulation such that convergence points exist. My future research works consist in completing the formalization and evaluating the effectiveness of the proposed methodology on real- world experiments, also considering existing high-performance applications developed by my research group in the last years.