NDLI: A statistical approach to branch modeling in static program performance prediction

Content Provider	IEEE Xplore Digital Library
Author	Gautama, H. van Gemund, A.J.C.
Copyright Year	2003
Description	Author affiliation: Fac. of Inf. Technol. and Syst., Delft Univ. of Technol., Netherlands (Gautama, H.; van Gemund, A.J.C.)
Abstract	Current static performance prediction methods have been less successful in statistically accounting for program workload distribution due to input data set variability, of which data-dependent branches are usually the most important contributors. While data-dependent basic block execution time is often characterized in terms of, e.g., mean and variance, branching conditions still are typically characterized by only one parameter, usually known as the truth probability. We propose and evaluate three statistical approaches to modeling branching behavior, to be used within a compositional method to predict program execution time distribution. The approaches are coined the empirical, the Bernoulli, and the ARP (Alternating Renewal Processes) approach. While the Empirical approach is based on measuring branching behavior in terms of the surrounding loop construct, the other approaches aim at deriving a statistical model of the branch itself, which enables a higher level of compositionality. Our measurement results, based on synthetic as well as on real programs, show that the Empirical approach delivers the highest accuracy, whereas the alternative approaches trade accuracy for compositionality. For Markovian branches, the compositional approaches deliver high prediction accuracy. In contrast to intuition and our synthetic experiments, in real programs the two-parameter ARP approach does not always outperform the one-parameter Bernoulli approach.
Sponsorship	IEEE Comput. Soc Tech. Committee on Parallel Process. IEEE Comput. Soc. Tech. Committee on Comput. Archit. IEEE Comput. Soc. Tech. Committee on Distrib. Process. ACM SIGARCH
File Size	335432
File Format	PDF
ISBN	0769519261
ISSN	15302075
DOI	10.1109/IPDPS.2003.1213503
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2003-04-22
Publisher Place	France
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Predictive models Accuracy Stochastic processes Costs Convolution Information technology Prediction methods Probability Performance analysis Sorting
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

An approach for RNA secondary structure prediction based on Bayesian network

A WCET-oriented static branch prediction scheme for real time systems

A grey prediction model for the static coefficients of bridge cross section

Program Interferometry

Static performance prediction of data-dependent programs (2000).

Static Correlated Branch Prediction (1999)

Simulation as a tool for life cycle cost analysis

The accuracy of fault prediction in modified code - statistical model vs. expert estimation

Binomial linear predictive approach to texture modeling

A statistical approach to branch modeling in static program performance prediction

Similar Documents

An approach for RNA secondary structure prediction based on Bayesian network

A WCET-oriented static branch prediction scheme for real time systems

A grey prediction model for the static coefficients of bridge cross section

Program Interferometry

Static performance prediction of data-dependent programs (2000).

Static Correlated Branch Prediction (1999)

Simulation as a tool for life cycle cost analysis

The accuracy of fault prediction in modified code - statistical model vs. expert estimation

Binomial linear predictive approach to texture modeling

A statistical approach to branch modeling in static program performance prediction