NDLI: Dynamic circular work-stealing deque

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

Randomized qeue management for DiffServ

Coloring unstructured radio networks

Windows scheduling of arbitrary length jobs on parallel machines

An adaptive power conservation scheme for heterogeneous wireless sensor networks with node redeployment

The expansion and mixing time of skip graphs with applications

Processor efficient parallel matching

A truthful mechanism for the non-utilitarian minimum radius spanning tree problem

A segmented parallel-prefix VLSI circuit with small delays for small segments

Weighted distributed hash tables

Using elimination to implement scalable and lock-free FIFO queues

Dynamic page migration with stochastic requests

Radio communication in random graphs: extended abstract

Randomization does not reduce the average delay in parallel packet switches

Name independent routing for growth bounded networks

Parallel scheduling of complex dags under uncertainty

Irrigating ad hoc networks in constant time

Decentralized algorithms using both local and random probes for P2P load balancing

Parallelizing time with polynomial circuits

Selfish routing with incomplete information

A forward planning situated protocol for data propagation in wireless sensor networks based on swarm intelligence techniques

Concurrent cache-oblivious b-trees

Collaborate with strangers to find own preferences

Broadcasting on networks of workstations

Oblivious routing on geometric networks

Dynamic circular work-stealing deque

On distributed smooth scheduling

Constant density spanners for wireless ad-hoc networks

Fast construction of overlay networks

Finding effective support-tree preconditioners

Autonomous virtual mobile nodes

Admission control to minimize rejections and online set cover with repetitions

Traffic engineering of management flows by link augmentations on confluent trees

Adversarial contention resolution for simple channels

Lexicographic QoS scheduling for parallel I/O

Scheduling malleable tasks with precedence constraints

Peer-to-peer networks based on random transformations of connected regular undirected graphs

Is partial quantum search of a database any easier?

A space lower bound for name-independent compact routing in trees

Efficient algorithms for verifying memory consistency

Value-maximizing deadline scheduling and its application to animation rendering

On competitive online read-many parallel disks scheduling

Dynamic circular work-stealing deque

Content Provider	ACM Digital Library
Author	Lev, Yossi Chase, David
Abstract	The non-blocking work-stealing algorithm of Arora, Blumofe, and Plaxton (henceforth ABP work-stealing) is on its way to becoming the multiprocessor load balancing technology of choice in both industry and academia. This highly efficient scheme is based on a collection of array-based double-ended queues (deques) with low cost synchronization among local and stealing processes. Unfortunately, the algorithm's synchronization protocol is strongly based on the use of fixed size arrays, which are prone to overflows, especially in the multiprogrammed environments for which they are designed. We present a work-stealing deque that does not have the overflow problem.The only ABP-style work-stealing algorithm that eliminates the overflow problem is the list-based one presented by Hendler, Lev and Shavit. Their algorithm indeed deals with the overflow problem, but it is complicated, and introduces a trade-off between the space and time complexity, due to the extra work required to maintain the list.Our new algorithm presents a simple lock-free work-stealing deque, which stores the elements in a cyclic array that can grow when it overflows. The algorithm has no limit other than integer overflow (and the system's memory size) on the number of elements that may be on the deque, and the total memory required is linear in the number of elements in the deque.
Starting Page	21
Ending Page	28
Page Count	8
File Format	PDF
ISBN	1581139861
DOI	10.1145/1073970.1073974
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2005-07-18
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Work stealing Lock-free Load balancing Deque
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

A dynamic-sized nonblocking work stealing deque

Scalable work stealing

Scalable work stealing

Scheduling parallel programs by work stealing with private deques

Work stealing and persistence-based load balancers for iterative overdecomposed applications

A Case for Work-stealing on FPGAs with OpenCL Atomics

Understanding and improving JVM GC work stealing at the data center scale

Lazy binary-splitting: a run-time adaptive work-stealing scheduler

A dynamic-sized nonblocking work stealing deque (2005).

Dynamic circular work-stealing deque

Similar Documents

A dynamic-sized nonblocking work stealing deque

Scalable work stealing

Scalable work stealing

Scheduling parallel programs by work stealing with private deques

Work stealing and persistence-based load balancers for iterative overdecomposed applications

A Case for Work-stealing on FPGAs with OpenCL Atomics

Understanding and improving JVM GC work stealing at the data center scale

Lazy binary-splitting: a run-time adaptive work-stealing scheduler

A dynamic-sized nonblocking work stealing deque (2005).

Dynamic circular work-stealing deque