NDLI: Reducing contention through priority updates ( SPAA '13 )

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

Fast greedy algorithms in mapreduce and streaming

Storage and search in dynamic peer-to-peer networks

Brief announcement: truly parallel burrows-wheeler compression and decompression

IRIS: a robust information system against insider dos-attacks

Coalescing-branching random walks on graphs

Work-efficient matrix inversion in polylogarithmic time

Profitable scheduling on multiple speed-scalable processors

Cloud scheduling with setup cost

Reduced hardware transactions: a new approach to hybrid transactional memory

Broadcasting in logarithmic time for ad hoc network nodes on a line using mimo

Brief announcement: locality in wireless scheduling

SybilCast: broadcast on the open airwaves (extended abstract)

Parallel rotor walks on finite graphs and applications in discrete load balancing

Communication optimal parallel multiplication of sparse random matrices

Nonclairvoyant sleep management and flow-time scheduling on multiple processors

Efficient online scheduling for deadline-sensitive jobs: extended abstract

Recursive design of hardware priority queues

Expected sum and maximum of displacement of random sensors for coverage of a domain: extended abstract

Brief announcement: universally truthful secondary spectrum auctions

On-the-fly pipeline parallelism

Parallel graph decompositions using random shifts

Communication efficient gaussian elimination with partial pivoting using a shape morphing data layout

Reallocation problems in scheduling

Locality-aware task management for unstructured parallelism: a quantitative limit study

Drop the anchor: lightweight memory management for non-blocking data structures

On dynamics in selfish network creation

Brief announcement: online batch scheduling for flow objectives

Reducing contention through priority updates

A constant factor approximation algorithm for the storage allocation problem: extended abstract

Optimal patrolling of fragmented boundaries

Efficient scheduling to minimize calibrations

Balls-into-bins with nearly optimal load distribution

Scalable statistics counters

Brief announcement: set it and forget it - approximating the set once strip cover problem

HEX: scaling honeycombs is easier than scaling clock trees

Non-monetary fair scheduling: a cooperative game theory approach

Brief announcement: between all and nothing - versatile aborts in hardware transactional memory

Brief announcement: towards a fully-articulated pessimistic distributed transactional memory

Brief announcement: a game-theoretic model motivated by the darpa network challenge

Reducing contention through priority updates ( SPAA '13 )

Content Provider	ACM Digital Library
Author	Shun, Julian Fineman, Jeremy T. Blelloch, Guy E. Gibbons, Phillip B.
Abstract	Memory contention can be a serious performance bottleneck in concurrent programs on shared-memory multicore architectures. Having all threads write to a small set of shared locations, for example, can lead to orders of magnitude loss in performance relative to all threads writing to distinct locations, or even relative to a single thread doing all the writes. Shared write access, however, can be very useful in parallel algorithms, concurrent data structures, and protocols for communicating among threads. We study the "priority update" operation as a useful primitive for limiting write contention in parallel and concurrent programs. A priority update takes as arguments a memory location, a new value, and a comparison function $>_{p}$ that enforces a partial order over values. The operation atomically compares the new value with the current value in the memory location, and writes the new value only if it has higher priority according to $>_{p}.$ On the implementation side, we show that if implemented appropriately, priority updates greatly reduce memory contention over standard writes or other atomic operations when locations have a high degree of sharing. This is shown both experimentally and theoretically. On the application side, we describe several uses of priority updates for implementing parallel algorithms and concurrent data structures, often in a way that is deterministic, guarantees progress, and avoids serial bottlenecks. We present experiments showing that a variety of such algorithms and data structures perform well under high degrees of sharing. Given the results, we believe that the priority update operation serves as a useful parallel primitive and good programming abstraction as (1) the user largely need not worry about the degree of sharing, (2) it can be used to avoid non-determinism since, in the common case when $>_{p}$ is a total order, priority updates commute, and (3) it has many applications to programs using shared data.
Starting Page	152
Ending Page	163
Page Count	12
File Format	PDF
ISBN	9781450315722
DOI	10.1145/2486159.2486189
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2013-07-23
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Parallel programming Memory contention
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

Reducing contention through priority updates ( PPoPP '13 )

Reducing contention through priority updates

Reducing contention through priority updates (2013)

Reducing contention through priority updates (poster paper).

Reducing contention through priority updates (2013)

Memory models: a case for rethinking parallel languages and hardware ( SPAA '09 )

Reducing lock contention on multi-core platforms

Contention Management Policy in Software Transactional Memory in Parallel and Distributed Systems

Reducing memory contention in shared memory multiprocessors

Reducing contention through priority updates ( SPAA '13 )

Similar Documents

Reducing contention through priority updates ( PPoPP '13 )

Reducing contention through priority updates

Reducing contention through priority updates (2013)

Reducing contention through priority updates (poster paper).

Reducing contention through priority updates (2013)

Memory models: a case for rethinking parallel languages and hardware ( SPAA '09 )

Reducing lock contention on multi-core platforms

Contention Management Policy in Software Transactional Memory in Parallel and Distributed Systems

Reducing memory contention in shared memory multiprocessors

Reducing contention through priority updates ( SPAA '13 )