Informatics and Applications

2023, Volume 17, Issue 2, pp 62-70

A QUEUEING SYSTEM FOR PERFORMANCE EVALUATION OF A MARKOVIAN SUPERCOMPUTER MODEL

R. V. Razumchik
A. S. Rumyantsev
R. M. Garimella

Abstract

Consideration is given to the well-known supercomputer model in the form of a Markovian nonwork- conserving two-server queueing system with unlimited queue capacity, in which customers are served by a random number of servers simultaneously. For the first time, it is shown that its basic probabilistic characteristics can be calculated from an unrelated single-server queueing system with infinite capacity, work conserving scheduling, and forced customers' losses. Based on the known matrix-analytic techniques for quasi-birth-and-death processes, it is shown that in certain special cases, the transient queue-size distribution can be found (in terms of Laplace transform) using the Level Crossing Information method and has a matrix-geometric form. Numerical examples which illustrate some properties of the established connection between the two queueing systems are provided.

[+] References (29)

Morozov, E. V., and A. S. Rumyantsev. 2011. Modeli mnogoservernykh sistem dlya analiza vychislitel'nogo klastera [Multi-server models to analyze high performance cluster], Transactions of the Karelian Research Centre of the Russian Academy of Sciences 5:75-85.
Rumyantsev, A., and E. Morozov. 2017. Stability criterion of a multiserver model with simultaneous service. Ann. Oper. Res. 252:29-39. doi: 10.1007/s10479-015-1917-2.
Hong, Y., and W Wang. 2022. Sharp waiting-time bounds for multiserver jobs. 23rd Symposium (International) on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing Proceedings. ACM. 161-170. doi: 10.1145/3492866.3549717
Grosof, I. 2022. Optimal scheduling in the multiserver-job model under heavy traffic. Proceedings ACM Measurement Analysis Computing Systems 3(6):51. 32 p. doi: 10.1145/ 3570612.
Wang, W, Q. Xie, and M. Harchol-Balter. 2022. Zero queueing for multi-server jobs. ACM Sigmetrics Performance Evaluation Review 1(49):13-14. doi: 10.1145/ 3543516.3453924.
Kim, S. 1979. M/M/s queueing system where customers demand multiple server use. Dallas, TX: Southern Methodist University, 1979. PhD Diss. 104 p.
Brill, P. H., and L. Green. 1984. Queues in which customers receive simultaneous service from a random number of servers: A system point approach. Manage. Sci. 30(1): 51-68.
Yashkov, S. F. 1989. Analiz ocheredey v EVM [Analysis of queues in computer systems], Moscow: Radio i svyaz'. 216 p.
Filippopoulos, D., and H. Karatza. 2007. An M/M/2 parallel system model with pure space sharing among rigid jobs. Math. Comput. Model. 45:491-530.
Chakravarthy, S. R., and H. D. Karatza. 2013. Two-server parallel system with pure space sharing and Markovian arrivals. Comput. Oper. Res. 40(1):510-519.
Harchol-Balter, M. 2021. Open problems in queueing theory inspired by datacenter computing. Queueing Syst. 97:3-37.
Rumyantsev, A., R. Basmadjian, A. Golovin, and S. Astafiev. 2021. A three-level modelling approach for asynchronous speed scaling in high-performance data centres. 12th Conference (International) on Future Energy Systems e-Energy Proceedings. ACM. 417-423.
Unwin, A. R. 1984. Results for dual resource queues. Modelling and performance evaluation methodology. Eds. F. Baccelli and G. Fayolle. Lecture notes in control and information sciences ser. Berlin/Heidelberg: Springer-Verlag. 60:351-370. doi: 10.1007/BFb0005182.
Melikov, A. Z. 1996. Computation and optimization methods for multiresource queues. Cybern. Syst. Anal. 32(6):821-836. doi: 10.1007/BF02366862.
Afanaseva, L., E. Bashtova, and S. Grishunina. 2020. Stability analysis of a multi-server model with simultaneous service and a regenerative input flow. Methodol. Comput. Appl. 22:1439-1455. doi: 10.1007/s11009-019-09721-9.
Grosof, I., M. Harchol-Balter, and A. Scheller-Wolf. 2020. Stability for two-class multiserver-job systems. arXiv.org. 29 p. Available at: https://arxiv.org/abs/2010.00631 (ac-cessed April 30, 2023).
Harchol-Balter, M. 2022. The multiserver job queueing model. Queueing Syst. 100(3-4):201-203. doi: 10.1007/ s11134-022-09762-x.
Vishnevskiy, V. M., and O. V. Semenova. 2006. Mathematical methods to study the polling systems. Automat. Rem. Contr. 67(2):173-220.
Pechinkin, A.V., and V. V. Chaplygin. 2004. Stationary characteristics of the SM/MSP/n/r queuing system. Automat. Rem. Contr. 65(9):1429-1443.
Dudin, A. N., V. I. Klimenok, and V. M. Vishnevsky. 2020. The theory of queuing systems with correlated flows. Cham, Switzerland: Springer. 410 p.
Zhang, J., and E.J. Coyle. 1989. Transient analysis of quasi-birth-death processes. Commun. Stat. Stochastic Models 5(3):459-496. doi: 10.1080/15326348908807119.
Vishnevskii, V. M., andA. N. Dudin. 2017. Queueing systems with correlated arrival flows and their applications to modeling telecommunication network. Automat. Rem. Contr. 78:1361-1403.
Bocharov, P.P., and A.V. Pechinkin. 1995. Teoriya massovogo obsluzhivaniya [Queueing theory]. Moscow: RUDN. 529 p.
Le Ny, L. M., and B. Sericola. 2002. Transient analysis of the BMAP/PH/1 queue. Int. J. Simulation Systems Science Technology 3(3):4-14.
Hiroyuki, M., and T. Takine. 2005. Algorithmic computation of the time-dependent solution of structured Markov chains and its application to queues. Stoch. Models 21:885-912.
Rumyantsev, A., R. Basmadjian, S. Astafiev, and A. Golovin. 2022. Three-level modeling of a speed-scaling supercomputer. Ann. Oper. Res. doi: 10.1007/s10479-022- 04830-0.
Gelbaum, B. R., and J. M. H. Olmsted. 2003. Counter examples in analysis. Courier Corporation. 195 p.
Dshalalow, J. H. 1995. Advances in queueing: Theory, methods and open problem. London: CRC Press. 528 p.
Ozawa, T. 2006. Sojourn time distributions in the queue defined by a general QBD process. Queueing Syst. 53(4):203-211. doi: 10.1007/s11134-006-7651-3.

[+] About this article