RUS  ENG
Полная версия
ЖУРНАЛЫ // Программные системы: теория и приложения // Архив

Программные системы: теория и приложения, 2019, том 10, выпуск 1, страницы 19–32 (Mi ps336)

Эта публикация цитируется в 2 статьях

Программное и аппаратное обеспечение для суперЭВМ

The optimal control of two work-stealing deques, moving one after another in a shared memory

E. A. Barkovskya, A. A. Lazutinab, A. V. Sokolovc

a LLC Small innovative enterprise “Arvata”
b Lomonosov Moscow State University
c Institute of Applied Mathematical Research

Аннотация: 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.

Ключевые слова и фразы: work-stealing schedulers, work-stealing deques, data structures, absorbing Markov chains, random walks.

УДК: 004.942

MSC: Primary 68Q85; Secondary 68P05, 68Q87

Поступила в редакцию: 28.10.2018
20.11.2018
Подписана в печать : 15.02.2019

Язык публикации: английский

DOI: 10.25209/2079-3316-2019-10-1-19-32



© МИАН, 2024