|
Article information
2026 , Volume 31, ¹ 1, p.106-120
Korsun A.V., Sushchenko A.A., Shkurkin A.S.
Optimizing the processing of a heterogeneous instruction stream by the processor pipeline
The aim of the work is to optimize the number of phases of the processor pipeline according to the criterion of minimum application execution time and analyze the conditions for the feasibility of pipelining. The study of the pipeline computing process is based on a model of the central processor considered as a homogeneous pipeline processing a heterogeneous flow of commands with heterogeneous probabilities of rebooting the pipeline. Rebooting occurs when branch prediction failures in various sections of the software algorithm. The dependence of the execution time of an application of a given size on the known complexity of individual commands and the overhead of saving and extracting intermediate results from processor control structures at individual pipeline phases is found. Based on the obtained dependence, the ratio for the optimal length of the processor pipeline is calculated analytically, which is found to be consistent with known special cases. Conditions for accelerating calculations in the form of inequalities are formulated for the parameters of the processor pipeline and the characteristics of applications. The obtained ratio for the optimal length of the processor pipeline with dynamic command execution allows assuming that the reboot probability is nonzero only in the sections of the application algorithm which contains conditional operators and commands that follow them within the sliding window (buffer) of processor commands. It allows more accurate accounting for the reasons of the processor pipeline reboots and optimizing the execution time of applications.
[link to elibrary.ru]
Keywords: processor pipeline, pipeline length, heterogeneous command flow, application execution time, application size, probability of pipeline restart
doi: 10.25743/ICT.2026.31.1.009
Author(s):
Korsun Alexander Viktorovich
Office: Tomsk State University
Address: 634050, Russia, Tomsk, Lenin st., 36
E-mail: aleksnfsl5@gmail.com
Sushchenko Andrey Andreevich
Dr.
Office: Institute for Applied Mathematics, Far Eastern Branch, Russian Academy of Science
Address: 690041, Russia, Vladivostok, Lenin st., 36
E-mail: sushchenko.aa@dvfu.ru
SPIN-code: 6699-3415Shkurkin Aleksey Sergeevich
PhD. , Associate Professor
Position: Head of Chair
Office: Tomsk State University
Address: 634050, Russia, Tomsk, Lenin st., 36
E-mail: shkurkin@mail.tsu.ru
SPIN-code: 2172-7582 References:
1. Tannenbaum E., Ostin T. Arkhitektura kompyutera [Computer architecture. 6th edition]. St.Petersburg: Piter; 2021: 816. (In Russ.)
2. Hamacher C., Vranesic Z., Zaky S. Computer organization. Boston: McGraw Hill Comp.; 1996: 555.
3. Sushchenko M.S., Sushchenko S.P. Matematicheskie modeli ierarkhicheskoy pamyati vychislitelnykh sistem [Mathematical models of hierarchical memory of computing systems]. Novosibirsk: Nauka; Tomsk: Izd-vo NTL; 2012: 148. (In Russ.)
4. Sushchenko S.P. Arkhitektura vychislitelnykh sistem. Uchebnoe posobie [Architecture of computing systems. Textbook]. Tomsk: Izdatelskiy Dom “SKK-Press”; 2006: 198. (In Russ.)
5. Emma P.G., Davidson E.S. Characterization of branch and data dependencies in programs for evaluating pipeline performance. IEEE Transactions on Computers. 1987; 36(7):859–875.
6. Hartstein A., Puzak T.R. The optimum pipeline depth for a microprocessor. ACM Sigarch Computer Architecture News. IEEE Computer Society; 2002; 30(2):7–13.
7. Belyaev A.A. The influence of software transitions and dependencies based on data in executable code on the performance of the DSP core pipeline. Izvestiya Vuzov. Electronics. 2009; 3(77):75–80. (In Russ.)
8. Belyaev A.A. Optimal performance depth of the software pipeline for applications with software transitions and dependency according to data. Izvestiya Vuzov. Electronics. 2010; 2(82):48–51.
9. Belyaev A.A. Teoriya, razrabotka i sozdanie problemno-orientirovannyx processornyx yader s optimal’nym vychislitel’nym konvejerom i mnogoyadernyx signal’nyx processorov na ix osnove: Dis. doktora texn. nauk [Theory, development and creation of problem-oriented processor cores with an optimal
computational pipeline and multi-core signal processors based on them]. Moscow: OAO Nauchnoproizvodstvennyy Tsentr “Elektronnye Vychislitel’no-informatsionnye Sistemy”; 2012: 377. (In Russ.)
10. Dubey P.K., Flynn M.J. Optimal pipelining. Journal of Parallel and Distributed Computing. 1990; 8(1):10–19.
11. Flynn M.J., Hung P., Rudd K.W. Deep-submicron microprocessor design issues. IEEE Micro. 1999; 19(4):11–22.
12. Husainov A.A., Titova E.A. Optimal depth of the computational pipeline for a given amount of input data. Computational Technologies. 2018; 23(1):96–104. DOI:10.5072/ICT.2018.1.12004. (In Russ.)
13. Husainov A.A., Chernov A.M., Maevskaya E.D., Romanchenko A.A. Modeli dlya rascheta vremeni raboty vychislitel’nykh konveyerov [Models for calculating the operating time of computational pipelines]. Materialy XXIII Mezhdunarodnoy Nauchno-Prakticheskoy Lonferentsii “Aktual’nye
Problemy Nauki”. Moscow: Izdatel’stvo “Sputnik+”; 2016: 83–91. (In Russ.)
14. Sushchenko S.P. Parametric optimization of a packet switching network. Avtomatika i Vychislitel’naya Tekhnika. 1985; (2):43–49. (In Russ.)
15. Rozanov Yu.A. Sluchaynye protsessy (kratkiy kurs) [Random processes (short course)]. Moscow: Nauka; 1971: 286. (In Russ.)
16. Feller W. An introduction to probability theory and its applications. Vol. 1: Third edition. Revised printing. N.Y., Chichester, Brisbane, Toronto: John Wiley & Sons; 1970.
17. Sushchenko S.P. Analysis of the end-to-end message delay in a multi-link virtual channel. Avtomatika i Vychislitel’naya Tekhnika. 1989; (3):52–64. (In Russ.)
18. Sushchenko S.P. Matematicheskie modeli komp’yuternykh setey [Mathematical models of computer networks]. Tomsk: Izdatel’skiy Dom Tomskogo Gosudarstvennogo Universiteta; 2017: 272. (In Russ.)
19. Vadzinski R.N. Spravochnik po veroyatnostnym raspredeleniyam [Handbook of probability distributions]. St. Petersburg: Nauka; 2001: 295. (In Russ.)
20. Prudnikov A.P., Brychkov Yu.A., Marichev O.I. Integraly i ryady [Integrals and series]. Moscow: Nauka; 1981: 800. (In Russ.)
Bibliography link:
Korsun A.V., Sushchenko A.A., Shkurkin A.S. Optimizing the processing of a heterogeneous instruction stream by the processor pipeline // Computational technologies. 2026. V. 31. ¹ 1. P. 106-120
|
