Control methods of work-stealing deques in dynamic schedulers of multiprocessor parallel computations

E. A. Aksenova ; A. V. Sokolov

Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 12 (2023) no. 4, pp. 76-93

Résumé

In parallel task schedulers, which are using the work-stealing strategy, each processor has own task deque. One end of the deque is used for insertion and deletion of tasks only by the owner, and the other is used for stealing of tasks by other processors. The article offers an overview of work-stealing deque's description of the deque's optimal management problems, which our team had solved for the work-stealing strategy. The idea of the algorithm for deque's managing in two-level memory is that if the memory allocated to the deques becomes overflow, elements are redistributed between memory levels. Elements from the deque's ends are stored in fast memory, since they will be worked with in the near time, and elements from the deque's middle part are stored in slow memory. In this case, it is necessary to determine the required number of elements that need to be left in fast memory, depending on the optimal criteria and system parameters.

Détail

Keywords: controlled random walks, optimal control of work-stealing deques, optimal deque caching, optimization of work-stealing load schedulers, simulation and Markov models of optimal control of data structures.