The Models and Methods of Optimal Control of Three Work-Stealing Deques Located in a Shared Memory

Abstract

“Work-stealing” is one of the most common methods of parallel task balancing. In this method, each core (processor) has a buffer of its tasks—a double-ended queue called “deque”. A core (processor) use one end of the deque to add new tasks or to take already available to execute them. The second end of the deque is accessible by other cores (processors), which have become empty and can intercept tasks—this is the mechanism of “work-stealing”. Algorithms and techniques for the high-performance big data processing are becoming increasingly sought after not only for storing databases but also for the proper handling of big data from a variety of domains such as science and engineering. Models and algorithms of optimal control of large deques belong to this area of research. The goal of this work is to develop, analyze and compare the models and methods of control of work-stealing deques in limited shared memory. For the case of three deques, the following control methods will be discussed: 1. Each of the three deques is located in its separate memory area; 2. Three deques move one after another in a circle; 3. Combined method—two deques are located one after another, one separately. To solve the posed problems, controlled random walks and simulation modeling were used.