Reduction of Invocation Overhead in Automatically Generated Programs with the Active Knowledge Concept

Parallel programs development automation is a relevant research direction, potentially beneficial in multiple ways. It allows to reduce complexity and labor intensity for human, improve efficiency of constructed programs and support software and algorithms accumulation and reuse. One of the problems here is to reduce the invocation overhead which arises from the fact that in practice programs have to be constructed mostly out of modules. This fact implies modules unification and overhead, related to their invocation, data transfer, run-time environment setup, etc. The overhead significantly affects the constructed program efficiency (i.e. program execution time, memory consumption, network load, etc.), which is essential in high performance computing. Programs construction system capabilities in reduction of the overhead highly depend on the computational model employed by the system. In the work we consider the invocation overhead reduction problem through the active knowledge concept [10] — a methodology for efficient programs construction automation in particular subject domains. The concept is based on the theory of parallel programs and systems synthesis on the basis of computational models [11]. It implies that to perform automatic construction of efficient-enough programs in a particular subject domain one has to make a machine-oriented partial formal description of the subject domain called active knowledge base [9]. It contains description of various algorithms, related software modules and peculiarities of the subject domain. Based on active knowledge base it is possible to formulate a class of applied problems to solve and automatically construct a program to solve any of the problems. The key concept here is computational model, which for simplicity can be concerned as a bipartite directed graph of operations and variables vertices. Ingoing and outgoing arcs for particular operation vertex denote its input and output variables. Computational model describes a subject domain in sense that the domain has some variables and there is an ability to compute some variables from some other variables. Each operation can be given a suitable computational module, called code fragment, capable of computing values of its output variables from values of its input variables. Conventional subroutine of given form can serve as an example of a code fragment. The computational process then is concerned as follows. Some variables are assigned with arbitrary values. Any operation can be executed if all its input variables have values. Operation execution is code fragment invocation with values of input and output variables’ values as input and output arguments. Operations are executed (maybe in parallel) until all variables marked as demanded are computed. The computational model can be employed for automatic programs construction. A constructed program consists of two parts. The first one is a set of code fragments contained in the active knowledge base. The second one is generated code, which can be called “glue” code. Its main purpose is to invoke code fragments, pass arguments to them, organize network data transfer and perform other similar tasks. To provide high efficiency of a constructed program the following two conditions have to be satisfied. Firstly, “glue” code has to be efficient. Secondly, the code fragments invocation overhead has to be low enough. For example, if a code fragment is a conventional subroutine, then its invocation requires control passing (call) and data movement between different memory locations and or registers. In conventional compilers this overhead can sometimes be reduced using the inlining technique. If a code fragment is a program written in another language, then corresponding run-time environment and data conversion has to be made. Notably, the inlining technique not always can be employed by the compiler because it relies on complex static code analysis. Unless the compiler is able to extract all necessary information to perform inlining it cannot be applied. An alternative approach is to manually provide code fragments with necessary metainformation. In such case invocation of the code fragment can be implemented not as a procedure call, but as an inline code snippet. Code snippet of particular form is an example of a code fragment with less overhead than a conventional procedure. The active knowledge concept supports this approach by allowing the inclusion of different code fragment types with necessary metainformation into active knowledge base. Another advantage the active knowledge concept suggests is automatic operations aggregation (batching). The idea behind this technique is to combine a group of similar operations into a single code fragment, thus reducing overhead. A practical example is aggregating multiple operations for GPU to reduce input/output data transfer between main memory and GPU memory.