NDLI: General data structure expansion for multi-threading

Please wait, while we are loading the content...

Look up!: your future is in the cloud

Optimizing database-backed applications with query synthesis

Fast condensation of the program dependence graph

Rely-guarantee references for refinement types over aliased mutable data

Terra: a multi-stage language for high-performance computing

Programming languages in security: keynote

CLAP: recording local executions to reproduce concurrency failures

Formal verification of SSA-based optimizations for LLVM

Almost-correct specifications: a modular semantic framework for assigning confidence to warnings

General data structure expansion for multi-threading

Thresher: precise refutations for heap reachability

Using managed runtime systems to tolerate holes in wearable memories

P: safe asynchronous event-driven programming

$SPL^{LIFT}:$ statically analyzing software product lines in minutes instead of years

Verifying higher-order programs with the dijkstra monad

Hybrid context-sensitivity for points-to analysis

Modular verification of linearizability with non-fixed linearization points

A general constraint-centric scheduling framework for spatial architectures

Automated feedback generation for introductory programming assignments

Scalable variable and data type detection in a binary rewriter

Harmonizing classes, functions, tuples, and type parameters in virgil iii

SMAT: an input adaptive auto-tuner for sparse matrix-vector multiplication

CONCURRIT: a domain specific language for reproducing concurrency bugs

Compiler testing via a theory of sound optimisations in the C11/C++11 memory model

Reasoning about nondeterminism in programs

AutoSynch: an automatic-signal monitor based on predicate tagging

TRANSIT: specifying protocols with concolic snippets

Limitations of partial compaction: towards practical bounds

Quipper: a scalable quantum programming language

Finding optimum abstractions in parametric dataflow analysis

Monadic abstract interpreters

Fast algorithms for Dyck-CFL-reachability with applications to alias analysis

Translation validation for a verified OS kernel

Steal Tree: low-overhead tracing of work stealing schedulers

Complete completion using types and weights

Fast RMWs for TSO: semantics and implementation

It's alive! continuous feedback in UI programming

When polyhedral transformations meet SIMD code generation

Dynamic determinacy analysis

Taming compiler fuzzers

Natural proofs for structure, data, and separation

Concurrent libraries with foresight

Reconciling exhaustive pattern matching with objects

How to combine widening and narrowing for non-monotonic systems of equations

Asynchronous functional reactive programming for GUIs

Static analysis for probabilistic programs: inferring whole program properties from finitely many paths

Machine-verified network controllers

Halide: a language and compiler for optimizing parallelism, locality, and recomputation in image processing pipelines

General data structure expansion for multi-threading

Content Provider	ACM Digital Library
Author	Ko, Hou-Jen Yu, Hongtao Li, Zhiyuan
Abstract	Among techniques for parallelizing sequential codes, privatization is a common and significant transformation performed by both compilers and runtime parallelizing systems. Without privatization, repetitive updates to the same data structures often introduce spurious data dependencies that hide the inherent parallelism. Unfortunately, it remains a significant challenge to compilers to automatically privatize dynamic and recursive data structures which appear frequently in real applications written in languages such as C/C++. This is because such languages lack a naming mechanism to define the address range of a pointer-based data structure, in contrast to arrays with explicitly declared bounds. In this paper we present a novel solution to this difficult problem by expanding general data structures such that memory accesses issued from different threads to contentious data structures are directed to different data fields. Based on compile-time type checking and a data dependence graph, this aggressive extension to the traditional scalar and array expansion isolates the address ranges among different threads, without struggling with privatization based on thread-private stacks, such that the targeted loop can be effectively parallelized. With this method fully implemented in GCC, experiments are conducted on a set of programs from well-known benchmark suites such as Mibench, MediaBench II and SPECint. Results show that the new approach can lead to a high speedup when executing the transformed code on multiple cores.
Starting Page	243
Ending Page	252
Page Count	10
File Format	PDF
ISBN	9781450320146
DOI	10.1145/2491956.2462182
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2013-06-16
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Multithreading Privatization Parallelization
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

General data structure expansion for multi-threading

Scalable Data-Privatization Threading for Hybrid MPI/OpenMP Parallelization of Molecular Dynamics

Boosting single-thread performance in multi-core systems through fine-grain multi-threading

A Scalable Data-Privatization Threading Algorithm for Hybrid MPI/OpenMP Parallelization of Molecular Dynamics

A cost-driven compilation framework for speculative parallelization of sequential programs

Analysis of Scalable Data-Privatization Threading Algorithms for Hybrid MPI/OpenMP Parallelization of Molecular Dynamics

Speculative separation for privatization and reductions.

A general compiler framework for speculative multithreading

Mitosis compiler: an infrastructure for speculative threading based on pre-computation slices

General data structure expansion for multi-threading

Similar Documents

General data structure expansion for multi-threading

Scalable Data-Privatization Threading for Hybrid MPI/OpenMP Parallelization of Molecular Dynamics

Boosting single-thread performance in multi-core systems through fine-grain multi-threading

A Scalable Data-Privatization Threading Algorithm for Hybrid MPI/OpenMP Parallelization of Molecular Dynamics

A cost-driven compilation framework for speculative parallelization of sequential programs

Analysis of Scalable Data-Privatization Threading Algorithms for Hybrid MPI/OpenMP Parallelization of Molecular Dynamics

Speculative separation for privatization and reductions.

A general compiler framework for speculative multithreading

Mitosis compiler: an infrastructure for speculative threading based on pre-computation slices

General data structure expansion for multi-threading