NDLI: Scheduling irregular parallel computations on hierarchical caches

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

Graph expansion and communication costs of fast matrix multiplication: regular submission

A study of transactional memory vs. locks in practice

Filtering: a method for solving graph problems in MapReduce

Brief announcement: full reversal routing as a linear dynamical system

A tight runtime bound for synchronous gathering of autonomous robots with limited visibility

Approximation algorithms for secondary spectrum auctions

Online packet-routing in grids with bounded buffers

Brief announcement: distributed shared memory based on computation migration

On a local protocol for concurrent file transfers

Brief announcement: a partitioned ticket lock

Tight bounds for anonymous adopt-commit objects

Scheduling irregular parallel computations on hierarchical caches

Near linear-work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs

Optimizing hybrid transactional memory: the importance of nonspeculative operations

Parallelism and data movement characterization of contemporary application classes

Brief announcement: better speedups for parallel max-flow

Stabilizing consensus with the power of two choices

Maximising lifetime for fault-tolerant target coverage in sensor networks

Sparse spanners vs. compact routing

Brief announcement: communication bounds for heterogeneous architectures

On multi-processor speed scaling with migration: extended abstract

Brief announcement: transaction polymorphism

A highly-efficient wait-free universal construction

Sharing-aware algorithms for virtual machine colocation

Linear-work greedy parallel approximate set cover and variants

Flat-combining NUMA locks

Work-stealing for mixed-mode parallelism by deterministic team-building

Brief announcement: reclaiming the energy of a schedule, models and algorithms

Convergence of local communication chain strategies via linear transformations: or how to trade locality for speed

Convergence to equilibrium of logit dynamics for strategic games

Re-Chord: a self-stabilizing chord overlay network

Brief announcement: large-scale multimaps

On scheduling in map-reduce and flow-shops

Brief announcement: multilane - a concurrent blocking multiset

A lock-free algorithm for concurrent bags

Data-oblivious external-memory algorithms for the compaction, selection, and sorting of outsourced data

Parallelism in dynamic well-spaced point sets

Location-based memory fences

The pochoir stencil compiler

Brief announcement: paging for multicore processors

The car sharing problem

On a bounded budget network creation game

Recommender systems with non-binary grades

Brief announcement: processor allocation for optimistic parallelization of irregular programs

Finding heavy distinct hitters in data streams

Brief announcement: read invisibility, virtual world consistency and permissiveness are compatible

Understanding bloom filter intersection for lazy address-set disambiguation

Brief announcement: locality-enhancing loop transformations for tree traversal algorithms

Brief announcement: program regularization in verifying memory consistency

Brief announcement: RedRem: a parallel redundancy remover

Scheduling irregular parallel computations on hierarchical caches

Content Provider	ACM Digital Library
Author	Fineman, Jeremy T. Blelloch, Guy E. Gibbons, Phillip B. Simhadri, Harsha Vardhan
Abstract	For nested-parallel computations with low depth (span, critical path length) analyzing the work, depth, and sequential cache complexity suffices to attain reasonably strong bounds on the parallel runtime and cache complexity on machine models with either shared or private caches. These bounds, however, do not extend to general hierarchical caches, due to limitations in (i) the cache-oblivious (CO) model used to analyze cache complexity and (ii) the schedulers used to map computation tasks to processors. This paper presents the parallel cache-oblivious (PCO) model, a relatively simple modification to the CO model that can be used to account for costs on a broad range of cache hierarchies. The first change is to avoid capturing artificial data sharing among parallel threads, and the second is to account for parallelism-memory imbalances within tasks. Despite the more restrictive nature of PCO compared to CO, many algorithms have the same asymptotic cache complexity bounds. The paper then describes a new scheduler for hierarchical caches, which extends recent work on "space-bounded schedulers" to allow for computations with arbitrary work imbalance among parallel subtasks. This scheduler attains provably good cache performance and runtime on parallel machine models with hierarchical caches, for nested-parallel computations analyzed using the PCO model. We show that under reasonable assumptions our scheduler is "work efficient" in the sense that the cost of the cache misses are evenly balanced across the processors---i.e., the runtime can be determined within a constant factor by taking the total cost of the cache misses analyzed for a computation and dividing it by the number of processors. In contrast, to further support our model, we show that no scheduler can achieve such bounds (optimizing for both cache misses and runtime) if work, depth, and sequential cache complexity are the only parameters used to analyze a computation.
Starting Page	355
Ending Page	366
Page Count	12
File Format	PDF
ISBN	9781450307437
DOI	10.1145/1989493.1989553
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2011-06-04
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Cache complexity Analysis of parallel algorithms Cost models Schedulers Parallel hierarchical memory
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

Scheduling irregular parallel computations on hierarchical caches.

Scheduling irregular parallel computations on hierarchical caches (2010).

Scheduling irregular parallel computations on hierarchical caches

Development of Hierarchical Analytical Scheduling (HAS) -- A Conceptual Framework

Models for parallel and hierarchical computation

Cache optimization for mixed regular and irregular computations

Space-Efficient Scheduling of Multithreaded Computations

Bounding Cache Miss Costs of Multithreaded Computations Under General Schedulers: Extended Abstract

Modeling set associative caches behavior for irregular computations

Scheduling irregular parallel computations on hierarchical caches

Similar Documents

Scheduling irregular parallel computations on hierarchical caches.

Scheduling irregular parallel computations on hierarchical caches (2010).

Scheduling irregular parallel computations on hierarchical caches

Development of Hierarchical Analytical Scheduling (HAS) -- A Conceptual Framework

Models for parallel and hierarchical computation

Cache optimization for mixed regular and irregular computations

Space-Efficient Scheduling of Multithreaded Computations

Bounding Cache Miss Costs of Multithreaded Computations Under General Schedulers: Extended Abstract

Modeling set associative caches behavior for irregular computations

Scheduling irregular parallel computations on hierarchical caches