NDLI: Internally deterministic parallel algorithms can be fast

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

Scalable framework for mapping streaming applications onto multi-GPU systems

Communication avoiding successive band reduction

A hybrid approach of OpenMP for clusters

A GPU implementation of inclusion-based points-to analysis

A methodology for creating fast wait-free data structures

Internally deterministic parallel algorithms can be fast

GKLEE: concolic verification and test generation for GPUs

Lock cohorting: a general technique for designing NUMA locks

Automatic communication optimizations through memory reuse strategies

LHlf: lock-free linear hashing (poster paper)

A performance analysis framework for identifying potential benefits in GPGPU applications

Faster topology-aware collective algorithms through non-minimal communication

DOJ: dynamically parallelizing object-oriented programs

Scalable GPU graph traversal

Concurrent tries with efficient non-blocking snapshots

Deterministic parallel random-number generation for dynamic-multithreading platforms

Algorithm-based fault tolerance for dense matrix factorizations

Revisiting the combining synchronization technique

FlexBFS: a parallelism-aware implementation of breadth-first search on GPU

Wait-free linked-lists

Efficient performance evaluation of memory hierarchy for highly multithreaded graphics processors

Efficient SIMD code generation for irregular kernels

S: a scripting language for high-performance RESTful web services

GPU-based NFA implementation for memory efficient high speed regular expression matching

A speculation-friendly binary search tree

Scalable parallel minimum spanning forest computation

Efficient deadlock avoidance for streaming computation with filtering

A work-stealing scheduler for X10's task parallelism with suspension

Programming parallel embedded and consumer applications in OpenMP superscalar

Scalable parallel debugging with statistical assertions

Extending a C-like language for portable SIMD programming

PARRAY: a unifying array representation for heterogeneous parallelism

An overview of Medusa: simplified graph processing on GPUs

Verification of software barriers

Optimizing remote accesses for offloaded kernels: application to high-level synthesis for FPGA

Collective algorithms for sub-communicators

Using GPU's to accelerate stencil-based computation kernels for the development of large scale scientific applications on heterogeneous systems

Synchronization views for event-loop actors

Mechanizing the expert dense linear algebra developer

CPHASH: a cache-partitioned hash table

The boat hull model: adapting the roofline model to enable performance prediction for parallel computing

RACECAR: a heuristic for automatic function specialization on multi-core heterogeneous systems

Speculative parallelization on GPGPUs

A lock-free, array-based priority queue

Adapting the polyhedral model as a framework for efficient speculative parallelization

An infrastructure for dynamic optimization of parallel programs

An overview of CMPI: network performance aware MPI in the cloud

Automatic datatype generation and optimization

OpenCL as a unified programming model for heterogeneous CPU/GPU clusters

NDetermin: inferring nondeterministic sequential specifications for parallelism correctness

BDDT:: block-level dynamic dependence analysisfor deterministic task-based parallelism

Concurrent breakpoints

Portable parallel performance from sequential, productive, embedded domain-specific languages

Establishing a Miniapp as a programmability proxy

Communication-centric optimizations by dynamically detecting collective operations

OpenMP-style parallelism in data-centered multicore computing with R

Performance analysis of parallel constraint-based local search

Internally deterministic parallel algorithms can be fast

Content Provider	ACM Digital Library
Author	Shun, Julian Fineman, Jeremy T. Blelloch, Guy E. Gibbons, Phillip B.
Abstract	The virtues of deterministic parallelism have been argued for decades and many forms of deterministic parallelism have been described and analyzed. Here we are concerned with one of the strongest forms, requiring that for any input there is a unique dependence graph representing a trace of the computation annotated with every operation and value. This has been referred to as internal determinism, and implies a sequential semantics---i.e., considering any sequential traversal of the dependence graph is sufficient for analyzing the correctness of the code. In addition to returning deterministic results, internal determinism has many advantages including ease of reasoning about the code, ease of verifying correctness, ease of debugging, ease of defining invariants, ease of defining good coverage for testing, and ease of formally, informally and experimentally reasoning about performance. On the other hand one needs to consider the possible downsides of determinism, which might include making algorithms (i) more complicated, unnatural or special purpose and/or (ii) slower or less scalable. In this paper we study the effectiveness of this strong form of determinism through a broad set of benchmark problems. Our main contribution is to demonstrate that for this wide body of problems, there exist efficient internally deterministic algorithms, and moreover that these algorithms are natural to reason about and not complicated to code. We leverage an approach to determinism suggested by Steele (1990), which is to use nested parallelism with commutative operations. Our algorithms apply several diverse programming paradigms that fit within the model including (i) a strict functional style (no shared state among concurrent operations), (ii) an approach we refer to as deterministic reservations, and (iii) the use of commutative, linearizable operations on data structures. We describe algorithms for the benchmark problems that use these deterministic approaches and present performance results on a 32-core machine. Perhaps surprisingly, for all problems, our internally deterministic algorithms achieve good speedup and good performance even relative to prior nondeterministic solutions.
Starting Page	181
Ending Page	192
Page Count	12
File Format	PDF
ISBN	9781450311601
DOI	10.1145/2145816.2145840
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2012-02-25
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Parallel programming Commutative operations Deterministic parallelism Graph algorithms Geometry algorithms Parallel algorithms String processing Sorting
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

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