Abstract
The analysis of fork-join queueing systems has played an important role for the performance evaluation of distributed systems where parallel computations associated with the same job are carried out and a job is considered served only when all the parallel tasks it consists of are served and then joined. The fork-join nodes that we consider consist of \(K\ge 2\) parallel servers each of which is equipped with two FCFS queues, namely the service-queue and the join-queue. The former stores the tasks waiting for being served while the latter stores the served tasks waiting for being joined. When the queueing station is saturated, i.e., the service-queues are never empty, we observe that the join-queue sizes tend to grow infinitely even if the expected service times at the servers are the same. In fact, this is due to the variance of the service time distribution. To tackle this problem, we propose a simple service-rate control mechanism, and show that under the exponential assumption on the service times, we can analytically study a set of relevant performance indices. We show that by selectively reducing the speed of some servers, significant energy saving can be achieved.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
Baccelli, F., Makowski, M.A.: Queueing models for systems with synchronization constraints. Proc. IEEE 77(1), 138–161 (1989)
Baccelli, F., Liu, Z.: On the execution of parallel programs on multiprocessor systems: a queuing theory approach. J. ACM 37(2), 373–414 (1990)
Baccelli, F., Massey, W.A., Towsley, D.: Acyclic fork-join queuing networks. J. ACM 36(3), 615–642 (1989)
Bruell, S.C., Balbo, G., Afshari, P.V.: Mean value analysis of mixed, multiple class BCMP networks with load dependent service stations. Perform. Eval. 4, 241–260 (1984)
Buzen, J.P.: Computational algorithms for closed queueing networks with exponential servers. Commun. ACM 16(9), 527–531 (1973)
Casale, G.: A generalized method of moments for closed queueing networks. Perform. Eval. 68(2), 180–200 (2011)
Fiorini, P.M., Lipsky, L.: Exact analysis of some split-merge queues. SIGMETRICS Perform. Eval. Rev. 43(2), 51–53 (2015)
Flatto, L., Hahn, S.: Two parallel queues created by arrivals with two demands. SIAM J. Appl. Math. 44(5), 1041–1053 (1984)
Heidelberger, P., Trivedi, K.: Analytic queueing models for programs with internal concurrency. IEEE Trans. Comput. C–32, 73–82 (1983)
Hoekstra, G.J., van der Mei, R.D., Bhulai, S.: Optimal job splitting in parallel processor sharing queues. Stoch. Models 28, 144–166 (2012)
Kelly, F.: Reversibility and Stochastic Networks. Wiley, New York (1979)
Lebrecht, A.S., Dingle, N.J., Knottenbelt, W.J.: Modelling zoned RAID systems using fork-join queueing simulation. In: Bradley, J.T. (ed.) EPEW 2009. LNCS, vol. 5652, pp. 16–29. Springer, Heidelberg (2009)
Lu, H., Pang, G.: Gaussian limits for a fork-join network with nonexchangeable synchronization in heavy traffic. Math. Oper. Res. 41(2), 560–595 (2016)
Marin, A., Rossi, S.: On discrete time reversibility modulo state renaming and its applications. In: 8th International Conference on Performance Evaluation Methodologies and Tools, VALUETOOLS, pp. 1–8 (2014)
Marin, A., Rossi, S.: On the relations between lumpability and reversibility. In: Proceedings of the IEEE 22nd International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS 2014), pp. 427–432 (2014)
Marin, A., Rossi, S.: On the relations between Markov chain lumpability and reversibility. Acta Inform. 1–39 (2016)
Nelson, R., Tantawi, A.N.: Approximate analysis of fork/join synchronization in parallel queues. IEEE Trans. Comput. 37(6), 739–743 (1986)
Nguyen, V.: Processing networks with parallel and sequential tasks: heavy traffic analysis and Browinian limits. Ann. Appl. Probab. 3(1), 28–55 (1993)
Olver, F.W., Lozier, D.W., Boisvert, R.F., Clark, C.W.: NIST Handbook of Mathematical Functions, 1st edn. Cambridge University Press, New York (2010)
Rauber, T., Rünger, G.: Energy-aware execution of fork-join-based task parallelism. In: Proceedings of the 20th IEEE International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, (MASCOTS), pp. 231–240 (2012)
Towsley, D., Romel, G., Astankovic, J.: Analysis of fork-join program response times on multiprocessors. IEEE Trans. Parallel Distrib. Syst. 1(3), 286–303 (1990)
Tsimashenka, I., Knottenbelt, W., Harrison, P.G.: Controlling variability in split-merge systems. In: Al-Begain, K., Fiems, D., Vincent, J.-M. (eds.) ASMTA 2012. LNCS, vol. 7314, pp. 165–177. Springer, Heidelberg (2012)
Tsimashenka, I., Knottenbelt, W.J., Harrison, P.G.: Controlling variability in split-merge systems and its impact on performance. Ann. Oper. Res. 239(2), 569–588 (2016)
Welch, P.D.: On the problem of the initial transient in steady-state simulations. Technical report, IBM Watson Research Center, Yorktown Heights, NY (1981)
Wright, P.E.: Two parallel processors with coupled inputs. Adv. Appl. Probab. 24, 986–1007 (1992)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Marin, A., Rossi, S. (2016). Dynamic Control of the Join-Queue Lengths in Saturated Fork-Join Stations. In: Agha, G., Van Houdt, B. (eds) Quantitative Evaluation of Systems. QEST 2016. Lecture Notes in Computer Science(), vol 9826. Springer, Cham. https://doi.org/10.1007/978-3-319-43425-4_8
Download citation
DOI: https://doi.org/10.1007/978-3-319-43425-4_8
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-43424-7
Online ISBN: 978-3-319-43425-4
eBook Packages: Computer ScienceComputer Science (R0)