13-EFT.WP.Methods.SimStack v1.0 | 第7章 并行化、调度与资源

目录 ／ 文档-技术白皮书 ／ 13-EFT.WP.Methods.SimStack v1.0

第7章 并行化、调度与资源

I. 范围与目标

• 本章给出从对象图 G=(V,E) 到可执行计划与资源分配的统一口径，覆盖代价模型、就绪集、启发式与放置规则、配额与隔离、观测与告警，并与 TS.* 指标、hb 语义及 tau_mono ↔ ts 时基一致。
• 目标：在满足守恒门与 SLO 的前提下，最小化 T_make(G)、控制 P99 与成本，形成可复用的实现绑定与运行流程。

II. 术语与符号

1. 图与路径
   • G=(V,E)，w(v)（标称工作量），c(e)（边通信代价），crit(G)（关键路径），D(G)=crit(G)，W(G)=Σ_v w(v)。
   • dist_in(v)：源到 v 的最短路径长度；dist_out(v)：v 到汇的最短路径长度；slack(v) = D(G) - dist_in(v) - dist_out(v)。
2. 就绪与优先级
   R(t)：时刻 t 的就绪集；p(v)：调度优先级分数；batch(v)：可批量合并的最小单元。
3. 资源与配额
   • 资源向量 cap = (cpu, mem, gpu, nic)；需求 req(v) 同构于 cap。
   • 配额 quota(k)：租户或阶段 k 的上限；主导资源占比 dom_ratio(k)。
4. 速率与利用
   • lambda(v)、mu(v)、rho(v)=lambda(v)/mu(v)；窗口估计 rho_hat(v;W)。
   • 成本度量 cost(res)：按资源单价线性或分段线性组合。
5. 指标与告警
   TS.latency.*，TS.throughput.*，TS.util.*，TS.queue.*，TS.hb.violations，TS.sli.success_rate。

III. 公设与最小方程（P61-/S62-）

1. P61-13（预算合规）
   任一时刻的分配 alloc(t) 必须满足 Σ_v use(v,t) ≤ cap 且对每个租户 use_k(t) ≤ quota(k)。
2. P61-14（公平与无饥饿）
   对活跃租户 k，当 req_k 可被满足时，存在有界等待上界；采用主导资源公平分配（DRF）或其等价近似。
3. P61-15（因果与幂等守护）
   调度、批量与推迟不得破坏 hb；若改变重试路径，必须遵循幂等或补偿契约。
4. S62-40（makespan 下界与并行度）
   T_make(G,P) ≥ max( W(G)/P , D(G) )，P 为有效并行度。
5. S62-41（Amdahl 与 Gustafson 上下界）
   S_amdahl(P) = 1 / ( s + (1 - s)/P )，S_gustafson(P) = s + (1 - s) * P，s 为串行份额。
6. S62-42（G/G/m 近似等待时间）
   对 m 并行服务：W_q ≈ ( C * rho^sqrt(2(m+1)) / ( m * (1 - rho) ) ) * ( 1 / mu )，C = ( c_a^2 + c_s^2 ) / 2，rho = lambda / ( m * mu )。
7. S62-43（优先级分数）
   • p(v) = ω1 * ( 1 / ( slack(v) + ε ) ) + ω2 * w(v) + ω3 * risk(v) + ω4 * age(v)。
   • 建议 ω1 ≥ ω2 ≥ 0，risk(v) 来自失败概率或重试成本。
8. S62-44（通信切割成本）
   跨宿主切割 E_cut 的代价：CommCost = Σ_{e∈E_cut} vol(e) * lat(link) + Σ_{e∈E_cut} vol(e) / bw(link)。
9. S62-45（DRF 份额）
   对租户 k，在资源 r 上的占比 sh_k^r = use_k^r / cap^r，主导资源份额 dom_k = max_r sh_k^r；调度按最小 dom_k 优先。

IV. 代价模型与就绪集

• 目标函数
  J = α * T_make + β * P99 + γ * cost(res) + δ * penalty(hb, retry)；α,β,γ,δ 由场景给定。
• 就绪集维护
  R(t) = { v | preds(v) 已完成 ∧ 资源可满足 req(v) }；按 p(v) 排序；支持 batch(v) 合并以提高 mu。
• 速率与批量
  批量规模 b 对服务率的影响：mu(b) ≈ mu0 * f(b)，f(b) 单调但存在饱和，清单记录 f 的拟合口径。

V. 启发式与放置规则

• 关键路径优先（CP-first）
  最小化 slack(v)；对同 slack，优先大 w(v)。
• HEFT 风格异构放置
  估计 EFT(v,h)（在宿主 h 的最早完成时间）并贪心最小化；EFT = avail(h) + exec(v,h) + xfer(preds→h)。
• 网络感知切割
  以 S62-44 最小化 CommCost；将高互联团块映射到同域，减少 E_cut。
• 热点与背压联动
  当某 v 的上游 B(u) 持续高位，优先放置 v 于拥塞域的近邻宿主，缩短缓冲驻留时间。
• 约束与隔离
  强约束：req(v) ⊆ cap(h)；软约束以罚项并入 J；租户隔离以 quota(k) 与 dom_k 控制。

VI. 资源配额、隔离与弹性

• 配额模型
  静态：每租户固定 quota(k)；动态：滑窗 ρ_hat(k;W) 超阈触发再分配。
• 弹性伸缩
  触发规则：若 ρ_hat(v;W) > ρ_hi 且 TS.latency.p99 超门，申请扩容 Δcap；若持续低载则回收。
• 隔离级别
  进程级、容器级、NUMA 亲和与 GPU MIG；清单记录绑定策略与亲和域。

VII. 数据与清单口径（调度与资源）

• 计划与放置
  plan.id，placement[v] = host，start/finish(tau_mono)，p(v)，batch.size，preds/dists。
• 资源与配额
  host.cap，alloc.timeline，quota(k)，dom_k，violations。
• 代价与目标
  objective.J，weights(α,β,γ,δ)，CommCost，cost(res) 摘要。
• 指标与告警
  TS.util.cpu/gpu/mem/nic，TS.queue.backlog，TS.latency.p99，TS.hb.violations，alerts。
• 时基与回放
  全部时刻以 tau_mono 记录并发布 ts 与 alpha/beta，支持回放。

VIII. 算法与实现绑定（I60-* 扩展）

• I60-6 build_exec_graph(spec:any) -> GraphRef（见第3章）
• I60-7 plan_schedule(graph:GraphRef, policy:dict, resources:dict) -> SchedPlanRef（见第3章）
• I60-15 allocate_resources(plan:SchedPlanRef, quotas:dict) -> AllocationRef
  输出宿主映射、亲和与配额生效证据。
• I60-16 autoscale(allocation:AllocationRef, signals:dict) -> Actions
  基于 ρ_hat 与 TS.* 触发扩缩容与迁移。
• I60-8 apply_backpressure(graph:GraphRef, strategy:dict) -> bp.Report（见第3章）
• I60-10 eval_slo(trace:any, targets:dict) -> TS.Report（见第3章）

IX. 计量流程与运行图（Mx-6* 对应）

1. Mx-67 schedule-compile-run
   • build_exec_graph → 估计 w(v), c(e) 与 dist_in/out；
   • plan_schedule 产出 p(v) 与初始放置；
   • allocate_resources 应用配额与亲和；
   • 事件循环：运行 → emit_metrics → apply_backpressure → 按需 autoscale。
2. Mx-68 rescale-and-rebalance
   • 监测 ρ_hat、TS.latency.p99；
   • 触发 autoscale 与迁移；
   • 验证 hb 不变式与幂等补偿。
3. Mx-69 incident-and-rollback
   • 告警升级与保护性降载；
   • 回滚到安全放置与 quota；
   • 产出事后报告与基线更新建议。

X. 观测、SLO 与告警

• SLI 与 SLO
  端到端：TS.latency.p99、TS.sli.success_rate；系统：TS.util.*、TS.queue.backlog、TS.hb.violations。
• 告警规则
  连续 K 个窗口 TS.latency.p99 > target 触发 scale_out；TS.hb.violations > 0 触发 block-and-audit。
• 看板与追溯
  以 ts 发布，落盘 tau_mono 与 alpha/beta；所有伸缩与迁移进入 audit.trail。

XI. 验证与测试矩阵

1. 最小必测
   • Amdahl/Gustafson：构造不同 s，验证加速上界；
   • G/G/m：注入 c_a^2/c_s^2，验证 W_q 估计与 P99 预测；
   • 放置切割：对比启发式前后 CommCost 与 TS.latency.p99。
2. 边界与极端
   突发流量与热点迁移；高配额冲突下的 DRF 公平性；GPU 稀缺与 NUMA 约束。
3. 回归与门限
   锁定基线，比较 ΔT_make、ΔTS.util.*、ΔTS.queue.backlog、ΔTS.hb.violations 与成本变化。

XII. 交叉引用与依赖

• 与线程网络（第3章）
  共享 P61-1..4 与 S62-10..14；就绪与背压策略通过 apply_backpressure 协同。
• 与耦合推进（第4章）
  步长与同步窗口可通过调度信号调整；失败与重试遵循幂等与补偿。
• 与时间校准（第5章）
  迁移与重放在 tau_mono 上执行，发布以 ts；到达时相关路径与测度保持一致。
• 与数据落盘（第6章）
  计划、配额、迁移与告警必须落盘到 manifest 与 audit.trail，字段名与单位遵循固定口径。

XIII. 风险、限制与开放问题

• 风险
  错置导致 E_cut 增大与尾延迟恶化；批量策略不当引入高 P99；伸缩震荡造成 hb 破坏与重试风暴。
• 限制
  启发式近似不保证全局最优；某些资源（GPU/MIG）具备不可分性与长尾争用。
• 开放问题
  联合最优化 步长×调度×放置 的统一控制；跨域网络抖动下的稳健迁移与可证明 SLO 保持。

XIV. 交付件与版本管理

1. 交付件
   • 调度策略库（CP-first、HEFT、网络感知切割、DRF）、放置与迁移工具、autoscale 策略与看板配置。
   • 基准图谱与负载生成器、对照实验脚本与回归门。
2. 版本管理
   自 v1.0 起冻结清单键名与指标集；新增策略以特性位控制，并附迁移说明。

XV. 本章新增术语与符号（记忆）

• 计划与优先：R(t)，p(v)，slack(v)，EFT(v,h)，batch(v)。
• 资源与配额：cap，req(v)，quota(k)，dom_k，DRF。
• 通信与切割：E_cut，CommCost，vol(e)，lat(link)，bw(link)。
• 目标与成本：J，α,β,γ,δ，cost(res)。
• 队列与并行：m，W_q，rho，c_a^2，c_s^2。
• 指标与告警：TS.util.*，TS.queue.*，TS.latency.p99，TS.hb.violations，audit.trail。