More Web Proxy on the site http://driver.im/

research-article

A hybrid Markov chain model for workload on parallel computers

Authors:

Joachim Lepping,

Wiebke SiebenAuthors Info & Claims

HPDC '10: Proceedings of the 19th ACM International Symposium on High Performance Distributed Computing

Pages 589 - 596

https://doi.org/10.1145/1851476.1851563

Published: 21 June 2010 Publication History

Abstract

This paper proposes a comprehensive modeling architecture for workloads on parallel computers using Markov chains in combination with state dependent empirical distribution functions. This hybrid approach is based on the requirements of scheduling algorithms: the model considers the four essential job attributes submission time, number of required processors, estimated processing time, and actual processing time. So far, no model exists that considers all those attributed at the same time. To assess the goodness-of-fit of a workload model the similarity between sequences of real jobs and jobs generated from the model needs to be captured. We propose to reduce the complexity of this task and to evaluate the model by comparing the results of a widely-used scheduling algorithm instead. This approach is demonstrated with commonly used scheduling objectives. To verify this evaluation technique, standard criteria for assessing the goodness-of-fit for workload models are additionally applied.

References

[1]

}}A. B. Downey and D. G. Feitelson. The Elusive Goal of Workload Characterization. Performance Evaluation Review, 26(4):14--29, March 1999.

Digital Library

[2]

}}C. Ernemann, B. Song, and R. Yahyapour. Scaling of Workload Traces. In D. G. Feitelson, L. Rudolph, and U. Schwiegelshohn, editors, Job Scheduling Strategies for Parallel Processing, volume 2862 of Lecture Notes in Computer Science, pages 166--183. Springer, October 2003.

[3]

}}D. G. Feitelson. Packing Schemes for Gang Scheduling. In D. G. Feitelson and L. Rudolph, editors, Job Scheduling Strategies for Parallel Processing, volume 1162 of Lecture Notes in Computer Science, pages 89--110. Springer, 1996.

Digital Library

[4]

}}D. G. Feitelson. Metrics for Parallel Job Scheduling and their Convergence. In D. G. Feitelson and L. Rudolph, editors, Job Scheduling Strategies for Parallel Processing, volume 2221, pages 188--206. Springer, 2001.

Digital Library

[5]

}}D. G. Feitelson. Workload Modeling for Performance Evaluation. In M. C. Calzarossa and S. Tucci, editors, Performance Evaluation of Complex Systems: Techniques and Tools, volume 2459 of Lecture Notes in Computer Science, pages 114--141. Springer, 2002.

Digital Library

[6]

}}D. G. Feitelson and A. M. Weil. Utilization and Predictability in Scheduling the IBM SP2 with Backfilling. In International Parallel Processing Symposium, pages 542--547. IEEE Computer Society Press, 1998.

Digital Library

[7]

}}C. Franke, J. Lepping, and U. Schwiegelshohn. Greedy Scheduling with Complex Objectives. In IEEE Symposium on Computational Intelligence in Scheduling, pages 113--120. IEEE Press, April 2007. CD-ROM.

[8]

}}S. Hotovy. Workload Evolution on the Cornell Theory Center IBM SP2. In D. G. Feitelson and L. Rudolph, editors, Job Scheduling Strategies for Parallel Processing, volume 1162 of Lecture Notes in Computer Science, pages 27--40. Springer, 1996.

Digital Library

[9]

}}J. Jann, P. Pattnaik, H. Franke, F. Wang, J. Skovira, and J. Riodan. Modeling of Workload in MPPs. In D. G. Feitelson and L. Rudolph, editors, Job Scheduling Strategies for Parallel Processing, volume 1291 of Lecture Notes in Computer Science, pages 95--116. Springer, 1997.

Digital Library

[10]

}}S. Kotz, C. B. Read, N. Balakrishnan, and B. Vidakovic. Encyclopedia of Statistical Science, volume 4. Wiley, 2nd edition, 2006.

[11]

}}C. B. Lee, Y. Schwartzman, J. Hardy, and A. Snavely. Are User Runtime Estimates Inherently Inaccurate? In Job Scheduling Strategies for Parallel Processing, volume 3277 of Lecture Notes in Computer Science, pages 253--263. Springer, April 2005.

Digital Library

[12]

}}H. Li and M. Muskulus. Analysis and Modeling of Job Arrivals in a Production Grid. ACM Sigmetrics Performance Evaluation Review, 34(4):59--70, 2007.

Digital Library

[13]

}}H. Li, M. Muskulus, and L. Wolters. Modeling Correlated Workloads by Combining Model Based Clustering and A Localized Sampling Algorithm. In Proceedings of 21st ACM International Conference on Supercomputing, pages 16--20. ACM Press, June 2007.

Digital Library

[14]

}}V. Lo, J. Mache, and K. Windisch. A Comparative Study of Real Workload Traces and Synthetic Workload Models for Parallel Job Scheduling. In D. G. Feitelson and L. Rudolph, editors, Job Scheduling Strategies for Parallel Processing, volume 1459 of Lecture Notes in Computer Science, pages 25--46. Springer, 1998.

Digital Library

[15]

}}U. Lublin and D. G. Feitelson. The Workload on Parallel Supercomputers: Modeling the Characteristics of Rigid Jobs. Journal of Parallel and Distributed Computing, 63(11):1105--1122, 2003.

Digital Library

[16]

}}S. Majumdar and E. W. Parsons. Parallel Job Scheduling: A Performance Perspective. In Performance Evaluation: Origins and Directions, volume 1769 of Lecture Notes in Computer Science, pages 233--252. Springer, 2000.

Digital Library

[17]

}}A. M. Mood, F. A. Graybill, and D. C. Boes. Introduction to the Theory of Statistics. McGraw-Hill, 3rd edition, 1974.

[18]

}}B. Song, C. Ernemann, and R. Yahyapour. Modeling of Parameters in Supercomputer Workloads. In Workshop on Parallel Systems and Algorithms, volume P-41 of Lecture Notes in Informatics, pages 400--409. Gesellschaft für Informatik, March 2004.

[19]

}}B. Song, C. Ernemann, and R. Yahyapour. Parallel Computer Workload Modeling with Markov Chains. In D. G. Feitelson, L. Rudolph, and U. Schwiegelshohn, editors, Job Scheduling Strategies for Parallel Processing, volume 3277 of Lecture Notes in Computer Science, pages 47--62. Springer, Oct 2004.

Digital Library

[20]

}}D. Sorensen and D. Gianola. Likelihood, Bayesian and MCMC Methods in Quantitative Genetics. Springer, 1st edition, 2002.

[21]

}}M. S. Squillante, D. D. Yao, and L. Zhang. The Impact of Job Arrival Patterns on Parallel Scheduling. SIGMETRICS Performance Evaluation Review, 26(4):52--59, 1999.

Digital Library

[22]

}}D. Tsafrir, Y. Etsion, and D. G. Feitelson. Modeling User Runtime Estimates. In D. G. F. et al., editor, Job Scheduling Strategies for Parallel Processing, volume 3834 of Lecture Notes in Computer Science, pages 1--35. Springer, 2005.

Digital Library

Cited By

Chiesi MVanzolini LMucci CFranchi Scarselli EGuerrieri R(2015)Power-Aware Job Scheduling on Heterogeneous Multicore ArchitecturesIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2014.231520326:3(868-877)Online publication date: 1-Mar-2015
https://doi.org/10.1109/TPDS.2014.2315203
Zhang WLiu JLiu CZheng QZhang W(2015)Workload modeling for virtual machine-hosted applicationExpert Systems with Applications: An International Journal10.1016/j.eswa.2014.10.01242:4(1835-1844)Online publication date: 1-Mar-2015
https://dl.acm.org/doi/10.1016/j.eswa.2014.10.012
Rumyantsev A(2014)Simulating Supercomputer Workload with Hpcwld Package for RProceedings of the 2014 15th International Conference on Parallel and Distributed Computing, Applications and Technologies10.1109/PDCAT.2014.36(138-143)Online publication date: 9-Dec-2014
https://dl.acm.org/doi/10.1109/PDCAT.2014.36
Show More Cited By

Index Terms

A hybrid Markov chain model for workload on parallel computers

Recommendations

Fast scheduling algorithms on parallel computers
Divisible Load Scheduling and Markov Chain Models

In this paper, the equivalence between various divisible load-scheduling policies and continuous time Markov chains is demonstrated. This provides a basic unification of both data parallel divisible load scheduling and Markov chain models for the first ...
Preemptive Scheduling of Hybrid Parallel Machines

<P>Multioperation production facilities are often segmented into independent workcells that handle different subsets of operations. We refer to a cell that consists of several groups of uniform special purpose machines, each capable of performing only ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

HPDC '10: Proceedings of the 19th ACM International Symposium on High Performance Distributed Computing

June 2010

911 pages

ISBN:9781605589428

DOI:10.1145/1851476

General Chairs:
Salim Hariri
University of Arizona
,
Kate Keahey
University of Chicago

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

University of Arizona: University of Arizona
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 June 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Conference

HPDC '10

Sponsor:

University of Arizona
SIGARCH

HPDC '10: The 19th International Symposium on High Performance Distributed Computing

June 21 - 25, 2010

Illinois, Chicago

Acceptance Rates

Overall Acceptance Rate 166 of 966 submissions, 17%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
189
Total Downloads

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

Reflects downloads up to 24 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chiesi MVanzolini LMucci CFranchi Scarselli EGuerrieri R(2015)Power-Aware Job Scheduling on Heterogeneous Multicore ArchitecturesIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2014.231520326:3(868-877)Online publication date: 1-Mar-2015
https://doi.org/10.1109/TPDS.2014.2315203
Zhang WLiu JLiu CZheng QZhang W(2015)Workload modeling for virtual machine-hosted applicationExpert Systems with Applications: An International Journal10.1016/j.eswa.2014.10.01242:4(1835-1844)Online publication date: 1-Mar-2015
https://dl.acm.org/doi/10.1016/j.eswa.2014.10.012
Rumyantsev A(2014)Simulating Supercomputer Workload with Hpcwld Package for RProceedings of the 2014 15th International Conference on Parallel and Distributed Computing, Applications and Technologies10.1109/PDCAT.2014.36(138-143)Online publication date: 9-Dec-2014
https://dl.acm.org/doi/10.1109/PDCAT.2014.36
Zhao GLi BHong T(2012)Pre-fetching Webpages on Mobile Social NetworkProceedings of the 2012 8th International Conference on Mobile Ad-hoc and Sensor Networks10.1109/MSN.2012.30(203-210)Online publication date: 14-Dec-2012
https://dl.acm.org/doi/10.1109/MSN.2012.30
Lassnig MFahringer TGaronne VMolfetas ABarisits MLathrop SCosta JKramer W(2011)A similarity measure for time, frequency, and dependencies in large-scale workloadsProceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis10.1145/2063384.2063441(1-11)Online publication date: 12-Nov-2011
https://dl.acm.org/doi/10.1145/2063384.2063441
Helmy TRasheed Z(2011)Colony of cooperating agents based independent job scheduling in a computation gridInternational Journal of Intelligent Computing and Cybernetics10.1108/175637811111367204:2(243-264)Online publication date: 7-Jun-2011
https://doi.org/10.1108/17563781111136720

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents