Relationship Invariants Based Sojourn Time Approximation for the Fork-Join Queueing System Roman S. Khabarov Vladimir A. Lokhvitckii Andry S. Dudkin MSA named MSA named MSA named after A.F.Mozhaysky after A.F.Mozhaysky after A.F.Mozhaysky Saint Petersburg, Russia Saint Petersburg, Russia Saint Petersburg, Russia xabarov1985@gmail.com lokhv_va@mail.ru andry-ll@mail.ru 3 service channels. In the case of Fork-Join, the freed channel may be occupied by the subtask of the next task (Figure 1). When organizing the Split-Merge service (Figure 2), a block occurs at the time of task Abstract entering, and the freed channels are idle, waiting for The approximation method of task the last of the subtasks of the current task to be sojourn time in the fork-join queuing serviced. system based on relationship invariants is proposed. The idea is in application of intuitive proportion between the certain queuing systems time characteristics. It is shown that, compared with the known methods, the proposed approximation is more accurate with server utilization higher then 0.7. Figure 1: Task service chart in Fork-Join queueing system 1 Introduction To evaluate the efficiency of query processing in systems using distributed and parallel computing technologies, queuing systems like Split-Merge and Figure 2: Task service chart in Split-Merge Fork-Join are used. queueing system The general idea of the Split-Merge and Fork-Join systems functioning is as follows: tasks received in the A rather large number of works has been devoted to the system are “split” into n sub-tasks, each of which is Fork-Join and Split-Merge processes [Alom2014, sent to the channel with numbers 1, 2, ..., n, Bacc1985, Bacc1989, Fior2015, Flat1979, Harr2003, respectively. Processed subtasks fall into the Khab2019, Nels1988, Olv2014, Ryzh1980, Ryzh2015, synchronization buffer, where they wait for the Qui2015, Var2002, Varma1994, Wright1992]. For the servicing completion of their related subtasks. At the Split-Merge system in [Harr2003], an exact solution end servicing of the last related subtask, was obtained to determine the maximum service time synchronization occurs, i.e. aggregation, after which of independent channels with exponential service time task leaves the system. It is regarded that and various intensities, as well as approximations for synchronization occurs instantly. the case of a general distribution. In [Fior2015], the The difference between the Split-Merge and Fork-Join mentioned distribution was obtained for homogeneous systems is shown in Figures 1 and 2 for the example of and heterogeneous servers, and its representation in Copyright c by the paper's authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). matrix-exponential form made it possible to find both In: A. Khomonenko, B. Sokolov, K. Ivanova (eds.): Selected Papers of the first and the moments of higher orders. It should be the Models and Methods of Information Systems Research noted that this method is characterized by high Workshop, St. Petersburg, Russia, 4-5 Dec. 2019, published at http://ceur-ws.org. 63 computational complexity, which is a consequence of of high and low system utilization interpolation the laborious operations of inversion and the Kronecker methods: product of matrices that are included in it. The use of 1 Kronecker algebra is associated with a significant v1 » [H n + (Vn - H n )r ] , (4) additional memory consumption, as well as many µ -l redundant operations with zero operands. In [Ryzh2019], an exact solution was found for an ænö æ i ö (m - 1)! å çç i ÷÷(-1) å n i -1 i where Vn = çç ÷÷ m+1 . arbitrary distribution of services based on Chebyshev- i =1 m =1 Laguerre numerical integration. The solution has a è ø èmø i relatively low complexity and high accuracy. For Fork-Join systems, the exact expression for the In this paper, we propose a method for finding the average sojourn time with an arbitrary service average sojourn time for a Fork-Join queueing system distribution was obtained only for a system with two with an arbitrary service distribution based on the approximation of relationship invariants. channels [Bacc1985, Fior2015]. For the case n > 2 and exponential service, using various methods, approximations of the average sojourn time were obtained in [Nels1988, Var2002, Varma1994]. We give 2 Method idea below a brief summary of the results. In [Ryzh2015], to find the time characteristics of multi- In [Flat1979], an exact formula is given for the average channel queueing system with priorities, a method was sojourn time for n = 2, and the exponential distribution used based on the invariants idea of the relationship of the service time between the desired characteristics: æ rö v1 = ç H 2 - ÷ × v1( M ) , (1) M /G/n è 8ø M k / Gk / n » M k / Gk / 1 × . (5) M / G /1 å 1 / i for n = 2 , H = 1.5 , n where H n = i =1 2 All designations are given in Kendall notation. r = l / µ – system utilization, Calculation methods for the systems indicated on the right are considered known. In particular, iterative v1( M ) = 1 ( µ - l ) – average sojourn time in methods of Takahashi-Takami or matrix-geometric M / M / 1 queueing system. progression are used to calculate systems [Ryzh1980, In [Nels1988], Nelson and Tantawi proposed an Taka1976]. For the non-priority systems M / G / 1 approximation for the average sojourn time in a Fork- and M / G / n with a non-uniform task flow, the total Join queueing system with n service channels intensity of the task flow and the weighted average moments of the servicing distribution were used. éH 4 æ H ö ù 12 - r 1 As an approximation of the service time, it is proposed v1 » ê n + çç1 - n ÷÷ r ú , n ³ 2. (2) ë H 2 11 è H 2 ø û 8 µ - l to use a second-order hyperexponential distribution H 2 applicable for values of the coefficient of In [Var2002], Varki and Merchant proposed a formula variation, both smaller and larger than 1.0. For example, when replacing the gamma distribution with 1é r æ n 1 v1 » êH n + çå + the parameter 1 < a < 2 by H 2 -approximation, one µë 2(1 - r ) çè i =1 i - r of the “probabilities” will be negative, and the other n 1 öù will exceed 1.0. As computational experiments show + (1 - 2 r )å ÷÷ú, n ³ 2. (3) [Ryzh2015], these paradoxical intermediate results do i =1 i (i - r ) ø û not interfere with the successful calculation of queueing system using known numerical methods In [Varma1994], Varma proposed a method for [Taka1976]. approximating the sojourn time based on a combination 64 Here we present the scheme proposed in 3 Calculation results [Ryzh2015] for the implementation of conversion invariants for an n-channel priority system: The following are the results of calculations of the a) By multiplying the channel rate by n, we obtain average sojourn time in the queueing system (Figures the equivalent single-channel system rate. 3-8) in comparison with the methods proposed in b) Calculate the waiting time distribution [Nels1988,Var2002,Varma1994] (formulas (2), (3), (4)) and simulation data. The comparison was carried moments {wi , j } for all types of requests i and the order out depending on the system utilization and the number of the moments j = 1, 3. of service channels at three values of the service time c) For the same initial data on the weighted average coefficient of variation {0.5, 1.0, 1.5}. service times and the total intensity of the incoming flow L as applied to the M / H 2 / 1 system, calculate the number of requests stationary distribution { pi } and the average requests number in the queue: ¥ Q(1) = å (i - 1) pi . i =1 d) For the M / H 2 / n system, it is similar to carry out the calculation of state probabilities at initial service intensities and obtain the average queue length: ¥ Q(n) = å (i - n) pi . i = n +1 Figure 3: Average sojourn time depending on the e) Recalculate the waiting time distribution number of service channels, υ = 0.5, ρ=0.9 moments in the system with priorities for all i and j for the multichannel case: Wi , j = wi , j × Q(n) Q(1) . f) Using them, according to relation (5), obtain the sojourn time distribution moments of each task type in a multichannel system. We propose a similar approach for finding the average sojourn time in the Fork-Join queueing system with the number of channels. We rewrite the proportion (5) in the following form M /G/n FJ n » FJ 2 × . (6) M /G/2 Figure 4: Average sojourn time depending on the Here FJ n and FJ 2 – Fork-Join queuing systems number of service channels, υ = 1.0, ρ=0.9 with n and 2 channels, respectively. To find the average sojourn time in FJ 2 , we use the formula (1). The calculation of the remaining queueing systems from the right-hand side of (6) will be carried out by known methods [Ryzh1980, Taka1976]. To ensure the equality of system utilization values, when calculating M / G / n queuing systems, the initial moments of service time for were multiplied by n 2 . 65 Figure 5: Average sojourn time depending on the Figure 8: Average sojourn time depending on the number of service channels, υ = 1.5, ρ=0.9 system utilization, υ = 1.5, n=4 As can be seen from the figures, the accuracy of approximation by the method of invariants of the ratio is higher than calculated by the formulas (2-4). Moreover, at low ρ values, the method of invariant relations gives underestimated estimates of the average sojourn time, especially when increasing the coefficient of variation of the service time. Since the proposed method (as well as other approximation methods compared here) allows us to estimate only the average sojourn time of task in the system, if higher moments are necessary, the Split-Merge calculation method mentioned above should be used, since the estimated values of the sojourn time estimates in this case are the Figure 6: Average sojourn time depending on the upper bound stay in Fork-Join queuing system. system utilization, υ = 0.5, n=4 4 Summary The relation invariants method showed well average sojourn time approximation accuracy for Fork-Join queueing system. Calculation results and simulation data comparison showed that the proposed approximation accuracy increases as system utilization increasing. At high the service time coefficient of variation values, the method gives underestimated sojourn time of the task in the system. If it is necessary to find the upper bounds of sojourn time higher moments, it is recommended to use the method Figure 7: Average sojourn time depending on the proposed in [Khab2019,Ryzh2019] system utilization, υ = 1.0, n=4 66 Acknowledgments evaluating model of tasks multy-threading processing in a distributed computing The study was carried out with the financial support of environment with Split-Join processes]. the Russian Foundation for Basic Research, project Vestnik of Russian New University. Series number 18-29-22064 \18. ”Complex systems: models, analisys, management”, no. 1. Pp. 26-34, 2019 (In References Russ.). [Alom2014] Alomari F., Menasce D.A. Efficient [Nels1988] Nelson, R., Tantawi A.N. Approximate Response Time Approximation for Multiclass analysis of fork/join synchronization in Fork and Join Queues in Open and Close parallel queues. IEEE Transactions on Queueing Networks. IEEE Transaction on Computers, vol. 37. Pp. 739-743, 1988. Parallel and Distributed Systems, vol. 25. pp.1437-1446, 2014. [Olv2014] Olvera-Cravioto M., Ruiz-Lacedelli O. Parallel queues with synchronization. In arXiv [Bacc1989] Baccelli F., Makowski A.M., Shwartz A. preprint https://arXiv:1501.00186, 2014. The Fork-Join Queue and Related Systems with Synchronization Constraints: Stochastic [Ryzh1980] Ryzhikov Y.I., Khomonenko A.D. Ordering and Computable Bounds. Advances Iterativnyj metod rascheta mnogokanalnyh in Applied Probability, vol. 21. No. 3. Pp. system s proizvolnym raspredeleniem vremeni 629-660, 1989. obsluzhivaniya [An iterative method for calculating multichannel systems with an [Bacc1985] Baccelli F. Two parallel queues created by arbitrary distribution of service time]. arrivals with two demands. The M/G/2 Problemy upravleniya i teoriya informacii symmetrical case. Technical report INRIA- [Management problems and information Rocquencourt, no. 426, 1985. theory], no. 3, Pp. 32-38, 1980 (In Russ.). [Fior2015] Fiorini P., Lipsky L. Exact Analysis of [Ryzh2015] Ryzhikov Y.I., Khomonenko A.D. Raschet Some Split-Merge Queues. Performance mnogokanal’nyh sistem obsluzhivaniya s Evaluation Review, vol. 43. No. 2. pp. 51-53, absolyutnym i otnositel’nym prioritetami na 2015. osnove invariantov otnosheniya [Calculation of multi-channel queueing systems with [Flat1979] Flatto, L., Hahn S. Two parallel queues preemptive and non-preemptive priorities created by arrivals with two demands. SIAM based on relationship invariants]. Journal on Applied Mathematics, vol. 44. Intellektual’nie technologii na transporte Pp.1041-1053, 1979. [Intellectual Technologies on Transport], no. 3, Pp. 11-17, 2015 (In Russ.). [Harr2003] Harrison P.G., Zertal S. Queueing models with maxima of service times. Computer [Ryzh2019] Ryzhikov Y.I., Lokhvitckii V.A., Performance Evaluation. Modelling Khabarov R.S. Metod rascheta dlitel’nosti Techiniques and Tools, pp. 152-168, 2003. obrabotki zadach v sisteme massovogo obsluzhivaniya s uchetom processov Split- [Khab2019] Khabarov R.S., Lokhvitckii V.A. Model’ Join [Method for calculating the duration of otsenivaniya operativnosti mnogopotochnoi processing tasks in a queuing system taking obrabotki zadach v raspredelennoi into account Split-Join processes]. Izvestiya vychislitel’noi srede s uchetom protsessov vysshikh uchebnykh zavedeniy. Split-Join. Vestnik Rossiyskogo novogo Priborostroenie [Journal of Instrument universiteta. Seriya ”Slozhnye sistemy: Engineering], vol. 62. No. 5. Pp. 419-423, modeli, analiz i upravlenie” [Efficiency 2019 (In Russ.). 67 [Taka1976] Takahashi Y., Takami Y. A numerical method for the steady-state probabilities of a GI/G/c queuing system in a general class. J. of the Operat. res. soc. of Japan, vol. 19(2). Pp. 147-157, 1976. Qui2015] Qiu Z., Perez J.G., Harrison P.G. Beyond the mean in fork-join queues: Efficient approximation for response-time tails. Performance evaluations, vol. 91. pp. 99-106, 2015. [Var2002] Varki E., Merchant A., Chen H. The M/M/1 Fork-Join Queue with Variable Subtasks. http://www.cs.unh.edu/varki/publication/2000 -nov-open.pdf, Accessed 19 Nov 2019. [Varma1994] Varma S., Makowski A.M. Interpolation Approximations for Symmetric Fork-Join Queues. Performance evaluations, vol. 20. Pp. 245-265, 1994. [Wright1992] Wright P.E. Two parallel processors with coupled inputs. Advances in Applied Probability, vol. 24. Pp. 986-1007, 1992. 68