About Optimal Management of Work-Stealing Deques in Two-Level Memory
Tóm tắt
This paper analyzes the problem of optimal control of two work-stealing deques in two-level memory (for example, registers—random access memory), where probabilities of parallel operations with deques are known. The classic sequential cyclic method for representing a deque in memory is considered. In the case of the deque overflowing in fast memory or emptying the FIFO-part or LIFO-part the necessary exchanges between fast and slow memory and shifts of elements in fast memory occur for relocation to the optimal state, which to be found. The task is to find the optimal partition of the total fast memory for deques and to determine the optimal state of each deque in each partition after the memory reallocation, i.e., to find the optimal number of elements, taken from both sides of the deque, to leave in the fast memory if the deque is filled or emptied. Optimality criteria for memory sharing is to maximize the sum of the mean operating times of each deque before the memory is redistributed and to maximize the lowest mean operating time of each deque before the memory is redistributed. The mathematical model in the form of an absorbing Markov chain are constructed. Simulation modeling, based on the proposed mathematical model, was carried out. The results of numerical experiments are presented.
Tài liệu tham khảo
citation_journal_title=J. ACM; citation_title=Scheduling multithreaded computations by work stealing; citation_author=R. D. Blumofe, C. E. Leiserson; citation_volume=46; citation_publication_date=1999; citation_pages=720-748; citation_doi=10.1145/324133.324234; citation_id=CR1
citation_title=
; citation_publication_date=1997; citation_id=CR2; citation_author=D. Knuth; citation_publisher=Addison-Wesley Professional
citation_journal_title=Inform. Process. Lett.; citation_title=The linked list representation of n LIFO-stacks and/or FIFO-queues in the single-level memory; citation_author=A. V. Sokolov, A. V. Drac; citation_volume=113; citation_publication_date=2013; citation_pages=832-835; citation_doi=10.1016/j.ipl.2013.07.021; citation_id=CR3
citation_journal_title=Obozr. Prikl. Prom. Mat.; citation_title=About the optimal methods of representation of dynamic data structures; citation_author=E. A. Aksenova, A. A. Lazutina, A. V. Sokolov; citation_volume=10; citation_publication_date=2003; citation_pages=375-376; citation_id=CR4
citation_journal_title=Distrib. Comput.; citation_title=A dynamic-sized nonblocking work stealing deque; citation_author=D. Hendler, Y. Lev, M. Moir, N. Shavit; citation_volume=18; citation_publication_date=2006; citation_pages=189-207; citation_doi=10.1007/s00446-005-0144-5; citation_id=CR5
M. Mitzenmacher, ‘‘Analyses of load stealing models based on differential equations,’’ in Proceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architectures SPAA’98 (1998), pp. 212–221.
A. V. Sokolov and E. A. Barkovsky, ‘‘The mathematical model and the problem of optimal partitioning of shared memory for work-stealing deques,’’ in PaCT 2015: Parallel Computing Technologies, Lect. Notes Comput. Sci. 9251, 102–106 (2015).
E. A. Aksenova and A. V. Sokolov, ‘‘Modeling of the memory management process for dynamic work-stealing schedulers,’’ in Proceedings of the 2017 Ivannikov ISPRAS Open Conference ISPRAS (2018), pp. 12–15.
D. Chase and Y. Lev, ‘‘Dynamic circular work-stealing deque,’’ in Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures SPAA’05 (2005), 21–28.
citation_journal_title=Commun. Comput. Inform. Sci.; citation_title=Multithreaded multifrontal sparse Cholesky factorization Using threading building blocks; citation_author=R. Povelikin, S. Lebedev, I. Meyerov; citation_volume=1129; citation_publication_date=2019; citation_pages=75-86; citation_doi=10.1007/978-3-030-36592-9_7; citation_id=CR10
E. A. Barkovsky and A. V. Sokolov, ‘‘Method for managing computer system memory,’’ RF Patent тДЦ 2647627 (2018).
E. Barkovsky, A. Lazutina, and A. Sokolov, ‘‘The optimal control of two work-stealing deques, moving one after another in a shared memory,’’ Program Syst.: Theory Appl., No. 10, 19–32 (2019).
citation_journal_title=Lobachevskii J. Math.; citation_title=The models and methods of optimal control of three work-stealing deques located in a shared memory; citation_author=E. A. Aksenova, E. A. Barkovsky, A. V. Sokolov; citation_volume=40; citation_publication_date=2019; citation_pages=1763-1770; citation_doi=10.1134/S1995080219110052; citation_id=CR13
citation_journal_title=Int. J. Web Grid Servic.; citation_title=Staccato: Shared-memory work-stealing task scheduler with cache-aware memory management; citation_author=R. Kuchumov, A. Sokolov, V. Korkhov; citation_volume=15; citation_publication_date=2019; citation_pages=394-407; citation_doi=10.1504/IJWGS.2019.103233; citation_id=CR14
citation_title=
; citation_publication_date=1989; citation_id=CR15; citation_author=P. J. Koopman; citation_publisher=Ellis Horwood
citation_journal_title=Program. Comput. Software; citation_title=Study of a non-Markovian stack management model in a two-level memory; citation_author=E. A. Aksenova, A. A. Lazutina, A. V. Sokolov; citation_volume=30; citation_publication_date=2004; citation_pages=25-33; citation_doi=10.1023/B:PACS.0000013438.25368.b4; citation_id=CR16
citation_journal_title=Discrete Math.; citation_title=Optimal control of two parallel stacks in two-level memory; citation_author=E. A. Aksenova, A. V. Sokolov; citation_volume=19; citation_publication_date=2007; citation_pages=67-75; citation_id=CR17
A. A. Lazutina and A. V. Sokolov, ‘‘On the optimal management of Work-Stealing deques in two-level memory,’’ Vestn. Komp’yut. Inform. Tekhnol. 17 (4), 51–60 (2020). http://www.vkit.ru/index.php/current-issue-rus/914-051-060.
citation_title=
; citation_publication_date=1980; citation_id=CR19; citation_author=A. V. Sokolov; citation_publisher=Karel. Otdel. Akad. Nauk
A. C. Yao, ‘‘An analysis of a memory allocation scheme for implementating stacks,’’ SIAM J. Comput., тДЦ 10, 398–403 (1981).
citation_journal_title=Lect. Notes Comput. Sci.; citation_title=The evolution of two stacks in bounded space and random walks in a triangle; citation_author=P. Flajolet; citation_volume=223; citation_publication_date=1986; citation_pages=325-340; citation_doi=10.1007/BFb0016257; citation_id=CR21
G. Louchard, R. Schott, M. Tolley, and P. Zimmermann, ‘‘Random walks, heat equation and distributed algorithms,’’ J. Comput. Appl. Math., тДЦ 53, 243–274 (1994).
citation_journal_title=Lect. Notes Comput. Sci.; citation_title=Probabilistic analysis of some distributed algorithms; citation_author=G. Louchard, R. Schott; citation_volume=431; citation_publication_date=1990; citation_pages=239-253; citation_doi=10.1007/3-540-52590-4_52; citation_id=CR23
R. S. Maier, ‘‘Colliding stacks: A large deviations analysis,’’ Random Struct. Algorithms, тДЦ 2, 379–421 (1991).
citation_title=
; citation_publication_date=1960; citation_id=CR25; citation_author=J. G. Kemeny; citation_author=J. L. Snell; citation_publisher=Van Nostrand