NDLI: Variability of data dependences and control flow

Content Provider	IEEE Xplore Digital Library
Author	Edler von Koch, T.J.K. Franke, B.
Copyright Year	2014
Description	Author affiliation: Inst. for Comput. Syst. Archit., Univ. of Edinburgh, Edinburgh, UK (Edler von Koch, T.J.K.; Franke, B.)
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.
Sponsorship	IEEE Comput. Soc.
Starting Page	180
Ending Page	189
File Size	1738781
Page Count	10
File Format	PDF
ISBN	9781479936045
e-ISBN	9781479936069
DOI	10.1109/ISPASS.2014.6844482
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2014-03-23
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Benchmark testing Instruments Merging Vectors Educational institutions Software Histograms
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