Ivanenko P. Methods for automation of development of autotuners for parallel programs

The thesis is devoted to the development of methods and models for automating optimization of software for parallel platforms. Thesis offers five new autotuning methods. The scientific novelty of the obtained results is a formal description of proposed autotuning methods. Work presents autotuning framework TuningGenie that uses term rewriting approach for source code transformations. With such approach, some formulated characteristics of computational logic can be automatically checked so correctness of optimizing transformations can be validated. Also utilizing means of rewriting rule systems is more agile comparing to text-like transformations – you can apply structural changes to your code like reversing the order of iterations over multidimensional data, etc. Effectiveness and nature of proposed methods are explained and estimated in a proposed model PRAM*. This model extends the conventional PRAM model with an additional layer of quick but limited memory and uses only one strategy for concurrent memory access orchestration. The correctness of the methods is proved in terms of discrete dynamic systems. Dynamic algebra model for multicore systems was created for this purpose. The results of the dissertation work are of a theoretical and practical nature and were motivated directly by a practical application. Therefore, a program implementation of all proposed methods of auto-tuning was created. This implementation is domain-independent and is suitable for any operating system that has Java virtual machine implementation. The auto-tuning system is based on rewriting rules framework and is focused primarily on software applications written in Java language. In general, the proposed solution is suitable for any imperative programming language. The effectiveness of the developed methods and tools was demonstrated with well-known model examples – optimization of sequential and parallel sorting algorithms, as well as the problem of modeling Brownian motion in an ideal gas. Also, the autotuning system was used to optimize the complex practical real-time task – a parallel algorithm for short-term meteorological forecasting.