Методы управления work-stealing деками в динамических планировщиках многопроцессорных параллельных вычислений

Методы управления work-stealing деками в динамических планировщиках многопроцессорных параллельных вычислений

Автор: Акснова Е.А., Соколов А.В.

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

Статья в выпуске: 4 т.12, 2023 года.

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

В параллельных планировщиках задач, работающих по стратегии work-stealing, каждый процессор имеет свой дек задач. Один конец дека используется для добавления и извлечения задач только владельцем, а другой - для перехвата задач другими процессорами. В статье предлагается обзор методов управления work-stealing деками, которые используются при реализации work-stealing планировщиков параллельных задач, а также представлено описание поставленных и решенных нашим коллективом задач оптимального управления деками для стратегии work-stealing. Принцип алгоритмов оптимального управления деками в двухуровневой памяти заключается в том, что при переполнении выделенного участка быстрой памяти происходит перераспределение элементов (задач) дека между уровнями памяти. В быстрой памяти остаются элементы из концов дека, так как с ними будет происходить работа в ближайшее время, а элементы средней части дека хранятся в медленной памяти. В таком случае необходимо определить оптимальное количество элементов, которое нужно оставить в быстрой памяти, в зависимости от критерия оптимальности и параметров системы.

Еще

Имитационные и марковские модели оптимального управления структурами данных, оптимальное кэширование деков, оптимальное управление work-stealing деками, оптимизация work-stealing балансировщиков, управляемые случайные блуждания

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

IDR: 147242606   |   DOI: 10.14529/cmse230403

Список литературы Методы управления work-stealing деками в динамических планировщиках многопроцессорных параллельных вычислений

  • Herlihy M., Shavit N. The Art of Multiprocessor Programming. Elsevier, 2008. 508 p.
  • Yu-Kwong K., Ishfaq A. Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessors // ACM Computing Surveys. 1999. Vol. 31, no. 4. P. 406–471. DOI: 10.1145/344588.344618.
  • Alakeel A.M. A Guide to Dynamic Load Balancing in Distributed Computer Systems // International Journal of Computer Science and Network Security. 2010. Vol. 10, no. 6. P. 153–160.
  • Beaumont O., Carter L., Ferrante J., et al. Centralized versus Distributed Schedulers for Bag-of-Tasks Applications // IEEE Transactions on Parallel and Distributed Systems. 2008. Vol. 19, no. 5. P. 698–709. DOI: 10.1109/TPDS.2007.70747.
  • Xia Y., Prasanna V. Hierarchical Scheduling of DAG Structured Computations on Manycore Processors with Dynamic Thread Grouping // Job Scheduling Strategies for Parallel Processing. Springer, 2010. Lecture Notes in Computer Science. Vol. 6253, P. 154–174. DOI: 10.1007/978-3-642-16505-4_9.
  • Hendler D., Shavit N. Non-Blocking Steal-Half Work Queues // Proceedings of the 21st Annual Symposium on Principles of Distributed Computing, PODC ’02, Monterey, California, July 21–24, 2002. New York, ACM, 2002. P. 280–289. DOI: 10.1145/571825.571876.
  • Hendler D., Shavit N. Work Dealing // Proceedings of the 14th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA ’02, Winnipeg, Canada, August 10–13, 2002. New York, ACM, 2002. P. 164–172. DOI: 10.1145/564870.564900.
  • Acar U.A., Chargueraud A., Rainey M. Scheduling Parallel Programs by Work Stealing with Private Deques // ACM SIGPLAN Notices. 2013. Vol. 48, no. 8. P. 219–228. DOI: 10.1145/2517327.2442538.
  • Arora N.S., Blumofe R.D., Plaxton C.G. Thread Scheduling for Multiprogrammed Multiprocessors // Proceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA ’98, Puerto Vallarta, Mexico, June 28 – July 2, 1998. New York, ACM, 1998. P. 119–129. DOI: 10.1145/277651.277678.
  • Yang J., He Q. Scheduling Parallel Computations by Work Stealing: A Survey // International Journal of Parallel Programming. 2018. Vol. 46, no. 2. P. 173–197. DOI: 10.1007/s10766-016-0484-8.
  • Blumof R.D., Joerg C.F., Kuszmaul B.C., et al. Cilk: An Efficient Multithreaded Runtime System // ACM SIGPLAN Notices. 1995. Vol. 30, no. 8. P. 207–216. DOI: 10.1145/209937.209958.
  • Leijen D., Schulte W., Burckhardt S. The Design of a Task Parallel Library // ACM SIGPLAN Notices. 2009. Vol. 44, no. 10. P. 227–242. DOI: 10.1145/1639949.1640106.
  • Tardieu O., Wang H., Lin H. A Work-Stealing Scheduler for X10’s Task Parallelism with Suspension // Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP ’12, New Orleans, Louisiana, USA, February 25–29, 2012. New York, ACM, 2012. P. 267–276. DOI: 10.1145/2145816.2145850.
  • Knuth D. The Art of Computer Programming. Volume 1. Addison-Wesley Professional, 1997. 672 p.
  • Blumofe R.D., Leiserson C.E. Scheduling Multithreaded Computations by Work Stealing // Journal of the ACM. 1999. Vol. 46, no. 5. P. 720–748. DOI: 10.1145/324133.324234.
  • Alam M., Varshney A.K. A New Approach of Dynamic Load Balancing Scheduling Algorithm for Homogeneous Multiprocessor System // International Journal of Applied Evolutionary Computation. 2016. Vol. 7, no. 2. P. 61–75. DOI: 10.4018/IJAEC.2016040104.
  • Amelina N., Fradkov A., Jiang Y., Vergados D.J. Approximate Consensus in Stochastic Networks With Application to Load Balancing // IEEE Transactions on Information Theory. 2015. Vol. 61, no. 4. P. 1739–1752. DOI: 10.1109/TIT.2015.2406323.
  • Li J., Agrawal K., Elnikety S., et al. Work Stealing for Interactive Services to Meet Target Latency // ACM SIGPLAN Notices. 2016. Vol. 51, no. 8. P. 1–13. DOI: 10.1145/3016078.2851151.
  • Robison A., Voss M., Kukanov A. Optimization via Reflection on Work Stealing in TBB // Proceedings of the IEEE International Parallel & Distributed Processing Symposium, IPDPS ’08, Miami, FL, USA, April 14–18, 2008. IEEE, 2008. P. 1–8. DOI: 10.1109/IPDPS.2008.4536188.
  • Dijk T., Pol J.C. Lace: Non-blocking Split Deque for Work-Stealing // Parallel Processing Workshops. Springer, 2014. Lecture Notes in Computer Science. Vol. 8806, P. 206–217. DOI: 10.1007/978-3-319-14313-2_18.
  • Fax´en K.-F. Wool-A work stealing library // ACM SIGARCH Computer Architecture News. 2008. Vol. 36, no. 5. P. 93–100. DOI: 10.1145/1556444.1556457.
  • Gmys J., Leroy R., Mezmaz M., et al.Work Stealing with Private Integer-Vector-Matrix Data Structure for Multi-core Branch-and-Bound Algorithms // Concurrency and Computation Practice and Experience. 2016. Vol. 28, no. 18. P. 4463–4484. DOI: 10.1002/cpe.3771.
  • Wimmer M., Versaci F., Traff J.L., et al. Data Structures for Task-based Priority Scheduling // ACM SIGPLAN Notices. 2014. Vol. 49, no. 8. P. 379–380. DOI: 10.1145/2692916.2555278.
  • Chen Q., Guo M., Guan H. LAWS: Locality-Aware Work-Stealing for Multi-socket Multi-core Architectures // Proceedings of the 28th ACM International Conference on Supercomputing, ICS’14, Munich, Germany, June 10–13, 2014. New York, ACM, 2014. P. 3–12. DOI: 10.1145/2597652.2597665.
  • Guo H., Chen Q., Guo M., Xu L. SAWS: Selective Asymmetry-Aware Work-Stealing for Asymmetric Multi-core Architectures // Proceedings of the IEEE 18th International Conference on High Performance Computing and Communications; IEEE 14th International Conference on Smart City; IEEE 2nd International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2016, Sydney, Australia, December 12–14, 2016. IEEE, 2016. P. 116–123. DOI: 10.1109/HPCC-SmartCity-DSS.2016.0027.
  • Guo Y., Zhao J., Cave V., Sarkar V. SLAW: A Scalable Locality-aware Adaptive Workstealing Scheduler for Multi-core Systems // ACM SIGPLAN Notices. 2010. Vol. 45, no. 5. P. 341–342. DOI: 10.1145/1837853.1693504.
  • Mitzenmacher M. Analyses of Load Stealing Models Based on Differential Equations // Proceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA/PODC98, Puerto Vallarta, Mexico, June 28 – July 2, 1998. New York, ACM, 1998. P. 212–221. DOI: 10.1145/277651.277687.
  • Wangkai J., Xiangjun P. SLITS: Sparsity-Lightened Intelligent Thread Scheduling // Proceedings of the ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS ’23, Orlando, Florida, United States, June 19–23, 2023. New York, ACM, 2023 P. 21–22. DOI: 10.1145/3578338.3593568.
  • Кучумов Р.И. Реализация и анализ Work-Stealing планировщика задач // Стохастическая оптимизация в информатике. 2016. Т. 12, № 1. C. 20–39.
  • Sokolov A.V., Drac A.V. The Linked List Representation of n LIFO-Stacks and/or FIFOQueues in the Single-Level Memory // Information Processing Letters. 2013. Vol. 113, no. 19–21. P. 832–835. DOI: 10.1016/j.ipl.2013.07.021.
  • Аксенова Е.А., Лазутина А.А., Соколов А.В. Об оптимальных методах представления динамических структур данных // Обозрение прикладной и промышленной математики. 2003. Т. 10, № 2. C. 375–376.
  • Hendler D., Lev Y., Moir M., Shavit N. A Dynamic-Sized Nonblocking Work Stealing Deque // Distributed Computing. 2006. Vol. 18. P. 189–207. DOI: 10.1007/s00446-005-0144-5.
  • Соколов А.В. Математические модели и алгоритмы оптимального управления динамическими структурами данных. Петрозаводск: Изд-во ПетрГУ, 2002. 215 с.
  • Драц А.В., Соколов А.В. Управление двумя FIFO-очередями в случае их движения друг за другом по кругу // Математические методы распознавания образов. 2011. Т. 15, № 1. C. 315–317.
  • Drac A.V., Sokolov A.V. The Circular Representation of 2 FIFO-Queues in Single Level Memory // Proceedings of the International Conference on Numerical Analysis and Applied Mathematics, ICNAAM-2014, Rhodes, Greece, September 22–28, 2014. AIP Publishing LLC, 2015. Vol. 1648. P. 520002. DOI: 10.1063/1.4912732.
  • Барковский Е.А., Соколов А.В. Способ управления памятью компьютерной системы (RU 2647627 C1). URL: http://www1.fips.ru/registers-doc-view/fips_servlet?DB=RUPAT&DocNumber=2647627&TypeFile=html (дата обращения: 18.07.2023).
  • Sokolov A., Barkovsky E. The Mathematical Model and the Problem of Optimal Partitioning of Shared Memory for Work-Stealing Deques // Parallel Computing Technologies (PaCT 2015): Proceedings of the 13th International Conference, Petrozavodsk, Russia, August 31 – September 4, 2015. Springer, 2015. Lecture Notes in Computer Science. Vol. 9251, P. 102–106. DOI: 10.1007/978-3-319-21909-7_11.
  • Барковский Е.А., Кучумов Р.И., Соколов А.В. Оптимальное управление двумя workstealing деками в общей памяти при различных стратегиях перехвата работы // Программные системы: теория и приложения. 2017. Т. 8, № 1. C. 83–103. DOI: 10.25209/2079-3316-2017-8-1-83-103.
  • Aksenova E.A., Sokolov A.V. Modeling of the Memory Management Process for Dynamic Work-Stealing Schedulers // Proceedings of Ivannikov ISPRAS Open Conference, ISPRAS 2017, Moscow, Russia, November 30 – December 1, 2017. IEEE, 2017. P. 12–15. DOI: 10.1109/ISPRAS.2017.00009.
  • Барковский Е.А., Лазутина А.А., Соколов А.В. Построение и анализ модели процесса работы с двумя деками, двигающимися друг за другом в общей памяти // Программные системы: теория и приложения. 2019. Т. 10, № 1. C. 3–17. DOI: 10.25209/2079-3316-2019-10-1-3-17.
  • Aksenova E.A., Barkovsky E.A., Sokolov A.V. The Models and Methods of Optimal Control of Three Work-Stealing Deques Located in a Shared Memory // Lobachevskii Journal of Mathematics. 2019. Vol. 40. P. 1763–1770. DOI: 10.1134/S1995080219110052.
  • Kuchumov R., Sokolov A., Korkhov V. Staccato: Shared-Memory Work-Stealing Task Scheduler with Cache-Aware Memory Management // International Journal of Web and Grid Services. 2019. Vol. 15, no. 4. P. 394–407. DOI: 10.1504/IJWGS.2019.103233.
  • Work-Stealing Task Scheduler. URL: https://github.com/rkuchumov/staccato.
  • CPP Distributed Scheduler. URL: https://gitlab.com/mildlyparallel/cpp-distributed-scheduler.
  • Хайдарова Р.Р., Муромцев Д.И., Лапаев М.В., Фищенко В.Д. Модель распределенной сверточной нейронной сети на кластере компьютеров с ограниченными вычислительными ресурсами // Научно-технический вестник информационных технологий, механики и оптики. 2020. Т. 20. № 5. С. 739–746. DOI: 10.17586/2226-1494-2020-20-5-739-746.
  • Saddik A., Latif R., Ouardi A.E., et al. Computer development based embedded systems in precision agriculture: tools and application // Acta Agriculturae Scandinavica, Section B – Soil & Plant Science. 2022. Vol. 72, no. 1. P. 589–611. DOI: 10.1080/09064710.2021.2024874.
  • Лазутина А.А., Соколов А.В. Об оптимальном управленииWork-Stealing деками в двухуровневой памяти // Вестник компьютерных и информационных технологий. 2020. Т. 17, № 4. C. 51–60. DOI: 10.14489/vkit.2020.04.pp.051-060.
  • Аксёнова Е. А., Лазутина А. А., Соколов А. В. Минимизация средних затрат на перераспределение при работе с work-stealing деком в двухуровневой памяти // Программные системы: теория и приложения. 2021. Т. 12, № 2. C. 53–71. DOI: 10.25209/2079-3316-2021-12-2-53-71.
  • Aksenova E.A., Lazutina A.A., Sokolov A.V. About Optimal Management of Work-Stealing Deques in Two-Level Memory // Lobachevskii Journal of Mathematics. 2021. Vol. 42. P. 1475–1482. DOI: 10.1134/S1995080221070027.
  • Aksenova E., Sokolov A. Minimizing the Average Cost of Redistribution when Working with Two Work-Stealing Deques in Two-Level Memory. Russian Supercomputing Days: Proceedings of Russian Supercomputing Days, Moscow, Russia, September 26–27, 2022. Moscow, MAKS Press, 2022. P. 4–12. URL: https://russianscdays.org/files/2022/RuSCDays22_Proceedings.pdf
Еще
Статья научная
SciUp 2024 © 2024 ©