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.
Fulltext:
PDF file (1575 kB)