Self-Aware Synchronization Mechanisms and Decision Making Techniques for Contention-Aware Thread Mapping
thesisposted on 13.12.2012 by Matteo Carminati
In order to distinguish essays and pre-prints from academic theses, we have a separate category. These are often much longer text based documents than a paper.
Nowadays, the power and the complexity of computing systems are evolving and increasing at an unprecedented rate. The advantages of highly-parallel systems could benefit an enormous variety of fields. However, the growing complexity is making it unfeasible for the average programmer to weight all the constraints and optimize the system for a wide range of machines and scenarios. The burden on programmers is noticeable and many research efforts were spent in addressing this issue. Clearly, it is not feasible to rely on human intervention to tune a system: conditions change constantly, rapidly, and unpredictably. It would be desirable to have the system automatically adapt to the mutating environment. A new paradigm is to be explored for these systems to be developed. Self-adaptive systems seem to be the answer to most of the problems previously described. They adapt their behavior and resources to automatically find the best way to accomplish a given goal despite changing environmental conditions and demands. Therefore, this kind of systems needs to monitor itself and its context, discern significant changes, determine how to react, and execute decisions: implementing the Observe Decide and Act control loop. The research work presented in this document aims at augmenting the GNU/Linux oper- ating system with autonomic features. The idea is to make the system aware of the level of data contention among different tasks and to allow it to take smart decisions about how to actually map them on the cores. Theoretical concepts about synchronization methods, memory hierarchy, and task scheduling and mapping help in sustaining that moving threads with high contention on the same core can lead to a reduction of the tasks execution time. To put this design into practice, the following contributions were made: - a monitoring infrastructure able to quantify the lock contention among threads was im- plemented; - an adaptation policy to smartly move tasks onto cores was designed; - the modifications to the kernel of the Linux operating system, in order to include this policy, were made; - a framework for the on-line learning of strategies able to exploits these principles was developed.