Анализ исполнения фрагментированных программ на основе факторов SLOW

Сергей Евгеньевич Киреев, Василий Сергеевич Литвинов

Аннотация


При исполнении параллельных программ, основанных на парадигме параллелизма задач, требуется решать ряд проблем, таких как выбор порядка запуска задач с учетом зависимостей между ними, распределение данных и задач по параллельным процессам, балансировка нагрузки на ресурсы. Эти проблемы относятся к области системного параллельного программирования, и их решение, как правило, обеспечивается специальной исполнительной системой. От качества решения этих проблем, а также от структуры и свойств прикладного алгоритма, лежащего в основе параллельной программы, зависит получаемая производительность. Если производительность программы недостаточна, то требуется ее оптимизация, а для этого нужно знать те причины («узкие места»), которые ограничивают ее производительность. Для определения узких мест программы обычно применяется профилирование, т.е. сбор некоторых характеристик исполнения, которые могут указать на источник проблемы. Однако обычные широко используемые средства профилирования параллельных программ не позволяют дать ответ в требуемых понятиях из-за сложности анализа асинхронного исполнения множества задач, а также из-за неспособности выделить в исполняющейся программе прикладную (множество задач) и системную (исполнительная система) компоненты. Поэтому для таких программ требуется разработка новых методов профилирования и анализа. В статье рассматривается проблема получения «понятных» характеристик выполнения параллельных программ на основе параллелизма задач для анализа производительности и оптимизации. Предлагается количественно оценить степень влияния следующих факторов: нехватка работы (Starvation), передача данных (Latency), накладные расходы (Overhead) и конфликт при доступе к общим ресурсам (Waiting for contention resolution). Представлен алгоритм получения соответствующих характеристик для системы фрагментированного программирования LuNA, а также способ их анализа для оптимизации LuNA-программ. Корректность подхода продемонстрирована на ряде синтетических экспериментов. Показано применение подхода к анализу «реальной» программы численного моделирования.

Ключевые слова


анализ производительности; параллельное программирование; фрагментированное программирование; параллелизм задач; система LuNA

Полный текст:

PDF

Литература


Thoman P., Dichev K., Heller T., et al. A taxonomy of task-based parallel programming technologies for high-performance computing. The Journal of Supercomputing. 2018. Vol. 74. P. 1422–1434. DOI: 10.1007/s11227-018-2238-4.

Kaiser H., Heller T., Adelstein-Lelbach B., et al. HPX: A Task Based Programming Model in a Global Address Space. 8th International Conference on PGAS Programming Models, PGAS’2014, Eugene OR, USA, October 6–10, 2014. Proceedings. Article 6. ACM, 2014. P. 1–11. DOI: 10.1145/2676870.2676883.

Malyshkin V.E., Perepelkin V.A. LuNA Fragmented Programming System, Main Functions and Peculiarities of Run-Time Subsystem. 11th International Conference on Parallel Computing Technologies, PaCT-2011, Kazan, Russia, September 19–23, 2011. Proceedings. Vol. 6873 / ed. by V. Malyshkin. Springer, 2011. P. 53–61. Lecture Notes in Computer Science. DOI: 10.1007/978-3-642-23178-0_5.

Shende S., Malony A.D. The TAU Parallel Performance System. International Journal of High Performance Computing Applications. 2006. Vol. 20. No. 2. P. 287–311. DOI: 10.1177/1094342006064482.

Lorenz D., Feld C. Scaling Score-P to the next level. Procedia Computer Science. 2017. Vol. 108. P. 2180–2189. DOI: 10.1016/j.procs.2017.05.107.

Extrae instrumentation package. URL: https://tools.bsc.es/extrae (accessed: 23.04.2024).

Vampir 10.4. URL: https://vampir.eu/ (accessed: 23.04.2024).

Zhukov I., Feld C., Geimer M., et al. Scalasca v2: Back to the Future. 8th International Workshop on Parallel Tools for High Performance Computing, HLRS, Stuttgart, Germany, October, 2014. Proceedings. Ed. by C. Niethammer, J. Gracia, A. Knüpfer, M. Resch, W. Nagel. Springer, 2015. P. 1–24. DOI: 10.1007/978-3-319-16012-2_1.

Mantovani F., Calore E. Multi-Node Advanced Performance and Power Analysis with Paraver. Advances in parallel computing. Vol. 32. IOS Press, 2018. P. 723–732. DOI: 10.3233/978-1-61499-843-3-723.

Intel Trace Analyzer and Collector. URL: https://www.intel.com/content/www/us/en/developer/tools/oneapi/trace-analyzer.html (accessed: 23.04.2024).

Huynh A., Thain D., Pericas M., Taura K. DAGViz: a DAG visualization tool for analyzing task-parallel program traces. 2nd WS on Visual Performance Analysis, VPA '15, November, 2015. Proceedings. No. 3. ACM, 2015. P. 1–8. DOI: 10.1145/2835238.2835241.

Huynh A., Taura K. Delay Spotter: A Tool for Spotting Scheduler-Caused Delays in Task Parallel Runtime Systems. 2017 IEEE International Conference on Cluster Computing, CLUSTER, Honolulu, HI, USA, September 5–8, 2017. IEEE, 2017. P. 114–125. DOI: 10.1109/CLUSTER.2017.82.

Ceballos G., Grass T., Hugo A., Black-Schaffer D. Analyzing performance variation of task schedulers with TaskInsight. Parallel Computing. 2018. Vol. 75. P. 11–27. DOI: 10.1016/j.parco.2018.02.003.

Pinto V.G. Performance Analysis Strategies for Task-based Applications on Hybrid Platforms: PhD thesis / Vinicius Garcia Pinto. Universidade Federal do Rio Grande do Sul - UFRGS, Brazil, UGA - Universite Grenoble Alpes, France, 2018. URL: https://theses.hal.science/tel-01962333.

Pinto V.G., Nesi L.L., Miletto M.C., Schnorr L.M. Providing In-depth Performance Analysis for Heterogeneous Task-based Applications with StarVZ. 2021 IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW, Portland, OR, USA, June 17–21, 2021. IEEE, 2021. P. 16–25. DOI: 10.1109/IPDPSW52791.2021.00013.

Malyshkin V.E. Fragmented programming technology. Bulletin of the South Ural State University. Computational Mathematics and Software Engineering. 2012. No. 46(305), Iss. 1. P. 45–55. (in Russian) DOI: 10.14529/cmse120104.

Bosilca G., Bouteiller A., Danalis A., et al. PaRSEC: Exploiting Heterogeneity to Enhance Scalability. Computing in Science & Engineering. 2013. Vol. 15. No. 6. P. 36–45. DOI: 10.1109/MCSE.2013.98.

Dokulil J., Benkner S. The OCR-Vx experience: lessons learned from designing and implementing a task-based runtime system. The Journal of Supercomputing. 2022. Vol. 78. P. 12344–12379. DOI: 10.1007/s11227-022-04355-0.

Bauer M., Treichler S., Slaughter E., Aiken A. Legion: Expressing locality and independence with logical regions. International Conference on High Performance Computing, Networking, Storage and Analysis, SC'12, Salt Lake City, UT, USA, November 10–16, 2012. Proceedings. IEEE, 2012. P. 1–11. DOI: 10.1109/SC.2012.71.

Akhmed-Zaki D., Lebedev D., Perepelkin V. Implementation of a three dimensional three-phase fluid flow ("oil-water-gas") numerical model in LuNA fragmented programming system. The Journal of Supercomputing. 2017. Vol. 73. P. 624–630. DOI: 10.1007/s11227-016-1780-1.

Daribayev B., Perepelkin V., Lebedev D., Akhmed-Zaki D. Implementation of the Two-Dimensional Elliptic Equation Model in LuNA Fragmented Programming System. IEEE 12th International Conference on Application of Information and Communication Technologies, AICT 2018, Almaty, Kazakhstan, October 17–19, 2018. Proceedings. IEEE, 2018. P. 161–164. DOI: 10.1109/ICAICT.2018.8747145.

Akhmed-Zaki D., Lebedev D., Perepelkin V. Implementation of a 3D model heat equation using fragmented programming technology. The Journal of Supercomputing. 2019. Vol. 75. No. 12. P. 7827–7832. DOI: 10.1007/s11227-018-2710-1.

Akhmed-Zaki D., Lebedev D., Malyshkin V., Perepelkin V. Automated Construction of High Performance Distributed Programs in LuNA System. 15th International Conference on Parallel Computing Technologies, PaCT 2019, Almaty, Kazakhstan, August 19–23. Proceedings. Vol. 11657 / ed. by V. Malyshkin. Springer, 2019. P. 3–9. Lecture Notes in Computer Science. DOI: 10.1007/978-3-030-25636-4_1.

Malyshkin V.E., Perepelkin V.A. A Multi-Agent Approach to Improve Execution Efficiency of Fragmented Programs in LuNA System. Problemy Informatiki. 2023. No. 3. P. 55–67. (in Russian) DOI: 10.24412/2073-0667-2023-3-55-67.

Belyaev N., Kireev S. LuNA-ICLU Compiler for Automated Generation of Iterative Fragmented Programs. 15th International Conference on Parallel Computing Technologies, PaCT 2019, Almaty, Kazakhstan, August 19–23, 2019. Proceedings. Vol. 11657 / ed. by V. Malyshkin. Springer, 2019. P. 10–17. Lecture Notes in Computer Science. DOI: 10.1007/978-3-030-25636-4_2.

Belyaev N., Perepelkin V. High-Efficiency Specialized Support for Dense Linear Algebra Arithmetic in LuNA System. 16th International Conference on Parallel Computing Technologies, PaCT 2021, Kaliningrad, Russia, September 13–18, 2021. Proceedings. Vol. 12942 / ed. by V. Malyshkin. Springer, 2021. P. 143–150. Lecture Notes in Computer Science. DOI: 10.1007/978-3-030-86359-3_11.

Malyshkin V., Perepelkin V. Trace-Based Optimization of Fragmented Programs Execution in LuNA System. 16th International Conference on Parallel Computing Technologies, PaCT 2021, Kaliningrad, Russia, September 13–18, 2021. Proceedings. Vol. 12942 / ed. by V. Malyshkin. Springer, 2021. P. 3–10. Lecture Notes in Computer Science. DOI: 10.1007/978-3-030-86359-3_1.

Malyshkin V., Perepelkin V., Lyamin A. Trace Balancing Technique for Trace Playback in LuNA System. 17th International Conference on Parallel Computing Technologies, PaCT 2023, Astana, Kazakhstan, August 21–25, 2023. Proceedings. Vol. 14098 / ed. by V. Malyshkin. Springer, 2023. P. 42–50. Lecture Notes in Computer Science. DOI: 10.1007/978-3-031-41673-6_4.

Joint SuperComputer Center of the Russian Academy of Sciences. URL: https://www.jscc.ru/ (accessed: 23.04.2024) (in Russian).

Kireev S. A Parallel 3D Code for Simulation of Self-gravitating Gas-Dust Systems. 10th International Conference on Parallel Computing Technologies, PaCT 2009, Novosibirsk, Russia, August 31 – September 4, 2009. Proceedings. Vol. 5698 / ed. by V. Malyshkin. Springer, 2009. P. 406–413. Lecture Notes in Computer Science. DOI: 10.1007/978-3-642-03275-2_40.




DOI: http://dx.doi.org/10.14529/cmse240205