Optimal control of three work-stealing deques located in two-level memory

The problem of even balancing of tasks between threads may arise during parallel computations. One way to resolve this issue is to implement distributed dynamic load balancing. In this balancing method each worker thread has its own task queue, and threads themselves distribute further tasks. One of the widely used distributed dynamic balancing methods is “work-stealing”: a thread that runs out of tasks begins to “steal” them from another thread. To utilize this method, each thread must have its own specialized deque where pointers to tasks are stored. In this paper, we propose and examine a new method for representing three work stealing deques in two-level memory. We consider the case of working with three deques, where one section of fast memory contains two LIFO parts of the deques, i.e., two stacks that grow towards each other. Third LIFO part and three FIFO parts are located in the other section of fast memory. FIFO parts are combined into one FIFO queue, from which elements are only deleted (being stolen). The middle parts of the deques are located in slow memory. They are accessed when LIFO or FIFO parts located in fast memory are empty or overflowed. We consider the problem of finding optimal partition of fast memory for three deques with predetermined probabilities of operations. This choice depends on the characteristics of memory levels, operation probabilities, and optimality criteria. The optimality criterion is the maximum mean system operating time (the average number of operations) before memory reallocation.