Оптимальное управление двумя work-stealing деками в общей памяти при различных стратегиях перехвата работы
Автор: Барковский Евгений Александрович, Кучумов Руслан Ильдусович, Соколов Андрей Владимирович
Журнал: Программные системы: теория и приложения @programmnye-sistemy
Рубрика: Программное и аппаратное обеспечение распределенных и суперкомпьютерных систем
Статья в выпуске: 1 (32) т.8, 2017 года.
Бесплатный доступ
В параллельных балансировщиках задач, работающих по стратегии work-stealing, каждый процессор имеет свой дек (deque) задач. Один конец дека используется только владельцем для добавления и извлечения задач, а другой — для перехвата другими процессорами. Целью работы является построение и анализ математических моделей процесса работы с двумя циклическими деками, расположенными в общей памяти. Параметрами этих моделей являются вероятности операций на каждом шаге дискретного времени (возможно как последовательное, так и параллельное выполнение операций). Модели строятся в виде случайных блужданий по целочисленной решетке на плоскости. На основе вышеупомянутых моделей решены задачи оптимального разделения памяти при некоторых стратегиях перехвата элементов. В качестве критерия оптимальности рассматривается максимальное среднее время до переполнения памяти. Проведены статистические исследования по оценке вероятностей операций работы с деками для нескольких типов задач, выполняемых в реализованном балансировщике. Для полученных вероятностей операций работы с деками проведены численные эксперименты по анализу разработанных моделей
ID: 14336116 Короткий адрес: https://sciup.org/14336116
Список литературы Оптимальное управление двумя work-stealing деками в общей памяти при различных стратегиях перехвата работы
- R. D. Blumofe, C. E. Leiserson. "Scheduling Multithreaded Computations by Work Stealing", Journal of the ACM, V. 46. No. 5. 1999. P. 720-748.
- M. Herlihy, N. Shavit. The Art of Multiprocessor Programming, Elsevier, 2008, 536 p.
- D. Knuth. The Art of Computer Programming. V. 1, Addison-Wesley, 2005, v+134 p.
- D. Hendler, N. Shavit. "Non-blocking Steal-half Work Queues", ACM Symposium on Principles of Distributed Computing (PODC 2002) (July 21-24, 2002, Monterey, California). P. 280-289.
- A. V. Sokolov, A. V. Drac. "The Linked List Representation of 𝑛 LIFO-Stacks and/or FIFO-Queues in the Single-Level Memory", Information Processing Letters, V. 13. No. 19-21. 2013. P. 832-835.
- Е. А. Аксенова, А. А. Лазутина, А. В. Соколов. Об оптимальных методах представления динамических структур данных//Обозрение прикладной и промышленной математики, Т. 10, № 2. 2003. С. 375-376.
- D. Hendler, Y. Lev, M. Moir, N. Shavit. "A Dynamic-Sized Nonblocking Work Stealing Deque", Distributed Computing, V. 18. No. 3. 2006. P. 189-207.
- M. Mitzenmacher. "Analyses of Load Stealing Models Based on Differential Equations", Proceedings of the ACM Symposium on Parallel Algorithms and Architectures (SPAA’ 98) (Puerto Vallarta, Mexico, June 28-July 2, 1998). P. 212-221.
- D. Chase, Y. Lev. "Dynamic Circular Work-Stealing Deque", ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2005) (Las Vegas, Nevada, USA, July 18-20, 2005). P. 21-28.
- 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, V. 30. No. 1. 2004. P. 25-33.
- E. A. Aksenova, A. V. Sokolov. "The Optimal Implementation of Two FIFO-queues in Single-Level Memory", Applied Mathematics, V. 2. No. 10. 2011. P. 1297-1302.
- А. В. Соколов, А. В. Драц. Моделирование некоторых методов представления 𝑛 FIFO очередей в памяти одного уровня//Эвристические алгоритмы и распределенные вычисления, Т. 1, № 1. 2014. С. 40-52.
- А. В. Калачев. Многоядерные процессоры, Бином, М., 2010.
- Дж. Кемени, Дж. Снелл. Конечные цепи Маркова, Наука, М., 1960, 272 с.
- N. S. Arora, R. D. Blumofe, C. G. Plaxton. "Thread Scheduling for Multiprogrammed Multiprocessors", ACM Symposium on Parallel Algorithms and Architectures (SPAA’ 98) (Puerto Vallarta, Mexico, June 28-July 2, 1998). P. 119-129.
- N. M. Le, A. Pop, A. Cohen, F. Z. Nardelli. "Correct and efficient work-stealing for weak memory model", ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP’ 13) (Shenzhen, China, February 23-27, 2013). P. 69-80.
- Р. И. Кучумов. Реализация и анализ work-stealing планировщика задач//Стохастическая оптимизация в информатике, Т. 12, № 1. 2016. С. 20-39.
- G. Paoloni. How to Benchmark Code Execution Times on Intel IA-32 and IA-64 Instruction Set Architectures, White Paper 324264-001, Intel, 2010, URL: http://www.intel.com/content/dam/www/public/us/en/documents/white-papers/ia-32-ia-64-benchmarkcode-execution-paper.pdf
- М. А. Посыпкин, И. Х. Сигал. Комбинированный параллельный алгоритм решения задачи о ранце//IV Международная конференция "Параллельные вычисления и задачи управления" (Москва, Россия, 27-29 октября 2008 г.). С. 177-189.
- D. Y. Yeh, T. Munakata. "Dynamic initial allocation and local reallocation procedures for multiple stacks", Communications of the ACM, V. 29. No. 2. 1986. P. 134-141.
- Е. А. Барковский, А. В. Соколов. Вероятностная модель для задачи оптимального управления work-stealing деками при различных стратегиях перехвата работы//IX Международная Петрозаводская конференция "Вероятностные методы в дискретной математике" (Петрозаводск, Россия, 30 мая-3 июня 2016 г.). С. 11-13.
- A. Sokolov, E. Barkovsky. "The Mathematical Model and The Problem of Optimal Partitioning of Shared Memory for Work-Stealing Deques", Parallel Computing Technologies, 13th International Conference PaCT 2015 (Petrozavodsk, Russia, August 31-September 4, 2015), Lecture Notes in Computer Science, vol. 9251, Springer International Publishing, 2015. P. 102-106.
