A vectorization of iterative computational processes and time acceleration estimates

O b j e c t i v e s. The problem of efficient organization of the execution of sequential computational processes in the vector mode is solved, taking into account the capabilities of modern high-performance vector-pipeline computers. The relevance of the problem under consideration is due to the fact that processes that occur during cyclic data processing and in iterative algorithms are the most difficult to parallelize. In solving the problem, three main objectives were set. Construction of a mathematical model that takes into account the main architectural and computational features of modern vector-conveyor computers. Calculation of the optimal total execution time of vector operations. Evaluation of the time gain compared to the sequential mode of data processing.

M e t h o d s. To achieve the objectives and to prove the main and auxiliary statements, an original method was used, including establishing the validity of the inductive assumptions in the cases under consideration, as well as an illustrative method of scheduling theory using Gantt charts.

R e s u l t s .   A vector model for the implementation of sequential calculations is proposed, which takes into account  the  main  features  of  vector-conveyor computers. The  optimal  total  execution  time  of  sequential calculations in the vector mode is determined, and a lower estimate of the time gain is obtained in comparison with the sequential mode of their execution.

C o n c l u s i o n. It has been established that when processing scalar input data in the sequential mode by vector operations with a pipeline length k, acceleration is possible by at least a factor nN (nk+N) , where N is the size of the  input,  n  is  the  number of vector and  corresponding scalar operations. The estimation of the  time acceleration in the vectorization of calculations is compared with the sequential mode of their execution.

1. In Chinin G. D. (ed.) Vektorizatsiya programm: teoriya, metody, realizatsiya : sbornik statej. Vectorization of Programs: Theory, Methods, Implementation: Collection of Articles. Moscow, Mir, 1991, 271 p. (In Russ.).

2. Voyevodin V. V., Voyevodin Vl. V. Parallel'nyye vychisleniya. Parallel Computing. Saint Petersburg, BHV-Peterburg, 2002, 608 p. (In Russ.).

3. Toporkov V. V. Modeli raspredelennykh vychisleniy. Distributed Computing Models. Moscow, Fizmatlit, 2004, 320 p. (In Russ.).

4. Miller R., Boxer L. Algorithms Sequential and Parallel: A Unified Approach. 1st ed. Prentice Hall, 1999, 330 p.

5. Pllana S., Xhafa F. Programming Multi Core and Many Core Computing System. John Wiley & Sons, 2017, 528 p.

6. Demidenko V. M., Klyaus P. S., Kovalenko N. S. Library of basic software modules for solving combinatorial ordering problems for a vector-conveyor computer. Problemy sozdaniya superEVM, supersistem i effektivnost' ikh primeneniya : tezisy dokladov Pervoy Vsesoyuznoy konferentsii, Minsk, 15–17 sentyabrya 1987 [Problems of Creating supercomputers, Supersystems and the Effectiveness of Their Application: Abstracts of the Report of the First All-Union Conference, Minsk, 15–17 September 1987]. Minsk, 1987, part 2, pp. 31-32 (In Russ.).

7. Demidenko V. M., Klyaus P. S. On the possibility of efficient pipelining of one combinatorial algorithm. Voprosy kibernetiki. Razrabotka i ispol'zovaniye superEVM [Questions of Cybernetics. Development and use of Supercomputers]. Moscow, Institute of Problems of Cybernetics, 1987, iss. 7, pp. 96-104 (In Russ.).

8. Demidenko V. M., Shevchenko L. I. Basic procedures in lexicographic digital sorting algorithms and their implementation on a vector-conveyor computer. Problemy sozdaniya superEVM, supersistem i effektivnost' ikh primeneniya : tezisy dokladov Pervoy Vsesoyuznoy konferentsii, Minsk, 15–17 sentyabrya 1987 [Problems of Creating supercomputers, Supersystems and the Effectiveness of Their Application: Abstracts of the Report of the First All-Union Conference, Minsk, 15–17 September 1987]. Minsk, 1987, part 2, pp. 33-35 (In Russ.).