Variability of data dependences and control flow

T.J.K. Edler von Koch, B. Franke

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Thread-level speculation and profile-guided parallelization techniques exploit the fact that many statically detected data and control flow dependences do not manifest themselves in every possible program execution. Instead, many of these may-dependences only occur infrequently, e.g. for some corner cases, or not at all for any legal program input. While the effectiveness of dynamic parallelization techniques critically depends on the absence of such dependences, not much is known about their nature. In this paper, we present an empirical analysis and characterization of the variability of both data dependences and control flow across program runs. We run the CBENCH benchmark suite with 100 randomly chosen input data sets and record complete control and data flow traces. Based on these traces, we build a whole-program control and data flow graph (CDFG) for each run and compare the resulting graphs to obtain a measure of the variance in the observed control and data flow. We show that, on average, the cumulative profile information gathered with at least 55, and up to 100, different input data sets is needed to achieve full coverage of the data flow observed across all runs. For control flow, the figure stands at 46 and 100 data sets, respectively. This suggests that profile-guided parallelization needs to be applied with utmost care, as misclassification of sequential loops as parallel was observed even when up to 94 input data sets are used.
Original languageEnglish
Title of host publicationPerformance Analysis of Systems and Software (ISPASS), 2014 IEEE International Symposium on
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages180-189
Number of pages10
ISBN (Print)978-1-4799-3604-5
DOIs
Publication statusPublished - 1 Mar 2014

Keywords

  • data flow analysis
  • parallel processing
  • program control structures
  • CBENCH benchmark suite
  • CDFG
  • control flow dependences
  • data dependence variability
  • data flow graph
  • data flow traces
  • dynamic parallelization techniques
  • legal program input
  • may-dependences
  • profile-guided parallelization techniques
  • program execution
  • statically detected data
  • thread-level speculation
  • whole-program control
  • Benchmark testing
  • Educational institutions
  • Histograms
  • Instruments
  • Merging
  • Software
  • Vectors

Fingerprint

Dive into the research topics of 'Variability of data dependences and control flow'. Together they form a unique fingerprint.

Cite this