short-paper

Network calculus for parallel processing

Authors:

G. Kesidis,

Y. Shan,

B. Urgaonkar,

J. LiebeherrAuthors Info & Claims

ACM SIGMETRICS Performance Evaluation Review, Volume 43, Issue 2

Pages 48 - 50

https://doi.org/10.1145/2825236.2825256

Published: 16 September 2015 Publication History

Get Access

Abstract

In this paper, we present preliminary results on the use of "network calculus" for parallel processing (fork join) systems, e.g., MapReduce. We derive a probabilistic bound that the delay through a single parallel processing stage exceeds a threshold.

References

[1]

G. Ananthanarayanan, A. Ghodsi, S. Shenker, and I. Stoica. Effective straggler mitigation: Attack of the clones. In Proc. USENIX NSDI, Lombard, IL, Apr. 2013.

Digital Library

Google Scholar

[2]

G. Ananthanarayanan, S. Kandula, A.G. Greenberg, I. Stoica, Y. Lu, B. Saha, and E. Harris. Reining in the Outliers in Map-Reduce Clusters using Mantri. In Proc. USENIX OSDI, Vancouver, Oct. 2010.

Digital Library

Google Scholar

[3]

Y. Chen, A. Ganapathi, R. Griffith, and R. Katz. The Case for Evaluating MapReduce Performance Using Workload Suites. In Proc. IEEE MASCOTS, 2011.

Digital Library

Google Scholar

[4]

Rene L. Cruz. SCED+: Efficient Management of Quality of Service Guarantees. In Proc. IEEE INFOCOM, pages 625--634, 1998.

Crossref

Google Scholar

[5]

M. Ead, H. Herodotou, A. Aboulnaga, and S. Babu. PStorM: Profile storage and matching for feedback-based tuning of MapReduce jobs. In Proc. Conf. on Extending Database Technology, March 2014.

Google Scholar

[6]

Facebook workload repository. https://github.com/SWIMProjectUCB/SWIM/wiki/ Workloads-repository, 2009-2010.

Google Scholar

[7]

Y. Jiang, Q. Yin, Y. Liu, and S. Jiang. Fundamental calculus on generalized stochastically bounded bursty traffic for communication networks. Computer Networks, 53(12):2011--2021, 2009.

Digital Library

Google Scholar

[8]

G. Kesidis, B. Urgaonkar, Y. Shan, S. Kamarava, and J. Liebeherr. Network calculus for parallel processing. Arxiv Tech. Report, http://arxiv.org/abs/1409.0820.

Google Scholar

[9]

M. Li, L. Zeng, S. Meng, J. Tan, L. Zhang, N.C. Fuller, and A.R. Butt. Online: MapReduce Online Performance Tuning. In Proc. HPDC, 2014.

Digital Library

Google Scholar

[10]

R. Nelson and A.N. Tantawi. Approximate analysis of fork/join synchronization in parallel queues. IEEE Trans. Computers, 37, 1988.

Digital Library

Google Scholar

[11]

C. Reiss, A. Tumanov, G.R. Ganger, and R.H. Katz. Heterogeneity and Dynamicity of CLouds at Scale: Google Trace Analysis. In Proc. ACM SOCC, Oct. 2012.

Digital Library

Google Scholar

[12]

A. Rizk, F. Poloczek, and F. Ciucu. Computable bounds in fork-join queueing systems. In Proc. ACM SIGMETRICS, June 2015.

Digital Library

Google Scholar

[13]

Y. Yu, M. Isard, D. Fetterly, M. Budiu, U. Erlingsson, P.K. Gunda, and J. Currey. DryadLINQ: A System for General-Purpose Distributed Data-Parallel Computing Using a High-Level Language. In Proc. USENIX OSDI, pages 1--14, 2008.

Digital Library

Google Scholar

Cited By

View all

Bora SWalker BFidler M(2023)The Tiny-Tasks Granularity Trade-Off: Balancing Overhead Versus Performance in Parallel SystemsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2022.323371234:4(1128-1144)Online publication date: 1-Apr-2023
https://doi.org/10.1109/TPDS.2022.3233712
Walker BBora SFidler M(2022)Performance and Scaling of Parallel Systems with Blocking Start and/or Departure BarriersIEEE INFOCOM 2022 - IEEE Conference on Computer Communications10.1109/INFOCOM48880.2022.9796754(460-469)Online publication date: 2-May-2022
https://doi.org/10.1109/INFOCOM48880.2022.9796754
Fidler MWalker BBora S(2020)Tiny Tasks – A Remedy for Synchronization Constraints in Multi-Server SystemsIEEE INFOCOM 2020 - IEEE Conference on Computer Communications10.1109/INFOCOM41043.2020.9155368(1063-1072)Online publication date: Jul-2020
https://doi.org/10.1109/INFOCOM41043.2020.9155368
Show More Cited By

Recommendations

Task Scheduling on the PASM Parallel Processing System

PASM is a proposed large-scale distributed/parallel processing system which can be partitioned into independent SIMD/MIMD machines of various sizes. One design problem for systems such as PASM is task scheduling. The use of multiple FIFO queues for ...
Network calculus and queueing theory: two sides of one coin: invited paper
VALUETOOLS '09: Proceedings of the Fourth International ICST Conference on Performance Evaluation Methodologies and Tools

Network calculus is a theory dealing with queueing type problems encountered in computer networks, with particular focus on quality of service guarantee analysis. Queueing theory is the mathematical study of queues, proven to be applicable to a wide ...
Exploiting parallel processing in large scientific applications

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGMETRICS Performance Evaluation Review

ACM SIGMETRICS Performance Evaluation Review Volume 43, Issue 2

September 2015

79 pages

ISSN:0163-5999

DOI:10.1145/2825236

Editor:
Giuliano Casale
Imperial College London, London

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 September 2015

Published in SIGMETRICS Volume 43, Issue 2

Check for updates

Qualifiers

Short-paper

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
179
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Bora SWalker BFidler M(2023)The Tiny-Tasks Granularity Trade-Off: Balancing Overhead Versus Performance in Parallel SystemsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2022.323371234:4(1128-1144)Online publication date: 1-Apr-2023
https://doi.org/10.1109/TPDS.2022.3233712
Walker BBora SFidler M(2022)Performance and Scaling of Parallel Systems with Blocking Start and/or Departure BarriersIEEE INFOCOM 2022 - IEEE Conference on Computer Communications10.1109/INFOCOM48880.2022.9796754(460-469)Online publication date: 2-May-2022
https://doi.org/10.1109/INFOCOM48880.2022.9796754
Fidler MWalker BBora S(2020)Tiny Tasks – A Remedy for Synchronization Constraints in Multi-Server SystemsIEEE INFOCOM 2020 - IEEE Conference on Computer Communications10.1109/INFOCOM41043.2020.9155368(1063-1072)Online publication date: Jul-2020
https://doi.org/10.1109/INFOCOM41043.2020.9155368
KhudaBukhsh WKar SRizk AKoeppl H(2019)Provisioning and Performance Evaluation of Parallel Systems with Output SynchronizationACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/33001424:1(1-31)Online publication date: 3-Mar-2019
https://dl.acm.org/doi/10.1145/3300142
Fidler MWalker BJiang Y(2018)Non-Asymptotic Delay Bounds for Multi-Server Systems with Synchronization ConstraintsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2017.277987229:7(1545-1559)Online publication date: 1-Jul-2018
https://doi.org/10.1109/TPDS.2017.2779872
Zeng MFodor V(2017)Distributing dynamic divisible loads2017 IFIP Networking Conference (IFIP Networking) and Workshops10.23919/IFIPNetworking.2017.8264889(1-2)Online publication date: Jun-2017
https://doi.org/10.23919/IFIPNetworking.2017.8264889
Walker B(2017)Benchmarking and simulating the fundamental scaling behaviors of a MapReduce engine2017 IFIP Networking Conference (IFIP Networking) and Workshops10.23919/IFIPNetworking.2017.8264877(1-6)Online publication date: Jun-2017
https://doi.org/10.23919/IFIPNetworking.2017.8264877
KhudaBukhsh WRizk AFrommgen AKoeppl H(2017)Optimizing stochastic scheduling in fork-join queueing models: Bounds and applicationsIEEE INFOCOM 2017 - IEEE Conference on Computer Communications10.1109/INFOCOM.2017.8057013(1-9)Online publication date: May-2017
https://doi.org/10.1109/INFOCOM.2017.8057013
Fidler MJiang Y(2016)Non-asymptotic delay bounds for (k, l) fork-join systems and multi-stage fork-join networksIEEE INFOCOM 2016 - The 35th Annual IEEE International Conference on Computer Communications10.1109/INFOCOM.2016.7524362(1-9)Online publication date: Apr-2016
https://doi.org/10.1109/INFOCOM.2016.7524362
Rizk APoloczek FCiucu F(2016)Stochastic bounds in Fork---Join queueing systems under full and partial mappingQueueing Systems: Theory and Applications10.1007/s11134-016-9486-x83:3-4(261-291)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1007/s11134-016-9486-x

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Recommendations

Task Scheduling on the PASM Parallel Processing System

Network calculus and queueing theory: two sides of one coin: invited paper

Exploiting parallel processing in large scientific applications