Построение и анализ модели процесса работы с двумя деками, двигающимися друг за другом в общей памяти
Автор: Барковский Евгений Александрович, Лазутина Анна Александровна, Соколов Андрей Владимирович
Журнал: Программные системы: теория и приложения @programmnye-sistemy
Рубрика: Программное и аппаратное обеспечение для супер ЭВМ
Статья в выпуске: 1 (40) т.10, 2019 года.
Бесплатный доступ
В work-stealing балансировщиках параллельных задач, каждое ядро имеет свой буфер задач-дек (англ. deque). Владелец дека использует один конец для добавления и извлечения задач, а из второго конца задачи перехватываются другими ядрами. В статье анализируются два метода представления деков: один из распространенных методов-раздельное последовательное циклическое представление деков; и новый предложенный нами метод, где общая память для деков заранее не делится и они двигаются друг за другом по кругу. Ранее эти методы анализировались нами для представления FIFO-очередей в сетевых приложениях, где для некоторых значений параметров системы метод «Друг за другом» давал лучший результат.Целью исследования является построение и анализ модели процесса работы с двумя последовательными деками, когда они двигаются друг за другом по кругу в общей памяти. Математическую модель мы будем строить как случайное блуждание по целым точкам в пирамиде. Имитационная модель строится с помощью метода Монте-Карло. Используемая стратегия work-stealing-перехват одного элемента. Предложены математическая и имитационная модели данного процесса и проведены численные эксперименты.
Work-stealing балансировщики, work-stealing деки, структуры данных, поглощающие цепи маркова, случайные блуждания
Короткий адрес: https://sciup.org/143169789
IDR: 143169789 | УДК: 004.942 | DOI: 10.25209/2079-3316-2019-10-1-3-17
The optimal control of two work-stealing deques, moving one after another in a shared memory
In the parallel work-stealing load balancers, each core owns 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. In the paper two representation methods of deques are analyzed: partitioned serial cyclic representation of deques (one of the conventional techniques); and the new approach proposed by our team, without partition of shared memory in advance between deques moving one after another in a circle. Previously we analyzed these methods for representing FIFO queues in network applications, where the “One after another” way gave the best result for some values of the system parameters.Purpose of this research is to construct and analyze models of the process of work with two circular deques located in shared memory, where they movie one after another in a circle. The mathematical model is constructed in the form of a random walk by integer points in the pyramid. The simulation model is constructed using the Monte Carlo method. The used work-stealing strategy is stealing of one element. We propose the mathematical and simulation models of this process and carry out numerical experiments.
Список литературы Построение и анализ модели процесса работы с двумя деками, двигающимися друг за другом в общей памяти
- R.D. Blumofe, C.E. Leiserson. “Scheduling multithreaded computations by work stealing”, Journal of the ACM, 5:46 (1999), pp. 720-748.
- M. Herlihy, N. Shavit. The art of multiprocessor programming, Elsevier, 2008, 536 pp.
- R.D. Blumofe, C.F. Joerg, B.C. Kuszmaul, C.E. Leiserson, K.H. Randall, Y. Zhou. “Cilk: an efficient multithreaded runtime system”, Journal of Parallel and Distributed Computing, 37:1 (1996), pp. 55-69.
- D. Leijen, W. Schulte, S. Burckhardt. “The design of a task parallel library”, ACM SIGPLAN, 44:10 (2009), pp. 227-242.
- O. Tardieu, H. Wang, H. Lin. “A work-stealing scheduler for X10's task parallelism with suspension”, ACM SIGPLAN, 47:8 (2012), pp. 267-276.
- G. Varisteas, Effective cooperative scheduling of task-parallel applications on multiprogrammed parallel architectures Effective cooperative scheduling of task-parallel applications on multiprogrammed parallel architectures, Doctoral Thesis in Information and Communication Technology Doctoral Thesis in Information and Communication Technology, 2015 URL http://kth.diva-portal.org/smash/get/diva2:861129/FULLTEXT01.pdf.
- D. Knuth. The art of multiprocessor programming, Addison-Wesley Professional, 1997, 672 pp.
- D. Hendler, N. Shavit. “Non-blocking steal-half work queues”, PODC '02, 2002, pp. 280-289.
- A.V. Sokolov, A.V. Drac. “The linked list representation of n LIFO-stacks and/or FIFO-queues in the single-level memory”, Information Processing Letters, 113:19-21 (2013), pp. 832-835.
- Е.А. Аксенова, А.А. Лазутина, А.В. Соколов. «Об оптимальных методах представления динамических структур данных», Обозрение прикладной и промышленной математики, 10:2 (2003), с. 375-376.
- D. Hendler, Y. Lev, M. Moir, N. Shavit. “A dynamic-sized nonblocking work stealing deque”, Distributed Computing, 18:3 (2006), pp. 189-207.
- M. Mitzenmacher. “Analyses of load stealing models based on differential equations”, SPAA '98, 1998, pp. 212-221.
- А.В. Калачев. Многоядерные процессоры, БИНОМ, М., 2014, 247 с.
- Е.А. Барковский, А.В. Соколов, Способ управления памятью компьютерной системы Способ управления памятью компьютерной системы, № 2647627. Бюллетень № 8 № 2647627. Бюллетень № 8, Опубл. 16.03.2018.
- А.В. Соколов. Математические модели и алгоритмы оптимального управления динамическими структурами данных, ПетрГУ, Петрозаводск, 2002.
- Е.А. Барковский, А.В. Соколов. «Модель управления двумя параллельными FIFO-очередями, двигающимися друг за другом в общей памяти», Информационно-управляющие системы, 2016, №1, с. 65-73.
- E.A. Aksenova, A.A. Lazutina, A.V. Sokolov. “Study of a non-Markovian stack management model in a two-level memory”, Programming and Computer Software, 30:1 (2004), pp. 25-33.
- E.A. Aksenova, A.V. Sokolov. “Optimal implementation of two FIFO-queues in single-level memory”, Applied Mathematics, 2:10 (2011), pp. 1297-1302.
- Е.А. Барковский, А.А. Лазутина, А.В. Соколов. “Модель управления двумя work-stealing деками, двигающимися друг за другом в общей памяти”, Обозрение прикладной и промышленной математики, 25:1 (2018), pp. 77.
- D. Chase, Y. Lev. “Dynamic circular work-stealing deque”, SPAA '05, 2005, pp. 21-28.
- Е.А. Барковский, А.В. Соколов. “Вероятностная модель для задачи оптимального управления work-stealing деками при различных стратегиях перехвата работы”, IX Международная Петрозаводская конференция, 2016, pp. 11-13.
- A.V. Sokolov, E.A. Barkovsky. “The mathematical model and the problem of optimal partitioning of shared memory for work-stealing deques”, PaCT 2015: Parallel Computing Technologies, Lecture Notes in Computer Science, vol. 9251, 2015, pp. 102-106.
- E.A. Aksenova, A.V. Sokolov. “Modeling of the memory management process for dynamic work-stealing schedulers”, 2017 Ivannikov ISPRAS Open Conference (ISPRAS), 2018, pp. 12-15.
- S. Mattheis, T. Schuele, A. Raabe, T. Henties, U. Gleim. “Work stealing strategies for parallel stream processing in soft real-time systems”, ARCS 2012: Architecture of Computing Systems - ARCS 2012, Lecture Notes in Computer Science, vol. 7179, 2002, pp. 172-183.
- А.И. Адамович, А.В. Климов. «Как создавать параллельные программы, детерминированные по построению? Постановка проблемы и обзор работ», Программные системы: теория и приложения, 8:4 (2017), с. 221-244.
- Е.А. Барковский, Р.И. Кучумов, А.В. Соколов. «Оптимальное управление двумя work-stealing деками в общей памяти при различных стратегиях перехвата работы», Программные системы: теория и приложения, 8:1 (2017), с. 83-103.
- Р.И. Кучумов. «Реализация и анализ work-stealing планировщика задач», Стохастическая оптимизация в информатике, 12:1 (2016), с. 20-39.
- Е.А. Барковский. «Реализация менеджера памяти в work-stealing балансировщике», Стохастическая оптимизация в информатике, 13:1 (2017), с. 56-65.
- R. Kuchumov, A. Sokolov, V. Korkhov. “Staccato: cache-aware work-stealing task scheduler for shared-memory systems”, ICCSA 2018: Computational Science and Its Applications - ICCSA 2018, Lecture Notes in Computer Science, vol. 10963, 2018, pp. 91-102.
- Дж. Кемени, Дж. Снелл. Конечные цепи Маркова, Наука, М., 1970, 272 с.
- Е.А. Аксенова, А.В. Соколов. «Оптимальное управление двумя параллельными стеками в двухуровневой памяти», Дискретная математика, 19:1 (2007), с. 67-75.
- А.В. Соколов. «Об оптимальном кешировании FIFO-очередей», Стохастическая оптимизация в информатике, 9:2 (2013), с. 108-123.
- P.J. Koopman. Stack computers: the new wave, Ellis Horwood Ltd., 1989, 502 pp.
