|
This article is cited in 2 scientific papers (total in 2 papers)
Hardware and Software for Supercomputers
The optimal control of two work-stealing deques, moving one after another in a shared memory
E. A. Barkovskya, A. A. Lazutinab, A. V. Sokolovc a LLC Small innovative enterprise “Arvata”
b Lomonosov Moscow State University
c Institute of Applied Mathematical Research
Abstract:
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.
Key words and phrases:
work-stealing schedulers, work-stealing deques, data structures, absorbing Markov chains, random walks.
Received: 28.10.2018 20.11.2018 Accepted: 15.02.2019
Citation:
E. A. Barkovsky, A. A. Lazutina, A. V. Sokolov, “The optimal control of two work-stealing deques, moving one after another in a shared memory”, Program Systems: Theory and Applications, 10:1 (2019), 19–32
Linking options:
https://www.mathnet.ru/eng/ps336 https://www.mathnet.ru/eng/ps/v10/i1/p19
|
Statistics & downloads: |
Abstract page: | 125 | Full-text PDF : | 39 | References: | 19 |
|