RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Guidelines for authors
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Program Systems: Theory and Applications:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Program Systems: Theory and Applications, 2019, Volume 10, Issue 1, Pages 19–32 (Mi ps336)  

Hardware and Software for Supercomputers

The optimal control of two work-stealing deques, moving one after another in a shared memory

E. A. Barkovskya, A. A. Lazutinab, A. V. Sokolovc

a LLC Small innovative enterprise “Arvata”
b Lomonosov Moscow State University
c Institute of Applied Mathematical Research

Abstract: In the parallel work-stealing load balancers, each core owns personal buffer of tasks called deque. One end of the deque is used by its owner to add and retrieve tasks, while the second end is used by other cores to steal tasks. In the paper two representation methods of deques are analyzed: partitioned serial cyclic representation of deques (one of the conventional techniques); and the new approach proposed by our team, without partition of shared memory in advance between deques moving one after another in a circle. Previously we analyzed these methods for representing FIFO queues in network applications, where the “One after another” way gave the best result for some values of the system parameters.
Purpose of this research is to construct and analyze models of the process of work with two circular deques located in shared memory, where they movie one after another in a circle. The mathematical model is constructed in the form of a random walk by integer points in the pyramid. The simulation model is constructed using the Monte Carlo method. The used work-stealing strategy is stealing of one element. We propose the mathematical and simulation models of this process and carry out numerical experiments.

Key words and phrases: work-stealing schedulers, work-stealing deques, data structures, absorbing Markov chains, random walks.

Funding Agency Grant Number
Russian Foundation for Basic Research 18-01-00125_a
This work was supported by grant RFBR No 18-01-00125-a.


DOI: https://doi.org/10.25209/2079-3316-2019-10-1-19-32

Full text: PDF file (949 kB)
References: PDF file   HTML file

UDC: 004.942
MSC: Primary 68Q85; Secondary 68P05, 68Q87
Received: 28.10.2018
20.11.2018
Accepted: 15.02.2019
Language:

Citation: E. A. Barkovsky, A. A. Lazutina, A. V. Sokolov, “The optimal control of two work-stealing deques, moving one after another in a shared memory”, Program Systems: Theory and Applications, 10:1 (2019), 19–32

Citation in format AMSBIB
\Bibitem{BarLazSok19}
\by E.~A.~Barkovsky, A.~A.~Lazutina, A.~V.~Sokolov
\paper The optimal control of two work-stealing deques, moving one after another in a shared memory
\jour Program Systems: Theory and Applications
\yr 2019
\vol 10
\issue 1
\pages 19--32
\mathnet{http://mi.mathnet.ru/ps336}
\crossref{https://doi.org/10.25209/2079-3316-2019-10-1-19-32}


Linking options:
  • http://mi.mathnet.ru/eng/ps336
  • http://mi.mathnet.ru/eng/ps/v10/i1/p19

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
    Translation
  • Program Systems: Theory and Applications
    Number of views:
    This page:31
    Full text:8
    References:8

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019