On-the-Fly Maintenance of Series-Parallel Relationships in Fork-Join Multithreaded Programs

On-the-Fly Maintenance of Series-Parallel Relationships in Fork-Join Multithreaded Programs

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"...

Full description

Bibliographic Details
Main Authors: Bender, Michael A., Fineman, Jeremy T., Gilbert, Seth, Leiserson, Charles E.
Format: Article
Language:English
Published: 2004
Subjects:
Amortized analysis
algorithms
Cilk
data race
data structure
dynamic set
fork-join
graph
least common ancestor
locking
multi-threading
mutual exclusion
on the fly
order maintenance
parallel computing
parse tree
race detection
series-parallel
SP-bags
SP-hybrid
SP-order
thread
trace
tree
work stealing
Online Access:http://hdl.handle.net/1721.1/7430

Internet

http://hdl.handle.net/1721.1/7430

Similar Items