Publications

Scientific publications

Elena A. Aksenova; Andrew V. Sokolov.
Modeling of the Memory Management Process for Dynamic Work-Stealing Schedulers
// IEEE Proceedings:  Proceedings of 2017 Ivannikov ISPRAS Open Conference (ISPRAS). 2018. Pp. 12-15
Parallel task schedulers that use the work-stealing strategy have tasks allocation close to optimal (e.g. all processors are loaded equally). The basic idea of the strategy is as follows: if one processor runs out of tasks, it steals them from another processor. All tasks are located in queues, where deque (double-ended queue) is the most common and effective implementation of such queue. The aim of this research is to construct and analyze mathematical models of n sequential circular deques located in a shared memory. Mathematical models are built in the form of random walks on an integer lattice in n-dimensional space. Operations (with given probabilities) occur at each step of the discrete time. On the basis of aforementioned models the following problems were solved: finding the optimal partition of a shared memory between n deques and finding the optimal number of elements for stealing. The criterion of optimality is the maximum mean time to the memory overflow.
Indexed at Web of Science, Google Scholar
Last modified: September 27, 2018