NDLI: Accelerating inclusion-based pointer analysis on heterogeneous CPU-GPU systems

Content Provider	IEEE Xplore Digital Library
Author	Yu Su Ding Ye Jingling Xue
Copyright Year	2013
Description	Author affiliation: Sch. of Comput. Sci. & Eng., Univ. of New South Wales, Sydney, NSW, Australia (Yu Su; Ding Ye; Jingling Xue)
Abstract	This paper describes the first implementation of Andersen's inclusion-based pointer analysis for C programs on a heterogeneous CPU-GPU system, where both its CPU and GPU cores are used. As an important graph algorithm, Andersen's analysis is difficult to parallelise because it makes extensive modifications to the structure of the underlying graph, in a way that is highly input-dependent and statically hard to analyse. Existing parallel solutions run on either the CPU or GPU but not both, rendering the underlying computational resources underutilised and the ratios of CPU-only over GPU-only speedups for certain programs (i.e., graphs) unpredictable. We observe that a naive parallel solution of Andersen's analysis on a CPU-GPU system suffers from poor performance due to workload imbalance. We introduce a solution that is centered around a new dynamic workload distribution scheme. The novelty lies in prioritising the distribution of different types of workloads, i.e., graph-rewriting rules in Andersen's analysis to CPU or GPU according to the degrees of the processing unit's suitability for processing them. This scheme is effective when combined with synchronisation-free execution of tasks (i.e., graph-rewriting rules) and difference propagation of points-to information between the CPU and GPU. For a set of seven C benchmarks evaluated, our CPU-GPU solution outperforms (on average) (1) the CPU-only solution by 50.6%, (2) the GPU-only solution by 78.5%, and (3) an oracle solution that behaves as the faster of (1) and (2) on every benchmark by 34.6%.
Sponsorship	IEEE Comput. Soc.
Starting Page	149
Ending Page	158
File Size	1315259
Page Count	10
File Format	PDF
ISBN	9781479907304
DOI	10.1109/HiPC.2013.6799110
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2013-12-18
Publisher Place	India
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Graphics processing units Semantics Australia Benchmark testing Weaving
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

Accelerating inclusion-based pointer analysis on heterogeneous cpu-gpu systems.

GPU Computing Pipeline Inefficiencies and Optimization Opportunities in Heterogeneous CPU-GPU Processors

Communication and Memory Access Latency Characteristics of CPU/GPU Heterogeneous Cluster

A scalable and portable approach to accelerate hybrid HPL on heterogeneous CPU-GPU clusters

Accelerating Exact Similarity Search on CPU-GPU Systems

Characterizing the performance benefits of fused CPU/GPU systems using FusionSim

Accelerating large vocabulary continuous speech recognition on heterogeneous CPU-GPU platforms

Component Allocation Optimization for Heterogeneous CPU-GPU Embedded Systems

Accelerating MapReduce on a coupled CPU-GPU architecture

Accelerating inclusion-based pointer analysis on heterogeneous CPU-GPU systems

Similar Documents

Accelerating inclusion-based pointer analysis on heterogeneous cpu-gpu systems.

GPU Computing Pipeline Inefficiencies and Optimization Opportunities in Heterogeneous CPU-GPU Processors

Communication and Memory Access Latency Characteristics of CPU/GPU Heterogeneous Cluster

A scalable and portable approach to accelerate hybrid HPL on heterogeneous CPU-GPU clusters

Accelerating Exact Similarity Search on CPU-GPU Systems

Characterizing the performance benefits of fused CPU/GPU systems using FusionSim

Accelerating large vocabulary continuous speech recognition on heterogeneous CPU-GPU platforms

Component Allocation Optimization for Heterogeneous CPU-GPU Embedded Systems

Accelerating MapReduce on a coupled CPU-GPU architecture

Accelerating inclusion-based pointer analysis on heterogeneous CPU-GPU systems