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

research-article

A regression-based approach to scalability prediction

Authors:

Bradley J. Barnes,

Barry Rountree,

David K. Lowenthal,

Bronis de Supinski,

Martin SchulzAuthors Info & Claims

ICS '08: Proceedings of the 22nd annual international conference on Supercomputing

Pages 368 - 377

https://doi.org/10.1145/1375527.1375580

Published: 07 June 2008 Publication History

Abstract

Many applied scientific domains are increasingly relying on large-scale parallel computation. Consequently, many large clusters now have thousands of processors. However, the ideal number of processors to use for these scientific applications varies with both the input variables and the machine under consideration, and predicting this processor count is rarely straightforward. Accurate prediction mechanisms would provide many benefits, including improving cluster efficiency and identifying system configuration or hardware issues that impede performance.

We explore novel regression-based approaches to predict parallel program scalability. We use several program executions on a small subset of the processors to predict execution time on larger numbers of processors. We compare three different regression-based techniques: one based on execution time only; another that uses per-processor information only; and a third one based on the global critical path. These techniques provide accurate scaling predictions, with median prediction errors between 6.2% and 17.3% for seven applications.

References

[1]

S. R. Alam and J. S. Vetter. Hierarchical model validation of symbolic performance models of scientific applications. In Euro-Par, Aug. 2006.

Digital Library

[2]

S. R. Alam, J. S. Vetter, P. K. Agarwal, and A. Geist. Performance characterization of molecular dynamics techniques for biomolecular simulations. In PPOPP, pages 59--68, Mar 2006.

Digital Library

[3]

D. Bailey, J. Barton, T. Lasinski, and H. Simon. The NAS parallel benchmarks. RNR-91-002, NASA Ames Research Center, Aug. 1991.

[4]

V. Balasundaram, G. Fox, K. Kennedy, and U. Kremer. An static performance estimator to guide data partitioning decisions. In Proceedings of the Third ACM SIGPLAN Symposium on Principles and Practices of Parallel Programming, pages 213--223, Apr. 1991.

Digital Library

[5]

R. Bell, A. Malony, and S. Shende. ParaProf: A Portable, Extensible, and Scalable Tool for Parallel Performance Profile Analysis. In Proceedings of the International Conference on Parallel and Distributed Computing (Euro-Par 2003), pages 17--26, Aug. 2003.

[6]

J. Brehm, P. H. Worley, and M. Madhukar. Performance modeling for SPMD message-passing programs. Concurrency: Practice and Experience, 10(5):333--357, Apr. 1998.

[7]

S. Browne, J. Dongarra, N. Garner, K. London, and P. Mucci. A scalable cross-platform infrastructure for application performance tuning using hardware counters. In Supercomputing, Nov. 2000.

Digital Library

[8]

B. Buck and J. K. Hollingsworth. An API for runtime code patching. The International Journal of High Performance Computing Applications, 14(4):317--329, Winter 2000.

Digital Library

[9]

G. Carey, J. Schmidt, V. Singh, and D. Yelton. A scalable, object-oriented finite element solver for partial differential equations on multicomputers. In International Conference on Supercomputing, pages 387--396, 1992.

Digital Library

[10]

D. Culler, R. Karp, D. Patterson, A. Sahay, E. Santos, K. Schauser, R. Subramonian, and T. von Eicken. LogP: A practical model of parallel computation. Communications of the ACM, 39(11):78--85, Nov. 1996.

Digital Library

[11]

L. DeRose and D. A. Reed. SvPablo: A multi-language architecture-independent performance analysis system. In Proceedings of the International Conference on Parallel Processing (ICPP’99), Sept. 1999.

Digital Library

[12]

T. R. P. for Statistical Computing. http://www.r-project.org/.

[13]

J. L. Gustafson. Reevaluating Amdahl’s law. Communications of the ACM, 31(5):532--533, May 1988.

Digital Library

[14]

J. K. Hollingsworth. Critical path profiling of message passing and shared-memory programs. IEEE Transactions on Parallel and Distributed Systems, 9(10):29--40, 1998.

Digital Library

[15]

E. Ipek, B. R. de Supinski, M. Schulz, and S. A. McKee. An approach to performance prediction for parallel applications. In Euro-Par, pages 196--205, Aug 2005.

Digital Library

[16]

D. Kerbyson, H. Alme, A. Hoisie, F. Petrini, H. Wasserman, and M. Gittings. Predictive performance and scalability modeling of a large-scale application. In Supercomputing, Nov. 2001.

Digital Library

[17]

J. Labarta, S. Girona, V. Pillet, and T. Cortes. DiP: A parallel program development environment. Lecture Notes in Computer Science, 1124:665--??, 1996.

Digital Library

[18]

B. C. Lee, D. M. Brooks, B. R. de Supinski, M. Schulz, K. Singh, and S. A. McKee. Methods of inference and learning for performance modeling of parallel applications. In PPOPP, pages 249--258, 2007.

Digital Library

[19]

G. Lyon, R. Kacker, and A. Linz. A scalability test for parallel code. Software -- Practice and Experience, 25(12):1299--1314, Dec. 1995.

Digital Library

[20]

G. Marin and J. Mellor-Crummey. Cross-architecture performance predictions for scientific applications using parameterized models. In SIGMETRICS 2004, pages 2--13, June 2004.

Digital Library

[21]

G. Marin and J. Mellor-Crummey. Application insight through performance modeling. In IEEE International Performance Computing and Communications Conference, Apr 2007.

[22]

M. Müller, H. Brunst, M. Jurenz, A. Knüpfer, M. Lieber, H. Mix, and W. Nagel. Developing Scalable Applications with Vampir, VampirServer and VampirTrace. In Proceedings of the Minisymposium on Scalability and Usability of HPC Programming Tools at PARCO 2007, to appear, Sept. 2007.

[23]

D. Nussbaum and A. Agarwal. Scalability of parallel machines. Communications of the ACM, 34(3):56--61, Mar. 1991.

Digital Library

[24]

F. Petrini, D. J. Kerbyson, and S. Pakin. The case of the missing supercomputer performance: Achieving optimal performance on the 8,192 processors of ASCI Q. In Supercomputing, 2003.

Digital Library

[25]

V. Pillet, J. Labarta, T. Cortes, and S. Girona. PARAVER: A tool to visualise and analyze parallel code. In Proceedings of WoTUG-18: Transputer and Occam Developments, volume 44 of Transputer and Occam Engineering, pages 17--31, Apr. 1995.

[26]

P. C. Roth and B. P. Miller. On-line automated performance diagnosis on thousands of processes. In PPOPP, pages 69--80, Mar 2006.

Digital Library

[27]

M. Schulz. Extracting critical path graphs from MPI applications. In IEEE Cluster, Sep 2005.

[28]

J. P. Singh, J. L. Hennessy, and A. Gupta. Scaling parallel programs for multiprocessors: Methodology and examples. IEEE Computer, 26(7):42--50, July 1993.

Digital Library

[29]

A. Snavely, L. Carrington, N. Wolter, J. Labarta, R. Badia, and A. Purkayastha. A framework for performance modeling and prediction. In Supercomputing, Nov. 2002.

Digital Library

[30]

A. Srivastava and A. Eustace. ATOM: A system for building customized program analysis tools. In ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 196--205, June 1994.

Digital Library

[31]

L. Valiant. A bridging model for parallel computation. Communications of the ACM, 33(8):103--111, Aug. 1990.

Digital Library

[32]

F. C. Wong, R. P. Martin, R. H. Arpaci-Dusseau, and D. E. Culler. Architectural requirements and scalability of the NAS Parallel Benchmarks. In Supercomputing, 1999.

Digital Library

[33]

P. H. Worley. The effect of time constraints on scaled speedup. SIAM J. Sci. Stat. Computing, 11(5):838--858, Sept. 1990.

Digital Library

[34]

L. T. Yang, X. Ma, and F. Mueller. Cross-platform performance prediction of parallel applications using partial execution. In Supercomputing, 2005.

Digital Library

Cited By

Meynet GIehl JDelanoy JLavoué GDupont F(2024)A Workload Prediction Model for 3D Textured Meshes in Webgl ContextProceedings of the 29th International ACM Conference on 3D Web Technology10.1145/3665318.3677156(1-11)Online publication date: 25-Sep-2024
https://dl.acm.org/doi/10.1145/3665318.3677156
Hutter ESolomonik EMohror KArnold DBadia R(2023)Application Performance Modeling via Tensor CompletionProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.1145/3581784.3607069(1-14)Online publication date: 12-Nov-2023
https://dl.acm.org/doi/10.1145/3581784.3607069
Zhang ZGlova ASherwood TBalkind JAamodt TJerger NSwift M(2023)A Prediction System ServiceProceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 210.1145/3575693.3575714(48-60)Online publication date: 27-Jan-2023
https://dl.acm.org/doi/10.1145/3575693.3575714
Show More Cited By

Index Terms

A regression-based approach to scalability prediction
1. Computing methodologies
  1. Modeling and simulation
    1. Model development and analysis

Recommendations

A scalable framework for large time series prediction
Abstract
Knowledge discovery systems are nowadays supposed to store and process very large data. When working with big time series, multivariate prediction becomes more and more complicated because the use of all the variables does not allow to have the ...
Prediction Framework for Potential Tuna Fish Zone in Indonesia
APIT '19: Proceedings of the 2019 Asia Pacific Information Technology Conference

As the promising and futuristic commodity, tuna fish catching becomes one of the most important activities that holds significant impacts for the people life. One of the problem to maximize the efficiency of fishing is to predict appropriately, which ...
Normalized nonconformity measures for regression Conformal Prediction
AIA '08: Proceedings of the 26th IASTED International Conference on Artificial Intelligence and Applications

In this paper we apply Conformal Prediction (CP) to the k-Nearest Neighbours Regression (k-NNR) algorithm and propose a way of extending the typical nonconformity measure used for regression so far. Unlike traditional regression methods which produce ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICS '08: Proceedings of the 22nd annual international conference on Supercomputing

June 2008

390 pages

ISBN:9781605581583

DOI:10.1145/1375527

General Chairs:
Theo Papatheodorou
University of Patras, Greece
,
Utpal Banerjee
Intel (retired), USA
,
Program Chairs:
Avi Mendelson
Intel, Israel
,
Kyle Gallivan
Florida State University, USA

Copyright © 2008 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 June 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ICS08

Sponsor:

ICS08: International Conference on Supercomputing

June 7 - 12, 2008

Island of Kos, Greece

Acceptance Rates

Overall Acceptance Rate 629 of 2,180 submissions, 29%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

178
Total Citations
View Citations
833
Total Downloads

Downloads (Last 12 months)55
Downloads (Last 6 weeks)10

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Meynet GIehl JDelanoy JLavoué GDupont F(2024)A Workload Prediction Model for 3D Textured Meshes in Webgl ContextProceedings of the 29th International ACM Conference on 3D Web Technology10.1145/3665318.3677156(1-11)Online publication date: 25-Sep-2024
https://dl.acm.org/doi/10.1145/3665318.3677156
Hutter ESolomonik EMohror KArnold DBadia R(2023)Application Performance Modeling via Tensor CompletionProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.1145/3581784.3607069(1-14)Online publication date: 12-Nov-2023
https://dl.acm.org/doi/10.1145/3581784.3607069
Zhang ZGlova ASherwood TBalkind JAamodt TJerger NSwift M(2023)A Prediction System ServiceProceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 210.1145/3575693.3575714(48-60)Online publication date: 27-Jan-2023
https://dl.acm.org/doi/10.1145/3575693.3575714
Xie ZLiu JLi JLi DDehnavi MKulkarni MKrishnamoorthy S(2023)MerchandiserProceedings of the 28th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming10.1145/3572848.3577497(204-217)Online publication date: 25-Feb-2023
https://dl.acm.org/doi/10.1145/3572848.3577497
Amaris MCamargo RCordeiro DGoldman ATrystram D(2023)Evaluating execution time predictions on GPU kernels using an analytical model and machine learning techniquesJournal of Parallel and Distributed Computing10.1016/j.jpdc.2022.09.002171:C(66-78)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1016/j.jpdc.2022.09.002
Zhai JJin YChen WZheng WZhai JJin YChen WZheng W(2023)Performance Prediction for Scalability AnalysisPerformance Analysis of Parallel Applications for HPC10.1007/978-981-99-4366-1_6(129-161)Online publication date: 19-Jun-2023
https://doi.org/10.1007/978-981-99-4366-1_6
Zhai JJin YChen WZheng WZhai JJin YChen WZheng W(2023)Graph Analysis for Scalability AnalysisPerformance Analysis of Parallel Applications for HPC10.1007/978-981-99-4366-1_5(101-128)Online publication date: 19-Jun-2023
https://doi.org/10.1007/978-981-99-4366-1_5
Seneviratne SLevy DDe Silva L(2023)A Taxonomy of Performance Forecasting Systems in the Serverless Cloud Computing EnvironmentsServerless Computing: Principles and Paradigms10.1007/978-3-031-26633-1_4(79-120)Online publication date: 12-May-2023
https://doi.org/10.1007/978-3-031-26633-1_4
Sasidharan A(2022)Performance Models for Heterogeneous Iterative ProgramsInternational Journal of Networking and Computing10.15803/ijnc.12.1_13112:1(131-163)Online publication date: 2022
https://doi.org/10.15803/ijnc.12.1_131
Arima EKang MSaba IWeidendorfer JTrinitis CSchulz M(2022)Optimizing Hardware Resource Partitioning and Job Allocations on Modern GPUs under Power CapsWorkshop Proceedings of the 51st International Conference on Parallel Processing10.1145/3547276.3548630(1-10)Online publication date: 29-Aug-2022
https://dl.acm.org/doi/10.1145/3547276.3548630
Show More Cited By

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