|
Hardware, software and distributed supercomputer systems
About optimal managment of work-stealing deques in two-level memory
E. A. Aksenovaa, A. A. Lazutinab, A. V. Sokolova a Institute of Applied Mathematical Research KarRC of RAS
b Lomonosov Moscow State University
Abstract:
The paper analyzes the problem of optimal control of a work-stealing deque in two-level memory (for example, registers –random access memory), where probabilities of parallel operations with the deque are known. The classic sequential cyclic method for representing a deque in memory is considered. If a deque overflows or empty, we transfer elements from its middle part from the fast memory to the slow memory, since data from the end parts of the deque may be needed earlier. The problem is to find the optimal number of elements from both sides of the deque to leave in the fast memory if the deque is full or empty. As an optimality criterion, we consider the minimum average cost of memory reallocation, which is necessary in case of overflow or emptying of fast memory. The simulation model of this process is constructed. The results of numerical experiments are presented.
Key words and phrases:
work-stealing balancers, work-stealing deques, Monte-Carlo method,
random walks.
Received: 15.01.2021 09.04.2021 Accepted: 12.05.2021
Citation:
E. A. Aksenova, A. A. Lazutina, A. V. Sokolov, “About optimal managment of work-stealing deques in two-level memory”, Program Systems: Theory and Applications, 12:2 (2021), 53–71
Linking options:
https://www.mathnet.ru/eng/ps382 https://www.mathnet.ru/eng/ps/v12/i2/p53
|
Statistics & downloads: |
Abstract page: | 111 | Full-text PDF : | 30 | References: | 21 |
|