论文地址

DCAF原理介绍

阿里 DCAF 算法全称为 Dynamic Computation Allocation Framework（动态计算分配框架），该算法由阿里巴巴提出，主要应用于在线广告推荐系统等场景，旨在解决在有限计算资源的情况下最大化收益的问题。

其核心思想是将计算资源分配问题抽象为背包问题，并对不同的请求根据其价值进行个性化的算力分配，从而在给定计算资源的情况下，获得最大收益。同时，DCAF 算法能够在请求量突发的情况下保持稳定，并带来机器资源的节省，例如在淘宝广告中同等效果情况下降低了 20%的 GPU 消耗。

具体来说，假设现在有 N 个请求{i=1....N}，请求都需要在 T 时间内预估完成，每个请求能选择 M 个行为{j=1,...,M}（可以理解为每个行为是针对每个请求采用的不同算力），qj 定义为进行第 j 个行为的花费，Qij 定义为第 i 个请求进行第 j 个行为的收益（与 qj 成正比例，在广告系统中为 eCPM），C 表示总的计算资源，xij 表示对于第 i 个请求采用第 j 个行为，且对于每一个请求，只能选择其中一个行为。那么整体的问题公式可以抽象为：

要解决这个问题，首先将背包问题用拉格朗日松弛，得到对偶函数：

分析该函数，因为 xij >=0，所以对于 xij 是一个向下的线性函数，故只会在的时候 xij 会取 1。那么函数也可以转化为：

由于µ与其对偶目标是负相关，那么对于µ而言的全局最优解为：

因此对于 xij 的全局最优解为：

为了求解拉格朗日乘子µ，提出一些假设：

  1. Qij 是随着 j 增大而增大的（随着计算资源的倾斜，收益会越来越高）。

  2. Qij/qj 是随着 j 增大而减小的（边际效应递减）。

根据假设，可以得到结论：对于每个 i，如果 Qij1/qj1 > Qij2/qj2，那么λ1 ≥ λ2，并且 max(sigma(xijQij))和 sigma(xijqj)都会随着λ增大而减小。最后可以用二分法来计算λ，从而得到每个 i 的最优行为 j。

在 Qij 的预估方面，会用 4 类特征进行预估，包括用户画像、用户行为、上下文特征、系统状态。DCAF 架构分为在线决策部分和离线预估部分。在线部分包含信息收集与监控（收集系统状态，如 CPU、GPU、运行时间、错误率等）、请求价值估计（用以模型计算 Qij，该阶段的模型要求轻量级，会使用部分其他模型的上下文特征）、策略执行（通过类似 PID 系统，来给予每个请求 i 的最优行为 j）。离线部分包括拉格朗日乘子求解器（用以计算全局λ）和预期收益估计器（计算收益 Qij，由于广告领域为 ctr*bid = eCPM，所以需要训练一个 CTR 模型来得到 Qij，并定期更新，提供给策略执行使用）。

关键特点

DCAF的关键特点包括：

  1. 个性化算力分配：根据流量请求的价值进行个性化的算力分配，而不是对所有请求分配相同的算力。

  2. 全局最优解：理论上可以保证在给定的计算预算内最大化总收入。

  3. 系统稳定性：引入了MaxPower概念，通过控制反馈机制，如PID控制器，来保持在线服务系统的稳定性，特别是在面对流量突增时。