NDLI: Experimental analysis of space-bounded schedulers

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

A distributed perspective on graph connectivity and cuts

On dynamic bin packing for resource allocation in the cloud

On computing maximal independent sets of hypergraphs in parallel

Brief announcement: few buffers, many hot spots, and no tree saturation (with high probability)

Provably good scheduling for parallel programs that use data structures through implicit batching

Scheduling selfish jobs on multidimensional parallel machines

A simple and practical linear-work parallel algorithm for connectivity

The PCL theorem: transactions cannot be parallel, consistent and live

Brief announcement: fairness-efficiency tradeoffs in tiered storage allocation

Automatic complexity analysis of explicitly parallel programs

A universal approach to data center network design

Simple dynamics for plurality consensus

Finding approximate partitions and splitters in external memory

Parallel peeling algorithms

On the online fault-tolerant server consolidation problem

Hierarchical graph partitioning

Brief announcement: queue delegation locking

Phase-concurrent hash tables for determinism

LP rounding and combinatorial algorithms for minimizing active and busy time

Executing dynamic data-graph computations deterministically using chromatic scheduling

Adaptive integration of hardware and software lock elision techniques

Brief announcement: deadline-aware scheduling of big-data processing jobs

Parallel streaming frequency-based aggregates

(Near) optimal resource-competitive broadcast with jamming

On characterizing the data movement complexity of computational DAGs for parallel execution

Balanced allocations and double hashing

Competitively scheduling tasks with intermediate parallelizability

Simple parallel and distributed algorithms for spectral graph sparsification

Brief announcement: fast dual ring queues

Scheduling shared continuous resources on many-cores

Ordering heuristics for parallel graph coloring

Transaction-friendly condition variables

Brief announcement: parallelization of asynchronous variational integrators forshared memory architectures

Ephemeral networks with random availability of links: diameter and connectivity

Tradeoffs between synchronization, communication, and computation in parallel linear algebra computations

Experimental analysis of space-bounded schedulers

Brief announcement: concurrent data structures for efficient streaming aggregation

A note on multiprocessor speed scaling with precedence constraints

Brief annoucement: a distributed minimum cut approximation scheme

Locality-based network creation games

Brief announcement: cache-oblivious scheduling of streaming pipelines

Brief announcement: amoebot -- a new model for programmable matter

Brief announcement: persistent unfairness arising from cache residency imbalance

Brief announcement: faster 3-periodic merging networks

Experimental analysis of space-bounded schedulers

Content Provider	ACM Digital Library
Author	Kyrola, Aapo Fineman, Jeremy T. Blelloch, Guy E. Gibbons, Phillip B. Simhadri, Harsha Vardhan
Abstract	The running time of nested parallel programs on shared memory machines depends in significant part on how well the scheduler mapping the program to the machine is optimized for the organization of caches and processors on the machine. Recent work proposed ``space-bounded schedulers'' for scheduling such programs on the multi-level cache hierarchies of current machines. The main benefit of this class of schedulers is that they provably preserve locality of the program at every level in the hierarchy, resulting (in theory) in fewer cache misses and better use of bandwidth than the popular work-stealing scheduler. On the other hand, compared to work-stealing, space-bounded schedulers are inferior at load balancing and may have greater scheduling overheads, raising the question as to the relative effectiveness of the two schedulers in practice. In this paper, we provide the first experimental study aimed at addressing this question. To facilitate this study, we built a flexible experimental framework with separate interfaces for programs and schedulers. This enables a head-to-head comparison of the relative strengths of schedulers in terms of running times and cache miss counts across a range of benchmarks. (The framework is validated by comparisons with the Intel\textregistered{} Cilk\texttrademark{} Plus work-stealing scheduler.) We present experimental results on a 32-core Xeon\textregistered{} 7560 comparing work-stealing, hierarchy-minded work-stealing, and two variants of space-bounded schedulers on both divide-and-conquer micro-benchmarks and some popular algorithmic kernels. Our results indicate that space-bounded schedulers reduce the number of L3 cache misses compared to work-stealing schedulers by 25--65\% for most of the benchmarks, but incur up to 7\% additional scheduler and load-imbalance overhead. Only for memory-intensive benchmarks can the reduction in cache misses overcome the added overhead, resulting in up to a 25\% improvement in running time for synthetic benchmarks and about 20\% improvement for algorithmic kernels. We also quantify runtime improvements varying the available bandwidth per core (the ``bandwidth gap''), and show up to 50\% improvements in the running times of kernels as this gap increases 4-fold. As part of our study, we generalize prior definitions of space-bounded schedulers to allow for more practical variants (while still preserving their guarantees), and explore implementation tradeoffs.
Starting Page	30
Ending Page	41
Page Count	12
File Format	PDF
ISBN	9781450328210
DOI	10.1145/2612669.2612678
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2014-06-23
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Work stealing Space-bounded schedulers Memory bandwidth Multicores Cache misses Thread schedulers
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

Experimental Analysis of Space-Bounded Schedulers

Low-synchronisation Work Stealing under Parallel Data-List Processing in Multicores

Steal Tree: low-overhead tracing of work stealing schedulers

A Work Stealing Algorithm for Parallel Loops on Shared Cache Multicores

Fence-free work stealing on bounded TSO processors

BWS: Balanced Work Stealing for Time-Sharing Multicores

Uni-Address Threads: Scalable Thread Management for RDMA-Based Work Stealing

The Data Locality of Work Stealing (2000)

BWS: balanced work stealing for time-sharing multicores

Experimental analysis of space-bounded schedulers

Similar Documents

Experimental Analysis of Space-Bounded Schedulers

Low-synchronisation Work Stealing under Parallel Data-List Processing in Multicores

Steal Tree: low-overhead tracing of work stealing schedulers

A Work Stealing Algorithm for Parallel Loops on Shared Cache Multicores

Fence-free work stealing on bounded TSO processors

BWS: Balanced Work Stealing for Time-Sharing Multicores

Uni-Address Threads: Scalable Thread Management for RDMA-Based Work Stealing

The Data Locality of Work Stealing (2000)

BWS: balanced work stealing for time-sharing multicores

Experimental analysis of space-bounded schedulers