[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/3629527.3652277acmconferencesArticle/Chapter ViewAbstractPublication PagesicpeConference Proceedingsconference-collections
research-article
Open access

Approximating Fork-Join Systems via Mixed Model Transformations

Published: 07 May 2024 Publication History

Abstract

While product-form queueing networks are effective in analyzing system performance, they encounter difficulties in scenarios involving internal concurrency. Moreover, the complexity introduced by synchronization delays challenges the accuracy of analytic methods. This paper proposes a novel approximation technique for closed fork-join systems, called MMT, which relies on transformation into a mixed queueing network model for computational analysis. The approach substitutes fork and join with a probabilistic router and a delay station, introducing auxiliary open job classes to capture the influence of parallel computation and synchronization delay on the performance of original job classes. Evaluation experiments show the higher accuracy of the proposed method in forecasting performance metrics compared to a classic method, the Heidelberger-Trivedi transformation. This suggests that our method could serve as a promising alternative in evaluating queueing networks that contains fork-join systems.

References

[1]
Firas Alomari and Daniel A Menasce. 2013. Efficient response time approximations for multiclass fork and join queues in open and closed queuing networks. IEEE Transactions on Parallel and Distributed Systems 25, 6 (2013), 1437--1446.
[2]
Marco Bertoli, Giuliano Casale, and Giuseppe Serazzi. 2009. JMT: performance engineering tools for system modeling. ACMSIGMETRICS Performance Evaluation Review 36, 4 (2009), 10--15.
[3]
Gunter Bolch, Stefan Greiner, Hermann De Meer, and Kishor S Trivedi. 2006. Queueing networks and Markov chains: modeling and performance evaluation with computer science applications. John Wiley & Sons.
[4]
Michael Burke, Ron Cytron, Jeanne Ferrante, and Wilson Hsieh. 1989. Automatic generation of nested, fork-join parallelism. The Journal of Supercomputing 3 (1989), 71--88.
[5]
Giuliano Casale. 2020. Integrated performance evaluation of extended queueing network models with line. In 2020 Winter Simulation Conference (WSC). IEEE, 2377--2388.
[6]
Giuliano Casale, Yicheng Gao, Zifeng Niu, and Lulai Zhu. 2023. LN: A Flexible Algorithmic Framework for Layered Queueing Network Analysis. ACM Transactions on Modeling and Computer Simulation (2023).
[7]
Giuliano Casale, Richard Muntz, and Giuseppe Serazzi. 2008. Geometric bounds: A noniterative analysis technique for closed queueing networks. IEEE Trans. Comput. 57, 6 (2008), 780--794.
[8]
K Mani Chandy and Doug Neuse. 1982. Linearizer: A heuristic algorithm for queueing network models of computing systems. Commun. ACM 25, 2 (1982), 126--134.
[9]
David Culler, Jaswinder Pal Singh, and Anoop Gupta. 1999. Parallel computer architecture: a hardware/software approach. Gulf Professional Publishing.
[10]
Rares-Andrei Dobre. 2023. Stochastic Modelling in JLINE: Redesigning and Augmenting the MVA Solver with Fork-Join Analysis Methods. Technical Report. MSc Final project, Department of Computing, Imperial College London.
[11]
Andrzej Duda and Tadeusz Czachórski. 1987. Performance evaluation of fork and join synchronization primitives. Acta Informatica 24 (1987), 525--553.
[12]
Greg Franks and MurrayWoodside. 1998. Performance of multi-level client-server systems with parallel service operations. In Proceedings of the 1st international workshop on Software and performance. 120--130.
[13]
Heidelberger and Trivedi. 1983. Analytic queueing models for programs with internal concurrency. IEEE Trans. Comput. 100, 1 (1983), 73--82.
[14]
Patricia A Jacobson and Edward D Lazowska. 1982. Analyzing queueing networks with simultaneous resource possession. Commun. ACM 25, 2 (1982), 142--151.
[15]
Gokcen Kestor, Sriram Krishnamoorthy, and Wenjing Ma. 2017. Localized fault recovery for nested fork-join programs. In 2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS). IEEE, 397--408.
[16]
Edward D Lazowska, John Zahorjan, G Scott Graham, and Kenneth C Sevcik. 1984. Quantitative system performance: computer system analysis using queueing network models. Prentice-Hall, Inc.
[17]
John DC Little. 1961. A proof for the queuing formula: L= ?? W. Operations research 9, 3 (1961), 383--387.
[18]
Jeff Magee, Naranker Dulay, Susan Eisenbach, and Jeff Kramer. 1995. Specifying distributed software architectures. In Software Engineering-ESEC'95: 5th European Software Engineering Conference Sitges, Spain, September 25--28, 1995 Proceedings 5. Springer, 137--153.
[19]
VictorWMak and Stephen F. Lundstrom. 1990. Predicting performance of parallel computations. IEEE Transactions on Parallel & Distributed Systems 1, 03 (1990), 257--270.
[20]
Randolph Nelson and Asser N Tantawi. 1988. Approximate analysis of fork/join synchronization in parallel queues. IEEE transactions on computers 37, 6 (1988), 739--743.
[21]
Martin Reiser and Stephen S Lavenberg. 1980. Mean-value analysis of closed multichain queuing networks. Journal of the ACM (JACM) 27, 2 (1980), 313--322.
[22]
S Salza and SS Lavenberg. 1981. Approximating response time distributions in closed queueing network models of computer performance. (1981).
[23]
Alexander Thomasian. 2014. Analysis of fork/join and related queueing systems. ACM Computing Surveys (CSUR) 47, 2 (2014), 1--71.
[24]
Kishor S Trivedi. 2008. Probability & statistics with reliability, queuing and computer science applications. John Wiley & Sons.
[25]
Elizabeth Varki. 1999. Mean value technique for closed fork-join networks. ACM SIGMETRICS Performance Evaluation Review 27, 1 (1999), 103--112.

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
ICPE '24 Companion: Companion of the 15th ACM/SPEC International Conference on Performance Engineering
May 2024
305 pages
ISBN:9798400704451
DOI:10.1145/3629527
This work is licensed under a Creative Commons Attribution International 4.0 License.

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 May 2024

Check for updates

Author Tags

  1. fork-join system
  2. queueing network
  3. synchronization delay

Qualifiers

  • Research-article

Conference

ICPE '24

Acceptance Rates

Overall Acceptance Rate 252 of 851 submissions, 30%

Upcoming Conference

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • 0
    Total Citations
  • 127
    Total Downloads
  • Downloads (Last 12 months)127
  • Downloads (Last 6 weeks)17
Reflects downloads up to 03 Jan 2025

Other Metrics

Citations

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media