ИССЛЕДОВАНИЕ FORK-JOIN СИСТЕМЫ С МАРКОВСКИМ ВХОДНЫМ ПОТОКОМ И РАСПРЕДЕЛЕНИЕМ ВРЕМЕНИ ОБСЛУЖИВАНИЯ ФАЗОВОГО ТИПА

В настоящей работе исследуется fork-join система массового обслуживания с коррелированным марковским входным потоком. Каждая из поступающих в систему заявок разбивается на K запросов, которые попадают для обслуживания на K обслуживающих подсистем. Каждая из подсистем состоит из одного обслуживающего прибора и буфера. Время обслуживания на приборах имеет фазовое распределение. Для частного случая K = 2 получено условие стационарного режима, представлены алгоритмы для расчета стационарного распределения и стационарных показателей производительности системы. Для исследования характеристик производительности fork-join системы в общем случае K > 2 предложен подход, базирующийся на комбинации методов машинного обучения и имитационного моделирования. Приведены результаты численных примеров.

Cписок литературы

1.           Vianna Е., Comarela G., Pontes Т., Almeida J., Almeida V., Wilkinson К., Kuno H., Dayal U. Analytical performance models for mapreduce workloads // International Journal of Parallel Programming, 2013, 41(4/495-525.

2.           Rizk A., Poloczek F., Ciucu F. Stochastic bounds in Fork-Join queueing systems under full and partial mapping. Queueing Systems, 2016. 83(3-4/261-291.

3.           Nguyen M., Alesawi S., Li N., Che H., Jiang H. ForkTail: A black-box fork-join tail latency prediction model for user-facing datacenter workloads // HPDC 2018 — Proceedings of the 2018 International Symposium on High-Performance Parallel and Distributed Computing, 2018. P. 206¬217.

4.           Enganti P., Rosenkrantz T., Sun L., Wang Z., Che H., Jiang H. Forkmv: Mean-and-variance estimation of fork-join queuing networks for datacenter applications // 2022 IEEE International Conference on Networking, Architecture and Storage (NAS), 2022. P. 1-8.

5.           Flatto L., Hahn S. Two Parallel Queues Created By Arrivals With Two Demands I // SIAM Journal on Applied Mathematics, 1984. 44(5): 1041-1053.

6.           Nelson R. D., Tantawi A. N. Approximate analysis of fork/join synchronization in parallel queues // IEEE Trans. Computers, 1988. 37:739-743.

7.           Kim C., Agrawala A. K. Analysis of the Fork-Join Queue // IEEE Transactions on Computers, 1989. 38 (2): 250—255.

8.           Vann S., Makowski A. M. Interpolation approximations for symmetric Fork-Join queues. Performance Evaluation, 1994. 20(l-3):245-265.

9.           Lui J. C. s., Muntz R., Towsley D. Computing performance bounds for fork-join queueing models. 08 2001.

10.         Balsamo S., Donatiello L., Van Dijk N. M. Bound performance models of heterogeneous parallel processing systems // IEEE Transactions on Parallel and Distributed Systems, 1998. 9(10):1041 1056.

11.         Lebrecht A. S., Knottenbelt W. J. Response time approximations in fork-join queues. 2007.

12.         Thomasian A. Analysis of fork/join and related queueing systems // ACM Computing Surveys, 2014, 47(2).

13.         Jiang L., Giachetti R. E. A queueing network model to analyze the impact of parallelization of care on patient cycle time // Health Care Management Science, 2008. 11(3/248-261.

14.         Armony M., Israelit S., Mandelbaum A., Marmor Y. N., Tseytlin Y., Yom-Tov G. B. On patient flow in hospitals: A data-based queueing-science perspective // Stochastic Systems, 2015. 5(1) :146 194.

15.         Narahari Y., Sundarrajan P. Performability analysis of fork-join queueing systems // Journal of the Operational Research Society, 1995. 46(10):1237-1249.

16.         Gallien J., Wein L. M. A simple and effective component procurement policy for stochastic assembly systems // Queueing Systems, 2001. 38(2/221-248.

17.         Kemper B., Mandjes M. Mean sojourn times in two-queue fork-join systems: Bounds and approximations // OR Spectrum, 2012. 34(3/723-742.

18.         Schol D., Vlasiou M., Zwart B. Large Fork-Join Queues with Nearly Deterministic Arrival and Service Times // Mathematics of Operations Research, 2022. 47(2):1335-1364.

19.         Qiu Z., Perez J. F., Harrison P. G. Beyond the mean in fork-join queues: Efficient approximation for response-time tails // Performance Evaluation, 2015. 91:99-116.

20.         Klimenok V. I. Performance characteristics of the fork-join queuing system // Informatics, 2023. 20(3/50-60.

21.         Marin A., Rossi S. Power control in saturated fork-join queueing systems // Performance Evaluation, 2017. 116:101-118.

22.         Lee K., Shah N.B., Huang L., Ramchandran K. The MDS queue: Analysing the latency performance of erasure codes // IEEE Transactions on Information Theory, 2017. 63(5/2822-2842.

23.         Wang W., Harchol-Balter М., Jiang Н., Scheller-Wolf A., Srikant R. Delay asymptotics and bounds for multi-task parallel jobs // SIGMETRICS Perform. Eval. Rev., jan 2019, 46(3):2-7.

24.         Nguyen M., Alesawi S., Li N., Che H., Jiang H. A black-box fork-join latency prediction model for data-intensive applications // IEEE Transactions on Parallel and Distributed Systems, 2020. 31(9):1983 2000.

25.         Vishnevsky V., Gorbunova A. V. Application of Machine Learning Methods to Solving Problems of Queuing Theory // Communications in Computer and Information Science, 2022. 1605 CCIS:304- 316.

26.         Gorbunova A. V., Vishnevsky V. M. Estimating the response time of a cloud computing system with the help of neural networks / / Advances in Systems Science and Applications, 2020. 20(3): 105 112.

27.         Vishnevsky V., Klimenok V., Sokolov A., Larionov A. Performance Evaluation of the Priority Multi-Server System MMAP/PH/M/N Using Machine Learning Methods // Mathematics, 2021. 9(24).

28.         Efrosinin D., Vishnevsky V., Stepanova N. Optimal Scheduling in General Multi-Queue System by Combining Simulation and Neural Network Techniques // Sensors, 2023. 23(12).

29.         Dieleman N. A., Berkhout J., Heidergott B. A neural network approach to performance analysis of tandem lines: The value of analytical knowledge // Computers and Operations Research, 2023. 152:106124.

30.         Lucantoni D. M. New results on the single server queue with a batch markovian arrival process // Communications in Statistics. Stochastic Models, 1991. 7(1):1—46.

31.         Dudin A. N., Klimenok V. L, Vishnevsky V. M. The theory of queuing systems with correlated flows. The Theory of Queuing Systems with Correlated Flows, 2019. P. 1-410.

32.         Neuts M. F. Matrix-geometric solutions in stochastic models. The Johns Hopkins University Press, 1981, Baltimore.

33.         Ozawa T. Sojourn time distributions in the queue defined by a general QBD process // Queueing Systems, 2006. 53(4):203-211.

34.         Horvath G. Efficient analysis of the queue length moments of the MMAP/MAP/1 preemptive priority queue. Performance Evaluation, 2012. 69(12):684 700.

35.         Vishnevsky V., Larionov A., Ivanov R., Semenova O. Estimation of IEEE 802.11 DCF access performance in wireless networks with linear topology using ph service time approximations and map input // 2017 IEEE 11th International Conference on Application of Information and Communication Technologies (AICT), 2017. P. 1-5.

36.         Gordon A.D., Breiman L., Friedman J.H., Olshen R. A., Stone C.J. Classification and Regression Trees // Biometrics, sep 1984. 40(3):874.

37.         Friedman J.H. Stochastic gradient boosting // Computational Statistics and Data Analysis, feb 2002.38 (4):367-378.

38.         Kingma D. P., Ba J. Adam: A method for stochastic optimization // International Conference on Learning Representations, dec.