无服务器线性代数的高性能分布式计算和容错能力的研究

281无服务器线性代数Vaishaal Shankar加州大学伯克利分校蒲启凡谷歌乔纳森·拉根-凯利MIT CSAIL卡尔·克劳斯加州大学伯克利分校本杰明·雷希特加州大学伯克利分校埃里克·乔纳斯芝加哥大学凯拉斯·沃德拉哈利斯坦福扬·斯托伊卡加州大学伯克利分校希瓦拉姆·文卡塔拉曼威斯康星大学麦迪逊分校摘要数据中心分解为数据中心操作员和应用程序设计人员提供了许多好处然而，从以服务器为中心的模型切换到非聚合模型需要开发新的编程抽象，这些抽象可以实现高性能，同时受益于更大的弹性。 为了探索数据中心分解的局限性，我们研究了一个应用领域，该领域几乎最大限度地受益于当前以服务器为中心的计算器：稠密线性代数。 我们建立NumPyWren，线性代数系统建立在一个分散的无服务器编程模型，和LAmbdaPACK，一个同伴域特定的语言设计的高度并行线性代数算法的无服务器执行。 我们表明，对于一些线性代数算法，如矩阵乘法，奇异值分解，Cholesky分解和QR分解，NumPyWren的性能（完成时间）是优化的以服务器为中心的MPI实现的2倍之内，并具有高达15%的计算效率（总CPU时间），同时提供容错。ACM参考格式：VaishaalShankar ， Karl Krauth ， Kailas Vodrahalli ， QifanPu，Ben-RaganRecht，Ion Stoica，Jonathan Ragan-Kelley，EricJonas，and Shiv- aram Venkataraman. 2020.无服务器线性代数。在ACM Sym-2020云计算研讨会（SoCC '20），2020年10月19日至21日，虚 拟 活 动 ， 美 国 。 ACM ， 纽 约 州 纽 约 市 ， 美 国 ， 15 页 。https://doi.org/10的网站上下载。1145/3419111.3421287本作品采用知识共享署名国际4.0许可协议进行许可。SoCC©2020版权归所有者/作者所有。ACM ISBN978-1-4503-8137-6/20/10。https://doi.org/10.1145/3419111.34212871介绍随着云提供商推动数据中心的分解[18]，我们看到分布式计算向更大弹性的转变数据中心分解为数据中心操作员和应用程序设计人员提供了好处通过解耦资源（CPU、RAM、SSD），数据中心运营商可以执行ecient装箱并保持高利用率，而不管应用逻辑（例如，一个应用程序在一台只使用5% RAM的机器上使用所有内核类似地，应用设计者具有在应用运行时期间按需供应和解除供应资源的灵活性（例如，仅在应用程序的令人尴尬的并行阶段期间要求许多核此外，解耦资源允许每种资源技术通过回避由当前以服务器为中心的系统（例如，内存容量墙使得CPU-内存共存不可持续）[18，41]。当前的分布式编程抽象（如MPI和MapReduce）依赖于单个服务器集合中紧密集成的资源。因此，为了编写用于分解的数据中心的应用，数据中心操作员必须公开新的编程抽象。无服务器计算（例如，AWS Lambda、Google CloudAzure Functions）是一种编程模型，其中云提供商管理服务器，并且还动态地管理资源的分配通常，这些服务公开用于执行程序逻辑的时间受限、无状态、函数即服务API，以及用于管理程序状态的对象存储系统 对于可以清晰地分离程序状态和逻辑的应用程序设计人员来说，无服务器平台提供了对大型计算能力的即时访问，而无需管理复杂的集群部署的开销。无服务器计算的设计约束对于分散式数据中心来说是自然的，但对于许多性能关键型应用程序来说是严峻的挑战，因为它们关闭了传统的性能优化途径，例如利用数据局部性或分层通信。作为一个直接的结果，无服务器平台是282（）（）SoCC主要用于简单的事件驱动应用程序，如物联网自动化，前端Web服务和日志处理。最近的工作已经将它们用于更广泛的应用，如并行数据分析[25]和分布式视频编码[17]。然而，这些工作负载要么是并行的，要么在功能之间使用简单的通信模式。 复杂的通信模式和工作负载是否以及如何在无服务器应用程序中有效地进行仍然是一个活跃的研究问题。我们研究一个应用领域，从当前的以服务器为中心的计算中心：密集线性算法。最先进的分布式线性代数框架[8，11，15]通过利用本地性，网络拓扑和单个服务器内资 源 的 紧 密 集 成 来 给 定 一 个 静 态 的 资 源 集 群 ，ScaLAPACK和LINPACK等框架在Top500等竞争中处于领先地位，这些竞争衡量了大规模线性代数任务可以实现的峰值FLOP。 因此，我们提出了一个问题：这些算法可以成功地移植到一个崩溃的数据中心吗？ 也就是说，我们能否实现与基于MPI的分布式线性代数框架相当的性能，但在无服务器编程模型施加的约束下运行？我们发现，分解实际上可以提供benets线性代数任务，因为这些工作负载有很大的动态范围内的内存和计算的要求，在他们的执行过程中。例如，在大型矩阵上执行Cholesky分解[5]（求解线性方程组的最流行方法之一）会产生具有振荡并行性和递减工作集大小的计算阶段。此外，我们发现，对于许多线性代数运算，无论其复杂结构如何，计算时间通常主导大问题大小的通信（例如，Cholesky分解的计算量为O n3，通信量为O n2. 因此，通过适当的阻塞，可以使用高带宽但高延迟的分布式存储作为大规模分布式存储器的替代。基于这些见解，我们设计了NumPyWren，一个系统，用 于 无 服 务 器 架 构 上 的 线 性 代 数 工 作 负 载 的TEMNumPyWren 执 行 使 用 LAmbdaPACK 编 写 的 程 序 ，LAmbdaPACK是我们构建的一种高级DSL，可以简洁地表达任意基于瓦片的线性代数算法。NumPyWren分析了LAmbdaPACK中的数据依赖关系，并提取了并行执行的任务图 NumPyWren然后作为无状态函数运行并行计算，同时将中间状态存储在分布式对象存储中。我们看到的主要挑战之一是，在新粒度对大型矩阵进行操作可能会导致非常大的任务图（对于块大小为4096的1Mx1M矩阵，有16M个节点我们通过使用循环优化文献中的思想来解决这个问题，图1：聚合S3读/写带宽作为数的函数达到的带宽几乎饱和的25千兆数据中心网络高达至少10k核心。原始的循环程序，而不是展开它，并表明LAmbdaPACK运行时可以扩展到大矩阵的大小，同时生成恒定大小的程序我们评估NumPyWren使用一组有代表性的分布式线性代数算法，并与基于MPI的实现ScaLAPACK比较。我们的实验表明，对于常用的线性代数例程（例如， Cholesky分解、矩阵乘法、SVD、QR）NumPyWren在具有相同硬件和核心数量的专用集群上运行的ScaLAPACK的挂钟时间可以达到2倍，同时使用的总CPU时间减少多达15%，并提供容错能力。总之，我们做出了以下贡献：(1) 我们提供了第一个具体的证据，大规模线性代数算法可以eciently使用无状态的功能和分散存储执行。(2) 我们设计了LAmbdaPACK，一种用于线性代数算法的领域专用语言，它捕获了新粒度的依赖关系，并且可以以简洁和可读的方式表达最先进的通信，避免线性代数算法(3) 我们表明，NumPyWren可以扩展到1M2矩阵上运行Cholesky分解，并且与ScaLAPACK相比，完成时间在2的因子内，同时使用的CPU时间减少15%2背景2.1无服务器环境在无服务器计算模型中，云提供商无法按需执行功能，隐藏了集群控制。来自最终用户的管理和管理费用。除了可用性优势之外，该模型还提高了效率：云提供商可以以无服务器线性代数SoCC283O OO（）O O OO比传统集群计算可能的粒度更小，并且用户不因空闲资源而被收费。然而，为了有效地管理资源，云提供商对每个资源的使用进行了限制接下来我们讨论这些约束如何影响我们系统的设计。计算。在无服务器平台中运行的计算资源通常限于单个CPU核心和短的计算窗口。例如，AWS Lambda在单个AVX核心上提供900秒的计算，并可访问高达3 GB的内存和512 MB的磁盘存储。用户可以执行许多并行功能，并且这些执行的聚合计算性能几乎呈线性扩展。函数执行中的线性可伸缩性仅适用于单个工作者之间没有通信的并行计算不幸的是，由于单个工作者是短暂的，并且由于他们的启动时间可能是错开的，因此传统的类似MPI的对等通信模型在这种环境中将不起作用。这鼓励我们利用存储，它可以用作工作人员之间的间接通信渠道。存储. 云提供商提供了从键值存储到关系数据库的许多存储选项。有些服务并不是纯粹的弹性服务，因为它们需要预先配置资源。 然而，像Amazon S3或Google Cloud这样的分布式对象存储系统拥有无限的存储空间，用户只需要为存储的数据量付费。 从[25]中完成的研究中，我们看到AWSLambda函数调用可以以800 GB/s或更高的聚合带宽读写AmazonS3，如图1所示，大致将数据中心网络带宽饱和到每个核心。 这意味着我们可以在分布式对象存储中存储计算期间的中间状态，并且仍然可以获得与从其他节点的RAM访问相同的带宽。最后，对象存储系统中的数据存储成本与实例存储器相比，TEM通常低几个数量级 例如，在Amazon S3上，数据存储的价格为每TB小时0.04美元;相比之下，最便宜的大型内存实例的价格为每TB小时6美元。 这意味着如果访问模式不需要实例内存，则使用存储系统可能更便宜。S3请求也按每个读请求4 e-6美元和每个写请求5e-6美元收费 然而，在我们的实验中，我们发现，如果存储粒度足够粗，则与总存储成本相比，每个请求的成本是微不足道的。除了存储服务之外，云提供商还提供订阅服务，如AmazonSQS或Google Task Queue。这些服务通常不支持高数据访问带宽，但提供了一致性保证比如至少一次交付，并且可以用于“控制平面”状态，比如在所有无服务器函数调用之间共享的任务队列。云供应商还提供一致的键值存储（例如，DynamoDB），可用于跨无服务器函数调用存储和2.2线性代数算法在这项工作中，我们广泛关注的情况下，大规模的稠密线性代数。这个领域有丰富的文献并行通信避免算法和现有的高性能实现[2，5，6，19]。为了激励设计决策，在随后的章节中，我们简要回顾了解决线性系统的核心子程序Cholesky因式分解的通信和计算模式。Cholesky因式分解是求解线性方程组最流行的算法之一，广泛应用于矩阵求逆、偏微分方程和蒙特卡罗模拟等领域。为了说明Cholesky分解的使用，考虑求解线性方程Ax =b的问题，其中A是对称正定矩阵。 首先对A进行Cholesky分解，得到两个三角矩阵A = LLT（ n3），然后求解两个相对简单的方程Ly = b（n2通过前向代换）和LTx= y（n2通过后向代换），得到解x. 从这个过程中，我们可以看到分解是最昂贵的步骤。[5]这是一个很好的学习方法。Cholesky分解的计算方法该算法将矩阵分为块，并推导出一个计算顺序，使总的数据传输最小化。我们选择这个例程不仅是因为它是最高性能的例程之一，还因为它展示了许多线性代数算法中算法1中示出了用于避免通信的Cholesky分解的伪代码在外部循环（j）的每一步，算法rst计算单个块Ajj的Cholesky分解（图1）。2（a））。该结果用于更新由A ij下方的列块组成的2（b））。最后，通过根据它们各自的位置对面板进行索引来更新列j右侧的所有块（图11）。2（c））。 这个过程是重复移动下对角线（图。2（d））。我们从分析算法1的计算结构中首先，我们看到算法在执行过程中表现出动态并行性外部循环由三个不同的步骤组成，它们具有不同的并行度，从1，K到 其中K是每一步的封闭子矩阵大小。此外，随着K在每次迭代中减小，可用的总体并行性SoCCV.Shankar，K.Krauth，K.Vodrahalli，Q.Pu，B.Recht，I.Stoica，J.Ragan-Kelley，E.Jonas，S.Venkataraman284.1：forj20... 杜德JJ.中国（）（）O O3：对于所有i2j+1... dNe胸罩算法高性能的经典算法（一）dB e–线性代数算法的现有实现（B当地CholeskyIter = 0Iter = 0Iter = 0Iter = 1任务依赖图2：并行Cholesky分解的前4个时间步：0）对角块Cholesky分解1）并行列更新2）并行子矩阵更新3）（后续）对角块Cholesky分解算法1避免通信的Cholesky [5]输入：A-正半对称矩阵B-块大小N-A 中的行数阻塞：Aij- A的第ij个块输出量：A的L-Cholesky分解NB向每个工人描述程序的控制流程然后，每个工作者基于其在全局任务图中的当前位置局部地推理其下游依赖性。在 接 下 来 的 两 节 中 ， 我 们 将 描 述 LAmbda-PACK（DSL，它允许这些全局依赖图的紧凑表示）和运行分布式程序的NumPyWren执行引擎3编程模型在本节中，我们将概述LAmbdaPACK，我们的2：Ljj（chole. sky（Ajj）领域专用语言，用于指定并行线性代数4：LijL5：结束6：对于所有k2j+1. de做平行线性代数被直接映射到无服务器的环境，因为他们严重依赖点对点通信-阳离子和利用数据和计算奢侈品的局部性7：对于所有l2。K...NBdo inparallel8：AKLKL在无服务器计算集群中是不存在的。而且大多数KJ9：结束10：结束ScalaPACK是专为有状态HPC集群设计的。因此，我们设计了LAmbdaPACK，以适应来自重新设计的想法。11：结束每一次迭代从K2减小到1。 我们的第二个观察结果是，该算法在迭代内和迭代之间的三个步骤之间具有非粒度的依赖性。例如，只要Lkj和Llj可用，就可以计算步骤3中的Akl（第8行）。类似地，下一次迭代可以在Aj+1j+1被更新时立即开始等在诸如MapReduce或Apache Spark之类的单程序多数据（SPMD）或批量同步并行（BSP）系统中，很难利用细粒度依赖性，其中在步骤之间强制执行全局同步屏障2.3NumPyWren概述我们将NumPyWren设计为针对具有类似于上述Cholesky分解的执行模式的线性代数工作负载。我们的目标是适应并行的数量时，我们的做法是将程序分解成可以并行运行 为了在无状态设置中大规模地实现这一点，我们建议以分散的方式执行依赖分析。我们分发一个全局依赖图在数值线性代数社区中，将算法表示为基于有向无环图（DAG）的计算[1，11]。 特别是LAmbdaPACK借用了Dague [12]的DAG执行框架技术，该框架针对HPC环境，尽管我们在分析方法和目标计算平台方面有所欠缺。 与Dague不同的是，LAmbdaPACK不需要用户预先指定线性代数内核的DAG，而是从命令式程序中推断程序DAG。通过允许算法被指定为命令式程序，我们获得了以简洁和可读的方式表达复杂的通信避免算法的能力，例如[14]中发现的那些算法，这些算法通常需要数百行MPI代码。我们在LAmbdaPACK中实现的所有算法都不到40行代码，这通常是由于底层算法的高度复杂性。我们设计的LAmbdaPACK允许用户简洁地执行，按平铺线性代数算法。这些例程将它们的计算表示为对矩阵块（不能在本地存储器中存储的小的子矩阵）的操作 平铺算法和在像ScaLAPACK的库中发现的经典算法之间的主要区别在于算法本身对于机器布局、连接性等是不可知的，只有丹尼斯并行地做无服务器线性代数SoCC285NOON一个计算图的块指数的矩阵这种统一的，独立于机器的抽象化复杂算法使我们能够适应大多数标准的线性代数例程的无状态执行引擎。3.1语言设计LAmbdaPACK程序是简单的命令式例程，它产生和消耗平铺矩阵。这些程序可以对标量值执行基本的算术和逻辑运算 它们不能直接读取或写入矩阵值;相反，所有实质性的计算都是通过调用矩阵瓦片上的原生内核来执行的。 矩阵瓦片由索引引用，LAmbdaPACK程序的主要作用是对内核调用进行排序，并为每个调用计算瓦片索引。LAmbdaPACK程序包括简单的for循环和if语句，但没有递归，只有一个级别的函数调用，从LAmbdaPACK例程到内核。每个矩阵块索引只能写入一次，这是许多函数式语言中的一个共同设计原则1。在这个程序中，将索引表达式捕获为符号对象是我们执行依赖性分析的关键。这些简单的原语足够强大，可以简洁地实现Tall SkinnyQR（TSQR），LU，Cholesky和奇异值分解等算法。LAmbdaPACK 的 描 述 如 图 3 所 示 ， Cholesky 和 TSQR 的LAmbdaPACK实现示例如图5所示。3.2程序分析我们的程序分析分为两个阶段。 简单地说，未压缩的dag太大而无法完全展开，因为dag中的节点数量可以随着Cholesky或QR等算法的输入大小而立方地增长。因此，第一阶段分析程序并提取任务的压缩DAGDAG中的每个任务都对应于一个数组写入，我们还提取了执行此任务所需的内核计算和数组读取这个过程是容易处理的，因为每个数组读取都有一个唯一的上游写入任务。第二个分析阶段发生在运行时，在执行任务之后，动态地发现下游任务。我们使用当前循环变量绑定的信息 来查 询下游任务的压 缩DAG。我们的压缩DAG表示需要恒定的空间，并支持查询节 点 - 边 缘 关 系 eciently 。 图 5 和 图4 分别示 出 了 示 例LAmbdaPACK程序和dag。LAmbdaPACK中没有并行原语，但是相反，LAmbdaPACK运行时推导出底层1任意程序都可以很容易地翻译成这个静态的单赋值-形式，但我们发现直接以这种风格编程是很自然的Uop=阴性|不|日志|天花板|地板|Log2Bop=添加|子|Mul|Div|Mod|和|或Cop=EQ|NE|Lt|GT|乐|葛IdxExpr=IndexExpr（Strmatrix_name，Expr[]indices）Expr =BinOp（Bop 操作，Expr 左，右表示）| CmpOp(Cop op, Expr left, Expr right)| UnOp(Uop op, Expr e)| Ref(Str name)| FloatConst（float val）| IntConst（int val）Stmt=KernelCall（Strfn_name，IdxExpr[] outputs，IdxExpr[]matrix_inputs，Expr[]scalar_inputs）| Assign(Ref ref, Expr val)| Block(Stmt* body)| If(Expr cond, Stmt body, Stmt?其他）| For(Str var, Expr min,Exprmax、Expr step、Stmt body）图3：LAmbdaPACK语言的描述。依赖关系图，静态分析程序。 为了并行执行程序，我们从程序引起的依赖结构构造内核调用的DAG。 简单地将程序转换为可执行图将导致DAG爆炸，因为表示程序所需的数据结构的大小将随着输入数据的大小而缩放，这可能导致难以处理的编译时间。感兴趣的大多数线性代数算法都是N3，甚至像MadLINQ[33]这样的系统在运行时使用的 N3操作的快速符号枚举也会导致难以处理的计算时间和开销，问题相比之下，我们从循环优化社区借用和扩展技术，将LAmbdaPACK程序转换为隐式有向无环图[16]。我们将程序DAG中的有了这个信息，程序迭代空间中的任何语句都可以执行。现在的挑战在于推导给定DAG中特定节点的我们的方法是在运行时处理依赖分析：每当一个存储位置被写入时，我们确定从同一存储位置读取的表达式（所有行，所有循环索引）我们通过将约束建模为方程组来解决确定特定节点的下游依赖性的问题。我们假设在一个线性代数算法中的行数必然很小。SoCCV.Shankar，K.Krauth，K.Vodrahalli，Q.Pu，B.Recht，I.Stoica，J.Ragan-Kelley，E.Jonas，S.Venkataraman286[客户端]----O（）[][]然而，程序的迭代空间通常太大而不能直接枚举（如上所述，这通常是n3）。幸运的是，线性代数算法中的数据访问模式是高度结构化的。特别是当数组仅由循环变量的函数索引时-即ai + b形式的函数，其中i是循环变量，a和b是编译时已知的常数-可以采用循环优化的标准技术来确定特定节点的依赖性。这些技术通常涉及求解整数值线性方程的小系统，其中系统中的变量数量取决于程序中嵌套循环变量线性分析的例子 考虑一下Cholesky Pro-图5中的gram如果在运行时，工作者正在执行程序的第7行，其中i=0，j=1和k=1，以确定下游依赖关系，分析器将扫描程序的7行中的每一行，并计算是否存在有效的循环索引集，使得可以从程序中的该点读取S1， 1， 1如果是，则元组（line_number，loop_indices）否认该任务的下游依赖性，并成为当前任务的子任务该程序中的所有指标表达式只包含一个指标，因此每个系统都能精确求解。 在这种情况下，唯一的子节点是节点（2，i：1，j：1，k：1）。请注意，此过程仅取决于程序的大小，而不是正在处理的数据的大小非线性和还原。 一些常见的算法-MIC模式-特别是归约-涉及非线性循环边界和数组索引。与传统的编译器不同，由于我们所有的分析都发生在运行时，所有的循环边界都已经确定。因此，我们可以通过首先求解线性方程组并使用该解来求解剩余的非线性方程组来求解线性和非线性方程组非线性分析的例子考虑图5中的TSQR程序。 假设在运行时，一个worker正在执行第6行，其中level = 0，i = 6，那么我们想要求解R i+2 level，level=R 6，1的循环变量赋值（第7行）。 在这种情况下，其中一个表达式包含一个涉及i和level的非线性项，因此我们不能直接求解这两个变量。然而，我们可以很容易地解决水平，并获得值1。然后，我们将结果值代入非线性表达式，得到一个只涉及i的线性方程。然后我们可以解出i，得到解（6，i：4，level：1）。我们注意到，图5所示的for循环结构是一个分支因子为2的树约简。使用这种方法，我们可以捕获的非线性数组索引，如高瘦QR（TSQR），通信避免QR（CAQR），比赛旋转LU（TSLU），和双对角分解（BDFAC）的算法中的树减少。用于我们分析的完整伪代码胆固醇trsm（i=0，j=1）trsm（i=0，j=2）trsm（i=0，k............图4：Cholesky分解1defint（O：BigMatrix，S：BigMatrix，N：int）：2，i在range（0，N）中3O[i，i]= chol（S[i，i，i]）4对于范围（i+1，N）中的j：5O[j，i]= trsm（O[i，i]，S[i，j，i]）6对于k在范围（i+1，j+1）中：10 -11-1时间复杂度为O [i，j，i]，O[k，i]）1deftsqr（A：BigMatrix，R：BigMatrix，N：Int）：2对于i在范围（0，N）中：3R[i，0]= qr_factor（A[i]）范围内水平为4（0，log2（N））5对于范围（0，N，2**（水平+1））中的i：[001 pdf 1st-31 files]第一个参数：7R[i，level]，R[i+2 ** level，level]）图5：Cholesky和Tall的LAmbdaPACK代码-瘦QR分解算法可以在算法2中找到算法中的SOLVE调用是指通用符号非线性方程求解器。我们的实现使用Sympy求解器[39]实施. 为了便于访问和易于开发，我们将我们的语言嵌入到Python中。由于大多数LAmbdaPACK调用优化的BLAS和LAPACK内核，使用高级解释语言的性能损失很小。4系统设计接 下 来 我 们 介 绍 NumPyWren的 系 统 架 构 我 们首先介绍NumPy-Wren中的高级组件，并跟踪计算的执行过程。 接下来，我们描述实现容错的技术无服务器线性代数SoCC287运行时状态执行人...获取/写入状态λλ获取/放置块对象存储λbucket/input/bucket/output/...获取/添加任务任务队列低秩列更新重生兰达斯G任务和置备程序λ⇥P22个P[{}（16 1220 1616 124X12 2531 2016 133420 3150 3730 255416 2037 3028 214216 1630 2846 2712 1325 2127 20图6：NumPyWren的执行框架的架构，显示了6 6分解。已执行第一个块更新指令以及单个列更新。算法2LAmbdaPACK分析输入：- LAmbdaPACK程序的源代码A-一个具体的数组被写入idx-A的具体数组索引被写入输出量：O={N0，.，Nk}-从A[idx]读取的程序节点的具体集合1：O=2：对于行做3：M线。read_matrices做4：如果M=A，则5：S = SOLV E M。symbolic_idxidx=06：O=O S7：如果结束8：结束9：结束并减轻掉队者。最后，我们讨论了我们的设计启用的动态优化。 为了充分利用云的弹性和易管理性，我们完全基于现有的云服务构建NumPyWren，同时确保我们能够实现高性能计算工作负载的性能和容错目标。我们的系统设计由独立可扩展的五个主要组件组成：运行时状态存储，任务队列，轻量级全局任务调度器，无服务器计算运行时和分布式对象存储。 图6展示了我们系统的组件。执行过程按以下步骤进行：1. 任务入队：客户端进程将需要执行的第一个任务入队到任务队列中。 任务队列是一个请求订阅样式的队列，包含DAG中所有节点，这些节点的输入依赖关系已得到满足并准备执行。2. ExecutorProvisioning ： 任 务 队 列 的 长 度 由Provisioning监控，该Provisioning管理计算资源以匹配执行期间的动态并行性。后第一个任务入队时，供应商启动执行器，并根据任务队列大小维护活动执行器的数量由于provider的角色只是轻量级的，它也可以作为一个“无服务器”的云函数定期执行。3. 任务执行：执行器管理执行和调度Numuling PyWren任务。一旦执行器准备就绪，它将轮询任务队列以获取可用的任务并执行任务中编码的指令。大多数任务涉及从对象 存 储 读 取 输 入 和 向 对 象 存 储 写 入 输 出 ， 以 及 执 行BLAS/LAPACK函数。 假设对象存储是一个分布式的、持久的存储系统，它支持各个键的写后读一致性。使用一个持久的对象存储和一个静态赋值语言有助于设计我们的容错协议。 当执行器接近许多无服务器系统施加的运行时限制时（AWS Lambda为900），执行器会自动终止。如果有必要的话，供应商将负责启动新的工人 只要我们选择任务的粗糙度，使得许多任务可以在分配的时间间隔内成功完成，我们就不会看到太大的及时工人终止的每小时惩罚。 我们的容错协议使运行中的程序保持在有效状态，即使工人超过运行时限制，并在执行过程中被云提供商杀死。4. 任务状态更新：一旦任务执行完成，完成并且输出已被持久化，则执行器更新运行时状态存储中的任务状态。运行时状态存储跟踪整个执行的控制状态，并需要支持每个任务的快速原子更新。如果一个已完成的任务有“准备好”执行的子任务，执行器会状态存储的原子性保证了每个子进程都将被调度。我们想强调的是，我们只需要运行时状态存储中的事务语义，我们不需要运行时状态存储和子任务排队原子地发生。我们将在第4节进一步讨论这一点 这种使用执行器执行调度的过程导致了任务的精确、分散、细粒度的调度。SoCCV.Shankar，K.Krauth，K.Vodrahalli，Q.Pu，B.Recht，I.Stoica，J.Ragan-Kelley，E.Jonas，S.Venkataraman288*O（）NumPyWren中的容错由于计算和存储的分解而更容易实现。由于对对象存储的所有写入都是持久的，因此在任务完成后不需要重新计算 因此，NumPyWren中的容错被简化为恢复失败任务的问题，与许多系统相反，所有未检查点的任务都必须重新执行[33]。在NumPyWren中，我们重新-MPI NumPyWren慢通过租赁机制[21]执行失败的任务，这允许系统跟踪任务状态，而无需调度程序定期与执行器通信。任务租赁：在NumPyWren中，所有挂起和可执行的任务都存储在任务队列中。我们维护一个不变式，即任务只有在完成后才能从队列中删除（即，运行时状态存储器已经被更新并且输出持久化到对象存储器）。当一个任务被工作者获取时，工作者获得对该任务的租用在租用期间，任务被标记为不可见，以防止其他工作线程获取相同的任务。 由于租约长度通常被设置为小于任务执行时间的值，例如， 10秒，工作者负责续订租约，并在执行任务时保持任务不可见。故障检测和恢复：在正常操作期间-工作线程将使用后台线程续订任务的租约，直到任务完成。如果任务完成，工作进程将从队列中删除该任务 如果工作进程失败，它将无法再续订租约，并且任务将对任何可用的工作进程可见。因此，故障检测通过租约到期发生，恢复延迟由租约长度确定。垃圾收集：由于NumPyWren将所有中间状态存储到持久对象存储中，因此当不再需要时，我们必须清除状态。然而，由于在对象存储中存储字节的成本极低（$0.04每TB小时），与处理TB级中间状态问题的计算成本相比，在程序结束时进行垃圾收集是成功的。我们用一个与程序关联的唯一id来标记对象存储中单个程序执行的所有分配 在程序执行终止后，NumPyWren通过启动一组并行的无服务器任务来异步地清理对象存储，以清理与给定程序ID相关联的所有对象。自动缩放：与传统的无服务器计算模型（每个新任务都分配一个新的容器）相反，NumPyWren中的任务调度和工作人员管理是分离的。这种解耦允许自动扩展计算资源，以实现更好的成本性能权衡。历史上，许多自动缩放策略已经被探索[36]。在NumPyWren中，我们采用了一个简单的自动缩放控件-表1：在具有512个虚拟内核的群集上，在N=256K的方形主机上运行时，MPI与NumPyWren的执行时间报告了3次运行的中位性能对于扩展，NumPyWren例如，假设sf= 0。5、当有100个挂起的任务，40个正在运行的worker时，我们再启动一百540= 10名工人。为了缩小规模，如果在最后T超时秒内没有找到任务，每个在平衡状态下，正在运行的worker数量是挂起任务数量的sf倍。 所有的自动缩放逻辑都由图6中的“provider”处理。5评价我 们 评 估 NumPyWren 的 4 个 线 性 代 数 算 法 矩 阵 乘 法（GEMM），QR分解（QR），奇异值分解（SVD）2和Cholesky分解（Cholesky）。 这些算法的计算复杂度均为N3，但在数据访问模式上有一定的局限性.对于所有四种算法，我们比较最先进的MPI实现。对于Cholesky，GEMM和SVD 3，我们使用ScaLAPACK，这是一个工业强度的Fortran库，专为高性能，分布式密集线性代数而设计。对于QR分解，我们使用了避免通信的QR分解算法的优化实现[14]，特别是[13]中的实现。 我们还做了详细的分析，我们的系统的可扩展性和容错性使用Cholesky分解。5.1设置实施. NumPyWren的实现大约有6000行Python代码，我们构建在Ama-zonWeb Service（AWS）平台上。 对于我 们 的 运 行 时 状 态 存 储 ， 我 们 使 用 Redis ， 一 个 由ElasticCache提供的键值存储。虽然ElasticCache是一种预配置（而不是“在保证工作的同时，也达到了良好的利用率完成时间低。2对于SVD，仅并行进行带状形式的简化算法（秒）（秒）下来SVD5.8e44.8e4N/A二维9.9e31.4e41.5xGEMM5.0e38.1e31.6xCholesky 1.7e32.5e31.5x无服务器线性代数SoCC289NumPyWren核心秒数(a) GEMM（b）QR图7：GEMM和QR5.2系统比较我们首先在表1中展示了NumPyWren与MPI在四种广泛使用的稠密线性代数方法上的端到端比较。 我们将MPI与NumPyWren进行比较，当在大小为256k（262144）的方阵上操作时，同时可以访问完全相同的硬件（256个物理核心，跨越8个R 4。16个xlargege实例）。在表1中，我们可以看到无服务器环境所施加的约束导致了1.4倍到1.6倍的性能损失。为了理解开销，在图7中，我们比较了算法MPI（核心-秒）NumPyWren（核心秒）资源节约通过两种算法：GEMM和QR分解，由一台机器在网络上读取的字节数我们看到NumPyWren读取的字节量总是大于SVD 2.1e7 6.2e6 3.4xQR 2.6e6 2.2e61.15x GEMM 1.2e61.9e60.63xCholesky 4.5e5 3.9e5 1.14x表2：在256K大小的方阵上运行的算法之间MPI与NumPyWren总CPU时间（以核心秒为单位）的比较。资源节约被称为MPI核心-秒. 我们计算“活动”核心秒数，NumPyWren作为作业执行前后的10秒窗口，以考虑启动拆卸延迟。工作量。 我们发现，我们可以用一个受管理的供应商提供的键值存储（如DynamoDB）来取代Redis，但性能会略有下降。 我们使用Amazon的简单队列服务（SQS）作为任务队列，Lambda或EC2。我们使用Amazon S3作为远程对象存储。模拟AWS Lambda. 由于我们无法轻松控制并发Lambda执行的数量或AWS提供的硬件类型，出于实验控制的原因，我们通过模仿EC2上的无服务器运行时来进行大部分评估，以进行与其他系统相比的所有实验。 我们的Lambda模拟基于PyWren框架中的“独立模式”[25]。 PyWren使用一个单独的SQS队列来模拟Lambda作业队列，并使用时间受限的进程来模拟短函数调用。在控制底层硬件（AVX、NIC等）时，使用SQS会导致不确定性。 此外，Lambda当前的定价比EC2 spot实例贵10倍，这使得本文中的大规模实验无法在Lambda上进行。 如表3所示，我们发现在MPI。这是每个任务无状态的直接后果因此，它的所有参数必须从远程对象存储（在我们的实验 中是AmazonS3 ） 中 读取 。 此 外， 对于QR 分解和GEMM，MPI读取的数据分别比NumPyWren少21倍和6倍。然而，我们注意到，即使NumPyWren在网络上读取的字节数超过MPI的21倍，我们的端到端完成时间也只慢了47%。在表2中，我们比较了NumPyWren和MPI使用的总核心秒数。对于MPI，核心秒数是核心总数乘以挂钟运行时间。对于NumPyWren，我们希望在我们的核心秒计算中只考虑“活动核心”，因为其他任务可以使用空闲核心。我们通过将启动延迟y添加到计算过程中执行的每个内核的总计算时间来计算总核心秒数，以说明无服务器核心的启动和冷却。我们根据[40]中测量的无服务器启动延迟计算y除了一个无服务器功能提供程序之外，所有无服务器功能提供程序的冷启动延迟都在10秒以下 对于我们的核心第二测量，我们使用y = 20 s来获得我们系统的保守性能测量。对于像QR和Cholesky这样具有可变并行度的算法，虽然我们的挂钟时间是可比的（ 在2倍之内），但我们发现NumPyWren使用的核心秒数减少了1.15倍。对于SVD，我们看到超过3倍的资源节省，但这种差异部分是由于SVD算法中使用的差异4。然而，对于具有固定并行度的算法（例如，GEMM），NumPyWren中的过度通信导致更高的资源消耗。EC2与AWS