NDLI: SD3: An Efficient Dynamic Data-Dependence Profiling Mechanism

Content Provider	IEEE Xplore Digital Library
Author	Minjang Kim Lakshminarayana, N.B. Hyesoon Kim Chi-Keung Luk
Copyright Year	1968
Abstract	As multicore processors are deployed in mainstream computing, the need for software tools to help parallelize programs is increasing dramatically. Data-dependence profiling is an important program analysis technique to exploit parallelism in serial programs. More specifically, manual, semiautomatic, or automatic parallelization can use the outcomes of data-dependence profiling to guide where and how to parallelize in a program. However, state-of-the-art data-dependence profiling techniques consume extremely huge resources as they suffer from two major issues when profiling large and long-running applications: 1) runtime overhead and 2) memory overhead. Existing data-dependence profilers are either unable to profile large-scale applications with a typical resource budget or only report very limited information. In this paper, we propose an efficient approach to data-dependence profiling that can address both runtime and memory overhead in a single framework. Our technique, called SD³, reduces the runtime overhead by parallelizing the dependence profiling step itself. To reduce the memory overhead, we compress memory accesses that exhibit stride patterns and compute data dependences directly in a compressed format. We demonstrate that SD³ reduces the runtime overhead when profiling SPEC 2006 by a factor of 4.1× and 9.7× on eight cores and 32 cores, respectively. For the memory overhead, we successfully profile 22 SPEC 2006 benchmarks with the reference input, while the previous approaches fail even with the train input. In some cases, we observe more than a 20× improvement in memory consumption and a 16× speedup in profiling time when 32 cores are used. We also demonstrate the usefulness of SD³ by showing manual parallelization followed by data dependence profiling results.
Sponsorship	IEEE Computer Society Technical Committee on Distributed Process IEEE Computer Society Technical Committee on VLSI IEEE Technical Committee on Computer Architecture IEEE Computer Society
Starting Page	2516
Ending Page	2530
Page Count	15
File Size	2578444
File Format	PDF
ISSN	00189340
Volume Number	62
Issue Number	12
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2013-01-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Runtime Memory management Heuristic algorithms Pararell processing Resource management Benchmark testing parallelization Profiling data dependence parallel programming program analysis compression
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Computational Theory and Mathematics Software Hardware and Architecture

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

Evaluating automatic parallelization in SUIF

Space and time optimal parallel sequence alignments

Parallelization of a dynamic unstructured algorithm using three leading programming paradigms

Exploiting Application Data-Parallelism on Dynamically Reconfigurable Architectures: Placement and Architectural Considerations

Program structuring for effective parallel portability

Complexity-Effective Contention Management with Dynamic Backoff for Transactional Memory Systems

Static and dynamic evaluation of data dependence analysis techniques

Efficient algorithms for data distribution on distributed memory parallel computers

A basic-cycle calculation technique for efficient dynamic data redistribution

SD3: An Efficient Dynamic Data-Dependence Profiling Mechanism

Similar Documents

Evaluating automatic parallelization in SUIF

Space and time optimal parallel sequence alignments

Parallelization of a dynamic unstructured algorithm using three leading programming paradigms

Exploiting Application Data-Parallelism on Dynamically Reconfigurable Architectures: Placement and Architectural Considerations

Program structuring for effective parallel portability

Complexity-Effective Contention Management with Dynamic Backoff for Transactional Memory Systems

Static and dynamic evaluation of data dependence analysis techniques

Efficient algorithms for data distribution on distributed memory parallel computers

A basic-cycle calculation technique for efficient dynamic data redistribution

SD3: An Efficient Dynamic Data-Dependence Profiling Mechanism