· DAG Scheduling · NPU
Cache-aware DAG Scheduling for NPUs
Models SIMD/NPU operator dependencies as a directed acyclic graph and jointly studies topological scheduling, data residency, and pipeline optimization under limited on-chip cache to reduce avoidable execution slack and data movement.
Problem
On SIMD/NPU architectures, compute-graph scheduling must satisfy operator dependencies and execution-unit constraints while managing limited on-chip capacity, data residency, and DMA movement. Under cache pressure, a readiness-only policy can trigger repeated swaps and avoidable pipeline gaps.
Mathematical and algorithmic approach
The method represents operator dependencies as a DAG and uses WCB-style scores to choose a schedule under topological and residency constraints. It combines contiguous multi-pool allocation, spill-victim selection, explicit swap-in/swap-out insertion, and ASAP-style compression that shifts tasks earlier while respecting execution-unit availability.
My contribution
Contributed to problem abstraction, algorithm design, experimental verification, and codebase organization, with emphasis on the coupling between graph scheduling and cache management.
Results and outputs
With total execution cycles and data movement as the primary optimization objectives, the project won a National Third Prize in the 2025 China Postgraduate Mathematical Contest in Modeling and was reorganized into a reproducible codebase with unified CLIs, smoke tests, and bilingual documentation.
Workflow
- 01
Graph scheduling
Select ready operators with WCB-style scores under dependency, residency, and execution-unit constraints.
- 02
Memory and spills
Allocate contiguous regions across cache pools, select spill victims under pressure, and insert swap operations.
- 03
Pipeline compression
Shift tasks left under execution-unit constraints to remove avoidable slack.