Metasloy: ideas about applying prediction to optimize programming and resource allocation in the OS
Hello, dear readers.
There is a lot of talk about “big data” , the processing of which should give us a lot of new opportunities in various fields. In this publication, I would like to talk a little bit about one of my long-standing work, which, generally speaking, involves the useful processing of some “big data” that naturally arise in the course of the work of the final program or even the operating system. In short, we are talking about at least temporary profiles of code execution and its various internal characteristics / variables - these can be universal (for example, sizes of memory blocks requested from the OS) or local (internal variables of the program) values. I think that of undoubted interest are:
a) parameterization of the temporal characteristics of the execution of individual code fragments, that is, the search for the dependence of its execution time on the values of its internal variables;
')
b) search for logical and approximate mathematical dependencies of some internal program variables on others.
For what the first idea is needed, it is probably quite obvious: to optimize the execution of the program, that is, to design high-performance algorithms. For example, if our program contains several computational blocks that are executed in parallel mode, then the most effective load distribution (balancing) may require the ability to predict the approximate execution time of these blocks. This can be a very nontrivial task if the working algorithms of the blocks are complex. Then a special subsystem would help us, which would first diligently collect the values of variables and block execution time, then try to determine the approximate dependence of time on these variables and provide (dynamically construct) some evaluation function, using which your program could already carefully plan and to distribute the load for parallel processing.
The second idea may seem strange, but it has at least two useful applications:
1. One of the internal variables can be the volume of the next allocated block of memory. If the operating system needs, for example, to predict the size of the next block allocated to a program and the moment of its allocation (to optimize memory allocation), then it would also be useful for a subsystem to which the program would report the values of some variables (in its discretion) X and block size N, and the subsystem would also register the request time T, after which it would build the dependencies N (X), T (X) and actively use them to optimize the allocation of resources, predict the need to use the paging file, and in other necessary th order. Similarly, the OS can predict the allocation and return of many other resources: file descriptors, graphics, etc.
2. There are algorithms, for example, from the field of numerical methods (for example, integrating the equations of aerodynamics), in which sometimes it is very important to get at least rough approximate results (for a start), based on which you can run the basic algorithms, and only then, when accurate results are ready, to make, for example, amendments. Here the models of variable dependencies on variables are used. For example, it is possible to implement one of the approaches to the parallel solution of the aerodynamic problem with the decomposition of the working area in space, in blocks.
So, we have assumed that the stated idea is at least not useless. How can you implement it ?
Suppose that a prediction subsystem appears in the operating system , which will use quickly the often idle CPU cores and, for example, video cards, to solve the problem, that is, to simulate the time and other characteristics of program execution depending on the data they provide for the OS (about the values of important variables at different points in time).
At one time, I developed a prototype of such a subsystem (“metasloi”), which solved the problem, building complex models of execution time and data. Since it was initially assumed that the models would be very non-trivial, I realized that the data provided by the program would not always be complete and it is desirable to additionally have some trace of its execution (with the values provided by the metasloy of variables), according to which the subsystem will restore some of the execution logic, determining some missing data (for example, pseudo-counters of internal nested loops for / while / do). This task was solved by analyzing large tables of variable values in the course of execution, with the search for cycles, transitions and conditions of cycles / transitions. The obtained variables (auxiliary counters of internal cycles in conjunction with the variables directly represented by the program) were already used directly to search for time / data dependence functions of these variables. This was done using the method of group accounting of arguments (MGUA).
The acquisition of data by metasloem was formalized by calling its functions, to which the identifiers of the program “tags” and the values of certain internal variables were transferred. Using this data, the metaslayer built the combined transition / functional dependency model as the body of a special function (in C ++), compiled it with an external compiler into a dynamic library (DLL) and connected it to the program, which thus obtained the required prediction tools.
This approach was tested on several test problems :
Now the development of this prototype metasloy is closed (I don’t have time for this and I have long handed over the code to another person for his experiments). But the idea remained and I tried to explain it here, in the hope that it would be interesting and sometime someone would develop it in full form (as an OS subsystem or a useful library).
There is a lot of talk about “big data” , the processing of which should give us a lot of new opportunities in various fields. In this publication, I would like to talk a little bit about one of my long-standing work, which, generally speaking, involves the useful processing of some “big data” that naturally arise in the course of the work of the final program or even the operating system. In short, we are talking about at least temporary profiles of code execution and its various internal characteristics / variables - these can be universal (for example, sizes of memory blocks requested from the OS) or local (internal variables of the program) values. I think that of undoubted interest are:
a) parameterization of the temporal characteristics of the execution of individual code fragments, that is, the search for the dependence of its execution time on the values of its internal variables;
')
b) search for logical and approximate mathematical dependencies of some internal program variables on others.
For what the first idea is needed, it is probably quite obvious: to optimize the execution of the program, that is, to design high-performance algorithms. For example, if our program contains several computational blocks that are executed in parallel mode, then the most effective load distribution (balancing) may require the ability to predict the approximate execution time of these blocks. This can be a very nontrivial task if the working algorithms of the blocks are complex. Then a special subsystem would help us, which would first diligently collect the values of variables and block execution time, then try to determine the approximate dependence of time on these variables and provide (dynamically construct) some evaluation function, using which your program could already carefully plan and to distribute the load for parallel processing.
The second idea may seem strange, but it has at least two useful applications:
1. One of the internal variables can be the volume of the next allocated block of memory. If the operating system needs, for example, to predict the size of the next block allocated to a program and the moment of its allocation (to optimize memory allocation), then it would also be useful for a subsystem to which the program would report the values of some variables (in its discretion) X and block size N, and the subsystem would also register the request time T, after which it would build the dependencies N (X), T (X) and actively use them to optimize the allocation of resources, predict the need to use the paging file, and in other necessary th order. Similarly, the OS can predict the allocation and return of many other resources: file descriptors, graphics, etc.
2. There are algorithms, for example, from the field of numerical methods (for example, integrating the equations of aerodynamics), in which sometimes it is very important to get at least rough approximate results (for a start), based on which you can run the basic algorithms, and only then, when accurate results are ready, to make, for example, amendments. Here the models of variable dependencies on variables are used. For example, it is possible to implement one of the approaches to the parallel solution of the aerodynamic problem with the decomposition of the working area in space, in blocks.
So, we have assumed that the stated idea is at least not useless. How can you implement it ?
Suppose that a prediction subsystem appears in the operating system , which will use quickly the often idle CPU cores and, for example, video cards, to solve the problem, that is, to simulate the time and other characteristics of program execution depending on the data they provide for the OS (about the values of important variables at different points in time).
Prototype
At one time, I developed a prototype of such a subsystem (“metasloi”), which solved the problem, building complex models of execution time and data. Since it was initially assumed that the models would be very non-trivial, I realized that the data provided by the program would not always be complete and it is desirable to additionally have some trace of its execution (with the values provided by the metasloy of variables), according to which the subsystem will restore some of the execution logic, determining some missing data (for example, pseudo-counters of internal nested loops for / while / do). This task was solved by analyzing large tables of variable values in the course of execution, with the search for cycles, transitions and conditions of cycles / transitions. The obtained variables (auxiliary counters of internal cycles in conjunction with the variables directly represented by the program) were already used directly to search for time / data dependence functions of these variables. This was done using the method of group accounting of arguments (MGUA).
The acquisition of data by metasloem was formalized by calling its functions, to which the identifiers of the program “tags” and the values of certain internal variables were transferred. Using this data, the metaslayer built the combined transition / functional dependency model as the body of a special function (in C ++), compiled it with an external compiler into a dynamic library (DLL) and connected it to the program, which thus obtained the required prediction tools.
This approach was tested on several test problems :
- selection of the most optimal number of threads for parallel processing in a cycle of complex data - dynamically constructed time characteristics models built in the metasloy;
- building an algorithmic model of a “secret” data file that cannot be stored directly — the data model that was built into the meta-layer was readable by the program from a file.
Conclusion
Now the development of this prototype metasloy is closed (I don’t have time for this and I have long handed over the code to another person for his experiments). But the idea remained and I tried to explain it here, in the hope that it would be interesting and sometime someone would develop it in full form (as an OS subsystem or a useful library).
Source: https://habr.com/ru/post/336580/
All Articles