无服务器计算的机器学习，出路在哪里？（二） 2.2、Cirrus: a Serverless Framework for End-to-end ML Workflows [5]
这篇文章也是节 2.1 中所介绍的 Berkeley 研究小组的研究成果，是对节 2.1 中分析的 NIPS’18 中文章所涉及工作的扩展和延伸。在专门用于无服务器基础设施和 ML 工作流的无服务器 ML 框架原型的基础上，将其封装为一个实现端到端管理的分布式 ML 训练框架 Cirrus，可以直接调用使用
（
https://github.com/ucbrise/cirrus），并将相关工作内容发表在发表在 SoCC ’19 中。Cirrus 专门用于无服务器云基础设施（如 Amazon AWS Lambda）中的 ML 训练。它提供高级原语来支持 ML 工作流中的一系列任务：数据集预处理、训练和超参数优化。Cirrus 结合了无服务器接口的简单性和无服务器基础设施（具体是指 AWS Lambda 和 S3）的可伸缩性，以最小化用户的工作。
Cirrus 的设计原则是：
- 自适应的细粒度资源分配。为了避免由于过度配置而造成的资源浪费，Cirrus 应该灵活地调整为每个工作流阶段保留的细粒度资源量。
- 无状态服务器端后端。为了确保无服务器计算资源的健壮和高效管理，Cirrus 设计了一个无状态的服务器端后端。有关当前部署的函数以及 ML 工作流任务和计算单元之间的映射的信息由客户端后端管理。因此，即使所有云端资源变得不可用，ML 训练工作流也不会失败，并且可以在资源再次可用时恢复其操作。
- 端到端无服务器 API。模型训练不是 ML 研究人员的唯一任务，数据集预处理、特征工程和参数调整等对于最终生成一个好的模型同样重要。Cirrus 应该提供一个完整的 API，允许开发人员以最小的工作量端到端的大规模地运行这些任务。
- 高可扩展性。ML 任务是高度计算密集型的，在没有有效并行化的情况下需要很长时间才能完成。因此，Cirrus 应该能够同时运行数千个 workers 和数百个实验。
与节 2.1 中所介绍的工作类似，Cirrus 利用四个系统模块来实现上述原则。首先，Cirrus 为 ML 开发人员提供了 Python 前端。这个前端有两个功能：a）为 ML 训练的所有阶段提供丰富的 API；b）在无服务器的基础设施中执行和管理大规模计算。其次，Cirrus 提供了一个客户端后端。第三，为了克服低延迟无服务器存储的不足，Cirrus 为 worker 共享的所有中间数据提供了低延迟分布式数据存储。第四，Cirrus 提供了一个在无服务器 Lambda 上运行的 worker 运行时（runtime）。该运行时提供了访问 S3 中的训练数据集和分布式数据存储中的中间数据的有效接口。Cirrus 的完整结构见图 4。
图 4. Cirrus 系统结构。系统由（有状态的）客户端（左）和（无状态的）服务器端（右）组成。预处理和面向用户的训练包含一个前端的 API。客户端后端管理云功能和向函数分配任务。服务器端由 Lambda Worker 和高性能数据存储组件组成。Lambda worker 将数据迭代器 API 导出到客户端后端，并包含许多迭代训练算法的有效实现。数据存储用于存储梯度、模型和中间预处理结果。
Cirrus 的整体结构与节 2.1 中是类似的。Cirrus 的前端和客户端后端是用 Python 实现的，方便 Cirrus 与现有的机器学习方法相结合。为了提高效率，分布式数据存储和 worker runtime 用 C++ 实现。表 2 列出了实现的不同组件以及它们的大小和实现语言。Worker runtime 代码包括迭代器接口和数据存储客户端实现。worker runtime 和数据存储通过 TCP 连接进行通信。作者实现了一个共享组件库，其中包括线性代数库、通用实用程序和 ML 算法，这些组件被所有系统组件共享。作者已经公开发布了 Apache 2 开源许可的实现（
）。
表 2. Cirrus 组件。
首先，Cirrus 为 ML 工作流的所有阶段提供了一个 Python 前端 API。前端是一个高度灵活的 thin Python API，默认情况下，它从开发人员那里抽象出所有的细节，同时提供了通过 API 的参数覆盖内部配置参数（例如，优化算法）的能力。前端还提供了一个运行在 Plotly 上的用户界面，供用户监控工作负载的进度和启动 / 停止任务。Cirrus Python API 分为三个子模块。每个子模块都打包了与工作流的每个阶段相关的所有函数和类。（1）预处理。预处理子模块允许用户对存储在 S3 中的训练数据集进行预处理。此子模块允许不同类型的数据集转换：最小 - 最大缩放、标准化和特征散列。（2）训练。Cirrus 的训练子模块支持 ML 模型，这些模型可以通过随机梯度下降进行训练。目前 Cirrus 支持稀疏 Logistic 回归、潜在 Dirichlet 分配、Softmax 和协同过滤。（3）超参数优化。超参数优化子模块允许用户在给定的参数集上运行网格搜索。Cirrus 允许用户改变 ML 训练参数（例如，学习率、正则化率、小批量大小）以及系统参数（例如，Lambda 函数大小、并发 worker 数量、梯度过滤）。
其次，Cirrus 的 Python 前端提供了一个到 Cirrus 客户端后端的接口。这个后端的功能和能够完成的任务与节 2.1 中介绍的框架完全相同。客户端后端从前端算法中抽象出 Lambda 的管理。客户端后台会保存一个当前活动的 Lambda 列表，以及一个 AWS Lambda API 的连接列表（每个连接用于启动一个 Lambda）。在训练期间加载的 Lambda 在其生存期结束时自动重新加载（每 15 分钟一次）。由于 Lambda API 的特殊性，从一台服务器上快速加载数百个 Lambda 是非常困难的。为了解决这个问题，后端保留一个线程池，可用于响应新 Lambda 任务的请求。
第三，Cirrus 提供了分布式存储模块。Cirrus 的数据存储用于存储所有 workers 共享的中间数据。由于现有产品中不允许 Lambda 之间进行交互通信，因此 Lambda 需要共享存储。无服务器 Lambda 的存储需要满足三个条件：首先，它需要低延迟（本文实现低至 300μs），以便能够适应延迟敏感的工作负载，例如用于 ML 训练的工作负载（迭代 SGD）。其次，它需要扩展到数百个 workers，以利用无服务器基础架构几乎线性的可扩展性。第三，它需要一个丰富的接口来支持不同的 ML 用例。例如，数据存储必须支持 multiget（§6.5）、常规键 / 值的 put/get 操作和参数服务器接口。为了实现低延迟，将数据存储部署在云 VMs 中。它实现了低至 300μs 的延迟，而 AWS S3 的延迟约为 10ms。此延迟对于训练阶段最大化模型的更新至关重要。作者使用稀疏表示来表征梯度和模型以实现高达 100 倍的压缩比，以便与存储和批处理请求进行数据交换。为了实现高可伸缩性，Cirrus 包括以下机制：（1）分片存储，（2）高度多线程，（3）数据压缩，（4）梯度滤波器和（5）异步通信。Cirrus 的分布式数据存储提供了一个接口，支持所有在 ML 工作流中存储中间数据的用例。该接口支持键值存储接口（set/get）和参数服务器接口（send 果然啊 dient/get model）。
最后，Cirrus 提供了一个运行时（Runtime），它封装了系统支持的不同计算之间共享的所有函数。如图 5，Cirrus 的 Runtime 为 ML 计算提供了通用抽象（General abstractions）和基本数据类型（Data primitives）用于访问训练数据、参数模型和中间结果。这些可用于向 Cirrus 添加新的 ML 模型。为了简化新算法的开发，Runtime 提供了一组线性代数库。Cirrus 的初始版本使用外部线性代数库如 Eigen 进行梯度计算。为了减少 Eigen 处理序列化和反序列化数据的时间，作者最终开发了自己的线性代数库。对于数据访问，Runtime 提供了一个由本地循环缓冲区支持的基于 minibatch 的迭代器，允许 worker 以低延迟访问训练 minibatch。此外，它还提供了一个高效的 API 来与分布式数据存储进行通信。
图 5. Cirrus Runtime。minibatch 是异步预取的，并在每个 Lambda 的内存中本地缓存（取决于使用的 Lambda 的大小）。将梯度异步发送至参数服务器，每次迭代模型同步从参数服务器中进行检索。
作者给出了 Cirrus 在不同阶段的详细工作方式。
（1）数据加载和预处理。Cirrus 假设训练数据存储在一个全局存储中，比如 S3。因此，使用 Cirrus 的第一步就是将数据集上传到云端。用户将数据集的路径传递给系统，然后由系统负责解析和上载数据集。在此过程中，Cirrus 将数据集从其原始格式（如 csv）转换为二进制格式。这种压缩消除了在训练和超参数调优阶段进行反序列化的需要，这有助于减少 Lambda 工作进程中的计算负载。其次，Cirrus 生成数据集大小相似的分区，并将其上传到 S3 存储桶（S3 Bucket）。
Cirrus 还可以应用变换（Transformations）来提高模型的性能。例如，对于 Cirrus 实现的异步 SGD 优化方法，对数据集中的特征进行规范化处理能够提高训练的效果。对于这些 transformations，Cirrus 启动了一个大型 Map Reduce 作业：每个输入分区一个 worker。在 map 阶段，每个 worker 计算其分区的统计信息（例如，平均值和标准差）。在 reduce 阶段，这些局部统计信息被聚合以计算全局统计信息。在最后的映射阶段，worker 转换每个分区样本，给出最终的每列统计信息。对于大型数据集，map 和 reduce 阶段会跨大量 worker 和列来聚合每列的统计信息。这会造成每秒生成大量新的写操作和读操作，而超出了 S3 支持的事务吞吐量。基于这个原因，作者使用 Cirrus 的低延迟分布式数据存储来存储映射的中间结果，并减少了计算量。
（2）模型训练。Cirrus 使用分布式 SGD 算法进行模型训练。在训练期间，worker 运行 Lambda 函数，并迭代计算梯度步长。每个梯度计算需要两个输入：一个 minibatch 和最新的模型。minibatch 是 Cirrus 的运行时通过迭代器从 S3 获取的。因为迭代器在工作内存中缓冲 minibatch，所以检索 minibatch 的延迟非常低。使用数据存储 API(get_sparse_model_X)从数据存储中同步检索最新的模型。对于每个迭代，每个 worker 都计算一个新的梯度。然后将此梯度异步发送到数据存储（send_gradient_X）以更新模型。
（3）超参数优化。超参数优化是一种模型参数的搜索方式，该模型参数能够保证生成最佳准确度。典型的做法是在多维参数空间上执行网格搜索。搜索可以是暴力破解（Brute-force）搜索或自适应搜索。常见的做法是让网格搜索完整地运行，然后对结果进行后处理，以找到最佳配置。这是一种代价高昂的资源浪费。Cirrus 通过提供超参数搜索仪表板（Hyperparameter search dashboard），来解决这种超时过度配置问题（over-provisioning over time）。Cirrus 超参数仪表板提供了一个统一的界面，用于监控模型随时间变化的损失收敛情况。它允许用户选择单个损失曲线并终止相应的训练实验。因此，Cirrus 提供了：启动超参数搜索的 API 和执行后端；监控模型精度收敛的仪表板；终止单个调优实验的能力，并节省了过度配置成本。
在文献 [2] 工作的基础上，Cirrus 为 ML 用户提供了一个轻量级的 Python API。作者同样给出了一个例子来展示这个 API 的功能。如图 6 所示，这个 API 与图 1 中给出的文献 [2] 中的 API 几乎相同。区别在于本文已经将 Cirrus 封装为模块“cirrus”，可直接在 python 中进行 import。
图 6. Cirrus API 示例。Cirrus 支持 ML 开发工作流的不同阶段：（a）预处理，（b）训练，和（c）超参数调优。
作者利用稀疏逻辑回归任务对比 Cirrus 和两个专门用于基于 VM 的 ML 训练框架：TensorFlow[6]和 Bosen[4]。TensorFlow 是一个用于 ML 计算的通用数据流引擎。Bosen 是一个分布式和多线程参数服务器，由 CMU 开发 Petuum 商业化，它针对大规模分布式集群和机器学习算法的陈旧更新进行了优化。逻辑回归是计算任何给定样本属于两个感兴趣的类的概率问题。本文实验中作者计算网站广告被点击的概率，并利用时间函数评估学习收敛性。使用 Criteo 显示广告数据集[7]。这个数据集包含 45M 个样本，大小为 11GB。每个样本包含 13 个数字特征和 26 个分类特征。在训练之前，对数据集进行了归一化处理，将分类特征哈希为一个大小为 2^20 的稀疏向量。为了评估 Bosen，作者使用 1、2 和 4 个 m5.2xlarge 亚马逊 AWS 实例（每个实例有 8 个 CPU 和 32GB 内存）。对于 Bosen 实验，作者将数据集分区到所有机器上。为了评估 Cirrus，作者使用 Amazon AWS Lambda 作为 worker，m5.large 实例（2 个 CPU，8GB 内存，10Gbps 网络）作为参数服务器，AWS S3 存储用于训练数据和定期备份型。作者报告了尝试两个系统的学习率范围后得到的最佳结果。对于 Bosen，只改变学习率和工人数量。所有其他配置参数都保留默认值。
图 7a 显示了不同数量的服务器（对于 Bosen）和 AWS Lambda（对于 Cirrus）在一段时间内实现的逻辑测试损失。通过对一个包含 50K 样本的数据集上的训练模型评估以得到损失值。作者发现，Cirrus 的收敛速度明显快于 Bosen。Bosen 的性能因为 worker 相互竞争共享本地缓存受到影响，该缓存在将梯度发送到参数服务器之前聚合梯度。这种设计最终导致了 Bosen 收敛速度较慢。在图 7b 中，作者使用相同的数据集和相同的预处理步骤将 Cirrus 与 TensorFlow 进行了比较。同样地，Cirrus 性能优于 TensorFlow。
图 7c 中的实验对比的是 Cirrus 和 Spark 完成协同过滤任务的性能，该实验中使用的是 Netflix 数据库[8]。由图 7c，Cirrus 比 Spark 收敛得更快，测试损耗更低。此外，作者还观察到 Spark 的 ALS 实现受到昂贵的 RDD 开销的影响，因为 Spark 需要将整个数据集加载到内存中。这导致 Spark 花了超过 94% 的时间来做与训练模型不直接相关的工作。相比之下，Cirrus 从 S3 连续向 worker 流式传输数据，这使得他们可以立即开始计算。
图 7. (a) Bosen 和 Cirrus 之间不同设置的时间损失比较。Bosen 达到的最佳损失为 0.485，Cirrus 达到最佳损失的速度至少快了 5 倍（200 秒 vs 1000 秒）。与最先进的 ML 训练框架相比，Cirrus 可以在一个或两个 Lambda 的寿命内（300-600 秒）更快地收敛，并且损失更低。(b) Tensorflow Criteo_tft 基准和 Cirrus 的收敛与时间曲线。Tensorflow 是在 32 核节点上执行的，Cirrus 在 10 个 Lambda 中运行。(c) 运行 Netflix 数据集时，Spark (ALS)和 Cirrus 的 RMSE 随时间变化曲线。Spark 在运行 Netflix 数据集时，前 4 分钟处理数据，并在 ALS 的 5 次迭代中收敛（RMSE=0.85）后终止。Cirrus 能够更快收敛到较低的 RMSE（0.833）。
图 8 中的实验验证的是 Cirrus 的可扩展性（Scalability）。通过设计该系统以实现 3 个维度的扩展：用 S3 存储训练数据，用 Lambda 计算，以及用分布式参数服务器共享内存，来实现扩展性。
存储扩展性：Cirrus 通过将 S3 中的训练数据集分割成中等大小的对象来解决这个问题。作者使用 10MB 的对象，因为作者发现这个大小可以实现良好的网络利用率，同时对于最小尺寸的 Lambda 来说也足够小。通过使用大型对象，减少了每秒的请求数量。因此，当每个 worker 从 S3 消耗 30MB/s 的训练数据时，能够将 S3 的吞吐量线性扩展到 1000 个 Cirrus workers（图 8a）。
计算扩展性：由图 8b，没有模型和参数的同步得情况下 Cirrus 可以通过并行传输输入训练数据和计算梯度来实现线性计算可伸缩性。
参数服务器扩展性：在参数服务器层面，主要挑战来自于每个虚拟机 VM 有限的网络带宽，以及更新模型和 worker 请求服务器所需的计算。Cirrus 通过 1）模型分片，2）稀疏梯度 / 模型，3）数据压缩，4）异步通信来解决这个问题。Cirrus 实现了线性可扩展性，最高可达 600 个 worker（图 8c）。
图 8. AWS 存储（GB / 秒）、AWS 无服务器计算（梯度 / 秒）和 Cirrus 数据存储（样本 / 秒）的可扩展性。每个 worker 消耗 30MB/s 的训练数据。
最后，作者对比了专门的 ML 系统 PyWren 与 Cirrus。PyWren 是一个运行在无服务器 Lambda 上的 map-reduce 框架。它提供了可扩展至数千名 worker 的 map 和 reduce 原语。PyWren 的 Runtime 经过优化可以在 AWS Lambda 上运行，AWS Lambda 也是本文用于 Cirrus 实验的无服务器平台。作者在实验中对 PyWren 进行了优化，使其每次模型更新的平均时间提高了 700 倍（从 14 秒到 0.02），但其模型每秒更新次数仍然远低于 Cirrus（图 9b），并且收敛速度明显慢于 Cirrus（图 9a）。
图 9. PyWren 和 Cirrus 在 10 个 Lambda 上运行时在稀疏逻辑回归工作负载上的性能。由于结合了预取、在模型训练迭代中重复使用 Lambda 以及通过 Cirrus 的快速数据存储进行高效的模型共享，Cirrus 实现了 2 个数量级的模型更新数量增长。训练数据预取解决了 S3 的高访问延迟问题，从而使更新速度增加了 10 倍 / 秒。
2.3、Distributed Machine Learning with a Serverless Architecture [9]
本文作者介绍了一个完全基于无服务器架构的分布式机器学习新框架：SIREN。SIREN 由本地客户端和无服务器云平台（例如 Amazon Lambda）组成，前者使用深度强化学习（Deep Reinforcement Learning，DRL）agent 进行资源调度决策，后者根据这些调度决策为 ML 训练作业加载无状态函数（Stateless Functions）。SIREN 的完整结构框架如图 10。
图 10.SIREN 结构
首先，将一个代码包部署到无服务器云平台中，其中包含用户定义的 ML 模型及其所依赖的库。然后，根据初始资源方案（即函数的数量和内存大小）加载无状态函数群，进行基于 SGD 的第一个 epoch 训练。在第一个 epoch 结束时，收集作业的函数状态和统计数据，并以状态（States）的形式反馈给本地客户端的 DRL agent，DRL agent 将采取行动为下一个 epoch 做出资源调度决策。SIREN 会随着训练作业的 epoch 推进自适应调整资源调度决策：在不同的 epoch 中，可以启动不同数量、不同内存配置的函数。
SIREN 采用的是 SGD 算法，使用 mini-batches 并在多个 Lambda 函数上运行。每个 Lambda 函数的作用就类似于传统参数服务器架构中的 worker。SIREN 与参数服务器架构的一个主要区别是，在 SIREN 中不存在参数服务器来处理模型参数更新。相反，数据和模型都存储在一个共同的数据存储中（例如 Amazon S3），所有函数都可以访问。每个函数从公共存储中读取当前模型，根据 mini-batches 训练数据计算梯度，然后直接用新计算的梯度更新公共存储中的模型。因此，整个架构是无服务器的。在 SIREN 中，作者提出了一种混合同步并行（Hybrid synchronous parallel，HSP）计算模式。如图 11 所示，在每个 epoch 内，所有的函数都可以异步更新模型，同时在每个 epoch 结束时施加一个同步屏障（Synchronization barrier），以便完成下一个 epoch 的资源调度。
已知 epoch 为 t，第 k 个 mini-batch 为Ξ_t,k，更新模型为：
在 epoch t-1 结束时的模型ω与ω_t,0 相同。HSP 在无服务器架构中是高效的，因为加载的函数是同质的，从而导致每个 epoch 的同步代价都很低。在无服务器云平台中，调用和终止函数也是轻量级的。
图 11. 无服务器云上的混合同步并行（HSP）处理。
作者使用 Python 代码实现了 SIREN，支持 AWS Lambda 之上的 ML 模型训练，并全面支持 MXNet APIs。机器学习开发人员可以在 SIREN 上运行他们的传统 MXNet 项目，而无需重构现有代码。如图 10 所示，SIREN 包括三个主要部分：(1)封装 MXNet 机器学习库的代码包；(2)用 AWS SDK boto3 构建本地客户端，调用并管理 AWS Lambda 中的无状态函数；(3)用 TensorFlow 实现 DRL agent，进行动态资源配置决策。此外，还对 AWS Lambda 进行了一系列约束，以保证无状态函数的轻量级和可移植性。
由于 AWS Lambda 的编程 runtime 不支持原生的 ML 训练算法，作者在代码包中引入了一部分 MXNet ML 库。在 AWS Lambda 上，代码包大小限制为 250 MB，这使得直接将任何现成的 ML 库（如 MXNet、TensorFlow）加载到 AWS Lambda 上都是不可行的。为了缩小 MXNet 代码包的大小，作者用不同的编译选项组合重新编译了 MXNet 源代码，并排除了无服务器云中不必要的编译选项。例如，禁用了 USE_CUDA、USE_CUDNN 和 USE_OPENMP 等选项。
在 AWS Lambda 上，单个函数的计算能力也受到限制：要求每个 Lambda 函数最多在 300 秒内执行完毕，最大内存大小为 3GB。但是，由于 AWS Lambda 支持每个 AWS 账户中多达 3000 个函数并发执行，因此 SIREN 通过使用大量 Lambda 函数并行化 ML 训练工作负载实现了高度的并行性。
作者提出了一种深度强化学习（Deep reinforcement learning，DRL）技术，用于完成 SIREN 中的动态资源部署。强化学习 (RL) 是一种经验驱动的方法，agent 通过与动态环境的交互以及执行行动获得奖励来学习如何在动态环境中表现。DRL 利用深度神经网络 (Deep neural network，DNN) 来解决 RL 问题。agent 观察来自动态环境的各种噪声信号，这些信号被称为状态（state），并将这些状态反馈给 DNN 由其产生动作。agent 在环境中采取动作并获得奖励，而奖励又被用来更新 DNN 中的参数，以做出更好的决策。DRL 在一个闭环中工作以改善决策，其最终目标是使总奖励最大化。
作者考虑在一个有 M 个样本的数据集上训练 ML 工作负载，总奖励预算为 B。如果达到一定的损失值 L 或者总奖励预算 B 用完，则训练终止。在任何一个 epoch t，调度器将对并行调用的函数数量（用 n_t 表示）以及每个函数的内存大小 m_t 做出判断。令 f_t,i 表示在第 t 个 epoch 加载第 i 个活跃函数，如图 11 所示。需要注意的是，如果函数 i 已经到了它的运行寿命，则会调用一个新的函数来代替它，且仍然用 f_t,i 来表示，所以在 epoch t 中总会有 n_t 个函数在并发执行。在每一个函数 f_t,i 中，重复计算一个新的 mini-batch 数据的聚合梯度，并根据 HSP 模式下的 SGD 更新模型参数。
在 epoch t 中，假设函数 f_t,i 花费一个完整周期(P^F)_t,i 来获取 mini-batch 数据，(P^C)_t,i 计算梯度，(P^U)_t,i 更新模型参数。函数 i 在 epoch t 的完整执行时间为：
epoch t 在 HSP 的全部持续时间为 P_t=max_i(P_t,i)。在 epoch t 结束时，ML 任务的损失值更新为 l_t。
无服务器云根据函数执行时间和函数内存大小向用户收费。令 c 表示使用 1GB 内存执行一个函数一秒钟的单价。一个 epoch t 的总花费为：
其中，T 表示 epoch 的总数。本文所述任务的目标是最小化作业完成时间，即在一定奖励预算 B 约束下解决以下优化问题：
在每个 epoch t 开始时，DRL agent 决定资源配置计划 (n_t, m_t)，即 DRL 任务中的动作 action，具体如图 12。衡量动作(n_t, m_t) 有效性的方法是在每个 epoch t 的结束进行数字 reward 量化计算。计算的依据是这个 epoch 持续的时间 P_t 和任务结束时预算是否透支。
图 12.DNN 策略表示的 DRL。
状态（State）：在本文所描述的问题中，epoch t 的状态表示为：
其中，l_t 表示 epoch t 的损失值，(P^F)_t、(P^C)_t、(P^U)_t 分别表示获取、平均计算和平均模型参数更新时间，P_t 为 epoch 的执行时间。u_t 和ω_t 分别表示平均内存和 CPU 的利用情况，b_t 为剩余预算。
动作（Action）：在本文所描述的问题中，动作表示为 a_t=(n_t, m_t)。n_t 表示激活的函数数量，m_t 表示每个函数的内存大小。DRL agent 根据策略选择操作，策略定义为给定当前状态下整个操作空间的概率分布π(a | s)。作者使用策略梯度方法，通过参数θ的函数来近似策略π(a | s)。因此，策略π可以写成π(a | s, θ)，其中θ是要学习的参数。将策略π定义为实值空间的高斯概率密度：
换句话说，如果作业成功停止，即在不超出预算 B 的情况下满足收敛阈值 L，则向 agent 分配正 C 的奖励。否则，如果作业失败，即在用完预算 B 之前还没有收敛，则给奖励赋值为负 C。在 DRL 中，agent 学习的是累计折扣奖励：
其中，γ ∈ (0, 1]为未来折扣奖励因子。在整个 DRL 训练过程中，上式中的目标函数引导着 agent 找到最优的估计值。
作者模拟了一个无服务器的云环境，运行由 DRL agent 控制的 mini-batch SGD 算法。作者使用 OpenAI Gym 实现模拟环境（
https://gym.openai.com(https://gym.openai.com/)），OpenAI Gym 是一个用于评估强化学习算法的开源接口。实验目的是验证与传统的网格搜索（Grid Search）基线方法所找到的最优（静态）策略相比使用 SIREN 进行调度的优势。作者比较了在 AWS Lambda 上使用 SIREN 和在 EC2 集群上使用 MXNet 训练 ML 作业的完成时间和成本。具体实验中选择了三种类型的 EC2 实例来构建测试集群：m4.large（2 vCPU，8GB 内存）、m4.xlarge（4 vCPU，16GB 内存）和 m4.2xlarge（8 vCPU，32GB 内存），每小时分别收费 0.1 美元、0.2 美元和 0.4 美元。
图 13 给出了 SIREN 与网格搜索最佳函数数量的比较实验。图 13（a）比较了通过网格搜索和 SIREN 实现的训练时间。与网格搜索相比，SIREN 在预算为 300 美元的情况下最多可减少 36% 的训练时间。如图 13（b）所示，网格搜索列举了不同预算下不同数量的函数的总奖励情况。SIREN 能够根据经验动态调整函数数量。图 13（c）给出了分配给每个 epoch 的函数数量。在前几个 epoch 中，SIREN 启动了大量的函数以快速降低损失值；在后几个 epoch，agent 减少了函数数量以节省成本。SIREN 的 DRL agent 通过与模拟的无服务器云的迭代交互进行在线训练。图 13（d）中的学习曲线表明，agent 通过探索不同数量的函数来学习最大化总奖励。agent 的训练在大约 200 次迭代之后完成。
图 13. SIREN 与网格搜索最佳函数数量比较。
图 14. 通过 SIREN 和 EC2 上的 MXNet 对 MNIST 数据集训练 LeNet。
图 14 的实验对比 SIREN 和 EC2 上的 MXNet。图 14(a)显示了使用 12 个 EC2 集群和使用 SIREN 训练 LeNet 的完成时间和相应的成本。由于 EC2 集群的异质性，EC2 上的成本与训练完成时间呈非线性关系。例如，m4.xlarge×6 集群和 m4.2xlarge×6 集群几乎在同一时间完成训练，但后者产生的成本是前者的两倍。相比之下，SIREN 通过更多的投资缩短了完成时间。图 14(b)显示，SIREN 动态调整每个训练 epoch 的函数及其内存。当函数数量减少时，每个函数收到的训练数据分区更大，需要更大的内存来处理数据分区。SIREN 中的 DRL agent 是通过与 AWS Lambda 在线交互进行训练的。从图 14(c)中的学习曲线可以看出，经过 150 次左右的迭代，DRL agent 的训练已经完成。
进一步的，作者在 m4.2xlarge instances 的集群上训练 LeNet、CNN 模型和线性分类模型并确定相应的成本。然后，在成本相同的情况下在 m4.2xlarge×8 集群上用 SIREN 训练同样的模型。图 15 中的实验数据显示，与相同成本的 EC2 集群相比，SIREN 使用这些模型分别减少了 40%、39.4% 和 44.3% 的训练时间。
图 15. 不同模型相同成本预算下 SIREN 与 EC2 的比较。
2.4、Serverless Linear Algebra [10]
本文作者构建了 NumPyWren：一个基于无服务器编程模型的线性代数系统，以及 LAmbdaPACK：一个为高度并行线性代数算法的无服务器执行而设计的领域特定语言。相关工作发表在 SoCC’20 中。
无服务器计算（例如，AWS Lambda、Google Cloud Functions、Azure Functions）是一种编程模型，云提供商在其中管理服务器同时动态管理资源分配。通常，无服务器平台计算会公开一个有时间限制的、无状态的 FaaS API，以及一个管理程序状态的对象存储系统。对于能够清晰地分离程序状态和逻辑的应用程序设计人员来说，无服务器平台提供了对大型计算能力的即时访问，而无需应对复杂集群部署的开销。
本文所研究的内容：密集线性代数（Dense linear algebra）极大地受益于现有的以服务器为中心的数据中心。现有的分布式线性代数框架可以通过利用局部性、网络拓扑和单个服务器内的资源紧密集成来完成高性能计算。在这样的背景下作者提出这样一个问题：这些线性代数算法能否成功地移植到一个分散数据中心中？也就是说，我们能否在无服务器编程模型中实现与基于 MPI 的分布式线性代数框架相当的性能？
本文作者构建了 NumPyWren，一个在无服务器架构上完成线性代数任务的系统。NumPyWren 执行使用 LAmbdaPACK 编写的程序，LAmbdaPACK 是作者构建的一个高级 DSL，可以简洁地表示任意基于分片的线性代数算法。NumPyWren 通过无状态函数执行来执行大规模密集线性代数程序。通过对中间语言 LAmbdaPACK 的分析，作者最终证明了分散式无服务器计算模型（Disaggregated serverless computing model）可以用于具有复杂通信程序的计算密集型程序。
NumPyWren 解决的是类似 Cholesky 分解的线性代数问题。考虑求解线性方程 Ax=b 的问题，其中 a 是对称正定矩阵。我们可以先把 a 分解成两个三角形矩阵 a=LL^T，然后解两个相对简单的 Ly=b 和 L^T x=y 得到解 x。从这个过程中可以看出，分解是该求解问题中计算代价最高的步骤。Communication-Avoiding Cholesky 是一个很好的计算 Cholesky 分解的算法。该算法将矩阵分成若干块，并得出一个计算顺序使总数据传输量最小。具体算法如下：
如图 16，在 outer loop(j)的每一步中，算法首先计算单个块 Ajj 的 Cholesky 分解(图 16(a))。这个结果用来更新由 Aij 下面的列块组成的 "面板（panel）"（图 16（b））。最后，第 j 列右边的所有区块都会根据各自的位置，通过索引更新面板（图 16(c)）。通过向下移动对角线重复这一过程（图 16（d））。
图 16. 并行 Cholesky 分解的前 4 个时间步骤：0）对角块 Cholesky 分解，1）并行列更新，2）并行子矩阵更新，3）（后续）对角块 Cholesky 分解。
作者针对 Algorithm 1 提出了两点问题。首先，作者认为 Algorithm 1 在执行过程中展现出了动态并行性。外循环（Outer loop）由三个不同的步骤组成，具有不同的并行度，从 O(1)、O(K)到 O(K2)，其中 K 是每个步骤的封闭子矩阵大小。其次，该算法在这三个步骤之间存在细粒度的依赖关系，无论是在一个迭代内还是在多个迭代之间。由此，作者提出了本文所考虑的工作，即：实现适应可用的并行化，作者通过将程序分解为可并行运行的细粒度执行单元来实现这一点。为了在无状态环境中实现这一点，作者建议以分散的方式执行依赖性分析。将描述程序控制流的全局依赖图分发给每个 worker。然后，每个 worker 根据其在全局任务图中的当前位置，对其下游依赖关系进行本地推理。
首先，我们介绍本文提出的 LAmbdaPACK：一种用于实现并行线性代数算法的特定语言。LAmbdaPACK 是生成和使用矩阵块（Tiled matrices）的命令式程序。这些程序可以对标量值执行基本的算术和逻辑运算。它们不能直接读取或写入矩阵值；相反，所有实质性的计算都是通过调用矩阵块上的本机内核来执行的。矩阵块由索引引用，LAmbdaPACK 程序的主要作用是对内核调用排序，并计算每个调用的分块索引。LAmbdaPACK 包括简单的 for 循环和 if 语句，但是没有递归，只有从 LAmbdaPACK 到内核的一级函数调用。每个矩阵块索引只能写入一次，这是许多函数式语言的共同设计原则。LAmbdaPACK 中的原语功能强大，包括 Tall Skinny QR（TSQR）、LU、Cholesky 和奇异值分解等等。LAmbdaPACK 的示例性描述如图 17 所示。
图 17. LAmbdaPACK 语言的示例性描述。
关于 LAmbdaPACK 的算法分析主要包括两个阶段。由于原始未压缩的 DAG 非常大，其节点数可能会随着 Cholesky 或 QR 等算法的输入大小呈立方级增长，因此，第一阶段的任务是分析程序并提取任务的压缩 DAG。DAG 中的每个任务对应一个数组写入，我们还需提取执行此任务所需的内核计算和数组读取。由于每个数组读取都有一个唯一的上游写入任务，因此此过程是可跟踪处理的。第二个阶段发生在 runtime，在执行任务之后，能够动态发现下游任务。使用当前循环变量绑定的信息来查询下游任务的压缩 DAG。图 18 和图 19 分别给出了 LAmbdaPACK 的 DAG 和程序示例。
图 18.LAmbdaPACK DAG 示例。
图 19. LAmbdaPACK 程序示例。
LAmbdaPACK 中没有并行原语，而是 LAmbdaPACK runtime 通过静态分析程序来推断底层依赖关系图。为了并行执行程序，作者从程序产生的依赖结构构造了一个内核调用的 DAG。作者借用并扩展了循环优化技术（loop optimization），将 LAmbdaPACK 程序转换为隐式有向无环图（Implicit DAG）。将程序 DAG 中的每个节点 N 表示为一个元组（line_number, loop_indices）。利用这个信息，可以执行程序迭代空间中的任何语句。
接下来，作者解决推导 DAG 中特定节点的下游依赖关系问题。作者提出在 runtime 处理依赖性分析：每当一个存储位置被写入时，确定从同一存储位置读取的 N（所有行，所有循环索引）中的表达式。每当一个存储位置被写入时，我们确定从同一存储位置读取 N（所有行，所有循环索引）中的表达式。作者将约束建模为一个方程组。假设单个线性代数算法中的行数必然很小，而程序迭代空间通常非常大。当数组仅由循环变量的仿射函数索引时，即形式为 ai+b 的函数，其中 i 是循环变量，a 和 b 是编译时已知的常数，则可以使用循环优化来有效地查找特定节点的依赖关系。
如图 19 中的程序示例，如果在 runtime 一个 worker 正在执行程序的第 7 行，i=0、j=1 和 k=1，以查找下游依赖项，则分析器将扫描这 7 行中的每一行，并计算是否存在一组有效的循环索引，以便在程序中的该点读取 S[1,1,1]。如果是这样，那么元组（line_number, loop_indices）定义了该任务的下游依赖项，并确定为当前任务的子任务。为了便于访问和开发，作者将 LAmbdaPACK 嵌入 Python 中。由于大多数 LAmbdaPACK 调用优化的 BLAS 和 LAPACK 内核，因此使用高级解释语言的性能损失很小。LAmbdaPACK 详细流程见 Algorithm2。
然后，我们介绍本文提出的 NumPyWren 框架。NumPyWren 框架包括五个独立可扩展的主要组件：runtime 状态存储、任务队列、轻量级全局任务调度器、无服务器计算 runtime 和分布式对象存储。图 20 展示了 NumPyWren 框架组件。
图 20. NumPyWren 执行框架的体系结构，具体为 6x6cholesky 分解期间的 runtime 状态。
- 任务排队（Task Queue）：客户端进程将需要执行的第一个任务排队到任务队列中。任务队列是一个发布 - 订阅样式的队列，它包含 DAG 中的所有节点，这些节点的输入依赖关系都已满足并准备好执行。
- 执行器配置（Executor Provisioning）：任务队列的长度由配置者（Provisioner）监控，provisioner 管理计算资源以匹配执行期间的动态并行性。在第一个任务排队后，provisioner 启动一个执行器（executor），并根据任务队列大小维护活动 executor 的数量。由于 provisioner 的角色只是轻量级的，所以它也可以作为 “无服务器” 云函数定期执行。
- 任务执行（Task Execution）：执行器管理 NumPyWren 任务的执行和调度。一旦执行器准备就绪，它就轮询任务队列以获取可用的任务，并执行任务中的编码指令。大多数任务涉及从对象存储读取输入和将输出写入对象存储，以及执行 BLAS/LAPACK 函数等。假定对象存储是一个分布式持久存储系统，它支持单个密钥的先读后写一致性。使用一个带有单一静态赋值语言的持久对象存储，有助于设计容错协议。当执行器接近无服务器系统的 runtime 限制时（AWS Lambda 为 900），执行器自动终止。如果有必要的话，provisioner 将负责雇佣新 worker。容错协议能够实现即使工作进程超过 runtime 限制或是在执行过程中被云提供商杀死，程序仍能在有效状态下运行。
- Runtime 状态更新（Runtime state update）：一旦任务执行完成并且输出被持久化，执行器就会更新 runtime 状态存储中的任务状态。runtime 状态存储跟踪整个执行的控制状态，并且需要支持每个任务的快速更新。如果已完成的任务具有 “ready” 子任务，则执行器会将该子任务添加到任务队列中。状态存储的原子性保证了每个子任务都能够被调度。这个使用执行器执行调度的过程实现了高效、分散、细粒度的任务调度。由于计算和存储的分离，NumPyWren 中的容错非常容易实现。因为对对象存储的所有写入都是持久的，所以在任务完成后都不需要重新计算。
- 任务租用（Task Lease）：在 NumPyWren 中，所有挂起的和可执行的任务都存储在一个任务队列中。保持一个不变量，即任务只有在完成后才能从队列中删除（例如，runtime 状态存储已更新，输出持久化到对象存储）。当一个 worker 获取一条任务，这个 worker 就获得了该任务的租约（lease）。在租用期间，该任务被标记为不可见，以防止其他 workers 获取这条任务。
- 故障检测和恢复（Failure Detection and Recovery）：在正常操作期间，worker 将使用后台线程续订任务租约，直到任务完成。如果任务完成，worker 将从队列中删除该任务。如果 worker 失败，它将无法再续订租约，并且该任务将对任何可用的 worker 可见。因此，故障检测在租约到期时发生，恢复时间由租约长度决定。
- 垃圾收集（Garbage collection）：由于 NumPyWren 将所有中间状态存储到一个持久对象存储区，因此在不再需要时清除状态是非常必要的。但是，由于在对象存储中存储字节的成本极低，与处理 TB 级中间状态问题的计算成本相比，在程序结束时进行垃圾收集就足够了。使用与程序相关联的唯一 id 标记对象存储中单个程序执行的所有分配。在程序执行终止后，NumPyWren 通过启动一组并行的无服务器任务来异步清理对象存储，以清理与给定程序 id 关联的所有对象。
- 自动缩放（Autoscaling）：与传统的无服务器计算模型（每个新任务分配一个新容器）不同，NumPyWren 中的任务调度和 worker 管理是解耦的。这种解耦允许自动扩展计算资源，以实现更好的性价比权衡。在 NumPyWren 中，作者采用了一个简单的自动缩放启发式算法，能够在保持较低作业完成时间的同时获得很好的利用率。
作者对 4 种线性代数算法：矩阵乘（Matrix Multiply，GEMM）、QR 分解（QR Decomposition，QR）、奇异值分解（Singular Value Decomposition，SVD）、Cholesky 分解（Cholesky Decomposition，Cholesky）进行了实验评价。对于这四种算法，作者将它们与最先进的 MPI 实现进行比较。其中 Cholesky，GEMM 和 SVDwe 使用 ScaLAPACK 实现，ScaLAPACK 是一个工业级 Fortran 库，专为高性能、分布式密集线性代数而设计。对于 QR 分解，则使用了 communication-avoiding QR 分解算法的优化实现。NumPyWren 实现大约有 6000 行 Python 代码，作者将其构建在 Amazon web 服务（AWS）平台上。对于 runtime 状态存储，使用的是 Redis--- 一个由 ElasticCache 提供的键值存储。尽管 ElasticCache 是一种配置的（而不是“无服务器”）服务，但作者发现使用一个实例就足以满足所有工作负载。此外，作者还发现，可以用托管供应商提供的键值存储（如 DynamoDB）来替换 Redis，但性能略有下降。作者将 Amazon 的简单队列服务（Simple queue Service，SQS）用于任务队列，Lambda 或 EC2，使用 Amazon S3 作为远程对象存储。
作者对实验进行了一些特殊的设备选择、环境选择或参数选择。首先，由于不能很容易地控制并发 Lambda 执行的数量或 AWS 提供的硬件类型，出于实验控制的原因，作者通过模仿 EC2 上的无服务器 runtime 来进行大部分评估以便与其他系统进行比较。其次，本文的 Lambda 模拟基于 PyWren 框架中的“独立模式”。PyWren 使用一个单独的 SQS 队列来模拟 Lambda 作业队列，并使用有时间限制的进程来模拟短函数调用。在控制底层硬件（AVX、NIC 等）时，使用 SQS 会导致不确定性。然后，目前 Lambda 的定价是 EC2 现货价格的 10 倍，这使得本文的大规模实验无法在 Lambda 上进行。作者通过实验对比发现，在 EC2 上运行模拟的无服务器环境与在 AWS Lambda 上运行的性能差别最小。最后，模拟环境中的实验还允许修改某些在真实无服务器环境中用户无法控制的系统参数，如函数超时等。
表 3 中给出针对四种密集线性代数方法 NumPyWren 与 MPI 的端到端性能比较。作者对比了在完全相同的硬件条件下（8 个 r4.16xlarge 实例中的 256 个物理核），处理大小为 256k（262144）的方阵时 MPI 和 NumPyWren 的性能。我们可以看到无服务器环境施加的限制导致的性能损失在 1.4x 到 1.6x 之间（按 wall-clock time 计算）。
表 3. 在具有 512 个虚拟核的集群上，在 N=256K 的方阵上运行时，不同算法的 MPI 与 NumPyWren 执行时间的比较。
在表 4 中，作者比较了 NumPyWren 和 MPI 使用的总核秒数（core-seconds）。对于 MPI，core seconds 是指核的总数乘以 wall-clock runtime。对于 NumPyWren，作者只计算“活动核（Active cores）”，因为空闲核是可以被其他任务利用的。作者通过在无服务器核启动和冷却计算过程中每个核的总计算时间中添加一个启动延时γ来计算总核秒数。具体的，作者选择γ=20s 以对系统进行保守的评估。对于 QR 和 Cholesky 这些具有可变并行性的算法，虽然 wall-clock time 相当，但作者发现 NumPyWren 使用的核秒数减少了 1.15 倍。对于 SVD，实验中显示出超过 3 倍的资源节省效果，不过，产生这种差异一部分是由于使用的 SVD 算法不同。然而对于具有固定数量的并行性的算法（如 GEMM），NumPyWren 中过多的通信会导致更高的资源消耗。
表 4. 在一个 256K 大小的方阵上运行算法的 MPI 与 NumPyWren 总 CPU 时间（以核秒为单位）比较。
三、文章小结
本文重点关注了基于无服务器计算的机器学习的最新研究进展。随着云计算的不断发展，开发人员对于按需执行或扩展的需求越来越强烈，越来越希望不去应对服务器或其它底层基础设施，而是集中精力关注于自身应用的开发和调优。无服务器计算的 FaaS 和 BaaS 服务必将迎来更多的关注。但是，正如我们开篇提到的，机器学习的算法或模型中包含大量的参数、复杂的处理流程，是典型的“性能关键型应用”。针对机器学习这种要求复杂通信模式和工作负载的应用如何基于无服务器计算去工作仍然是一个有待研究的问题。
本文关注了三个研究小组的四篇研究论文。其中前两篇文章提出了一种无服务器基础设施和 ML 工作流的无服务器 ML 框架原型，并将其封装为一个实现端到端管理的分布式 ML 训练框架 Cirrus，可以直接调用使用。第三篇文章提出了一个基于无服务器架构的分布式机器学习新框架，以及一种深度强化学习技术，用于实现 SIREN 中的动态资源供应。作者还提出了一种能够在无服务器架构中高效工作的 HSP 计算模式。最后一篇文章重点关注的是无服务器计算的模密集线性代数程序应用，作者提出了一个在无服务器架构上完成线性代数任务的系统 NumPyWren，通过对中间语言 LAmbdaPACK 的分析，作者最终证明了该分散式无服务器计算模型 NumPyWren 可以用于具有复杂通信程序的计算密集型程序。
在几篇文章中，作者都通过实验证明了几种框架在执行机器学习任务时性能远优于经典的基于粗粒度的 VM 集群的 ML 框架。尽管无服务器的机器学习具有敏捷、快速、可伸缩性等优点，但是它对机器学习的集成还处于初级阶段，它自身也面临着工具不全面、不成熟或者配置方式不统一等问题。随着越来越多的研究人员关注，越来越多的应用开发提出成本节约和效率提高的需要，无服务器计算将迎来更快更好的发展。
本文参考引用的文献：
[1] Charles Reiss, Alexey Tumanov, Gregory R Ganger, Randy H Katz, and Michael A Kozuch. 2012. Heterogeneity and dynamicity of clouds at scale: Google trace analysis. In Proceedings of the Third ACM Symposium on Cloud Computing. ACM, 7.[2] Joao Carreira, Pedro Fonseca, Alexey Tumanov, et al., A Case for Serverless Machine Learning NIPS'18
http://learningsys.org/nips18/assets/papers/101CameraReadySubmissioncirrus_nips_final2.pdf[3] Eric Jonas, Shivaram Venkataraman, Ion Stoica, and Benjamin Recht. Occupy the cloud: Distributedcomputing for the 99%. CoRR, abs/1702.04024, 2017.[4] Jinliang Wei, Wei Dai, Aurick Qiao, Qirong Ho, Henggang Cui, Gregory R Ganger, Phillip B Gibbons,Garth A Gibson, and Eric P Xing. Managed communication and consistency for fast data-parallel iterativeanalytics. In Proceedings of the Sixth ACM Symposium on Cloud Computing, pages 381–394. ACM, 2015.[5] Joao Carreira, Pedro Fonseca, Alexey Tumanov, et al., Cirrus: a Serverless Framework for End-to-end ML Workflows，SoCC ’19:ACM Symposium on Cloud Computing,
https://dl.acm.org/doi/10.1145/3357223.3362711[6] Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et al. [n. d.]. TensorFlow: A System for Large-Scale Machine Learning[7] Criteo Dataset.
http://labs.criteo.com/2014/02/kaggle-display-advertisingchallenge-dataset/.[8] Netflix Dataset.
https://www.kaggle.com/netflix-inc/netflix-prize-data.[9] Hao Wang, Di Niu, Baochun Li，Distributed Machine Learning with a Serverless Architecture，IEEE INFOCOM 2019，
https://ieeexplore.ieee.org/abstract/document/8737391[10] Vaishaal Shankar, et al., Serverless linear algebra, SoCC '20: ACM Symposium on Cloud Computing,
https://dl.acm.org/doi/10.1145/3419111.3421287[11] Serverless Machine Learning on Modern Hardware Using Apache Spark，
https://databricks.com/session/serverless-machine-learning-on-modern-hardware-using-apache-spark