Оптимальное управление тремя work-stealing деками в двухуровневой памяти

Оптимальное управление тремя work-stealing деками в двухуровневой памяти

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

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

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

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

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

Еще

Двухуровневая память, метод монте-карло, структуры данных, work-stealing деки

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

IDR: 147245990   |   УДК: 004.942   |   DOI: 10.14529/cmse240303

Optimal control of three work-stealing deques located in two-level memory

The problem of even balancing of tasks between threads may arise during parallel computations. One way to resolve this issue is to implement distributed dynamic load balancing. In this balancing method each worker thread has its own task queue, and threads themselves distribute further tasks. One of the widely used distributed dynamic balancing methods is “work-stealing”: a thread that runs out of tasks begins to “steal” them from another thread. To utilize this method, each thread must have its own specialized deque where pointers to tasks are stored. In this paper, we propose and examine a new method for representing three work stealing deques in two-level memory. We consider the case of working with three deques, where one section of fast memory contains two LIFO parts of the deques, i.e., two stacks that grow towards each other. Third LIFO part and three FIFO parts are located in the other section of fast memory. FIFO parts are combined into one FIFO queue, from which elements are only deleted (being stolen). The middle parts of the deques are located in slow memory. They are accessed when LIFO or FIFO parts located in fast memory are empty or overflowed. We consider the problem of finding optimal partition of fast memory for three deques with predetermined probabilities of operations. This choice depends on the characteristics of memory levels, operation probabilities, and optimality criteria. The optimality criterion is the maximum mean system operating time (the average number of operations) before memory reallocation.

Еще

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

  • Herlihy М., Shavit N. The Art of Multiprocessor Programming. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 2008. DOI: 10.5555/1734069.
  • Kwok Y.-K., Ahmad I. Static scheduling algorithms for allocating directed task graphs to multiprocessors // ACM Comput. Surv. New York, NY, USA, 1999. Dec. 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 multiple bag-of-task applications // Proceedings 20th IEEE International Parallel & Distributed Processing Symposium. 2006. P. 10. DOI: 10.1109/IPDPS.2006.1639262.
  • Xia Y., Prasanna V.K., Li J. Hierarchical Scheduling of DAG Structured Computations on Manycore Processors with Dynamic Thread Grouping // Job Scheduling Strategies for Parallel Processing / ed. by E. Frachtenberg, U. Schwiegelshohn. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. 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 Twenty-First Annual Symposium on Principles of Distributed Computing. Monterey, California: Association for Computing Machinery, 2002. P. 280-289. DOI: 10.1145/571825.571876.
  • Hendler D., Shavit N. Work dealing // Proceedings of the Fourteenth Annual ACM Symposium on Parallel Algorithms and Architectures. Winnipeg, Manitoba, Canada: Association for Computing Machinery, 2002. P. 164-172. DOI: 10.1145/564870.564900.
  • Acar U.A., Chargueraud A., Rainey М. Scheduling parallel programs by work stealing with private deques // SIGPLAN Not. New York, NY, USA, 2013. Feb. 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 Tenth Annual ACM Symposium on Parallel Algorithms and Architectures. Puerto Vallarta, Mexico: Association for Computing Machinery, 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. Apr. Vol. 46, no. 2. P. 173-197. DOI: 10.1007/sl0766-016-0484-8.
  • Knuth D.E. The art of computer programming, volume 1 (3rd ed.): fundamental algorithms. USA: Addison Wesley Longman Publishing Co., Inc., 1997. DOI: 10.5555/260999.
  • 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/1JAEC. 2016040104.
  • Амелина H.O., Корнивец А.Д., Иванский Ю.В., Тюшев К.И. Применение консенсусно-го протокола для балансировки загрузки стохастической децентрализованной сети при передаче данных // XII Всероссийское совещание по проблемам управления: Труды научной конференции, Москва, 16-19 июня, 2014. Москва: ИПУ РАН, 2014. С. 8902-8911.
  • 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 // SIGPLAN Not. New York, NY, USA, 2016. Feb. Vol. 51, no. 8. Article 14. DOI: 10.1145/3016078.2851151.
  • Wimmer M., Versaci F., Traff J.L., et al. Data structures for task-based priority scheduling // SIGPLAN Not. New York, NY, USA, 2014. Feb. Vol. 49, no. 8. P. 379-380. DOI: 10.1145/2692916.2555278.
  • 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: https://doi.org/10. 1002/cpe.3771.
  • Mitzenmacher M. Analyses of load stealing models based on differential equations // Proceedings of the Tenth Annual ACM Symposium on Parallel Algorithms and Architectures. Puerto Vallarta, Mexico: Association for Computing Machinery, 1998. P. 212-221. DOI: 10.1145/277651.277687.
  • Kuchumov R., Sokolov A., Korkhov V. Staccato: Cache-Aware Work-Stealing Task Scheduler for Shared-Memory Systems // Computational Science and Its Applications - ICCSA 2018 / ed. by O. Gervasi, B. Murgante, S. Misra, et al. Cham: Springer International Publishing, 2018. P. 91-102. DOI: 10.1007/978-3-319-95171-3_8.
  • 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/1JWGS.2019.103233.
  • Аксенова Е.А., Соколов А.В. Методы управления work-stealing деками в динамических планировщиках многопроцессорных параллельных вычислений // Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. 2023. Т. 12, № 4. С. 76-93. DOI: 10.14529/cmse230403.
  • Chase D., Lev Y. Dynamic circular work-stealing deque // Proceedings of the Seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures. Las Vegas, Nevada, USA: Association for Computing Machinery, 2005. P. 21-28. DOI: 10.1145/ 1073970.1073974.
  • Sokolov A., Drac A. The linked list representation of n LIFO-stacks and/or FIFO-queues in the single-level memory // Information Processing Letters. 2013. Vol. 113, no. 19. P. 832-835. DOI: 10.1016/j.ipl.2013.07.021.
  • Hendler D., Lev Y., Moir M., Shavit N. A dynamic-sized nonblocking work stealing deque // Distributed Computing. 2006. Feb. Vol. 18, no. 3. P. 189-207. DOI: 10.1007/s00446-005-0144-5.
  • Аксенова E.A., Лазутина А.А., Соколов А.В. Об оптимальных методах представления динамических структур данных // Обозрение прикладной и промышленной математики. 2003. Т. 10, № 2. С. 375-376.
  • Sokolov A., Barkovsky Е. The Mathematical Model and the Problem of Optimal Partitioning of Shared Memory for Work-Stealing Deques // Parallel Computing Technologies / ed. by V. Malyshkin. Cham: Springer International Publishing, 2015. P. 102-106. DOI: 10.1007/978-3-319-21909-7_ll.
  • Барковский E.A., Кучумов Р.И., Соколов А.В. Оптимальное управление двумя work-stealing деками в общей памяти при различных стратегиях перехвата работы // Программные системы: теория и приложения. 2017. Т. 8, № 1. С. 83-103. DOI: 10.25209/ 2079-3316-2017-8-1-83-103.
  • Барковский Е.А., Лазутина А.А., Соколов А.В. Построение и анализ модели процесса работы с двумя деками, двигающимися друг за другом в общей памяти // Программные системы: теория и приложения. 2019. Т. 10, № 1. С. 3-17. DOI: 10.25209/2079-3316-2019-10-1-3-17.
  • Aksenova Е.А., Barkovsky Е.А., 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. Nov. Vol. 40, no. 11. P. 1763-1770. DOI: 10.1134/S1995080219110052.
  • Лазутина A.A., Соколов А.В. Об оптимальном управлении Work-Stealing деками в двухуровневой памяти // Вестник компьютерных и информационных технологий. 2020. Т. 17, №4. С. 51-60. DOI: 10.14489/vkit.2020.04.pp.051-060.
  • Аксенова Е.А., Лазутина А.А., Соколов А.В. Минимизация средних затрат на перераспределение при работе с work-stealing деком в двухуровневой памяти // Программные системы: теория и приложения. 2021. Т. 12, № 2. С. 53-71. DOI: 10.25209/2079-3316-2021-12-2-53-71.
  • Aksenova Е.А., Lazutina A. A., Sokolov A.V. About Optimal Management of Work-Stealing Deques in Two-Level Memory // Lobachevskii Journal of Mathematics. 2021. July. Vol. 42, no. 7. P. 1475-1482. DOI: 10.1134/S1995080221070027.
Еще
QR-код для установки приложения SciUp Наведите камеру и скачайте бесплатное приложение SciUp