Elena Aksenova, Andrew Sokolov.
Minimizing the average cost of redistribution when working with two work-stealing deques in two-level memory
// Russian Supercomputing Days: Proceedings of the International Conference. September 26–27, 2022, Moscow, Russia. / Ed. by Vl. Voevodin. – Moscow : MAKS Press, 2022. Pp. 4-12
Ключевые слова: work-stealing balancers, work-stealing deques, data structures, random walks
In work-stealing parallel task balancers, each core has its own task buffer - deque. The owner of the deque uses one end to add and retrieve tasks, and from the other end, tasks are intercepted by other cores. The paper considers the problem of optimal control of two work-stealing deques in a two-level memory. The probabilities of parallel operations with deques are known. The task is to find the optimal division of fast memory for deques and determine the optimal number of elements for both ends of each deque, which storing in fast memory after memory reallocation. As an optimality criterion, we consider the minimum sum of average memory redistribution costs that occur in the case of overflow or emptying of fast memory by each deque. This criterion makes it possible to take into account specific speeds of access to memory levels and apply the developed methods to different combinations of fast and slow memory. A simulation model of the work process is constructed, the results of numerical experiments are presented.
Индексируется в РИНЦ