The optimal control of two work-stealing deques, moving one after another in a shared memory

The optimal control of two work-stealing deques, moving one after another in a shared memory

Автор: Barkovsky Eugene Aleksandrovich, Lazutina Anna Aleksandrovna, Sokolov Andrew Vladimirovich

Журнал: Программные системы: теория и приложения @programmnye-sistemy

Рубрика: Программное и аппаратное обеспечение для супер ЭВМ

Статья в выпуске: 1 (40) т.10, 2019 года.

Бесплатный доступ

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.

Еще

Work-stealing schedulers, work-stealing deques, data structures, absorbing markov chains, random walks, work-stealing балансировщики, work-stealing деки

Короткий адрес: https://sciup.org/143169788

IDR: 143169788   |   DOI: 10.25209/2079-3316-2019-10-1-19-32

Список литературы The optimal control of two work-stealing deques, moving one after another in a shared memory

  • 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. Doctoral Thesis in Information and Communication Technology, Royal Institute of Technology, KTH, Stockholm, Sweden, 2015.
  • D. Knuth. The Art of Multiprocessor Programming, Addison-Wesley Professional, 1997.
  • D. Hendler, N. Shavit. “Non-blocking Steal-half Work Queues”, ACM PODC, 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, 13 (2013), pp. 832-835.
  • E.A. Aksenova, A.A. Lazutina, A.V. Sokolov. “About the Optimal Methods of Representation of Dynamic Data Structures”, Review of applied and industrial mathematics, 10:2 (2003), pp. 375-376 (Russian).
  • 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”, ACM SPAA, 1998, pp. 212-221.
  • A.V. Kalachev. Multicore Architectures, Moscow, BINOM, 2014, 247 pp. (Russian).
  • E.A. Barkovsky, A.V. Sokolov. “A Way to Manage the Memory of a Computer System. No. 2647627”, Bulletin no. 8, publ. 16.03.2018 (Russian).
  • A.V. Sokolov. Mathematical Models and Algorithms of the Optimal Control of Dynamic Data Structures, Petrozavodsk, PetrSU, 2002 (Russian).
  • E.A. Barkovsky, A.V. Sokolov. “Management Model for Two Parallel FIFO Queues Moving One after Another in Shared Memory”, Information and Control Systems, 2016, no.1, pp. 65-73 (Russian).
  • 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. “The Optimal Implementation of Two FIFO-Queues in Single-Level Memory”, Applied Mathematics, 2 (2011), pp. 1297-1302.
  • E.A. Barkovsky, A.A. Lazutina, A.V. Sokolov. “The Model of Control of Two Work-Stealing Deques Moving One After Another in a Shared Memory”, Review of applied and industrial mathematics, 25:1 (2018), pp. 77 (Russian).
  • D. Chase, Y. Lev. “Dynamic Circular Work-Stealing Deque”, ACM SPAA, 2005, pp. 21-28.
  • E.A. Barkovsky, A.V. Sokolov. “Probabilistic Model for the Problem of Optimal Control of Work-Stealing Deques with Various Strategies of Work-Stealing”, Strategies of Work-Stealing. Probabilistic methods in discrete mathematics, 2016, pp. 11-13 (Russian).
  • A.V. Sokolov, E.A. Barkovsky. “The Mathematical Model and The Problem of Optimal Partitioning of Shared Memory for Work-Stealing Deques”, Lecture Notes in Computer Science, 9251 (2015), pp. 102-106.
  • E.A. Aksenova, A.V. Sokolov. “Modeling of the Memory Management Process for Dynamic Work-Stealing Schedulers”, 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”, Lecture Notes in Computer Science, 7179 (2002), pp. 172-183.
  • A.I. Adamovich, A.V. Klimov. “How to create deterministic by construction parallel programs? Problem statement and survey of related works”, Program systems: Theory and applications, 2017, no.4, pp. 221-244 (Russian).
  • E.A. Barkovsky, R.I. Kuchumov, A.V. Sokolov. “Optimal control of two deques in shared memory with various work-stealing strategies”, Program systems: Theory and applications, 2017, no.1, pp. 83-103 (Russian).
  • R.I. Kuchumov. “Implementation and Analysis of the Work-Stealing Task Scheduler”, Stochastic optimization in computer, 12:1 (2016), pp. 20-39 (Russian).
  • E.A. Barkovsky. “Implementation of the Memory Manager in the Work-Stealing Scheduler”, Stochastic optimization in computer science, 13:1 (2017), pp. 3-12 (Russian).
  • R. Kuchumov, A. Sokolov, V. Korkhov. “Staccato: Cache-Aware Work-Stealing Task Scheduler for Shared-Memory Systems”, Lecture Notes in Computer Science, 10963:1 (2018), pp. 91-102.
  • J.G. Kemeny, J.L. Snell. Finite Markov Chains, Van Nostrand, 1969.
  • E.A. Aksenova, A.V. Sokolov. “Optimal Control of Two Parallel Stacks in Two-Level Memory”, Discrete mathematics, 19:1 (2007), pp. 67-75 (Russian).
  • A.V. Sokolov. “About the Optimal Caching of FIFO Queues”, Stochastic optimization in computer science, 9:2 (2013), pp. 72-88 (Russian).
  • P.J. Koopman. Stack Computers: The New Wave, Ellis Horwood Ltd., 1989.
Еще
Статья научная
QR-код для установки приложения SciUp Наведите камеру и скачайте бесплатное приложение SciUp