Optimal Control of Three Work-Stealing Deques Located in Two-Level Memory
DOI:
https://doi.org/10.14529/cmse240303Keywords:
data structures, Monte Carlo method, two-level memory, work stealing dequesAbstract
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.References
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.
