Entry Wagner:1994:ASE from sigplan1990.bib

Last update: Thu Apr 12 03:37:15 MDT 2012                Valid HTML 3.2!

Index sections

Top | Symbols | Numbers | Math | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

BibTeX entry

@Article{Wagner:1994:ASE,
  author =       "Tim A. Wagner and Vance Maverick and Susan L. Graham
                 and Michael A. Harrison",
  title =        "Accurate Static Estimators for Program Optimization",
  journal =      j-SIGPLAN,
  volume =       "29",
  number =       "6",
  pages =        "85--96",
  month =        jun,
  year =         "1994",
  CODEN =        "SINODQ",
  DOI =          "http://doi.acm.org/10.1145/178243.178251",
  ISBN =         "0-89791-598-4",
  ISBN-13 =      "978-0-89791-598-4",
  ISSN =         "0362-1340 (print), 1523-2867 (print), 1558-1160 (electronic)",
  ISSN-L =       "0362-1340",
  bibdate =      "Wed Jun 18 16:26:55 MDT 2008",
  bibsource =    "http://portal.acm.org/;
                 http://www.acm.org/pubs/contents/proceedings/pldi/178243/index.html",
  URL =          "http://www.acm.org:80/pubs/citations/proceedings/pldi/178243/p85-wagner/",
  abstract =     "Determining the relative execution frequency of
                 program regions is essential for many important
                 optimization techniques, including register allocation,
                 function inlining, and instruction scheduling.
                 Estimates derived from profiling with sample inputs are
                 generally regarded as the most accurate source of this
                 information; static (compile-time) estimates are
                 considered to be distinctly inferior. If static
                 estimates were shown to be competitive, however, their
                 convenience would outweigh minor gains from profiling,
                 and they would provide a sound basis for optimization
                 when profiling is impossible. We use quantitative
                 metrics to compare estimates from static analysis to
                 those derived from profiles. For C programs, simple
                 techniques for predicting branches and loop counts
                 suffice to estimate intraprocedural frequency patterns
                 with high accuracy. To determine inter-procedural
                 estimates successfully, we combine function-level
                 information with a Markov model of control flow over
                 the call graph to produce arc and basic block frequency
                 estimates for the entire program. For a suite of 14
                 programs, including the C programs from the SPEC92
                 benchmark suite, we demonstrate that static estimates
                 are competitive with those derived from profiles. Using
                 simple heuristics, we can determine the most frequently
                 executed blocks in each function with 81\% accuracy.
                 With the Markov model, we identify 80\% of the
                 frequently called functions. Combining the two
                 techniques, we identify 76\% of the most frequently
                 executed call sites.",
  acknowledgement = ack-nhfb,
  annote =       "Published as part of the Proceedings of PLDI'94.",
  classification = "C1180 (Optimisation techniques); C4240 (Programming
                 and algorithm theory); C6110 (Systems analysis and
                 programming); C6150C (Compilers, interpreters and other
                 processors)",
  conflocation = "Orlando, FL, USA; 20-24 June 1994",
  conftitle =    "ACM SIGPLAN '94 Conference on Programming Language
                 Design and Implementation (PLDI)",
  corpsource =   "Div. of Comput. Sci., California Univ., Berkeley, CA,
                 USA",
  keywords =     "algorithms; branches; C programs; call graph; control
                 flow; execution frequency; experimentation; function
                 frequency; function inlining; function-level
                 information; heuristics; instruction scheduling;
                 intra-procedural frequency patterns; languages; loop
                 counts; Markov model; Markov processes; optimisation;
                 performance; profiling; program compilers; program
                 optimization; program regions; programming; programming
                 theory; quantitative metrics; register allocation;
                 software metrics; SPEC92 benchmark suite; static
                 analysis; static compile-time estimates; static
                 estimators",
  sponsororg =   "ACM",
  subject =      "{\bf D.3.4} Software, PROGRAMMING LANGUAGES,
                 Processors, Optimization. {\bf D.3.4} Software,
                 PROGRAMMING LANGUAGES, Processors, Compilers. {\bf
                 F.2.2} Theory of Computation, ANALYSIS OF ALGORITHMS
                 AND PROBLEM COMPLEXITY, Nonnumerical Algorithms and
                 Problems, Computations on discrete structures. {\bf
                 D.3.2} Software, PROGRAMMING LANGUAGES, Language
                 Classifications, C. {\bf D.3.3} Software, PROGRAMMING
                 LANGUAGES, Language Constructs and Features, Control
                 structures.",
  treatment =    "P Practical; T Theoretical or Mathematical",
}

Related entries