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.
Fulltext:
PDF file (977 kB)