Cost Models for Locality and Parallelism
Talkat Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013) · 2013-10-21..10-24·
summary
Defines a program‑centric cost model that counts transfers on nested parallel DAGs and shows how to map it to a tree of caches using a parallel depth‑first scheduler that pins maximal M‑sized subtasks. Introduces parallel cache complexity (locality) and effective cache complexity (adds imbalance penalties), gives tight bounds for matrix multiply (parallelizability 1.5) and sorting (1.0), and reports a practical result: sorting 100 million doubles in about one second on a 32‑core machine.
AI-written summary · about
chapters (20)
- 0:00Start
- 0:07For scalability...
- 2:46This Talk
- 3:13Parallel Program Directed Acyclic Graph
- 5:32Cost Model for Time
- 7:28Upper Bounds (Algorithms)
- 8:37Lower Bounds
- 9:46Problem: Unwieldy Model
- 10:53Separate Cost Model & Schedule
- 11:59Program-Centric Cost Models
- 13:07Realistic Machine Model: Tree of caches
- 14:10Program-Centric Cost Model for Sequential Algorithms Cache Oblivious Framework JFLPR 99
- 16:42Program-Centric Metrics for Parallel Programs For nested parallel programs on shared memories.
- 17:32Nested Parallel DAGS
- 18:32Locality: Parallel Cache Complexity
- 20:07Scheduling on Tree of Caches Annotate tasks with size, schedule based on size
- 21:10Scheduling: Cost Model to Machines
- 21:35Schedule preserves locality Communication Costs
- 22:21Effective Cache Complexity BFGS'11 Extend Q* to include cost of imbalance
- 26:06Summary Important to quantify locality and parallelism.
related talks
25mAutomatically Deriving Cost Models for Structured Parallel Processes(...)
31mSome Novel Computational Models to Think About
01h 20mAn Introduction to Distributed, Massively Parallel, and Local Computation Algorithms
01h 27mKeynote: Multidimensional Parallel Standard C++
01h 07mThe Asynchronous C++ Parallel Programming Model
25mDistCache: Provable Load Balancing for Large-Scale Storage Systems with Distributed...
21mDistCache: Provable Load Balancing for Large-Scale Storage Systems with Distributed Caching
01h 05mGraph Algorithms in the MPC Model