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

Елена Алексеевна Аксёнова, Евгений Александрович Барковский, Андрей Владимирович Соколов

Аннотация


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

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


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

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

PDF

Литература


Herlihy M., 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 M. 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 byWork Stealing: A Survey. International Journal of Parallel Programming. 2018. Apr. Vol. 46, no. 2. P. 173–197. DOI: 10.1007/s10766-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/IJAEC.2016040104.

Amelina N.O., Kornivec A.D., Ivanskij J.V., Tjushev K.I. Primenenie konsensusnogo protokola dlja balansirovki zagruzki stohasticheskoj decentralizovannoj seti pri peredache dannyh. XII Vserossijskoe soveshhanie po problemam upravlenija: Scientific conference proceedings, Moscow, 16–19 June, 2014. Moscow: ICS of RAS, 2014. P. 8902–8911. (in Russian).

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/IJWGS.2019.103233.

Aksenova E.A., Sokolov A.V. Control Methods of Work-stealing Deques in Dynamic Schedulers of Multiprocessor Parallel Computations. Bulletin of the SUSU. Series: Computational Mathematics and Software Engineering. 2023. Vol. 12, no. 4. P. 76–93. (in Russian) 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.

Aksenova E.A., Lazutina A.A., Sokolov A.V. Ob optimal’nyh metodah predstavlenija dinamicheskih struktur dannyh. Obozrenie prikladnoj i promyshlennoj matematiki. 2003. Vol. 10, no. 2. P. 375–376. (in Russian).

Sokolov A., Barkovsky E. 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_11.

Barkovksy E., Kuchumov R., Sokolov A. Optimal Control of Two Deques in Shared Memory with Various Work-Stealing Strategies. Program Systems: Theory and Applications. 2017. Vol. 8, no. 1. P. 83–103. (in Russian) DOI: 10.25209/2079-3316-2017-8-1-83-103.

Barkovsky E., Lazutina A., Sokolov A. The Optimal Control of Two Work-Stealing Deques, Moving One After Another in a Shared Memory. Program Systems: Theory and Applications. 2019. Vol. 10, no. 1. P. 19–32. DOI: 10.25209/2079-3316-2019-10-1-19-32.

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. Nov. Vol. 40, no. 11. P. 1763–1770. DOI: 10.1134/S1995080219110052.

Lazutina A.A., Sokolov A.V. About Optimal Management of Work-Stealing Deques in Two-Level Memory. Herald of Computer and Information Technologies. 2020. Vol. 17, no. 4. P. 51–60. (in Russian) DOI: 10.14489/vkit.2020.04.pp.051-060.

Aksenova E.A., Lazutina A.A., Sokolov A.V. About Optimal Managment of Work-Stealing Deques in Two-Level Memory. Program Systems: Theory and Applications. 2021. Vol. 12, no. 2. P. 53–71. (in Russian) 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. July. Vol. 42, no. 7. P. 1475–1482. DOI: 10.1134/S1995080221070027.




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