mireabulletinRussian Technological JournalRussian Technological Journal2782-32102500-316XRTU MIREA10.32362/2500-316X-2021-9-6-7-15mireabulletin-394Research ArticleИНФОРМАЦИОННЫЕ СИСТЕМЫ. ИНФОРМАТИКА. ПРОБЛЕМЫ ИНФОРМАЦИОННОЙ БЕЗОПАСНОСТИINFORMATION SYSTEMS. COMPUTER SCIENCES. ISSUES OF INFORMATION SECURITYСравнительный анализ методов оптимизации программного обеспечения для борьбы с предикацией ветвлений на графических процессорахComparative analysis of software optimization methods in context of branch predication on GPUshttps://orcid.org/0000-0002-7323-9595СесинИ. Ю.SesinI. Yu.

Сесин Игорь Юрьевич, аспирант, кафедра инструментального и прикладного программного обеспечения Института информационных технологий

119454, Россия, Москва, пр-т Вернадского, д. 78

Igor Yu. Sesin, Postgraduate Student, Department of the Tool and Applied Software, Institute of Information Technologies

78, Vernadskogo pr., Moscow, 119454 Russia

isesin@protonmail.comhttps://orcid.org/0000-0002-4922-7260БолбаковР. Г.BolbakovR. G.

Болбаков Роман Геннадьевич, к.т.н., доцент, заведующий кафедрой инструментального и прикладного программного обеспечения Института информационных технологий

119454, Россия, Москва, пр-т Вернадского, д. 78

Roman G. Bolbakov, Cand. Sci. (Eng.), Associate Professor, Head of the Department of the Tool and Applied Software, Institute of Information Technologies

78, Vernadskogo pr., Moscow, 119454 Russia

bolbakov@mirea.ruМИРЭА – Российский технологический университетРоссияMIREA – Russian Technological UniversityRussian Federation20210212202196715Copyright © Сесин И.Ю., Болбаков Р.Г., 20212021Сесин И.Ю., Болбаков Р.Г.Sesin I.Y., Bolbakov R.G.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.rtj-mirea.ru/jour/article/view/394

Технология GPGPU (General Purpose computing for Graphical Processing Units – расчеты общего назначения на графических процессорах) является мощным инструментом для переноса задач параллельной обработки информации на GPU (Graphical Processing Unit – графический процессор). Эта технология находит применение практически в любой области, требующей проведения массы параллельных расчетов, и применяется как в научной и коммерческой, так и в любительской среде. Разработчики программ общего назначения, запускаемых на GPU, неизбежно сталкиваются с падением производительности ввиду предикации ветвления кода. В условиях предикации ветвления исполняются обе ветви условного оператора вне зависимости от истинности условия, но посредством маскирования выполняемых инструкций программа учитывает только результат работы верной ветви. Из-за этого программы общего назначения, имеющие большие участки кода, скрытые за условными операторами, становятся существенно менее производительными на графических процессорах. В статье рассматриваются существующие в предметной области методы и подходы к увеличению производительности программного обеспечения в рамках их применимости к решению проблемы падения производительности при предикации. Приводится описание методов, их сильных и слабых сторон, а также рамок их применимости, на базе чего делается заключение о возможности их использования на GPU. В число рассмотренных методов и подходов вошли следующие: оптимизирующие компиляторы, JIT-компиляция, предсказатель переходов, спекулятивное исполнение, адаптивная оптимизация, специализация алгоритма во время исполнения, оптимизация на основе профилирования. Показано, что указанные аппаратные и программные подходы к увеличению производительности программного обеспечения преимущественно ориентированы на решение проблем специфичных для CPU (Central Processing Unit – центральный процессор) и в целом неприменимы для разрешения потерь производительности при предикации на GPU. Указывается на необходимость создания отдельного подхода, ориентированного именно на решение проблемы предикации ветвления на GPU.

General Purpose computing for Graphical Processing Units (GPGPU) technology is a powerful tool for offloading parallel data processing tasks to Graphical Processing Units (GPUs). This technology finds its use in variety of domains – from science and commerce to hobbyists. GPU-run general-purpose programs will inevitably run into performance issues stemming from code branch predication. Code predication is a GPU feature that makes both conditional branches execute, masking the results of incorrect branch. This leads to considerable performance losses for GPU programs that have large amounts of code hidden away behind conditional operators. This paper focuses on the analysis of existing approaches to improving software performance in the context of relieving the aforementioned performance loss. Description of said approaches is provided, along with their upsides, downsides and extents of their applicability and whether they address the outlined problem. Covered approaches include: optimizing compilers, JIT-compilation, branch predictor, speculative execution, adaptive optimization, run-time algorithm specialization, profile-guided optimization. It is shown that the aforementioned methods are mostly catered to CPU-specific issues and are generally not applicable, as far as branch-predication performance loss is concerned. Lastly, we outline the need for a separate performance improving approach, addressing specifics of branch predication and GPGPU workflow.

расчеты общего назначения на графических процессорахоптимизирующие компиляторыпредикацияgeneral-purpose computing for graphical processing unitsoptimizing compilerspredicationReferencesMarkidis S., Chien S.W.D., Laure E., Peng I.B., Vetter J.S. NVIDIA Tensor Core Programmability, Performance & Precision. In: 2018 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW). Vancouver, BC, Canada; 2018, p. 522−531. https://doi.org/10.1109/IPDPSW.2018.00091Markidis S., Chien S.W.D., Laure E., Peng I.B., Vetter J.S. NVIDIA Tensor Core Programmability, Performance & Precision. In: 2018 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW). Vancouver, BC, Canada; 2018, p. 522−531. https://doi.org/10.1109/IPDPSW.2018.00091Sanzharov V.V., Gorbonosov A.I., Frolov V.A., Voloboy A.G. Examination of the Nvidia RTX. CEUR Workshop Proceedings. 2019;2485:7−12. http://dx.doi.org/10.30987/graphicon-2019-2-7-12Sanzharov V.V., Gorbonosov A.I., Frolov V.A., Voloboy A.G. Examination of the Nvidia RTX. CEUR Workshop Proceedings. 2019;2485:7−12. http://dx.doi.org/10.30987/graphicon-2019-2-7-12Flynn M.J. Very high speed computing systems. Proceedings of the IEEE. 1966;54(12):1901−1909. https://doi.org/10.1109/PROC.1966.5273Flynn M.J. Very high speed computing systems. Proceedings of the IEEE. 1966;54(12):1901−1909. https://doi.org/10.1109/PROC.1966.5273Fisher J.A., Faraboschi P., Young C. Embedded computing: A VLIW approach to architecture, compilers, and tools. Elsevier; 2004. ISBN: 978-1-55860-766-8. URL: https://www.researchgate.net/publication/220690439_Embedded_computing_a_VLIW_approach_to_architecture_compilers_and_toolsFisher J.A., Faraboschi P., Young C. Embedded computing: A VLIW approach to architecture, compilers, and tools. Elsevier; 2004. ISBN: 978-1-55860-766-8. URL: https://www.researchgate.net/publication/220690439_Embedded_computing_a_VLIW_approach_to_architecture_compilers_and_toolsKnoop J., Rüthing O., Steffen B. Partial dead code elimination. In: Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation (PLDI ‘94). 1994, p. 147−158. https://doi.org/10.1145/178243.178256Knoop J., Rüthing O., Steffen B. Partial dead code elimination. In: Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation (PLDI ‘94). 1994, p. 147−158. https://doi.org/10.1145/178243.178256Fink S., Knobe K., Sarkar V. Unified analysis of array and object references in strongly typed languages. In: Palsberg J. (Ed.). Static Analysis. SAS 2000. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. 2000. V. 1824. P. 155−174. https://doi.org/10.1007/978-3-540-45099-3_9Fink S., Knobe K., Sarkar V. Unified analysis of array and object references in strongly typed languages. In: Palsberg J. (Ed.). Static Analysis. SAS 2000. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. 2000. V. 1824. P. 155−174. https://doi.org/10.1007/978-3-540-45099-3_9Runeson J., Nyström S.-O. Retargetable graph-coloring register allocation for irregular architectures. In: Krall A. (Ed.). Software and Compilers for Embedded Systems (SCOPES 2003). Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. 2003. V. 2826. P. 240−254. https://doi.org/10.1007/978-3-540-39920-9_17Runeson J., Nyström S.-O. Retargetable graph-coloring register allocation for irregular architectures. In: Krall A. (Ed.). Software and Compilers for Embedded Systems (SCOPES 2003). Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. 2003. V. 2826. P. 240−254. https://doi.org/10.1007/978-3-540-39920-9_17Blindell G.H. Instruction Selection: Principles, Methods, & Applications. Springer; 2016. 171 p. ISBN 978-3-319-34017-3. http://dx.doi.org/10.1007/978-3-319-34019-7Blindell G.H. Instruction Selection: Principles, Methods, & Applications. Springer; 2016. 171 p. ISBN 978-3-319-34017-3. http://dx.doi.org/10.1007/978-3-319-34019-7Gibbons P.B., Muchnick S.S. Efficient instruction scheduling for a pipelined architecture. ACM SIGPLAN Notices. 1986;21(7):11−16. https://doi.org/10.1145/13310.13312Gibbons P.B., Muchnick S.S. Efficient instruction scheduling for a pipelined architecture. ACM SIGPLAN Notices. 1986;21(7):11−16. https://doi.org/10.1145/13310.13312Su Ch.-L., Tsui Ch.-Y., Despain A.M. Low power architecture design and compilation techniques for high-performance processors. In: Proceedings of COMPCON ʼ94. 1994, p. 489−498. https://doi.org/10.1109/CMPCON.1994.282878Su Ch.-L., Tsui Ch.-Y., Despain A.M. Low power architecture design and compilation techniques for high-performance processors. In: Proceedings of COMPCON ʼ94. 1994, p. 489−498. https://doi.org/10.1109/CMPCON.1994.282878Aycock J. A brief history of just-in-time. ACM Comput. Surv. 2003;35(2):97−113. https://doi.org/10.1145/857076.857077Aycock J. A brief history of just-in-time. ACM Comput. Surv. 2003;35(2):97−113. https://doi.org/10.1145/857076.857077Ogihara M. Fundamentals of Java Programming. Springer; 2018. 532 p.Ogihara M. Fundamentals of Java Programming. Springer; 2018. 532 p.Sage K. The Origins of Programming. In: Concise Guide to Object-Oriented Programming. Undergraduate Topics in Computer Science. Springer, Cham.; 2019, p. 1−9. https://doi.org/10.1007/978-3-030-13304-7_1Sage K. The Origins of Programming. In: Concise Guide to Object-Oriented Programming. Undergraduate Topics in Computer Science. Springer, Cham.; 2019, p. 1−9. https://doi.org/10.1007/978-3-030-13304-7_1Saabith A.S., Fareez M.M.M., Vinothraj T. Python current trend applications-an overview. IJAERD. 2019;6(10):6−12. URL: http://ijaerd.com/papers/finished_papers/IJAERDV06I1085481.pdfSaabith A.S., Fareez M.M.M., Vinothraj T. Python current trend applications-an overview. IJAERD. 2019;6(10):6−12. URL: http://ijaerd.com/papers/finished_papers/IJAERDV06I1085481.pdfMcFarling S. Combining Branch Predictors. Digital Western Research Lab (WRL). Technical Report, TN-36. 1993. 29 р. URL: https://www.hpl.hp.com/techreports/Compaq-DEC/WRL-TN-36.pdfMcFarling S. Combining Branch Predictors. Digital Western Research Lab (WRL). Technical Report, TN-36. 1993. 29 р. URL: https://www.hpl.hp.com/techreports/Compaq-DEC/WRL-TN-36.pdfSkadron K., Martonosi M., Clark D.W. A Taxonomy of branch mispredictions, and alloyed prediction as a robust solution to wrong-history mispredictions. In: Proceedings of the 2000 International Conference on Parallel Architectures and Compilation Techniques. Philadelphia. 2000. https://doi.org/10.1109/PACT.2000.888344Skadron K., Martonosi M., Clark D.W. A Taxonomy of branch mispredictions, and alloyed prediction as a robust solution to wrong-history mispredictions. In: Proceedings of the 2000 International Conference on Parallel Architectures and Compilation Techniques. Philadelphia. 2000. https://doi.org/10.1109/PACT.2000.888344Vintan L.N., Iridon M. Towards a high performance neural branch predictor. In: IJCNNʼ99. International Joint Conference on Neural Networks Proceedings. 1999. https://doi.org/10.1109/IJCNN.1999.831066Vintan L.N., Iridon M. Towards a high performance neural branch predictor. In: IJCNNʼ99. International Joint Conference on Neural Networks Proceedings. 1999. https://doi.org/10.1109/IJCNN.1999.831066Kocher P., Horn J., Fogh A., Genkin D., et al. Spectre attacks: Exploiting speculative execution. In: 2019 IEEE Symposium on Security and Privacy (SP). 2019. 19 p. https://doi.org/10.1109/SP.2019.00002Kocher P., Horn J., Fogh A., Genkin D., et al. Spectre attacks: Exploiting speculative execution. In: 2019 IEEE Symposium on Security and Privacy (SP). 2019. 19 p. https://doi.org/10.1109/SP.2019.00002Bhattacharyya A., Sandulescu A., Neugschwandtner M., Sorniotti A., et al. SMoTherSpectre: exploiting speculative execution through port contention. In: Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security (CCS ʼ19). 2019, p. 785−800. https://doi.org/10.1145/3319535.3363194Bhattacharyya A., Sandulescu A., Neugschwandtner M., Sorniotti A., et al. SMoTherSpectre: exploiting speculative execution through port contention. In: Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security (CCS ʼ19). 2019, p. 785−800. https://doi.org/10.1145/3319535.3363194Chen G., Chen S., Xiao Y., Zhang Y., Lin Z., Lai T.H. SgxPectre: Stealing intel secrets from SGX enclaves via speculative execution. In: 2019 IEEE European Symposium on Security and Privacy (EuroS&P). IEEE. 2019, p. 142−157. https://doi.org/10.1109/EuroSP.2019.00020Chen G., Chen S., Xiao Y., Zhang Y., Lin Z., Lai T.H. SgxPectre: Stealing intel secrets from SGX enclaves via speculative execution. In: 2019 IEEE European Symposium on Security and Privacy (EuroS&P). IEEE. 2019, p. 142−157. https://doi.org/10.1109/EuroSP.2019.00020Arnold M., Fink S., Grove D., Hind M., Sweeney P.F. Adaptive optimization in the Jalapeno JVM. In: Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications. 2000, p. 47–65. https://doi.org/10.1145/353171.353175Arnold M., Fink S., Grove D., Hind M., Sweeney P.F. Adaptive optimization in the Jalapeno JVM. In: Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications. 2000, p. 47–65. https://doi.org/10.1145/353171.353175Riazanov A. Implementing an Efficient Theorem Prover. PhD thesis. The University of Manchester; 2003. 210 p. URL: https://www.researchgate.net/publication/2906405_Implementing_an_Efficient_Theorem_ProverRiazanov A. Implementing an Efficient Theorem Prover. PhD thesis. The University of Manchester; 2003. 210 p. URL: https://www.researchgate.net/publication/2906405_Implementing_an_Efficient_Theorem_ProverGrant B., Mock M., Philipose M., Chambers C., Eggers S.J. Annotation-directed run-time specialization in C. ACM SIGPLAN Not. 1997;32(12):163−178. https://doi.org/10.1145/258994.259016Grant B., Mock M., Philipose M., Chambers C., Eggers S.J. Annotation-directed run-time specialization in C. ACM SIGPLAN Not. 1997;32(12):163−178. https://doi.org/10.1145/258994.259016Pettis K., Hansen R.C. Profile guided code positioning. In: Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation (PLDI ‘90). 1990, p. 16−27. https://doi.org/10.1145/93542.93550Pettis K., Hansen R.C. Profile guided code positioning. In: Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation (PLDI ‘90). 1990, p. 16−27. https://doi.org/10.1145/93542.93550Wicht B., Vitillo R.A, Chen D., Levinthal D. Hardware Counted Profile-Guided Optimization. 24 November 2014. URL: https://arxiv.org/pdf/1411.6361.pdfWicht B., Vitillo R.A, Chen D., Levinthal D. Hardware Counted Profile-Guided Optimization. 24 November 2014. URL: https://arxiv.org/pdf/1411.6361.pdf

The authors declare that there are no conflicts of interest present.