Decouple and Decompose: Scaling Resource Allocation with DeDe
summary
DeDe reformulates large resource-allocation LPs/MIPs by making a matrix copy, applying ADMM to decouple row (resource) and column (demand) constraints, then solving alternating per-resource and per-demand subproblems in parallel. Implementation is a Python package built on CVXPY and Ray. Experiments show 65× faster runtime vs a commercial solver on cluster scheduling, handling 2,000 jobs on 16,000 CPUs/GPUs and achieving better fairness; similar wins on traffic engineering with 3 million demands on 8,000 links.
AI-written summary · about
chapters (7)
- 0:00DeDe and resource allocation
- 1:22Large-scale allocation challenges
- 4:15Decoupling with ADMM
- 8:08Decomposing for parallel solving
- 9:34DeDe implementation and API
- 12:05Performance evaluation
- 15:15Summary and future
related talks
17mApplication of Online Resource Allocation Based on Ray
26mParallel Declarative Solutions of Sequencing Problems using Multi-valued Decisio
13mA Fast Solver-Free Algorithm for Traffic Engineering in Large-Scale Data Center Network
19mLook Before, Before You Leap: Online Vector Load Balancing with Few Reassignments
15mDistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language...
17mDuhu: Shared Disaggregated Memory for Distributed Data Processing Frameworks
19mDistributed load balancing: a new framework and improved guarantees
19mEfficient LLM Serving on Commodity GPU Clusters with Data-Reduced Cross-Instance...