2022 № 2(55)

CONTENTS

Evstifeev E. V., Moskalenko О. I. Application of calculation of local Lyapunov exponents to analyze characteristics of intermittent generalized synchronization
Stubarev I. M.. Alsowa О. K. Improving the quality of recommender system algorithm using associative analysis methods
Balakin V., Emanov F., Berkaev D. Beam parameters monitor and control software tools for VEPP-5 injection complex damping ring
Medvedev Yu. G. Simulation the passage of a laminar flow through a local constriction in a pipe
Filatov A. Yu., Mikheev V. V. Incremental approaches to thread-local garbage collection

Saratov State University, 410012, Saratov, Russia

Regional Science and Education Mathematics Centre Mathematics of the Future, 410012, Saratov, Russia

APPLICATION OF CALCULATION OF LOCAL LYAPUNOV EXPONENTS TO ANALYZE CHARACTERISTICS OF INTERMITTENT GENERALIZED SYNCHRONIZATION

DOI: 10.24412/2073-0667-2022-2-5-16

EDN: AMQZYA

In the work we investigated the main characteristics of intermittent generalized synchronization, such as the distributions of the durations of laminar phases at a fixed value of the coupling parameter and the dependence of the mean duration of laminar phases on the supercriticality parameter, by calculating the local Lyapunov exponents. This method should make it possible to carry out research not only in the case of unidirectional coupling of interacting systems, but also in the case of mutual one. The analyzed systems were Rossler oscillators with a relatively simple topology of the attractor (hyperbolic type) and Lorenz oscillators with a relatively complex (two-sheeted) topology of the attractor. It was found that in the first case there is an on-off intermittency described by functions of a power-law type, and in the second case there is a hop-intermittency subject to exponential laws.

Initially, generalized synchronization in the context of continuous dynamic systems means establishing a connection between the state vectors of systems in the form of a functional relationship. Later it was proved that, in the general case, there is a connection in the form of a functional, i.e. there is a dependence on the history of the systems. The method for calculating local Lyapunov exponents is the most universal and allows one to correctly analyze the behavior of systems in both cases.

The behavior of systems is controlled not only by their own control parameters, but also by a coupling parameter that characterizes a kind of degree of synchronization. With an increase in the coupling parameter, at a certain critical value, a continuous (strong) generalized synchronization is established, characterized by a smooth functional relationship. Intermittent generalized synchronization occurs at values of the coupling parameter slightly less than the critical one and is characterized by a fractal functional relationship. The regime is called weak generalized synchronization and it is this regime that is considered in the work.

Assessment of the characteristics of intermittency would be impossible without the use of the method of identifying characteristic phases of the interacting systems’ behavior. Intermittent behavior is characterized by the fact that time intervals of synchronous, in the sense of generalized synchronization, oscillations (laminar phases) alternate with time intervals corresponding to asynchronous bursts (turbulent phases). At the same time, with an increase in the coupling parameter between systems, an increase in the mean duration of the laminar phases of behavior and a simultaneous decrease in the average duration of turbulent phases is observed. The nature of the dependence of the average duration on the coupling parameter depends on the type of intermittency.

The reported study was funded by a grant from the President- of the Russian Federation according to the research project N MD-18.2022.1.2.

То distinguish the characteristic phases of behavior, a certain threshold value of the investigated quantity is introduced, which depends on time. Laminar phases correspond to those periods of time at which the investigated value is below the threshold value, and turbulent phases occur otherwise. It should be noted that for the most accurate statistics, the ultrashort laminar phases of behavior should be ignored.

Generally, the auxiliary system approach is used to detect characteristic phases of behavior of coupled oscillators but since the method is applicable only in case of unidirectional coupling a development of more general-purpose method is required. In this work, a method for calculating the local Lyapunov exponents was proposed. These exponents are calculated in almost the same way as the usual ones, except that in this case the accumulation interval is finite, which makes it possible to analyze the time dynamics of systems.

The definition of the main characteristics of intermittency was carried out as follows. First, the critical value of the coupling parameter was estimated, which made it possible to estimate the operating range of the coupling parameter corresponding to the intermittency of interest to us. Then, time series were obtained for the local Lyapunov exponents. The study was conducted according to the time dependencies. After establishing the optimal parameters of the methods, such as the value of the accumulation interval, the minimum considered duration of the laminar phases, the threshold value, the main characteristics of intermittency were assessed.

It was found that the numerically obtained characteristics are in good agreement with the theoretical ones. This allows us to conclude that the method for calculating the local Lyapunov exponents makes it possible to analyze with a sufficiently high accuracy the intermittent behavior on the boundary of generalized synchronization with unidirectional and mutual coupling of systems, in the case of a simple and complex topology of attractors.

It should be noted that the question of the influence of the magnitude of the additive stationary noise, when added to the equations of one of the systems, remains open and will be considered in subsequent works.

The proposed method can also be used in the field of computational mathematics and problems based on data mining. For example, it can be used in neural networks to classify unknown signals.

Key words: intermittent generalized synchronization, local Lyapunov exponents, intermittency characteristics, Lorenz systems, Rossler oscillators.

References

1. Boccaletti S, Kurths J., Osipov G. et al. The synchronization of chaotic systems // Physics Report. 2002. V. 366, I. 1-2. P. 1-101.

2. Nikolai F. Rulkov, Mikhail M. Sushchik, Lev S. Tsimring, and Henry D. I. Abarbanel Generalized synchronization of chaos in directionally coupled chaotic systems// Phys. Rev. E. 1995. V. 51, N 2. P. 980.

3. Koronovskii A. A., Moskalenko O.I., Hramov A.E. Nearest neighbors, phase tubes, and generalized synchronization // Phys Rev E. 2011. V. 84, N 3. P. 037201.

4. Koronovskii A.A., Moskalenko O.I., Hramov A.E. О mekhanizmah, privodyashchih к ustanovleniyu rezhima obobshchennoj sinhronizacii // Jurnal tekhnicheskoj fiziki. 2006. V. 76, N 2. P. 1.

5. Rosenblum M.G., Pikovsky A.S., Kurts J. et al. Synchronization approach to analysis of biological systems // Fluct. Noise Lett. 2004. V. 4. N 1. P. L53.

6. Moskalenko O.I., Koronovskii A.A., Hramov A.E. Generalized synchronization of chaos for secure coupling: Remarkable stability to noise // Physics Letters A. 2010. V. 374. N 29. P. 2925-2931.

7. B.K. Meadows, Т.Н. Heath, J.D. Neff, E.A. Brown, D.W. Fogliatti, M. Gabbay, V. In, P. Hasler, S.P. Deweerth, W. L. Ditto. Nonlinear antenna technology // Proc. IEEE. 2002. V. 90. P. 882.

8. Hramov А. Е., Koronovskii A. A., Ponomarenko V. I., Prokhorov М. D. Detecting synchronization of self-sustained oscillators by external driving with varying frequency // Phys. Rev. E. 2006. V. 73. P. 026208.

9. Pyragas K. Weak and strong synchronization of chaos. // Phys. Rev. E. 1996. V. 54. P. 4508.

10. Moskalenko O.I., Koronovskij A. A., Hanadeev V. A. Peremezhayushcheesya povedenie na granice obobshchennoj sinhronizacii vo vzaimno svyazannyh sistemah so slozhnoj topologiej attraktora // ZHTF. 2019. V. 89, N 3. P. 338-341.

11. Koronovskii A. A., Moskalenko O.I., Pivovarov A. A., Khanadeev Vladislav A. Jump intermittency as a second type of transition to and from generalized synchronization // Phys. Rev. E. 2020. V. 102. P. 012205.

12. Abarbanel H.D.I., Rulkov N.F., Sushchik M. M. Generalized synchronization of chaos: The auxiliary system approach // Phys Rev E. 1996. V. 53. Iss. 5. P. 4528.

13. Kuznecov S.P. „Dinamicheskij haos“. M: FIZMATLIT, 2006.

14. Abarbanel H.D.I., Brown R., Kennel M.B. Variation of Lyapunov Exponents on a Strange Attractor // Journal of Nonlinear Science. 1991. V. 1. P. 175-199.

15. Alexander E. Hramov, Alexey A. Koronovskii, Maria K. Kurovskaya. Zero Lyapunov exponent in the vicinity of the saddle-node bifurcation point in the presence of noise // Phys. Rev. E. 2008. V. 78. P. 036212.

16. Lorenz E.N. Deterministic Nonperiodic Flow // J. Atmos. Sci. 1963. V. 20. 2. P. 130-141.

Bibliographic reference: Evstifeev E. V., Moskalenko О. I. Application of calculation of local Lyapunov exponents to analyze characteristics of intermittent generalized synchronization //journal “Problems of informatics”. 2022, № 2. P.5-16. DOI:10.24412/2073-0667-2022-2- 5-16. EDN: AMQZYA

I. M. Stubarev*^,**, O.K. Alsowa*

* Novosibirsk State Technical University, 630087, Novosibirsk, Russia

**LLC ,,FBConsult“, 630083, Novosibirsk, Russia

IMPROVING THE QUALITY OF RECOMMENDER SYSTEM ALGORITHM USING ASSOCIATIVE ANALYSIS METHODS

DOI: 10.24412/2073-0667-2022-2-17-26

EDN: ERYREM

FB Consult specializes in the development, implementation, and support of full-featured CRM solutions for banks, insurance, commercial and industrial, pharmaceutical companies. A customer relationship management system (CRM-system) is an information system designed to collect and process customer data. The data obtained from this system can be used in a recommendation system, helping managers to determine the needs of customers more accurately. Understanding the diverse insurance needs of the population and comparing them with related products offered by insurance companies makes insurance more effective and makes insurance companies more successful. Earlier, FB Consult developed an analytical platform that includes services for recommendations and time series analysis.

The objective of the study is to test the impact of the affinity analysis algorithm for the F2-scorc metric-evaluation of the recommendation algorithm based on collaborative filtering and cluster analysis of data.

The article describes the developed algorithm, which consists of 2 stages. At the training stage, which takes a long time, but is carried out only when there is a significant change in customer data, a recommendation model is created. First of all, customers are divided into clusters based on metadata using the EM algorithm, and a list of the most popular products is generated for each cluster. This is necessary to solve the cold start problem. In addition, customers are divided into clusters according to shopping lists in order to further speed up the collaborative filtering algorithm, since customers from another cluster will not be close to the customer for whom the recommendation is calculated, and the association rules are calculated using the Apriori algorithm. As a result, the model consists of a list of the most popular products for each cluster, a customer classifier by metadata, a customer classifier by shopping lists, customer lists divided into clusters by shopping and a list of found association rules. The recommendation phase is for each customer and therefore must be fast. If the customer does not have purchased products yet, then he is classified by his metadata and receives a recommendation from the list of popular products for his cluster. Otherwise, the customer is classified according to the shopping¬list, then, using collaborative filtering, the closest customers are found among the customers of his cluster and recommendations are formed on the basis of their purchases. In addition, if a customer has a cause for a previously found association rule in the purchased products, he is recommended its effect along with recommendations based on purchases of similar customers.

Testing and analysis of the effectiveness of the developed algorithm was carried out on the data of insurance company. The data includes 30 thousand customers and 21 types of products from 2010 to 2020. As a result of testing, it was revealed that the proportion of correctly found products for recommendation among the products that needed to be recommended increased, but also the proportion of recommended products that were clearly not necessary for recommendations (were not removed from the customer during testing) increased. Should take into account that these could be products that should be recommended to customers, but that they have not purchased yet.

In this article, a study was carried out of the impact of affinity analysis on the recommendation algorithm. The main result of this work is to improve the F2-score metric in comparison with the basic implementation of the recommendation algorithm. With the help of affinity analysis, you can generate not only positive, but also negative association rules. In future work, it is planned to investigate the use of such rules in order to reduce the likelihood of recommending products that are contained in the effect of these rules, thereby increasing the accuracy of the system.

Key words: recommender system, collaborative filtering, cluster analysis,affinity analysis, Apriori algorithm, Data mining.

References

1. Stubarev I. M., Belov A. I., Alsova О. K. Development of the analytical platform for CRM-system // Actual problems of electronic instrument engineering (APEIE-2018). Novosibirsk: NSTU, 2018. P. 546-551.

2. Stubarev I.M., Alsova O.K. Rekomendatel’nyy servis na baze CRM sistemy: Svidetel’stvo о gosudarstvennoy registratsii programmy dlya EVM N 2019617387. 2019.

3. Soh H., Sanner S., White M., Jamieson G. Deep sequential recommendation for personalized adaptive user interfaces // IUI ACM. 2017. P. 589-593.

4. Yu W., Не X., Qin Z., Chen X., Zhang H., Xiong L. Aesthetic-based clothing recommendation // Proceedings of the 2018 world wide web conference. 2018. P. 649-658.

5. Liang D., Krishnan R. G., Hofman M.D., Jebara T. Variational autoencoders for collaborative filtering // Proceedings of the 2018 world wide web conference. 2018. P. 689-698.

6. Lin W., Alvarez S. A., Ruiz C. Efficient adaptive-support association rule mining for recommender systems // Data Min. Knowl. Discov. 2002. P. 83-105.

7. Lin W., Alvarez S.A., Ruiz C. Collaborative recommendation via adaptive association rule mining // Data Min. Knowl. Discov. 2000. P. 83-105.

8. Agrawal R., Srikant R. Fast Discovery of Association Rules // Proc, of the 20th International Conference on VLDB. 1994.

9. Agrawal R., Imielinski T., Swami A. Mining Associations between Sets of Items in Massive Databases // Proc, of the 1993 ACM-SIGMOD Int’l Conf, on Management of Data,. 1993. P. 207-216.

10. Han J., Kamber M. Data mining: concepts and techniques // Burlington: Morgan Kaufmann Publishers. 2012.

11. Bagui S., Dhar P. C. Positive and negative association rule mining in Hadoop’s MapReduce environment // Journal of Big Data. 2019. T. 6. N 1. P. 1-16.

12. Sasaki Y. The truth of the F-measure // Teach Tutor Mater. 2007. P. 1-5.

Bibliographic reference: Stubarev I. M.. Alsowa О. K. Improving the quality of recommender system algorithm using associative analysis methods //journal “Problems of informatics”. 2022, № 2. P.17-26. DOI:10.24412/2073-0667-2022-2-17-26. EDN: ERYREM

V. Balakin*,**, F. Emanov*’***, D. Berkaev*

*Budker Institute of Nuclear Physics of Siberian Branch Russian Academy of Sciences (BINP SB RAS)

630090, Novosibirsk, Russia

**Novosibirsk State Technical University, 630073, Novosibirsk, Russia

***Novosibirsk State University, 630090, Novosibirsk, Russia

BEAM PARAMETERS MONITOR AND CONTROL SOFTWARE TOOLS FOR VEPP-5 INJECTION COMPLEX DAMPING RING

DOI: 10.24412/2073-0667-2022-2-27-43

EDN: EATUQJ

Description of beam parameters control and operation software tools for VEPP-5 injection complex damping ring is given in this article.

Software consists of two key parts („orbit“ and ,,knob“), each of them includes three types of programs: daemon, service and user GUI-applications, the latter intended for injection complex operational staff.

,,Knob“ is a combination of accelerator control system elements, which makes isolated change of only one chooscd parameter (beam betatron tunes, for instance). Discussed in the article are features of this part: creation of ,,knobs“ from user application window or by sending a request to the control system command channel directly, keeping the table of already created ,,knobs“, editing it, and using ,,knobs“ for injection complex operation.

,,Orbit“ includes damping ring beam position monitor (BPM) data processing, displaying of betatron tunes and turn-by-turn beam position measurements from chooscd BPM and beam positions inside vacuum chamber along damping ring perimeter, collected from 16 BPM installed on accelerator. Moreover, this software part is intended for damping ring response matrix measurements and creating of the„knobs“ which allows operational staff to conduct assigned changes of beam parameters using this matrix.

Key words: software tools, beam parameters control, response matrix, knob.

The reported study was funded by RFBR, project number 20-32-90082.

References

1. Astrclina К. V. et al. Production of intense positron beams at the VEPP-5 injection complex / / JETP, 2008, Vol. 106, P. 94-114.

2. Maltseva Yu. et al. VEPP-5 Injection Complex: New Possibilities for BINP Electron-Positron Colliders // in Proc. IPACT8, Vancouver, Canada, Paper МОРМК0П, DOI: 10.18429/JACoW- IPAC2018-MOPMK011.

3. Zhuravlev A. N. et al. Status of VEPP-4 accelerator complex // Pepan Letters. 2020, Vol. 17, N 7 232, P. 876-893.

4. Shatunov Р. et al. High luminosity at VEPP-2000 collider with new injector //in Proc. IPACT7, Copenhagen, Denmark, Paper WEPIK029, DOI: 10.18429/JACoW-IPAC2017- WEPIK029.

5. Shen G. et. al. Prototype of beam commissioning environment and its application for NSLS-II // in Proc. IPAC10, Kyoto, Japan, Paper WEPEB026, DOI: 10.18429/JACoW-IPAC2010- WEPEB026.

6. Romanov A. L. Nastroika orbitv i elektronno-opticheskoi strukturv nakopitelva VEPP-2000 metodom matric otklikov / dissertaciya na soiskanie uchenoj stepeni kandidata fiziko-matematicheskih nauk, g. Novosibirsk, 2011.

7. SHatunov P. Yu. Magnitnaya sistema nakopitelya s elektron-pozitronnymi vstrechnymi puchkami VEPP-2000 / dissertaciya na soiskanie uchenoj stepeni kandidata fiziko-matematicheskih nauk, g. Novosibirsk, 2011.

8. Rogovsky Yu. A., Bekhtenev E. A. Pickup beam measurement system at the VEPP-2000 collider // in Proc. DIPAC2011, Hamburg, Germany, Paper MOPD68, DOI: 10.18429/JACoW-DIPAC2011- MOPD68.

9. Jacquet D. et al. LSA-the high level application software of the LHC and its performance during the first 3 years of operation //in Proc. ICALEPCS2013, San Francisco, CA, USA, Paper THPPC058, DOI: 10.18429/JACoW-ICALEPCS2013- THPPC058.

10. Miller G. J. et al. Toolchain for online modeling of the LHC //in Proc. ICALEPCS2011, Grenoble, France, Paper MOPMN018, DOI: 10.18129 /JACoW-ICALEPCS2011- MOPMN018.

11. Bolkhovityanov D., Emanov F. A. VEPP-5 injection complex control system base software upgrade // in Proc. RuPAC2018, Protvino, Russia, Paper THPSC07, DOL 10.18429/JaCOW- RUPAC2018-THPSC07.

12. Bolkhovityanov D., Cheblakov P., Emanov F. A. CXv4, a modular control system // in Proc. ICALEPCS2015, Melbourne, Australia, Paper WEPGF093, DOI: 10.18429/JACoW-ICALEPCS2015- WEPGF093.

13. Safranek J. Experimental determination of storage ring optics using orbit response measurements // Nucl. Instrum. Methods. 1997. A. 388, P. 27.

Bibliographic reference: Balakin V., Emanov F., Berkaev D. Beam parameters monitor and control software tools for VEPP-5 injection complex damping ring //journal “Problems of informatics”. 2022, № 2. P.27-43. DOI:10.24412/2073-0667-2022-2- 27-43. EDN: EATUQJ

Yu.G. Medvedev

Institute of Computational Mathematics and Mathematical Geophysics SB RAS, 630090, Novosibirsk, Russia

SIMULATION THE PASSAGE OF A LAMINAR FLOW THROUGH A LOCAL CONSTRICTION IN A PIPE

DOI: 10.24412/2073-0667-2022-2-44-52

EDN: FWVFHD

This paper presents a study using discrete simulation methods for problems of spatial dynamics. A cellular automaton model of the gas flow, which was used in the work, is a discrete simulation model. Such methods make it possible to obtain relatively simple software implementations on modern supercomputers. The aim of the work is to check the possibility of using the studied model under conditions of flow in a straight pipe at a constant temperature in a sub-critical mode; under these conditions, the critical Reynolds number is several thousand. The simulation object is a gas flow passing in the space between parallel flat walls. Such a flow corresponds to a two-dimensional case, since the characteristics of a three-dimensional flow between two parallel planes and in a pipe with a circular cross section, which is not considered here, differ only in coefficients. The narrowing or variable distance between the planes in the three-dimensional case corresponds to the variable diameter of the two-dimensional pipe. The objective of the paper is to simulate the flow with the specified boundary conditions using a discrete cellular automaton model and compare it with the known results obtained using continuous models. Such a comparison is necessary in the framework of the study of the possibility of using a discrete model. The desired dependencies are the distribution of velocity and pressure along the direction of flow for various sizes of the constriction and various pressure gradients at the ends of the pipe.

The model cover two-dimensional simulated space by hexagonal cells arranged in a regular pattern; each cell has six neighbors. The state of the cell is a vector of six integers denoting the number of discrete model particles with unit mass and unit velocity directed towards one of the six neighboring cells. The cellular automaton operates in synchronous mode using an iterative transition function. An iteration consists of two steps: collision and propagation. During a collision, the particle velocity vectors in each cell are changed, regardless of the states of other cells. During a propagation, each particle moves to one of the neighboring cells in the direction of its velocity vector. The simulation result is the velocity field and the pressure field obtained after the required number of iterations by the averaging method. The averaging neighborhood at each point constituting the fields is the set of cells whose centers are separated from this point no further than some averaging radius. The flow velocity at a point is the average velocity of the particles located in the cells of the averaging neighborhood. The gas pressure at a point is proportional to the concentration of particles located in the cells of the averaging neighborhood centered at this point.

A software implementation of the model is made with a set of three modules: a boundary conditions constructor, a simulator, and a post-processor. The constructor in interactive mode allows you to create a cellular array with the required values of the states of each cell and place it in a file that is used by the simulator. The simulator performs a given number of iterations over the original cellular array. It is a CLI parallel program with the ability to run on a computing cluster. Parallelism is implemented by the method of domain decomposition of a cellular array using the MPI library. The post-processor averages the result obtained by the simulator and visualizes the averaged values in the form of velocity and pressure fields built either on the entire cellular array or on its selected area.

Computer experiments were carried out with a cellular array of 5000 by 500 cells. The lumen of the constriction of the pipe varied from 100 to 400 cells. The inlet and outlet pressures also varied. To establish a stationary flow regime, 100 thousand iterations were carried out in each of the experiments. After that, the post-processor was launched. To calculate the average particle velocity, the averaging radius was chosen to be equal to twenty cells. To calculate the average concentration of particles, the averaging radius was chosen to be equal to five cells. The velocity and pressure fields of the gas flow in a two-dimensional pipe are obtained. Velocity and pressure distributions along the direction of flow are plotted for various sizes of constriction and various pressure gradients at the ends of the pipe. In the constricted part of the pipe, the flow velocity was maximum in each of the experiments. It can be seen from a comparison of the experiments that the flow velocity has an inverse dependence on the diameter of the constricted part of the pipe, which corresponds to the existing view on the process’ physics. So, the possibility of using the studied model under conditions of flow in a straight pipe at a constant temperature in a sub-critical mode with a critical Reynolds number of the order of several thousand was shown. The simulation results are consistent with the known data. This allows us to conclude that the cellular automaton model of the gas flow adequately simulates the laminar flow in the pipe.

Key words: simulation modeling, cellular automata, gas flow.

References

1. Schiff J.L. Cellular Automata: A Discrete View of the World. New Jersey: John Wiley & Sons Inc., 2008.

2. Chopard B. Cellular Automata Modeling of Physical Systems // R. Meyer ed. Computational Complexity. New York: Springer, 2012. P. 407-433.

3. Bandman O.L. Parallel’nava realizatsiva kletochno-avtomatnivkh algoritmov modelirovaniva prostranstvennoy dinamiki // Sib. zhurn. vychisl. matematiki / RAN. Sib. otd-nie. Novosibirsk, 2007. V. 10, N 4. P. 335-348. (in Russian)

4. Medvedev Yu. G. Mnogochastichnaya kletochno-avtomatnaya model’ potoka zhidkosti FHP-MP // Vestnik Tomskogo gosudarstvennogo universiteta, seriya „Upravleniye, vychislitel’naya tekhnika i informatika“N 1 (6). 2009. P. 33-40. (in Russian)

5. Landau L.D., Lifshitz E.M. Teoreticheskaya fisika. Tom VI. Gidrodinamika. 5-e izd. M.: Fizmatlit, 2001. (in Russian)

6. Bandman O.L. Kletochno-avtomatniye modeli estestvennykh protsessov i ikh realizatsiva na sovremennykh komp’yuterakh // PDM, 2017, N 35. P. 102-121. (in Russian)

7. Gorodnichev M., Medvedev Yu. A Web-Based Platform for Interactive Parameter Study of Large- Scale Lattice Gas Automata // PaCT-2019 proceedings, LNCS 11657, Springer, 2019, P. 321-333.

Bibliographic reference: Medvedev Yu. G. Simulation the passage of a laminar flow through a local constriction in a pipe //journal “Problems of informatics”. 2022, № 2. P.44-52. DOI:10.24412/2073-0667-2022-2- 44-52. EDN: FWVFHD

A. Yu. Filatov, V.V. Mikheev

Novosibirsk State University, 630090, Novosibirsk, Russia

Huawei Novosibirsk Research Center, 630090, Novosibirsk, Russia

INCREMENTAL APPROACHES TO THREAD-LOCAL GARBAGE COLLECTION

DOI: 10.24412/2073-0667-2022-2-53-72

EDN: GLGOOM

Recent advances in computational technology gave rise to highly multiprocessor systems that are used in different domains. Modern managed programming languages such as Java, Scala and Kotlin are expected to use all of the available computational resources to provide competitive performance in production environments. These requirements pose a new challenges to developers of managed runtimes which require scalable and efficient automatic memory management. Wide adoption of cache coherent non-uniform memory access (ccNUMA) systems drew attention to garbage collection techniques that encourage data locality and minimize number of inter-node memory accesses.

Thread-local garbage collection is a promising research direction that allows to design scalabalc, throughput-oriented and NUMA-aware algorithms for automatic memory management. Memory manager divide heap objects into independent groups: local objects that are biased to the thread allocated them and shared (or global) objects which are accessible by more than one thread. Any operation with thread-local memory - either allocation of a new object, tracing of reachable objects or reclamation of unused memory - may be performed in an independent manner without any synchronization between different threads. Improved locality of data make thread-local memory manager an attractive alternative to conventional GC algorithms especially for software targeting ccNUMA hardware.

One of the main advantages of the proposed scheme is that memory manager may use any garbage collection approach to manage thread-local heaps. In particular, any existing well-studied algorithm for uniprocessor systems may by adopted to thread-local setting. However, single-threaded tracing approaches share a common drawback - marking phase may take a significant time to complete leading to low responce time and reduced throughput of an application. There are plenty of incremental approaches to classic garbage collector designes but applicability of them to thread-local memory management (which itself is an incremental GC design) is an open research question.

This research paper focuses on the approach that treats local and global objects as generations and uses special „globalization11 operation to evacuate an object from local heap into shared memory. Conventional generational scheme is known to introduce memory drag - unreachable objects from old generation remain in heap until collection of this generation is triggered. Problem of such „floating garbage“ introduces more overheads for thread-local garbage collector because it cannot locally reclaim shared objects. Performance overheads of preliminary evacuation require thorough analysis before being- applied in production environments.

Main contributions of this work are the following:

— Evacuation procedure is formalized in terms of an abstract object graph concurrently modified by intercommunicating agents and correctness of evacuating transformation is proven. Upper bound for potential number of inter-agent messages that depend on local component size is found.

— Two non-trivial evacuation strategies are studied using large benchmarking suite. First strategy uses age of objects to determine the long-living ones and evacuate them into shared heap. Second strategy is based on the idea that stack frame depth is proportional to the overhead incurred by repeated thread-local marking of references stored in memory of this frame.

Described incremental thread-local memory manager was used to run well-known DaCapo benchmark suite written in Java, machine-learning application written in Scala and several tests from open-source benchmarking repository aimed at performance evaluation of Apache Spark framework for distributed large-scale data processing. Performance measurements indicate that chosing optimal parameters to the studied incremental algorithms may tremendously increase throughput of some applications. At the same time, there are applications that are very sensitive to the configuration of a thread-local memory manager and slight modification of a parameter may lead to significant performance drop. Development of auto-tuning techniques for incremental thread-local garbage collection remains an open problem.

Key words: incremental garbage collection, JVM, thread local heaps, NUMA.

References

1. Jones R., Hosking A., Moss E. The Garbage Collection Handbook: The Art of Automatic Memory Management. Chapman & Hall/CRC, 1st edition. 2011.

2. Doligez D., Leroy X. A Concurrent, Generational Garbage Collector for a Multithreaded Implementation of ML. In Proceedings of the 20th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’93. Association for Computing Machinery. 1993. New York, USA. P. 113-123.

3. Meyer B. Object-Oriented Software Construction (2nd Ed.). PrenticeHall, Inc., USA, 1997.

4. Tamar Domani Gal, Goldshtein Gal, Kolodner Elliot K., Lewis Ethan, Petrank Erez, Sheinwald Dafna. Thread-Local Heaps for Java. In SIGPLAN Not, ACM Press, 2002. P. 76-87.

5. Marlow S., Peyton Jones S. Multicore garbage collection with local heaps. In Proceedings of the International Symposium on Memory Management, ISMM ’ll, New York, NY, USA, 2011. Association for Computing Machinery. P. 21-32.

6. Mole M., Jones R., Kalibera T. A study of sharing definitions in thread-local heaps. In ICOOOLPS. 2012.

7. Sivaramakrishnan КС, Dolan S., White L., Jaffer S., Kelly T., Sahoo A., Parimala S., Dhiman A., Madhavapeddy A. Retrofitting parallelism onto OCAML. Proc. ACM Program. Lang., 4(ICFP), August 2020.

8. Filatov A., Mikheev V. Quantitative evaluation of thread-local garbage collection efficiency for JAVA. Programming and Computer Software, 45:111, 01 2019.

9. Wilson P. R. Uniprocessor garbage collection techniques. In Proceedings of the International Workshop on Memory Management, IWMM ’92, P. 1-42, London, UK, UK, 1992. Springer-Verlag.

10. Lieberman H., Hewitt C. A real-time garbage collector based on the lifetimes of objects. Commun. ACM, 26 (6): 419-429, June 1983.

11. Anderson T. A. Optimizations in a private nursery-based garbage collector. In Proceedings of the 2010 International Symposium on Memory Management, ISMM TO, P. 21-30, New York, NY, USA, 2010. Association for Computing Machinery.

12. Filatov A., Mikheev V. Evaluation of thread-local garbage collection. In 2020 Ivannikov Memorial Workshop (IVMEM), P. 15-21, 2020.

13. Apache Hadoop’s official website, 2020 [Electron, res.]: https://hadoop.apache.org/.

14. Apache Spark™official website. [Electron, res.]: https://spark.apache.org/, 2020.

15. Gurevich Yu. Specification and validation methods, chapter Evolving Algebras 1993: Lipari Guide, P. 9-36. Oxford University Press, Inc., New York, NY, USA, 1995.

16. Zamulin A. An ASM-based formal model of a Java program. Programming and Computer Software, 29 (3): P. 130-139, 2003.

17. Blackburn S. M., Garner R., Hoffmann C., Khang A. M., McKinley K. S., Bentzur R., Diwan A., Feinberg D., Frampton D., Guyer S. Z., Hirzel M., Hosking A., Jump M., Lee H., Moss J.E.B., Phansalkar A., Stefanovic D., VanDrunen T., Daniel von Dincklage, Wiedemann B. The DaXapo benchmarks: Java benchmarking development and analysis. In Proceedings of the 21st Annual ACM SIGPLAN Conference on Object- Oriented Programming Systems, Languages, and Applications, OOPSLA ’06, P. 169-190, New York, NY, USA, 2006. Association for Computing Machinery.

18. Drepper U. What every programmer should know about memory. 2007.

19. Mccallum A., Schultz K., Singh S. Factorie: Probabilistic programming via imperatively defined factor graphs. P. 1249-1257, 01 2009.

20. Biei D., Ng A., Jordan M. Latent Dirichlet allocation. Journal of Machine Learning Research, 2003. V. 3. P. 993-1022.

21. Sewe A., Mezini M., Sarimbekov A., Binder W. Da capo con Scala: design and analysis of a Scala benchmark suite for the Java virtual machine. In OOPSLA ’ll Proceedings of the 2011 ACM international conference on Object oriented programming systems languages and applications, P. 657¬676. ACM, 2011.

22. HiBench source repository. [Electron. Res.]: https://github.com/Intel-bigdata/HiBench, 2020.

Bibliographic reference: Filatov A. Yu., Mikheev V. V. Incremental approaches to thread-local garbage collection //journal “Problems of informatics”. 2022, № 2. P.53-72. DOI:10.24412/2073-0667-2022-2-53-72. EDN: GLGOOM

Main menu

You are here

2022 № 2(55)

Languages