Исследование fork-join системы с марковским входным потоком и распределением времени обслуживания фазового типа

Исследование fork-join системы с марковским входным потоком и распределением времени обслуживания фазового типа

Автор: Вишневский В.М., Клименок В.И., Соколов А.М., Ларионов А.А.

Журнал: Проблемы информатики @problem-info

Рубрика: Теоретическая и системная информатика

Статья в выпуске: 4 (61), 2023 года.

Бесплатный доступ

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

Еще

Fork-join система массового обслуживания, марковский входной поток, фазовое распределение времени обслуживания, стационарные характеристики производительности, машинное обучение

Короткий адрес: https://sciup.org/143182819

IDR: 143182819   |   DOI: 10.24412/2073-0667-2023-4-29-56

Список литературы Исследование fork-join системы с марковским входным потоком и распределением времени обслуживания фазового типа

  • Vianna Е., Comarela G., Pontes Т., Almeida J., Almeida V., Wilkinson К., Kuno H., Daval U. Analytical performance models for mapreduce workloads // International Journal of Parallel Programming, 2013, 41(4):495-525.
  • 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.
  • 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. 206217.
  • Enganti P., Rosenkrantz Т., 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.
  • Flatto L., Hahn S. Two Parallel Queues Created By Arrivals WTith Two Demands I // SIAM Journal on Applied Mathematics, 1984. 44(5):1041-1053.
  • Nelson R. D., Tantawi A.N. Approximate analysis of fork/join synchronization in parallel queues // IEEE Trans. Computers, 1988. 37:739-743.
  • Kim C., Agrawala A. K. Analysis of the Fork-Join Queue // IEEE Transactions on Computers, 1989. 38(2):250-255.
  • Varm S., Makowski A.M. Interpolation approximations for symmetric Fork-Join queues. Performance Evaluation, 1994. 20(l-3):245-265.
  • Lui J. C. s., Muntz R., Towslev D. Computing performance bounds for fork-join queueing models. 08 2001.
  • 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.
  • Lebrecht A.S., Knottenbelt W. J. Response time approximations in fork-join queues. 2007.
  • Thomasian A. Analysis of fork/join and related queueing systems // ACM Computing Surveys, 2014, 47(2).
  • 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.
  • Armonv M.. Israelii S., Mandelbaum A., Marmor Y. N., Tsevtlin Y., Yom-Tov G. B. On patient flow in hospitals: A data-based queueing-science perspective // Stochastic Systems, 2015. 5(1):146-194.
  • Narahari Y., Sundarrajan P. Performabilitv analysis of fork-join queueing systems // Journal of the Operational Research Society, 1995. 46(10):1237-1249.
  • Gallien J., Wein L.M. A simple and effective component procurement policy for stochastic assembly systems // Queueing Systems, 2001. 38(2):221-248.
  • Kemper В., Mandjes M. Mean sojourn times in two-queue fork-join systems: Bounds and approximations // OR Spectrum, 2012. 34(3):723-742.
  • 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.
  • 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.
  • Klimenok V. I. Performance characteristics of the fork-join queuing system // Informatics, 2023. 20(3):50-60.
  • Marin A., Rossi S. Power control in saturated fork-join queueing systems // Performance Evaluation, 2017. 116:101-118.
  • 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.
  • Wang W., Harchol-Baltcr M., .Jiang H., Schcllcr-Wolf A., Srikant R. Delay asymptoties and bounds for multi-task parallel jobs /7 SIGMETRICS Perform. Eval. Rev., jan 2019, 46(3):2 7.
  • Nguyen M., Alesawi S., Li N., Che H., .Jiang H. A black-box fork-join latency prediction model for data-intensive applications /7 IEEE Transactions on Parallel and Distributed Systems, 2020. 31(9):1983 2000.
  • Vishnevsky V., Gorbunova A. V. Application of Machine Learning Methods to Solving Problems of Queuing Theory /7 Communications in Computer and Information Science, 2022. 1605 CCIS:304 316.
  • Gorbunova A. V., Vishnevsky V. M. Estimating the response time of a cloud computing system with the help of neural networks /7 Advances in Systems Science and Applications, 2020. 20(3) :105 112.
  • Vishnevsky V., Klimenok V., Sokolov A., Larionov A. Performance Evaluation of the Priority Multi-Server System .\1.\1AP I'll M X Using Machine Learning Methods /7 Mathematics, 2021. 9(24).
  • Efrosinin D., Vishnevsky V., Stepanova N. Optimal Scheduling in General Multi-Queue System by Combining Simulation and Neural Network Techniques /7 Sensors, 2023. 23(12).
  • Dieleman N. A., Bcrkhout -J., Heidergott B. A neural network approach to performance analysis of tandem lines: The value of analytical knowledge /7 Computers and Operations Research, 2023. 152:106124.
  • Lueantoni D. M. New results on the single server queue with a batch markovian arrival process /7 Communications in Statistics. Stochastic Models, 1991. 7(1):1 46.
  • Dudin A.N., Klimenok V. I., Vishnevsky V. M. The theory of queuing systems with correlated flows. The Theory of Queuing Systems with Correlated Flows, 2019. P. 1 410.
  • Neuts M.F. Matrix-geometric solutions in stochastic models. The .Johns Hopkins University Press, 1981, Baltimore.
  • Ozawa T. Sojourn time distributions in the queue defined by a general QBD process /7 Queueing Systems, 2006. 53(4):203 211.
  • Horvath G. Efficient analysis of the queue length moments of the MMAP/MAP/1 preemptive priority queue. Performance Evaluation, 2012. 69(12):684 700.
  • 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 /7 2017 IEEE 11th International Conference on Application of Information and Communication Technologies (AICT), 2017. P. 1 5.
  • Gordon A.D., Breiman L., Friedman .J.H., Olshen R. A., Stone C.J. Classification and Regression Trees /7 Biometrics, sep 1984. 40(3):874.
  • Friedman .J.H. Stochastic gradient boosting /7 Computational Statistics and Data Analysis, feb 2002. 38(4):367 378.
  • Kingma D.P., Ba .J. Adam: A method for stochastic optimization /7 International Conference on Learning Representations, dec.
Еще
Статья научная
QR-код для установки приложения SciUp Наведите камеру и скачайте бесплатное приложение SciUp