Минимизация средних затрат на перераспределение при работе с work-stealing деком в двухуровневой памяти
Автор: Е. А. Аксёнова, А. А. Лазутина, А. В. Соколов
Журнал: Программные системы: теория и приложения @programmnye-sistemy
Рубрика: Программное и аппаратное обеспечение распределенных и суперкомпьютерных систем
Статья в выпуске: 2 (49) т.12, 2021 года.
Бесплатный доступ
В работе рассмотрена задача оптимального управления workstealing деком (англ. — deque) в двухуровневой памяти. Предполагается, что известны вероятности параллельных операций с деком и временные характеристики памяти для двух уровней. Задача состоит в нахождении оптимального числа элементов с двух сторон дека, которые при перераспределении дека должны быть оставлены в быстрой памяти. В качестве критерия оптимальности рассмотрены минимальные средние затраты на перераспределение памяти, которые возникают в случае переполнения или опустошения быстрой памяти. Такой критерий позволяет учитывать конкретные скорости доступа к уровням памяти и применять разработанные методы к разным сочетаниям быстрой и медленной памяти. Построены математическая и имитационная модели процесса работы с деком, представлены результаты численных экспериментов.
Work-stealing балансировщики, work-stealing деки, кэширование деков, случайные блуждания, имитационные модели.
Короткий адрес: https://sciup.org/143173915
IDR: 143173915 | DOI: 10.25209/2079-3316-2021-12-2-53-71
Список литературы Минимизация средних затрат на перераспределение при работе с work-stealing деком в двухуровневой памяти
- M. Hasegava, Y. Shigei. “High-speed top-of-stack scheme for VLSI processor: a management algorithm and its analysis”, Proceedings of the 12th annual international symposium on Computer architecture, ISA’85 (June, 1985), pp. 48–54.
- T. Stanley, R. Wedig. “A performance analysis of automatically managed top of stack buffers”, Proceedings of the 14th annual international symposium on Computer architecture, ISCA’87 (June, 1987), pp. 272–281.
- P. J. Koopman, Stack Computers: The New Wave, Ellis Horwood series in computers and their applications, Halsted Press, 1989, ISBN 978-0745804187, 234 pp.
- A. K. Kim, V. I. Perekatov, S. G. Yermakov. Microprocessors and computing systems of the Elbrus family, Piter, SPb., 2013, ISBN 978-5-459-01697-0 (in Russian), 272 pp.
- Yu. V. Shevchuk, A. Yu. Shevchuk. “Etherbox32vm virtual machine”, Program Systems: Theory and Applications, 7:4(31) (2016), pp. 119–143 (in Russian).
- R. D. Blumofe, C. E. Leiserson. “Scheduling multithreaded computations by work stealing”, Journal of the ACM, 46:5 (1999), pp. 720–748.
- D. Knuth. The Art of Computer Programming. V. 1: Fundamental Algorithms, Addison-Wesley Professional, 1997, ISBN 978-0201896831.
- A. V. Sokolov, E. A. Barkovsky. “The mathematical model and the problem of optimal partitioning of shared memory for work-stealing deques”, PaCT 2015: Parallel Computing Technologies, Lecture Notes in Computer Science, vol. 9251, ed. V. Malyshkin, Springer, Cham, 2015, ISBN 978-3-319-21908-0, pp. 102–106.
- E. A. Aksenova, A. V. Sokolov. “Modeling of the memory management process for dynamic work-stealing schedulers”, 2017 Ivannikov ISPRAS Open Conference (ISPRAS) (30 Nov.–1 Dec. 2017, Moscow, Russia), 2018, pp. 12–15.
- A. V. Sokolov, Ye. A. Barkovskiy. Method for managing computer system memory, Pat. 2647627 Rossiyskaya Federatsiya, MPK G06F9/5005 (2006.01); G06F12/02 (2006.01), zayavitel’ i patentoobladatel’ FGBUN FITs “Karel’skiy nauchnyy tsentr Rossiyskoy akademii nauk”. No 2016143800; zayavl. 08.11.2016; opubl. 16.03.2018, Byul. No 8 (in Russian), 13 pp.
- 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), pp. 19–32.
- E. A. Aksenova, E. A. Barkovsky, A. V. Sokolov. “The models and methods of optimal control of three work-stealing deques located in a shared memory”, Lobachevskii Journal of Mathematics, 40:11 (2019), pp. 1763–1770.
- A. V. Sokolov. Mathematical models and algorithms for optimal control of dynamic data structures, Izd-vo PetrGU, Petrozavodsk, 2002 (in Russian), 215 pp.
- Ye. A. Barkovskiy, A. V. Sokolov. “Management model for two parallel FIFO queues moving one after another in shared memory”, Informatsionno-upravlyayushchiye sistemy, 2016, no. 1, pp. 65–73 (in Russian).
- R. Kuchumov, A. Sokolov, V. Korkhov. “Staccato: shared-memory work-stealing task scheduler with cache-aware memory management”, Inter. Journal of Web and Grid Services, 15:4 (2019), pp. 394–407.
- A. V. Sokolov. “About the optimal caching of FIFO queues”, Stokhasticheskaya optimizatsiya v informatike, 9:2 (2013), pp. 108–123 (in Russian).
- E. A. Aksenova, A. A. Lazutina, A. V. Sokolov. “Study of a non-Markovian stack management model in a two-level memory”, Programming and Computer Software, 30:1 (2004), pp. 25–33.
- E. A. Aksenova, A. V. Sokolov. “Optimal management of two parallel stacks in two-level memory”, Discrete Math. Appl., 17:1 (2007), pp. 47–55.
- A. A. Lazutina, A. V. Sokolov. “About optimal management of work-stealing deques in two-level memory”, Vestnik komp’yuternykh i informatsionnykh tekhnologiy, 17:4 (2020), pp. 51–60 (in Russian).
- A. V. Sokolov. “About memory allocation for two stacks”, Avtomatizatsiya eksperimenta i obrabotki dannykh, KF AN SSSR, Petrozavodsk, 1980, pp. 65–71 (in Russian).
- A. C. Yao. “An analysis of a memory allocation scheme for implementing stacks”, SIAM J. Computing, 10:2 (1981), pp. 398–403.
- P. Flajolet. “The evolution of two stacks in bounded space and random walks in a triangle”, MFCS 1986: Mathematical Foundations of Computer Science 1986, Lecture Notes in Computer Science, vol. 233, Springer, Berlin–Heidelberg, 1986, ISBN 978-3-540-39909-4, pp. 325–340.
- G. Louchard, R. Schott, M. Tolley, P.Zimmermann. “Random walks, heat equation and distributed algorithms”, J. Comput. Appl. Math., 53:2 (1994), pp. 243–274.
- G. Louchard, R. Schott. “Probabilistic analysis of some distributed algorithms”, CAAP 1990: CAAP’90, Lecture Notes in Computer Science, vol. 431, Springer, Berlin–Heidelberg, 1990, ISBN 978-3-540-52590-5, pp. 239–253.
- R. S. Maier. “Colliding stacks: a large deviations analysis”, Random Structures and Algorithms, 2:4 (1991), pp. 379–420.
- W. Feller. An Introduction to Probability Theory and its Applications. V. I, 3rd Edition, Wiley, 1968, ISBN 978-0471257080, 509 pp.
- T. Kohonen, Content-Adressable Memories, Springer Series in Information Sciences, vol. 1, Springer-Verlag, Berlin–Heidelberg, 1980, ISBN 978-3-642-96552-4
