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

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

Аннотация


Эффективность работы распределенных систем во многом зависит от равномерной загруженности потоков, что обеспечивается за счет различных стратегий балансировки задач между ними. Одним из методов децентрализованной динамической стратегии балансировки, где каждый поток участвует в распределении задач, является «work-stealing». Принцип метода в том, что поток не имеющий задач перехватывает («steal») их у других потоков. В основе процесса лежит специальная структура данных, work-stealing дек, в котором находятся указатели на задачи. При работе с деками возникает проблема их эффективного расположения в памяти. В двухуровневой памяти дек можно расположить разделив его на концы и середину: в быстрой памяти (первый уровень) находятся вершина и основание дека; в медленной памяти (второй уровень) — середина. Таким образом, система может быстро обращаться к концам дека, где элементы активно добавляются и удаляются. В статье анализируется новый метод представления трех work-stealing деков в двухуровневой памяти, где концы деков находятся в отдельных участках памяти. Для него строится имитационная модель на основе метода Монте-Карло, с помощью которой исследуются задачи оптимального разделения памяти. В качестве критерия оптимальности используется максимальное среднее время работы системы до перераспределения памяти.

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


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

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

PDF

Литература


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.




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