NDLI: On-the-fly maintenance of series-parallel relationships in fork-join multithreaded programs

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

On delivery times in packet networks under adversarial traffic

Object location in realistic networks

Fighting against two adversaries: page migration in dynamic networks

Packet-mode policies for input-queued switches

Balanced graph partitioning

Scheduling against an adversarial network

Sharing the cost of multicast transmissions in wireless networks

A scalable lock-free stack algorithm

Effectively sharing a cache among threads

Improved combination of online algorithms for acceptance and rejection

Online algorithms for network design

Dynamic analysis of the arrow distributed protocol

Adaptive channel queue routing on k-ary n-cubes

Simple efficient load balancing algorithms for peer-to-peer systems

Online hierarchical cooperative caching

Parallelism versus memory allocation in pipelined router forwarding engines

Bi-criteria algorithm for scheduling jobs on cluster platforms

On achieving optimized capacity utilization in application overlay networks with multiple competing sessions

Selfish load balancing and atomic congestion games

DCAS is not a silver bullet for nonblocking algorithm design

Cache-oblivious shortest paths in graphs using buffer heap

Time complexity of practical parallel steiner point insertion algorithms

Expansion properties of (secure) wireless networks

Optimal early stopping uniform consensus in synchronous systems with process omission failures

Compact name-independent routing with minimum stretch

Consistent and compact data management in distributed storage systems

New results on web caching with request reordering

Lower bounds for graph embeddings and combinatorial preconditioners

On-the-fly maintenance of series-parallel relationships in fork-join multithreaded programs

Pagoda: a dynamic overlay network for routing, data management, and multicasting

How to route and tax selfish unsplittable traffic

Efficient orchestration of sub-word parallelism in media processors

Online algorithms for prefetching and caching on parallel disks

The inherent queuing delay of parallel packet switches

The effect of faults on network expansion

Writing-all deterministically and optimally using a non-trivial number of asynchronous processors

Geometric generalizations of the power of two choices

An NC algorithm for finding a maximal acyclic set in a graph

Efficient search in unstructured peer-to-peer networks

The potential in energy efficiency of a speculative chip-multiprocessor

On-the-fly maintenance of series-parallel relationships in fork-join multithreaded programs

Content Provider	ACM Digital Library
Author	Leiserson, Charles E. Fineman, Jeremy T. Bender, Michael A. Gilbert, Seth
Abstract	A key capability of data-race detectors is to determine whether one thread executes logically in parallel with another or whether the threads must operate in series. This paper provides two algorithms, one serial and one parallel, to maintain series-parallel (SP) relationships "on the fly" for fork-join multithreaded programs. The serial SP-order algorithm runs in O(1) amortized time per operation. In contrast, the previously best algorithm requires a time per operation that is proportional to Tarjan's functional inverse of Ackermann's function. SP-order employs an order-maintenance data structure that allows us to implement a more efficient "English-Hebrew" labeling scheme than was used in earlier race detectors, which immediately yields an improved determinacy-race detector. In particular, any fork-join program running in T1 time on a single processor can be checked on the fly for determinacy races in O(T1) time. Corresponding improved bounds can also be obtained for more sophisticated data-race detectors, for example, those that use locks.By combining SP-order with Feng and Leiserson's serial SP-bags algorithm, we obtain a parallel SP-maintenance algorithm, called SP-hybrid. Suppose that a fork-join program has n threads, T1 work, and a critical-path length of T∞. When executed on P processors, we prove that SP-hybrid runs in O((T1/P +PT,/i>∞)lg
Starting Page	133
Ending Page	144
Page Count	12
File Format	PDF
ISBN	1581138407
DOI	10.1145/1007912.1007933
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2004-06-27
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Work stealing On the fly Amortized analysis Dynamic set Fork-join Series-parallel Sp-bags Tree Data structure Multi-threading Locking Cilk Race detection Sp-order Least common ancestor Mutual exclusion Algorithm Parse tree Thread Trace Parallel computing Graph Order maintenance Sp-hybrid Data race
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