A Representation Method of Three Work- Stealing Deques in Two-Level Memory

Бесплатный доступ

The efficiency of distributed systems largely depends on the uniformity of thread workload. To achieve this, various strategies for balancing tasks between threads are utilized. One of the methods of dynamic distributed load balancing, where each thread participates in task distribution, is called “work-stealing.” In this method, a thread without tasks steals them from other threads. This process is based on a special data structure, a work-stealing deque, where pointers to tasks are stored. Thus, the problem of efficient placement of deques in memory arises. A deque can be represented in two-level memory in a divided form: the often-accessed ends of a deque are placed in the fast memory of the first level, while its middle is left in the slow memory of the second level. This way, the system can quickly access the ends of the deque where elements are being actively added and removed. In this paper, a new representation method of three work-stealing deques in two-level memory where the ends of the deques are placed in separate memory areas is described. We propose a simulation model of this approach based on the Monte Carlo method and solve several problems of optimal partitioning of memory. The optimality criterion is the maximum mean system operating time to memory reallocation.

Еще

Data structures, Monte Carlo method, two-level memory, work-stealing deques

Короткий адрес: https://sciup.org/147252009

IDR: 147252009   |   УДК: 004.942   |   DOI: 10.14529/cmse250302