Минимизация средних затрат на перераспределение при работе с work-stealing деком в двухуровневой памяти
Автор: Е. А. Аксёнова, А. А. Лазутина, А. В. Соколов
Журнал: Программные системы: теория и приложения @programmnye-sistemy
Рубрика: Программное и аппаратное обеспечение распределенных и суперкомпьютерных систем
Статья в выпуске: 2 (49) т.12, 2021 года.
Бесплатный доступ
В работе рассмотрена задача оптимального управления workstealing деком (англ. — deque) в двухуровневой памяти. Предполагается, что известны вероятности параллельных операций с деком и временные характеристики памяти для двух уровней. Задача состоит в нахождении оптимального числа элементов с двух сторон дека, которые при перераспределении дека должны быть оставлены в быстрой памяти. В качестве критерия оптимальности рассмотрены минимальные средние затраты на перераспределение памяти, которые возникают в случае переполнения или опустошения быстрой памяти. Такой критерий позволяет учитывать конкретные скорости доступа к уровням памяти и применять разработанные методы к разным сочетаниям быстрой и медленной памяти. Построены математическая и имитационная модели процесса работы с деком, представлены результаты численных экспериментов.
Work-stealing балансировщики, work-stealing деки, кэширование деков, случайные блуждания, имитационные модели.
Короткий адрес: https://sciup.org/143173915
IDR: 143173915 | УДК: 004.942+004.272.3 | DOI: 10.25209/2079-3316-2021-12-2-53-71
About optimal managment of work-stealing deques in two-level memory
The paper analyzes the problem of optimal control of a work-stealing deque in two-level memory (for example, registers –random access memory), where probabilities of parallel operations with the deque are known. The classic sequential cyclic method for representing a deque in memory is considered. If a deque overflows or empty, we transfer elements from its middle part from the fast memory to the slow memory, since data from the end parts of the deque may be needed earlier. The problem is to find the optimal number of elements from both sides of the deque to leave in the fast memory if the deque is full or empty. As an optimality criterion, we consider the minimum average cost of memory reallocation, which is necessary in case of overflow or emptying of fast memory. The simulation model of this process is constructed. The results of numerical experiments are presented.
Список литературы Минимизация средних затрат на перераспределение при работе с 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
