RU205189U1 - Control device for the selection of means for parallelizing cyclic sections of program code - Google Patents

Abstract

The utility model relates to computer technology, in particular to the field of creation (programming) of parallel programs, and can be used to automatically select a means for parallelizing cyclic sections of programs under development with a different number of loop iterations. complex calculations in cyclic sections of programs due to automatic selection of the optimal (with a minimum running time of the parallelized section) parallelization tool for each cycle and the current number of iterations (repetitions) in the program cycle. The technical result is achieved by using the primary statistical data collected during testing on the execution time of each program cycle with a different number of iterations of this cycle, special processing of the obtained statistical data with the construction of a smoothed empirical time distribution function, and evaluating the cycle execution time along the upper limit of the confidence interval for each tool parallelization and sequential transformation of the processed statistics into an array of optimal parallelization tools, which allows you to quickly search for the number of the optimal loop parallelization tool and significantly reduce the operating time of the target program as a whole. , user interface, block of knowledge acquisition, block of test run, block of statistics storage, block of time estimation, b The novelty of the declared utility model is the collection of statistical data characterizing the execution of each cycle in the form of four parameters when using parallelization tools, building empirical smoothed time distribution functions from the collected statistics, estimating the cycle time at the upper boundary of the confidence interval of the distribution function, creating an array of optimal parallelization tools, accelerated selection of parallelization tools from an array of optimal ones in terms of input parameters - the cycle number and the current number of iterations.

Description

The utility model relates to computer technology, in particular to the field of creation (programming) of parallel programs. The technical problem and the result of the development of a useful model is to reduce the time spent on performing complex calculations in cyclic sections of programs due to the automatic selection of the optimal (with a minimum running time of the parallelized section) parallelization tool for each cycle and the current number of iterations (repetitions) in the program cycle.

Recently, in the field of engineering and scientific and technical calculations, modeling tasks, real-time tasks, there has been a tendency towards rejection of sequential solutions and classical single-processor computers. Almost all modern software being created in the above areas is focused on parallel computing environments. Simultaneously with the growing demand for parallel programs and with the spread of multicore (multiprocessor) computing systems, the development of parallel programs is becoming more and more urgent, since it is advisable to make the most of all the available capabilities of modern computers. At the same time, many computational problems are most effectively solved using multicore computing systems with shared memory (SMP Symmetric Multiprocessing) [1].

At present, intensive research is underway in the field of using all kinds of automation in the creation of parallel programs, in particular in the field of creating development tools, debugging and researching parallel programs. The popularity of systems with shared memory is confirmed by the growth and development of the number of various parallelization tools - standards and technologies such as OpenCL, OpenMP, C ++ AMP, TBB, Cilk Plus, OpenACC, etc., focused on parallel programming, i.e. creation of parallel programs. Despite the fact that all parallelization tools provide the programmer with the ability to work with parallel threads, their interfaces and internal structure are very different. At the moment, there is no exact method for determining the most effective means of parallelization, except for comparing them with each other in relation to a specific problem being solved [2]. Thus, depending on the current context of the program for the same section of the program code, the effectiveness of various parallelization tools will differ. The criterion for the efficiency of parallelization is the execution time of an application with identical hardware and software requirements.

It is expedient to consider cyclic program sections as the direct object of parallelization in the target program, since about 80% of the program's time is spent on the execution of just cycles [3]. Thus, reducing the time spent on the execution of the target program involves the parallelization of cyclic sections of the target program, multithreaded parallel execution in multicore computers.

Parallelization tools for the developer are represented as a "black box"; they are applied by introducing special additions (directives) into the program code, shown in Fig. one.

In practical work on the use of parallelization tools, it was found that there is a dependence of the cycle execution time on the parallelization tool used, which implements the parallelization of this cycle, and on the number of cycle iterations.

, где

- минимальное среди всех средств распараллеливания время работы i-го цикла, N - число запусков распараллеливаемых циклов.Different means of parallelization have their own peculiarities, and depending on the input parameters of the program code being parallelized, they can have different efficiency of the operation shown in Fig. 2. In total, FIG. 2 shows 4 cycles with different lengths (number of iterations). Each cyclic section has characteristic parameters such as the cycle number, the number of repetitions (iterations) in the course of the program operation and the execution time of the given cycle. The rectangles indicate the execution times of the corresponding parallelized loops for the indicated parallelization means. The designations T show the total running times of the target program (consisting of 4 cycles) parallelized using the indicated technologies: Ts - Serial (sequential execution), Tc - Cilk Plus, To - OpenMP, TBT - Boost Threads, TT - TBB. The maximum efficiency (minimum time) of the parallelizable target program can be achieved if it is possible to select the parallelization technology individually for each cycle. Thus, the optimal (Optimal) program execution time will be

where

- the minimum among all parallelization tools, the running time of the i-th cycle, N - the number of starts of the parallelized cycles.

The claimed device automatically selects the optimal means for parallelizing the cyclic section with a minimum cycle time.

The closest solution to the claimed device is the system [4], which includes a knowledge base, an inference engine, working memory, an explanation block, a user interface, and a knowledge acquisition block. And also a close solution is the approach to using several parallelization tools in one developed program [5].

The block diagram of the claimed device is shown in Fig. five.

BZRS - The block of knowledge of the resulting statistics (1) is intended for storing the data of the resulting statistics for the quick selection of the number of the parallelization tool obtained by the device during operation and the calculations performed, the rules and criteria for selecting the parallelization tool by input parameters. Input 1 of the BZRS unit is connected to the output 7 of the MLV unit (2). Output 3 of the BZRS unit is connected to the input 1 of the MLV unit (2). Input 2 of the BZRS unit is connected to the output 4 of the BON unit (10).

MLV - Logic inference machine (2) is designed to provide logical and arithmetic operations with data stored in the PDU block (3), the BZRS block (1) and the BON block (10), as well as for the implementation of control actions, requests, transmission and reception commands and signals necessary for the operation of the device. Inputs 1, 2, 3 and 9 of the MLV unit are connected to the outputs: 3 units BZRS (1), output 2 of the BRP unit (3), output 2 of the BPZ unit (6) and output 3 of the BON unit (10), respectively. Outputs 4, 5, 6, 7 and 8 are connected to inputs: 2 BON blocks (10), input 2 of BHS block (8), input 1 of BO block (4), input 1 of BZRS block (1) and input 1 of BRP block ( 3) respectively.

BRP - Working memory block (3) is intended for storing in memory the necessary initial data (BID 3.1) for performing a test run in the BOD block (7) and obtaining primary statistics, storing the modified program code of the target program (BOD 3.2), storing libraries of parallelization tools (BSR 3.3) required for the parallelization process. Inputs 1 and 4 of the PDU block (3) are connected to the outputs: 8 of the MLV unit (2) and 3 of the BPP unit (7), respectively, outputs 2 and 3 of the PDU unit (3) are connected to the inputs: 2 MLV units (2), 1 unit BTP (7), respectively.

BO - Explanation block (4) is intended for transferring information messages to the PI block (5) when loading and preparing the initial data and other information in the PDU block (3), as well as transmitting the output parameter of the number of the parallelization tool selected by the device to the jointly working target program through the PI block (5). Inputs 1 and 2 of PI block (5) are connected by outputs: 3 BO blocks (4) and 1 block BPZ (6), respectively. Outputs 3 and 4 of PI block (5) are connected to inputs: 2 BO blocks (4) and 3 BPZ blocks (6), respectively.

PI - User interface (5) is intended for interaction with the user (programmer-developer) or with the target program, for the optimization of which the declared device is used. Inputs 1, 2 of PI block (5) and outputs 3, 4 of PI block (5) are connected to outputs 3, 1 and inputs 2, 3 of BO block (4), BPZ block (6), respectively. Input 6 and output 5 of the PI block (5) are the main external input and output of the declared device.

BPZ - The block of knowledge acquisition (6) is intended for organizing a dialogue procedure, the purpose of which is to enter and correct the stored data into the PDU block (3) through the MLV block (2). Input 3 is connected to output 4 of PI block (5). Output 2 and 1 of the BPZ unit (6) are connected to the input 3 of the MLV unit (2) and the input 2 of the PI unit (5), respectively.

BTP - Test run block (7) is designed to carry out a test run of the entered BOD program code (3.2), request and use, if necessary, the initial BID data (3.1) and the BSR parallelization means (3.3), the output parameters of the BTP block (7) are primary statistics a test run in the form of a table row of a specific cycle profile, consisting of: cycle numbers, number of iterations, parallelizer number and execution time. Input 1 is connected to output 3 of the PDU (3). Output 2 is connected to input 1 of the BHS unit (8). Output 3 is connected to input 4 of the PDU block (3).

BCS - Statistics storage unit (8) is intended for storing statistics obtained from the BTP unit (7). Statistics are generated from a test run or added manually. Input 1 is connected to outputs 2 of the BTP unit (7), input 2 is connected to output 5 of the MLV unit (2). Output 3 is connected to input 1 of the BOV unit (9).

BOV - The block for estimating the cycle execution time by means of parallelization (9) is intended for processing statistics obtained from the BCS block (8) and forming time counts to obtain samples of statistics for each cycle with a certain number of iterations, as well as special processing of the obtained statistical data with the construction of a smoothed empirical time distribution functions, and estimating the execution time at the upper bound of the confidence interval for each parallelizer. Input 1 is connected to output 3 of the BHS unit (8). Output 2 is connected to input 1 of the BON unit (10).

BON - The block for determining the number (10) is designed to convert the processed statistics obtained from the BOV block (9) into an array of optimal means (resulting statistics) for parallelization for each cyclic section of the program and transfer to the BZRS block (1), this array allows you to perform accelerated search for the number of the optimal means of parallelizing the loops and significantly reduce the program time as a whole. Inputs 1 and 2 of the BON unit (10) are connected to the outputs 2 of the BOV unit (9) and 4 of the MLV unit (2), respectively. Outputs 3 and 4 of the BON unit (10) are connected to the inputs 9 of the MLV unit (2) and 2 of the BZRS unit (1), respectively.

In the preliminary step shown in FIG. 3 when preparing the target program being developed to work together with the declared device, the developer (programmer) determines in the program code the most expensive cycles (cyclic sections of the program), numbers them, adds additional marks of the beginning and end of the cycle, then copies them into the program code, creating the so-called clones of cycles. Then it adds a parallelization tool to each clone in the form of special directives from the set of parallelization tools available to it (see Fig. 1). This way, each loop gets the same number of clones, equal to the number of parallelizers available.

A target program is a program being developed that requires the most efficient use of the provided hardware and technical capabilities, i.e. parallelization, such as a control program, simulation, complex mathematical calculations in real time.

The body of the program code is increased by a certain number of loop clones, equal to the number of parallelization means, but the duration of the program execution remains the same, since all the clones are not executed during execution, only one selected by the declared device is executed, this is shown in Fig. 4. The process of managing the optimal choice of the clone (with the parallelization tool applied) allows to reduce the time spent executing the cyclic sections of the program and the entire program as a whole. This is due to the fact that the time spent on executing the same cyclic section with a given number of iterations when using different parallelization tools will differ significantly. Therefore, optimization of the choice of a branch (clone) of the program allows you to reduce the time spent on executing the cycle and the program as a whole. The operation of the device is automated, according to the input parameters of the cyclic section of the target program (cycle number and the number of iterations in the cycle). The declared device generates a decision on the parallelization tool used and a command is formed to connect one of the branches of the cloned given cyclic program section with a minimum cycle parallelization time.

The operation of the device involves two stages. The first preparatory stage is necessary for loading the target program code, source data and libraries of parallelization tools, as well as performing a test run of the target program and filling in the initial statistics. The second stage is directly the operation of the device with automatic selection of the parallelization tool for each cyclic section of the target program interacting with the declared device.

At the first stage, the device is prepared for operation, for this purpose, at the input 6 of the PI block (5), the following are sequentially entered: the code of the target program, initial data and libraries of parallelization tools, from the output of which the packets enter the input 3 of the BPZ block (6), from the output 2 of which are fed to the input 3 of the MLV unit (2) and from the output 8 of which they enter the input 2 of the PDU unit (3) (BID (3.1), BOD (3.2), BSR (3.3)), respectively, this is where the preparation of the device for the test run ends ...

After that, at the operator's command from the output 4 of the PI block (5), a command is generated to turn on the device into the test "run" mode of the target program to collect primary statistics, the generated control command in the form of a signal is fed to input 3 of the BPZ block (6), from output 2 which is fed to the input 3 of the MLV unit (2) with subsequent transmission from outputs 4,5,6,7,8 to the corresponding inputs: input 2 of the BON unit (10), input 2 of the BCS unit (8), input 1 of the BO unit (4 ), input 1 of the BZRS block (1), input 1 of the RP block (3) to initiate their operation in a given mode.

After receiving the control signal about the start of the device operation, from the output 3 of the BOD block (3.2) to the input 1 of the BTP block (7), a modified program code is fed, followed by loading the initial data from the BID block (3.1) for a test run. In the FTP block (7), based on the modified program and initial data, a test run of all clones of all cycles is performed, with the cycle number, the time of its beginning and end, the number of iterations in this cycle, and the number of the parallelization tool fixed. Application of means of parallelization occurs according to the directives set before each clone of the cyclic section of the program. When a directive is found to parallelize the next clone of the cyclic section from the output 3 of the BTP block (7), a request command is generated to connect the library of the parallelization tool to this clone to control the parallelization of the clone, which is fed to input 4 of the BSR block (3.3).

At the end of the execution of one of the clones of this cyclic section, the time of the clone execution is recorded. Subsequent clones of the cyclic sections of the target program are executed in the same way.

At the output 2 of the BTP block, the parameters of the cycle time-iteration profile are formed for each clone in the form of four parameters (cycle number, number of iterations, the number of the parallelization tool, the execution time of the clone of this cycle), which are fed to the input 1 of the BCS block (8) to fill the table primary statistics (time-iteration profile). The modified program code of the target program is completely "run" by the BTP block (7) with the formation of the time-iteration profile of all cycles and clones of the cycles.

Due to the fact that the parameter of the cycle execution time is a random variable, and the probability distribution function of the cycle execution time is unknown, therefore, it becomes necessary to repeat the "test run" 3-5 times to collect a sufficient amount of statistical data and then form a time sample from the statistics profile with 3-5 counts for each cycle and parallelization facility.

The data of the initial statistics accumulated in the BCS block (8) from the output 3 is fed to the input 1 of the BOV block (9), where the primary statistical data received at the input is processed, the empirical distribution functions of the execution time of each cycle for a certain number of iterations are mathematically constructed [6], each empirical distribution function is approximated by a smooth curve using Bernstein polynomials [7], the values of the upper bound of the confidence interval of the execution time of each cycle for a certain number of iterations are estimated, a modified time-iteration profile for each cycle is formed in the form (cycle number, number of iterations, tool number parallelization, the upper bound on the execution time of this cycle). The resulting modified profile is transmitted from output 2 to input 1 of the BON block (10).

In the BON block (10), for all the time-iteration profiles of each cycle received and processed in the BOV block (10), an array of the resulting statistics of the optimal means for parallelizing the cycle is formed. Thus, the resulting statistics has the form of an array with intervals of the initial and final number of loop iterations, the number of the optimal parallelization tool for this iteration interval. From the output 4 of the BON block (10) to the input 2 of the BZRS block (1), the resulting statistics are fed for saving and subsequent use when choosing a parallelization tool, which will allow a quick selection of the optimal tool.

At the second stage of the operation of the claimed device, when the target program and the device connected to it work together, the work proceeds as follows, the input data received from the target program in the form of a cycle number and the number of iterations is fed from the target program to the input 6 of the PI block (5) in a loop, from the output 4 of which these data are fed to the input 3 of the BPZ block (6) and from the output 2 of which they are fed to the input 3 of the MLV block (2). To the other input 1 of the MLV block (2) from the output 3 of the BZRS block (1), an array of the resulting statistics of the optimal means for parallelizing the cycle is fed. Based on the input data and the available resulting statistics, in the MLV block (2), they are compared and a conclusion is made that the input data has entered the corresponding iterative interval of the resulting statistics array, and the optimal parallelization tool is instantly selected. Based on the results of choosing the number of the optimal parallelization tool, a response signal is generated with the tool number, which from the output 6 of the MLV block (2) is fed to the input 1 of the BO block (4), and then from the output 3 of which it is fed to the input 1 of the PI block (5) and through the output 5 of the PI block (5) is fed to the control of the connection of the optimal means in the target program working together with the declared device.

If the resulting statistics do not fall into the generated intervals, the input data received from the output 4 of the MLV block (2) is fed to the input 2 of the BON block (10), where the cycle execution time is mathematically calculated according to the graphs of the approximated trends in the time change versus the number of iterations for the available parallelization tools. Next, the optimal tool is selected according to the minimum cycle execution time and from the output 3 of the BON block (10) the signal goes to the input 9 of the MLV block (2), and then to the output 6 and further stages are similar when the input data of the cycle enters the iteration interval.

In the current mode of joint operation of the target program and the declared device, statistics of the execution of the cyclic sections of the target program are collected and the primary statistics are systematically replenished in the BCS block (8) to correct the array of the resulting statistics of the optimal parallelization tools.

In addition, the data located in the BCS block (8) and the data located in the BZRS block (1) can be corrected through the PI block (5) in manual mode.

The elements of the claimed utility model are made in the form of software and hardware modules on a PC expansion board of x86 architecture.

By conducting experiments on the research modeling complex of military operations at the Military Academy of Aerospace Defense named after Marshal of the Soviet Union G.K. Zhukov, it was found that the use of the claimed device can reduce the time needed to obtain simulation results and operational-tactical calculations by 1.3-1.4 times.

The presented version of the claimed device does not exhaust the possible ways of its practical implementation.

Sources taken into account:

1. Automatic Paralleli / ation. Carnegie Mellon University, HPCA-4, February 1-4, 1998. Sutter H. The Free Lunch Is Over A Fundamental Turn Toward Concurrency in Software. Dr. Dobb's Journal, March 2005.

2. Aksenov M.A. Analysis of Parallel Programming Technologies for Application in Modeling Complexes for Military Purposes in the Interest of Increasing the Efficiency of Modeling // Collection of Scientific Papers of the IV All-Russian Scientific and Practical Conference "Topical Issues of the State and Prospects for the Development of Complex Technical Systems for Military Purpose" Bauman. 2020.P.77-86.

3. Voevodin VV, Voevodin Vl.V. Parallel computing. St. Petersburg: St. Petersburg, 2002. 608 p.

4. Jaratano D., Riley G. Expert systems. Design and programming principles. - M .: Publishing house "Williams", 2007, fig. 1.6, p. 70;

5. Andreev A.E. Technologies for programming multiprocessor systems: textbook. allowance / Andreev A.E., Egunov V.A., Shapovalov O.V .; VolgSTU. Volgograd, 2015.103 p.

6. Krasovsky Yu.M. Mathematical foundations of military cybernetics [Text]: (Textbook) / Yu.M. Krasovsky, M.S. Lyubushkin; Resp. ed. M.S. Lyubushkin; Military. team acad. anti-aircraft. defense. Department number 12. - Kalinin: [b. and.], 1971. - 446 p.

7. Golik F.V. Approximation of empirical probability distributions by Bernstein polynomials. Radio Electronics Journal [electronic journal]. 2018. No. 7.

Claims (1)

The control device for the selection of means for parallelization of cyclic sections of the program code is implemented by the block of the logical inference machine (MLV), which performs the operation of choosing the optimal parallelization tool based on the input data in the form of the cycle number and the number of iterations in the cycle, obtained from the knowledge acquisition unit (KLU) and the array of resulting statistics optimal means of parallelizing a cycle obtained from a block of knowledge of the resulting statistics (BZRS), containing a block of the knowledge base of the resulting statistics (BZRS), a block of an inference machine (MLV), a block of working memory (BW), an explanation block (BO), a user interface (PI ), a block of knowledge acquisition (BPZ), where 3 output and 1 input of the BZRS block are connected to 1 input and 7 output, respectively, of the MLV unit, 8 and 6 outputs of which are connected to 1 inputs, respectively, of the BRP and BO blocks, the 3 output and 2 inputs of which are connected with 1 input and 3 output, respectively, of the PI block, 6 input and 5 output of which are the main external and the input and output of the device, and output 4 and input 2 of the PI unit are connected to the 3 input and 1 output, respectively, of the BPZ unit, the 2 output of which is connected to the 3 input of the MLV unit, characterized in that, according to the utility model, it additionally contains a test run unit (BTP) , a statistics storage unit (BCS), a unit for evaluating the cycle execution time by means of parallelization (BOV), a unit for determining the number of a parallelization tool (BON), a working memory unit (BDU), which additionally includes a block of initial data (BID), a block of program code ( BPK), a block of parallelization means (BSR), while the 2 and 3 outputs of the PDU block are connected to 2 and 1 inputs of the MLV and BTP blocks, respectively, and the input 4 of the PDU block is connected to the 3rd output of the BTP unit, the 2nd output of which is connected to 1 input of the block BCS, the 3 output of which is connected to 1 input of the BOV unit, and the 2 input of the BCS unit is connected to the 5 output of the MLV unit, which performs the operation of choosing the optimal parallelization tool based on the input data at input 3 in the form of a qi number kla and the number of iterations in the cycle obtained from the output of the 2 block of knowledge acquisition (BK) and the array of the resulting statistics of the optimal means of parallelizing the cycle obtained at the input 1 from the output of the 3 block of knowledge of the resulting statistics (BZRS), 4 output and 9 input of the MLV block are connected to 2 input and 3 output, respectively, of the BON block, 4 output and 1 input of which are connected to the 2 input and 2 output of the BZRS and BOV blocks, respectively, and the control inputs and outputs of the BID, BOD, BSR blocks, which are part of the BRP block, have the same numbers for each block.

Images