|
DOI: 10.14489/vkit.2020.04.pp.051-060
Лазутина А. А., Соколов А. В.
ОБ ОПТИМАЛЬНОМ УПРАВЛЕНИИ WORK-STEALING ДЕКАМИ В ДВУХУРОВНЕВОЙ ПАМЯТИ
(c. 51-60)
Аннотация. Рассмотрена задача оптимального управления Work-Stealing деком (англ. – deque) в двухуровневой памяти. Предположено, что известны вероятности параллельных операций с деком. Задача состоит в нахождении числа элементов с двух сторон дека, которые при перераспределении дека оставлены в быстрой памяти для максимального среднего времени попадания в состояния, когда требуется провести перераспределение памяти. Построены математическая модель процесса в виде поглощающей цепи Маркова и имитационная модель. Представлены результаты численных экспериментов.
Ключевые слова: Work-Stealing балансировщики; Work-Stealing деки; структуры данных; поглощающие цепи Маркова; случайные блуждания.
Lazutina A. A., Sokolov A. V.
ABOUT OPTIMAL MANAGEMENT OF WORK-STEALING DEQUES IN TWO-LEVEL MEMORY
(pp. 51-60)
Abstract. In the parallel work-stealing load balancers, each core owns a personal buffer of tasks called deque. One end of the deque is used by its owner to add and retrieve tasks, while the second end is used by other cores to steal tasks. Our experience in software implementations has shown that it is important to optimize work with cache memory in parallel work-stealing load balancers. For example, by modifying deques so that they can hold task objects instead of pointers, we managed to increase the performance more than 2.5 times on the CPU-bound applications and decrease last-level cache misses up to 30 % compared to Intel TBB (Threading Building Blocks) and Intel / MIT (Massachusetts Institute of Technology) Cilk work-stealing schedulers. Therefore, it is important to investigate special methods of working with deques in two-level memory, and not just try to optimize the use of universal cache implementations. The paper analyzes the problem of optimal control of a work-stealing deque in two-level memory (for example, registers – random access memory), where probabilities of parallel operations with the deque are known. The classic sequential cyclic method for representing a deque in memory is considered. If a deque overflows or empty, we transfer elements from its middle part from the fast memory to the slow memory, since data from the end parts of the deque may be needed earlier. The problem is to find the optimal number of elements from both sides of the deque to leave in the fast memory if the deque is full or empty. The average time to get into the states when it is necessary to reallocate the memory is maximized.The simulation model and the mathematical model in the form of an absorbing Markov chain were constructed. The results of numerical experiments are presented.
Keywords: Work-stealing balancers; Work-stealing deques; Data structures; Absorbing Markov chains; Random walks.
А. А. Лазутина (Московский государственный университет имени М. В. Ломоносова, Москва, Россия)
А. В. Соколов (ФГБУН ФИЦ «Карельский научный центр Российской академии наук», Петрозаводск, Россия) E-mail:
Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
A. A. Lazutina (Lomonosov Moscow State University, Moscow, Russia)
A. V. Sokolov (Karelian Research Centre of the Russian Academy of Sciences, Petrozavodsk, Russia) E-mail:
Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
1. Blumofe R. D., Leiserson C. E. Scheduling Multithreaded Computations by Work Stealing // Journal of the ACM. 1999. V. 46, No. 5. P. 720 – 748.
2. Кнут Д. Э. Искусство программирования. Т. 1. Основные алгоритмы = The Art of Computer Programming. V. 1. Fundamental Algorithms / пер. с англ. С. Г. Тригуб, Ю. Г. Гордиенко, И. В. Красикова и др. М.: Вильямс, 2002. Т. 1. 720 с.
3. Sokolov A. V., Barkovsky E. A. The Mathematical Model and the Problem of Optimal Partitioning of Shared Memory for Work-Stealing Deques // Lecture Notes in Computer Science. 2015. V. 9251. P. 102 – 106.
4. Aksenova E. A., Sokolov A. V. Modeling of the Memory Management Process for Dynamic Work-Stealing Schedulers // Proc. of 2017 Ivannikov ISPRAS Open Conf. (ISPRAS). 2018. P. 12 – 15. doi: 10.1109/ISPRAS.2017.00009
5. Пат. 2647627 Российская Федерация, МПК G06F9/5005 (2006.01); G06F12/02 (2006.01). Способ управления памятью компьютерной системы / Соколов А. В., Барковский Е. А.; заявитель и патентообладатель ФГБУН ФИЦ «Карельский научный центр Российской академии наук». № 2016143800; заявл. 08.11.2016; опубл. 16.03.2018, Бюл. № 8. 13 с.
6. Барковский Е. А., Лазутина А. А., Соколов А. В. Построение и анализ модели процесса работы с двумя деками, двигающимися друг за другом в общей памяти // Программные системы: теория и приложения. 2019. Т. 10, № 1(40). C. 3 – 17. doi: 10.25209/2079-3316-2019-10-1-3-17
7. 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. V. 40, Is. 11. P. 1763 – 1770.
8. Соколов А. В. Математические модели и алгоритмы оптимального управления динамическими структурами данных. Петрозаводск: Изд-во ПетрГУ, 2002. 215 c.
9. Барковский Е. А., Соколов А. В. Модель управления двумя параллельными FIFO-очередями, двигающимися друг за другом в общей памяти // Информационно-управляющие системы. 2016. № 1. С. 65 – 73. doi: 10.15217/ issn1684-8853.2016.1.65
10. Kuchumov R., Sokolov A., Korkhov V. Staccato: Shared-Memory Work-Stealing Task Scheduler with Cache-Aware Memory Management // Inter. Journal of Web and Grid Services. 2019. V. 15, No. 4. P. 394 – 407. doi: 10.1504/ IJWGS.2019.103233
11. Соколов А. В. Об оптимальном кешировании FIFO-очередей // Стохастическая оптимизация в информатике. 2013. Т. 9, № 2. С. 108 – 123.
12. Aksenova E. A., Lazutina A. A., Sokolov A. V. Study of a Non-Markovian Stack Management Model in a Two-Level Memory // Programming and Computer Software. 2004. V. 30, No. 1. P. 25 – 33.
13. Аксенова Е. А., Соколов А. В. Оптимальное управление двумя параллельными стеками в двухуровневой памяти // Дискретная математика. 2007. Т. 19, № 1. С. 67 – 75.
14. Hasegava M., Shigei Y. High-Speed Top-of-Stack Scheme for VLSI Processor: a Management Algorithm and Its Analysis // Proc. of 12th Symposium on Computer Architecture. June, 1985. P. 48 – 54.
15. Stanley T., Wedig R. A Performance Analysis of Automatically Managed Top of Stack Buffers // Proc. of 14th Symposuim on Computer Architecture. June, 1987. P. 272 – 281.
16. Koopman P. J. Stack Computers: The New Wave. Chichester: Horwood, 1989. 234 с.
17. Ким А. К., Перекатов В. И., Ермаков С. Г. Микропроцессоры и вычислительные комплексы семейства «Эльбрус». СПб.: Питер, 2013. 272 с.
18. Шевчук Ю. В., Шевчук А. Ю. Виртуальная машина. Etherbox32vm [Электронный ресурс] // Программные системы: теория и приложения. 2016. Т. 7, № 4(31). С. 119 – 143. URL: http://psta. psiras.ru/read/psta2016_4_119-143.pdf (дата обращения: 02.02.2020).
19. Феллер У. Введение в теорию вероятностей и ее приложения. Т. 1 = An Introduction to Probability Theory and its Applications. V. I. / пер. с англ. Ю. В. Прохорова; предисл. А. Н. Колмогорова. М.: Мир; Ред. литературы по мат. наукам, 1984.
20. Кемени Дж., Снелл Дж. Конечные цепи Маркова / пер. с англ. С. А. Молчанова, Н. Б. Леви-ной, Я. А. Когана; под ред. А. А. Юшкевича. М.: Наука, 1970. 272 c.
21. Поляк Б. Т., Щербаков П. С. Почему метод Монте-Карло неэффективен в оптимизационных задачах большой размерности? // Стохастическая оптимизация в информатике. 2014. Т. 10, № 1. С. 89 – 100.
1. Blumofe R. D., Leiserson C. E. (1999). Scheduling Multithreaded Computations by Work Stealing. Journal of the ACM, Vol. 46, (5), pp. 720 – 748.
2. Knut D. E. (2002). The Art of Computer Programming. Vol. 1. Fundamental Algorithms. Moscow: Vil'yams. [in Russian language]
3. Sokolov A. V., Barkovsky E. A. (2015). The Mathematical Model and the Problem of Optimal Partitioning of Shared Memory for Work-Stealing Deques. Lecture Notes in Computer Science, Vol. 9251, pp. 102 – 106.
4. Aksenova E. A., Sokolov A. V. (2018). Modeling of the Memory Management Process for Dynamic Work-Stealing Schedulers. Proceedings of 2017 Ivannikov ISPRAS Open Conference, pp. 12 – 15. doi: 10.1109/ISPRAS.2017.00009
5. Sokolov A. V., Barkovskiy E. A. Method for managing computer system memory. Ru Patent No. 2647627. Russian Federation. [in Russian language]
6. Barkovskiy E. A., Lazutina A. A., Sokolov A. V. (2019). Building and analyzing a model of the process of working with two decks moving one after another in a common memory. Programmnye sistemy: teoriya i prilozheniya, Vol. 10, 40(1), pp. 3 – 17. [in Russian language] doi: 10.25209/2079-3316-2019-10-1-3-17
7. Aksenova E. A., Barkovsky E. A., Sokolov A. V.(2019). The Models and Methods of Optimal Control of Three Work-Stealing Deques Located in a Shared Memory. Lobachevskii Journal of Mathematics, Vol. 40, (11), pp. 1763 – 1770.
8. Sokolov A. V. (2002). Mathematical models and algorithms for optimal control of dynamic data structures. Petrozavodsk: Izdatel'stvo PetrGU. [in Russian language]
9. Barkovskiy E. A., Sokolov A. V. (2016). A model for managing two parallel FIFO queues moving one after another in shared memory. Informatsionno-upravlyayushchie sistemy, (1), pp. 65 – 73. [in Russian language] doi: 10.15217/ issn1684-8853.2016.1.65
10. Kuchumov R., Sokolov A., Korkhov V. (2019). Staccato: Shared-Memory Work-Stealing Task Scheduler with Cache-Aware Memory Management. International Journal of Web and Grid Services, Vol. 15, (4), pp. 394 – 407. doi: 10.1504/ IJWGS.2019.103233
11. Sokolov A. V. (2013). About optimal caching of FIFO queues. Stohasticheskaya optimizatsiya v informatike, Vol. 9, (2), pp. 108 – 123. [in Russian language]
12. Aksenova E. A., Lazutina A. A., Sokolov A. V. (2004). Study of a Non-Markovian Stack Management Model in a Two-Level Memory. Programming and Computer Software, Vol. 30, (1), pp. 25 – 33.
13. Aksenova E. A., Sokolov A. V. (2007). Optimal management of two parallel stacks in two-level memory. Diskretnaya matematika, Vol. 19, (1), pp. 67 – 75. [in Russian language]
14. Hasegava M., Shigei Y. (1985). High-Speed Top-of-Stack Scheme for VLSI Processor: a Management Algorithm and Its Analysis. Proceedings of 12th Symposium on Computer Architecture, pp. 48 – 54.
15. Stanley T., Wedig R. (1987). A Performance Analysis of Automatically Managed Top of Stack Buffers. Proceedings of 14th Symposuim on Computer Architecture, pp. 272 – 281.
16. Koopman P. J. (1989). Stack Computers: The New Wave. Chichester: Horwood.
17. Kim A. K., Perekatov V. I., Ermakov S. G. (2013). Microprocessors and computing systems of the Elbrus family. Saint Petersburg: Piter. [in Russian language]
18. Shevchuk Yu. V., Shevchuk A. Yu. (2016). Virtual machine. Etherbox32vm. Programmnye sistemy: teoriya i prilozheniya, Vol. 7, 31(4), pp. 119 – 143. Available at: http://psta. psiras.ru/read/psta2016_4_119-143.pdf (Accessedя: 02.02.2020). [in Russian language]
19. Feller U. (1984). An Introduction to Probability Theory and its Applications. Vol. I. Moscow: Mir. [in Russian language]
20. Yushkevich A. A. (Ed.), Kemeni Dzh., Snell Dzh. (1970). Finite Markov chains. Moscow: Nauka. [in Russian language]
21. Polyak B. T., Shcherbakov P. S. (2014). Why is the Monte Carlo method ineffective in optimization problems of large dimension? Stohasticheskaya optimizatsiya v informatike, Vol. 10, (1), pp. 89 – 100. [in Russian language]
Статью можно приобрести в электронном виде (PDF формат).
Стоимость статьи 350 руб. (в том числе НДС 18%). После оформления заказа, в течение нескольких дней, на указанный вами e-mail придут счет и квитанция для оплаты в банке.
После поступления денег на счет издательства, вам будет выслан электронный вариант статьи.
Для заказа скопируйте doi статьи:
10.14489/vkit.2020.04.pp.051-060
и заполните форму
Отправляя форму вы даете согласие на обработку персональных данных.
.
This article is available in electronic format (PDF).
The cost of a single article is 350 rubles. (including VAT 18%). After you place an order within a few days, you will receive following documents to your specified e-mail: account on payment and receipt to pay in the bank.
After depositing your payment on our bank account we send you file of the article by e-mail.
To order articles please copy the article doi:
10.14489/vkit.2020.04.pp.051-060
and fill out the form
.
|
Archive
Разработка концепции и создание сайта - ООО «Издательский дом «СПЕКТР»