ABSTRACT
This poster proposes an efficient runtime scheduler that provides provable performance guarantees to parallel programs that use data structures through the use of implicit batching.
- R. D. Blumofe and C. E. Leiserson. Scheduling multithreaded computations by work stealing. Journal of the ACM, 46(5):720--748, 1999. Google ScholarDigital Library
- A. Braginsky and E. Petrank. A lock-free B+ tree. In SPAA, pages 58--67, 2012. Google ScholarDigital Library
- D. Hendler, I. Incze, N. Shavit, and M. Tzafrir. Flat combining and the synchronization-parallelism tradeoff. In SPAA, pages 355--364, 2010. Google ScholarDigital Library
- W. J. Paul, U. Vishkin, and H. Wagener. Parallel dictionaries in 2--3 trees. In ICALP, pages 597--609, 1983. Google ScholarDigital Library
Index Terms
- Provably good scheduling for parallel programs that use data structures through implicit batching
Recommendations
Provably good scheduling for parallel programs that use data structures through implicit batching
PPoPP '14This poster proposes an efficient runtime scheduler that provides provable performance guarantees to parallel programs that use data structures through the use of implicit batching.
Provably good scheduling for parallel programs that use data structures through implicit batching
SPAA '14: Proceedings of the 26th ACM symposium on Parallelism in algorithms and architecturesAlthough concurrent data structures are commonly used in practice on shared-memory machines, even the most efficient concurrent structures often lack performance theorems guaranteeing linear speedup for the enclosing parallel program. Moreover, ...
Unbounded parallel-batching scheduling with two competitive agents
We consider the scheduling problems arising when two agents, each with a family of jobs, compete to perform their respective jobs on a common unbounded parallel-batching machine. The batching machine can process any number of jobs simultaneously in a ...
Comments