A runtime approach for estimating resource usage
Pages 261 - 266
Abstract
In the era of information explosion, a program is necessary to be scalable. Therefore, scalability analysis becomes very important in software verification and validation. However, current approaches to empirical scalability analysis remain limitations related to the number of supported models and performance. In this paper, we propose a runtime approach for estimating the program resource usage with two aims: evaluating the program scalability and revealing potential errors. In this approach, the resource usage of a program is first observed when it is executed on inputs with different scales, the observed results are then fitted on a model of the usage according to the program's input. Comparing to other approaches, ours supports diverse models to illustrate the resource usage, i.e., linear-log, power-law, polynomial, etc. We currently focus on the computation cost and stack frames usage as two representatives of resource usage, but the approach can be extended to other kinds of resource. The experimental result shows that our approach achieves more precise estimation and better performance than other state-of-the-art approaches.
References
[1]
C. Beath, I. Becerra-Fernandez, J. Ross, and J. Short. Finding value in the information explosion. MIT Sloan Management Review, 53(4): 18, 2012.
[2]
R. Dara, S. Li, W. Liu, A. Smith-Ghorbani, and L. Tahvildari. Using dynamic execution data to generate test cases. pages 433--436, 2009.
[3]
S. F. Goldsmith. Measuring empirical computational complexity. PhD thesis, 2009. AAI3426551.
[4]
S. F. Goldsmith, A. S. Aiken, and D. S. Wilkerson. Measuring empirical computational complexity. In Proc. of the the 6th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering, ESEC-FSE '07, pages 395--404. ACM, 2007.
[5]
B. S. Gulavani and S. Gulwani. A numerical abstract domain based on expression abstraction and max operator with application in timing analysis. In Proc. of the 20th international conference on Computer Aided Verification, CAV '08, pages 370--384. Springer-Verlag, 2008.
[6]
S. Gulwani, K. K. Mehra, and T. Chilimbi. Speed: precise and efficient static estimation of program computational complexity. In Proc. of the 36th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, POPL '09, pages 127--139. ACM, 2009.
[7]
M. Hofmann and S. Jost. Static prediction of heap space usage for first-order functional programs. In Proc. of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, POPL '03, pages 185--197. ACM, 2003.
[8]
M. Hofmann and S. Jost. Type-based amortised heap-space analysis. In Proc. of the 15th European conference on Programming Languages and Systems, ESOP'06, pages 22--37. Springer-Verlag, 2006.
[9]
H. Ince. Non-parametric regression methods. Computational Management Science, 3(2): 161--174, 2006.
[10]
S. Jost, H. wolfgang Loidl, K. Hammond, N. Scaife, and M. Hofmann. 'carbon credits' for resource-bounded computations using amortised analysis. In In Formal Methods (FM'09), pages 354--36. Springer, 2009.
[11]
M. Kluge, A. Knupfer, and W. E. Nagel. Knowledge based automatic scalability analysis and extrapolation for mpi programs. In Proc. of the 11th international Euro-Par conference on Parallel Processing, Euro-Par'05, pages 176--184. Springer-Verlag, 2005.
[12]
H. H. Liu. Software Performance and Scalability: A Quantitative Approach. Wiley Publishing, 2009.
[13]
C. S. Păsăreanu, P. C. Mehlitz, D. H. Bushnell, K. Gundy-Burlet, M. Lowry, S. Person, and M. Pape. Combining unit-level symbolic execution and system-level concrete execution for testing nasa software. In Proc. of the 2008 international symposium on Software testing and analysis, ISSTA '08, pages 15--26. ACM, 2008.
[14]
M. Rosendahl. Automatic complexity analysis. In Proc. of the fourth international conference on Functional programming languages and computer architecture, FPCA '89, pages 144--156. ACM, 1989.
Index Terms
- A runtime approach for estimating resource usage
Recommendations
Resource usage analysis
It is an important criterion of program correctness that a program accesses resources in a valid manner. For example, a memory region that has been allocated should eventually be deallocated, and after the deallocation, the region should no longer be ...
Estimating Worst-case Resource Usage by Resource-usage-aware Fuzzing
Fundamental Approaches to Software EngineeringAbstractWorst-case resource usage provides a useful guidance in the design, configuration and deployment of software, especially when it runs under a context with limited amount of resources. Static resource-bound analysis can provide sound upper bounds ...
A Game Theoretic Approach for Resource Usage
Revised Selected Papers of the 5th International Workshop on Resource Discovery - Volume 8194Existing web infrastructures support the publication of a tremendous amount of resources, and over the past few years Data Resource Usage has become an everyday task for millions of users all over the world. In this work we model Resource Usage as a ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
December 2013
345 pages
ISBN:9781450324540
DOI:10.1145/2542050
- General Chairs:
- Thang Huynh Quyet,
- Binh Nguyen Thanh,
- Program Chairs:
- Tien Do Van,
- Marc Bui,
- Son Ngo Hong
Copyright © 2013 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
- SOICT: School of Information and Communication Technology - HUST
- NAFOSTED: The National Foundation for Science and Technology Development
- ACM Vietnam Chapter: ACM Vietnam Chapter
- Danang Univ. of Technol.: Danang University of Technology
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 05 December 2013
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- Vietnam National University, Hanoi
Conference
SoICT '13
Sponsor:
- SOICT
- NAFOSTED
- ACM Vietnam Chapter
- Danang Univ. of Technol.
SoICT '13: 4th International Symposium on Information and Communication Technology
December 5 - 6, 2013
Danang, Vietnam
Acceptance Rates
SoICT '13 Paper Acceptance Rate 40 of 80 submissions, 50%;
Overall Acceptance Rate 147 of 318 submissions, 46%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 61Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 16 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in