The Models and Methods of Optimal Control of Three Work-Stealing Deques Located in a Shared Memory
- Авторы: Aksenova E.1, Barkovsky E.2, Sokolov A.1
-
Учреждения:
- Institute of Applied Mathematical Research of the Karelian Research Centre of the Russian Academy of Sciences
- Small Innovative Enterprise OOO Arvata
- Выпуск: Том 40, № 11 (2019)
- Страницы: 1763-1770
- Раздел: Article
- URL: https://journals.rcsi.science/1995-0802/article/view/206040
- DOI: https://doi.org/10.1134/S1995080219110052
- ID: 206040
Цитировать
Аннотация
“Work-stealing” is one of the most common methods of parallel task balancing. In this method, each core (processor) has a buffer of its tasks—a double-ended queue called “deque”. A core (processor) use one end of the deque to add new tasks or to take already available to execute them. The second end of the deque is accessible by other cores (processors), which have become empty and can intercept tasks—this is the mechanism of “work-stealing”. Algorithms and techniques for the high-performance big data processing are becoming increasingly sought after not only for storing databases but also for the proper handling of big data from a variety of domains such as science and engineering. Models and algorithms of optimal control of large deques belong to this area of research. The goal of this work is to develop, analyze and compare the models and methods of control of work-stealing deques in limited shared memory. For the case of three deques, the following control methods will be discussed: 1. Each of the three deques is located in its separate memory area; 2. Three deques move one after another in a circle; 3. Combined method—two deques are located one after another, one separately. To solve the posed problems, controlled random walks and simulation modeling were used.
Ключевые слова
Об авторах
E. Aksenova
Institute of Applied Mathematical Research of the Karelian Research Centre of the Russian Academy of Sciences
Автор, ответственный за переписку.
Email: aksenova@krc.karelia.ru
Россия, Petrozavodsk, 185910
E. Barkovsky
Small Innovative Enterprise OOO Arvata
Автор, ответственный за переписку.
Email: barkevgen@gmail.com
Россия, Petrozavodsk, 185910
A. Sokolov
Institute of Applied Mathematical Research of the Karelian Research Centre of the Russian Academy of Sciences
Автор, ответственный за переписку.
Email: sokavs@gmail.com
Россия, Petrozavodsk, 185910
![](/img/style/loading.gif)