Supercomputing Software and Hardware

Article # 1_2019

15 с.

PDF

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

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 jobs. 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. (In Russian)

Key words: Work-Stealing Schedulers, Work-Stealing Deques, Data Structures, Absorbing Markov Chains, Random Walks.

article citation

 DOI

https://doi.org/10.25209/2079-3316-2019-10-1-3-17