A Representation Method of Three Work-Stealing Deques in Two-Level Memory
DOI:
https://doi.org/10.14529/cmse250302Keywords:
data structures, Monte Carlo method, two-level memory, work-stealing dequesAbstract
The efficiency of distributed systems largely depends on the uniformity of thread workload. To achieve this, various strategies for balancing tasks between threads are utilized. One of the methods of dynamic distributed load balancing, where each thread participates in task distribution, is called “work-stealing.” In this method, a thread without tasks steals them from other threads. This process is based on a special data structure, a work-stealing deque, where pointers to tasks are stored. Thus, the problem of efficient placement of deques in memory arises. A deque can be represented in two-level memory in a divided form: the often-accessed ends of a deque are placed in the fast memory of the first level, while its middle is left in the slow memory of the second level. This way, the system can quickly access the ends of the deque where elements are being actively added and removed. In this paper, a new representation method of three work-stealing deques in two-level memory where the ends of the deques are placed in separate memory areas is described. We propose a simulation model of this approach based on the Monte Carlo method and solve several problems of optimal partitioning of memory. The optimality criterion is the maximum mean system operating time to memory reallocation.References
Dinu S., Raicu G. Load Balancing in Parallel Computing: An Evolutionary Approach. Advanced Topics in Optoelectronics, Microelectronics, and Nanotechnologies XI. Vol. 12493 / ed. by M. Vladescu, R.D. Tamas, I. Cristea. International Society for Optics, Photonics. SPIE, 2023. P. 124931M. DOI: 10.1117/12.2643056.
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.
Shafiq D., Jhanjhi N., Abdullah A. Load Balancing Techniques in Cloud Computing Environment: A Review. Journal of King Saud University – Computer and Information Sciences. 2021. Vol. 34. DOI: 10.1016/j.jksuci.2021.02.007.
Amelina N.O., Kornivec A.D., Ivanskij J.V., Tjushev K.I. Primenenie konsensusnogo protokola dlja balansirovki zagruzki stohasticheskoj decentralizovannoj seti pri peredache dan-nyh. XII Vserossijskoe soveshhanie po problemam upravlenija: Scientific Conference Proceedings, Moscow, Russia, June 16–19, 2014. Moscow: ICS of RAS, 2014. P. 8902–8911. (in Russian).
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.
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.
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.
Hwu W.-m. GPU Computing Gems, Jade Edition. 2012. DOI: 10.1016/C2010-0-68654-8.
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. SPAA ’98. DOI: 10.1145/277651.277678.
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.
Lin C.-X., Huang T.-W., Wong M.D.F. An Efficient Work-Stealing Scheduler for Task Dependency Graph. 2020 IEEE 26th International Conference on Parallel and Distributed Systems (ICPADS). 2020. P. 64–71. DOI: 10.1109/ICPADS51040.2020.00018.
Li J., Agrawal K., Elnikety S., et al. Work Stealing for Interactive Services to Meet Target Latency. SIGPLAN Notices. New York, NY, USA, 2016. Vol. 51, no. 8. Article 14. DOI: 10.1145/3016078.2851151.
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. SIGPLAN Notices. New York, NY, USA, 2014. Vol. 49, no. 8. P. 379–380. DOI: 10.1145/2692916.2555278.
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.
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., Lazutina A.A., Sokolov A.V. About Optimal Management 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-253-71.
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 Management of Work-Stealing Deques in Two-Level Memory. Lobachevskii Journal of Mathematics. 2021. Vol. 42, no. 7. P. 1475–1482. DOI: 10.1134/S1995080221070027.
Aksenova E.A., Barkovsky E.A., Sokolov A.V. Optimal Control of Three Work-Stealing Deques Located in Two-Level Memory. Bulletin of the South Ural State University. Series: Computational Mathematics and Software Engineering. 2024. Vol. 13, no. 3. P. 47–60. (in Russian) DOI: 10.14529/cmse240303.
