Optimal control of two deques in shared memory with various work-stealing strategies

In parallel load balancers based on work-stealing strategy each processor has its own task deque. One end of the deque is used by the owner to add and retrieve tasks, and the second — by the other processors to steal tasks. The aim of this research is to construct and analyze mathematical models of the process of work with two cyclic deques located in the shared memory. The parameters of these models are the probabilities of operations (serial or parallel) at each step of discrete time. Mathematical models are built as random walks on an integer lattice in the plane. On the basis of models, problems of optimal partition of memory were solved for various work-stealing strategies. As the criterion of optimality we consider the maximum mean time to the memory overflow. Statistical studies to assess the probabilities of operations were carried out for multiple types of tasks. For this purpose, as a part of our RFBR grant, work-stealing balancer was constructed. Obtained probabilities were used in numerical experiments to analyze the developed models. To solve these problems apparatus of controlled random walks, absorbing Markov chains and LAPACK system were used. Calculations were made using cluster KRC RAS. (In Russian)