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

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

Автор: Киреев С.Е., Литвинов В.С.

Журнал: Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика @vestnik-susu-cmi

Статья в выпуске: 2 т.13, 2024 года.

Бесплатный доступ

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

Еще

Анализ производительности, параллельное программирование, фрагментированное программирование, параллелизм задач, система luna

Короткий адрес: https://sciup.org/147243961

IDR: 147243961   |   DOI: 10.14529/cmse240205

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

  • Thoman P., Dichev К., Heller Т., 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/sll227-018-2238-4.
  • Kaiser H., Heller Т., Adelstein-Lelbach В., 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 // llth 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 С. 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 (дата обращения: 23.04.2024).
  • Vampir 10.4. URL: https://vampir.eu/ (дата обращения: 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. Knupfer, et al. Springer, 2015. P. 1-24. DOI: 10.1007/978-3-319-16012-2_l.
  • 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 (дата обращения: 23.04.2024).
  • Huynh A., Thain D., Pericàs M., Taura К. 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 Tasklnsight // 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 - Université 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.
  • Малышкин В.Э. Технология фрагментированного программирования // Вестник ЮУр-ГУ. Серия: Вычислительная математика и информатика. 2012. № 46(305), Вып. 1. С. 45-55. DOI: 10.14529/cmsel20104.
  • 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/sll227-022-04355-0.
  • Bauer М., 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/sll227-016-1780-1.
  • Daribayev В., 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/sll227-018-2710-l.
  • 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_l.
  • Малышкин В.Э., Перепелкин В.А. Мультиагентный подход к повышению эффективности исполнения фрагментированных программ в системе LuNA // Проблемы информатики. 2023. № 3. С. 55-67. 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_ll.
  • 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_l.
  • 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.
  • Межведомственный Суперкомпьютерный Центр Российской Академии Наук. URL: https://www.jscc.ru/ (дата обращения: 23.04.2024).
  • 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.
Еще
Статья научная
QR-код для установки приложения SciUp Наведите камеру и скачайте бесплатное приложение SciUp