ACM通信
研究突出了
分布式矩阵向量乘法中近乎完美负载平衡的无速率码
信贷:盖蒂,Freepnglogos
大规模的机器学习和数据挖掘应用需要计算机系统执行大量的矩阵-向量和矩阵-矩阵乘法运算，这些运算需要在多个节点上并行处理。离散节点(不可预测地变慢或故障的计算节点)的存在是这种分布式计算的主要瓶颈。理想的负载平衡策略是动态地将更多的任务分配给更快的节点，这需要了解或监控节点的速度，以及快速移动数据的能力。最近提出的固定速率擦除编码策略可以处理不可预测的节点减速，但它们忽略了散乱节点所做的部分工作，从而导致大量冗余计算。我们提出一个rateless喷泉编码我们证明它的延迟渐进地等于理想的负载平衡，并且它执行的冗余计算渐进地为零。我们的想法是创造线性组合米并将这些编码行分配给不同的工作节点。原始的矩阵向量积可以被解码只要稍微大于米行向量积由节点共同完成。并行和分布式计算的计算速度比非编码方案快三倍。
1.简介
矩阵向量乘法构成了大量科学计算和机器学习应用的核心，包括解偏微分方程、神经网络的前向和后向传播、计算图的PageRank等。在大数据时代，大多数这些应用程序都涉及到将非常大的矩阵和向量相乘，在一台机器上无法高效地执行计算。这推动了一些算法的发展，这些算法寻求通过在多个计算节点上分布计算来加快矩阵向量乘法的速度。单个节点工人)并行执行各自的任务，而中心节点主)将所有这些worker的输出集合起来，完成计算。
掉队者的问题。不幸的是，大规模分布式计算作业经常会因为运行在异常缓慢或无响应的worker上的任务而遇到瓶颈叫掉队。3.由于作业只有在所有并行任务都执行完的情况下才算完成，因此对于具有大量并行任务的作业来说，这个问题更加严重。即使一个节点速度变慢并成为掉队者的概率很小，也会导致作业的预期延迟大幅增加。正如迪恩所指出的3.（表1)时，执行多个并行任务的延迟可能比单个任务的中值延迟(1 ms)大很多(140 ms)。在云基础设施中，节点的分散被广泛观察到，这是一种常态，而不是例外。
表1。比较不同的相乘策略米xn矩阵A和向量x使用p工作者节点。延迟值是近似的，许多计算值是针对没有一个节点变慢的情况。
1.1.以前的解决方法
负载均衡策略。克服等待慢节点的瓶颈的一个明显的解决方案是将任务从繁忙或慢节点转移到空闲或快节点。这种工作窃取或动态负载平衡策略通常在共享和分布式内存设置中实现。这种方法包括建立一种持续监控工人的协议，并将任务从慢工人转移到快工人。它需要对计算环境进行相当大的集中控制，而这在云系统中可能不可行，因为云系统中的节点可能会由于后台进程、网络中断等原因而不可预测地变慢。在分布在很大地理区域的分布式系统中，数据隐私和在节点之间移动数据的通信成本也可能是问题所在。因此，最好制定一种原则性强、易于实施的分散缓解办法，不涉及在工人之间移动数据。
任务复制。现有系统，如MapReduce4和火花20.通过启动掉线任务的副本来处理掉线的问题，这被称为备用任务。Wang对这种任务复制策略进行了理论分析18文中提出了基于工人运行时分布尾部添加冗余副本的方案。在排队理论领域，最近有一系列的工作分析了多服务器系统中任务复制对排队延迟的影响。8，9，11，17对于本工作的重点，分布式矩阵-向量乘法，一个简单的复制策略是分割矩阵一个成p / r(r除以工人人数p)子矩阵，并复制每个子矩阵r工人。然后，主人等待最快的工人从每一套r来完成它的子矩阵和向量的乘法x以便恢复结果b = Ax。
Erasure-coded矩阵向量乘法。从编码理论的角度看，任务复制是一种特例擦除码克服数据丢失或擦除，并从传输位的一个子集恢复消息的方法。Erasure code最初用于解决分布式存储中快速下载内容时的掉线问题。10被划分为k块和使用(磷、钾最大距离可分离(MDS)代码(如里德-所罗门代码)可以通过下载任何k的p编码的块。
与分布式存储不同，计算任务的擦除编码并不简单。一份工作,n并行任务需要设计成任何k的n任务足以完成工作。然而，对于线性计算，如矩阵向量乘法，这是可能的。近期作品6，12，13采用MDS代码来加快分布式环境下矩阵向量积的计算速度。例如，假设我们想要乘一个矩阵一个与向量x使用3个worker节点和一个(3,2)MDS代码。然后,我们分手一个沿行分成两个矩阵一个1而且一个2这样
．工作节点存储矩阵一个1，一个2,一个1+一个2，每个节点将其矩阵乘以x。任何两个工人的结果都足以获得Ax,因此，系统可以容忍1个掉队者。
1.3.我们的无速率编码方法
矩阵向量乘法采用的复制或MDS编码策略为固定速率策略;也就是说，它们确定了冗余率k / p当编码矩阵一个并使用最快的结果k的p工作者节点。这种方法的主要缺点是:(1)它不能在最快的时间内执行负载平衡k节点和考虑其速度的变化，(2)它丢弃了由p- - - - - -k离散的工人。我们建议使用。来解决这两个问题rateless喷泉码，特别是Luby Transform (LT)代码14这是已知的可扩展的，并构成了无线通信标准中实用的擦除编码方案的基础。16
无速率编码的矩阵向量乘法算法生成米e=α米(α > 1)编码的线性组合米矩阵的行一个然后平均分配p工作者节点。每一个线性组合都是通过选择产生的d的米均匀随机的行并将它们相加。例如,如果d= 2，我们选择行一个1而且一个3.的一个,则编码行为一个1+一个3.，如图3一．的值d，简称度的线性组合，是一种I.I.D.实现的精心选择的度分布ρ(d)．对于LT码，ρ(d)为鲁棒孤子分布。每个工人收到米e/ p矩阵的编码行一个还有向量的一个拷贝x。它计算行向量积，例如一个1+一个3.）Tx＝b1+b3.对于编码行(一个1+一个3.)，并将它们发送回主节点。由于精心选择的度分布ρ(d)，主人可以使用迭代剥离解码器14(见图3 b)来恢复乘积向量b＝斧头具有较低的解码复杂度O(日志米)．总的来说，它需要等待任何米的＝米(1 + ε)要完成的行向量积所有对于节点，ε是一个很小的开销;ε→0为米→∞。
与先前提出的基于MDS代码的编码技术相比，无速率代码提供了以下关键优势。
接近理想的负载平衡。为了适应不同工作节点的速度，最小化完成乘法运算的总时间Ax,人们可以使用一种理想的负载平衡方案，只要每个工作节点完成当前任务，就会动态地分配一个行向量积计算任务给每个工作节点。因此，速度更快的节点比速度更慢的节点完成更多的任务，这就是最终的结果b＝斧头时获得。p节点共同完成米行向量的产品。我们的无速率编码策略实现了几乎相同的负载平衡优势，而不需要每次动态分配一个行向量乘积的任务所带来的通信开销。在我们的策略中，节点需要共同完成任务米的＝米(1 + ε)行向量的乘积，对于小的ε，当它趋于0时米→∞。相比之下，MDS的编码策略不会根据不同的节点减速程度进行调整;他们使用来自k节点并忽略其余的p- - - - - -k节点。因此，无速率编码比MDS编码策略具有更低的时延。
微不足道的冗余计算。MDS编码的一个主要缺点是，如果没有离散，那么工作人员就会集体工作议员/ k行向量积，而不是m。在无速率编码策略下，节点的总体性能最高米的＝米(1 + ε)行向量积其中ε→0表示米，矩阵的行数一个增加。
最大的流浪者宽容。一个(p，k) mds编码的分布式计算具有较强的鲁棒性p- - - - - -k离散的节点,k∈[1,2，…，p］．减少k增加了离散容忍度，但也增加了冗余计算。无速率编码方案的容忍度可达p- 1个离散节点，冗余计算开销可以忽略不计。
低解码复杂度。有人可能会说，MDS编码方法也可以使用部分计算，并实现近乎完美的负载平衡，如果我们构建一个(米e，米) MDS代码(用于给定的冗余量米e/ m)编码米xn矩阵。这种代码的解码复杂度是O（米3.)，这对于大号来说是不可接受的米在实践中。无速率码提供较低的解码复杂度:O（米日志米)用于LT码，14而且O（米)为迅猛龙密码。16
在Severinson中，最近提出了使用LT编码进行矩阵向量乘法15和王。19然而，这些作品没有利用LT代码的“无速率”属性，而是在固定速率设置中使用它们。据我们所知，我们的工作是最先开发的ratelessLT代码的本质是在分布式矩阵计算中执行负载平衡，并利用慢速工作人员完成的所有部分工作。我们提供了该策略在理想负载平衡下所实现的延迟的第一个理论分析，并表明它渐进地实现了近乎完美的延迟和计算成本。此外，我们在Amazon EC2上给出了大量的实验结果，局部并行计算和分布式计算。
2.问题公式化
2.1.系统模型
考虑乘以a的问题米×n矩阵一个与一个n×1的向量x使用p工作节点和一个主节点，如图1．工作节点只能与主节点通信，不能直接与其他工作节点通信。目的是计算结果b＝斧头以一种分布式的方式，并减轻不可预测的节点减速或分散的影响。的行一个使用纠错代码进行编码，以给出米e×n编码矩阵一个e,在那里米e≥m。我们表示由参数α =添加的冗余量米e/ m。矩阵一个e是沿着它的行分开给p余子式一个e, 1、……一个e,p同等大小的:这样的工人我存储子矩阵一个e,我．来计算矩阵和向量的乘积b＝斧头,向量x与工人沟通，使工人我是负责计算产品的吗一个e,我x。
图1。基于主-worker框架的编码分布式矩阵向量乘法系统模型。主控程序生成编码矩阵Ae通过对a . Worker行应用一种编码方案我存储了a的一个子矩阵e用一个e,我并发送编码行向量积为e,我致主人(我= 1,…,p)．不同的be,我’s可能有不同的尺寸。master解码be中编码的行向量积e,我，我= 1,…,p来恢复b = Ax。
为了完成分配的任务，每个工作人员需要计算表单的行向量乘积序列一个e,jx在哪里一个e,j是jth排一个e．由于节点速度的可变性或分配给它的计算量的可变性，工作节点完成一个或多个行向量乘积的时间可能是随机的。主节点将所有工作者(或其子集)的计算聚合到向量中be，然后对其进行解码，得出最终结果b＝斧子。如果be是不可解码的，主程序等待工人计算更多的行向量积。
2.2.性能标准
我们使用以下度量来比较不同的分布式矩阵-向量乘法方案通过理论分析和相关的模拟(章节4)，并行、分布式和无服务器环境的实验(章节5)。
定义1(延迟(T))。延迟T是系统完成足够的计算所需的时间，以便b＝斧头能否成功解码从工人计算聚合be．
定义2(计算量(C))。计算次数C定义为行向量乘积的总个数一个e,jx由工作节点集体执行，直到b＝斧头是解码。
对于任何策略，我们都有C≥米在哪里米行数是一个或者是元素的个数b。
2.3.比较的基准
我们将提出的无速率编码策略的性能与三种基准进行比较:理想负载平衡、r-replication，以及(磷、钾) mds编码策略，正式描述如下。图2说明了在每种策略中，行向量积任务分配给工人和从工人那里收集任务的不同方式。
图2。每个正方形表示总共的一个行向量积任务米被完成的任务p工人。在理想方案中，我们有一个中心队列米任务和每个工人被分配一个新的任务，一旦它成为空闲，直到所有米任务完成。在复制方案中，主服务器等待每个子矩阵的最快worker。MDS编码后，主节点需要等待k的p工人，但每个工人都要完成米/ k任务。无速率编码策略只需要等待米(1 + ε)任务所有的工人。
理想的负载平衡。的乘法米×n矩阵一个与n×1的向量x可以被当作工作对待吗米任务，其中每个任务对应于一个行向量乘积。在理想的负载平衡策略中，主节点维护一个中心队列米任务。它动态地将一个任务分配给p当一个worker完成它之前的任务时。矩阵与向量的乘法在精确时完成米任务是由工人集体完成的。这种策略无缝地适应不同的工作速度，而不执行任何冗余计算(C＝米）;因此，它给出了最佳的延迟计算权衡。这种策略可能不切实际，因为主节点和工作节点之间经常通信。然而，它可以作为一个很好的理论基准来与无速率、复制和MDS策略进行比较。
的r复制策略。一个简单的分布式乘法策略是分割一个沿着它的行进入p / r余子式一个1、……一个p / r,rm / p每行(假设p / r分米)，然后将每个子矩阵乘以x在并行r不同的工作节点。主程序从最快的程序中收集结果r被分配计算产品任务的节点一个我x对所有我。计算得到的产品聚合到米×1的向量b。r设置= 1对应于幼稚或未编码的策略一个分解为p个子矩阵，每个工作节点计算对应的子矩阵-向量乘积。虽然这种方法执行的计算次数最少，但它很容易出现分散的节点或节点故障。增加副本的数量以冗余计算为代价提供了更大的离散容忍度。真实的分布式计算框架，如MapReduce4和火花20.经常使用r= 2;也就是说，每个计算分配给两个不同的工作节点，以增加可靠性和错落容忍度。
的（磷、钾）MDS-coded策略。近期作品12，13应用MDS编码来克服非编码策略中存在的掉队问题。这个策略包括提前繁殖一个在中心节点用合适的编码矩阵F表示MDS的代码。使用(磷、钾) MDS代码，矩阵一个是沿着它的行分成k矩阵一个1、……一个k,各有米/ k行。MDS代码添加p- - - - - -k冗余的矩阵一个k＋1、……一个p，它们是两个矩阵的独立线性组合一个1、……一个k．工人我计算产品一个我x．因此，该系统具有较强的鲁棒性p - k流浪汉。然而，这种策略增加了大量的计算开销。当没有节点慢时，系统执行议员/ k行向量乘积(与米未编码情况下的行向量积)。
3.提出Rateless策略
我们描述了无速率码，特别是LT码，14可以应用于执行编码矩阵向量乘法，然后提出一种分布式实现该方案，以减少在计算矩阵向量积中的掉线b＝斧头使用第2.1节的框架。
3.1.LT-coded矩阵向量乘法
Luby中提出的Luby变换(LT)代码14是一类擦除码，可用于从有限的源符号集合生成无限数量的编码符号。将LT码应用于矩阵-向量乘法米矩阵的行数一个源符号。每个编码符号都是的和d从矩阵行中均匀随机选择的源符号。因此,如果年代d⊆{1,2，…，米}是的集合d行索引，对应的编码行是
．
每个编码行的原始行数，或度d，根据Luby中描述的鲁棒孤子度分布来选择。14一旦程度d是选择的，编码是通过选择来执行的d源符号均匀随机(这决定年代d)，并将它们相加，以产生一个编码符号。说明了编码过程图3一．
图3。(a)行编码的二部图表示1,一个2,……米矩阵a的每一行编码为d均匀随机选取A的行，其中d由鲁棒孤子度分布导出。(b)在迭代解码过程的每一步中，直接解码一个单次一编码的符号，并从其参与的所有求和中减去该符号。
一旦行编码矩阵一个e都生成了，我们可以计算编码后的矩阵向量积吗be＝一个ex．解码所需的矩阵向量积b＝斧头来自于米的的象征be我们使用迭代剥译码器在露比描述。14如果b= (b1，b2、……b米，解码器就可以接收符号b1+b2+b3.，b2+b4，b3.，b4，以此类推，因为每一行一个e几行的和是一个。解码(见图3 b)以迭代的方式执行。在每次迭代中，解码器找到一个一级编码符号，覆盖相应的源符号，并从与该源符号相连的所有其他编码符号中减去该符号。
由于编码使用随机二部图，解码所需的符号数量米源符号成功地是一个随机变量，这对于鲁棒孤子度分布是
概率至少为1 - δ。14此外，这里描述的解码过程的复杂性是O（米ln米)用于LT码(由于鲁棒孤子分布的精心设计)。这是在我们的设置中选择LT码而不是其他解码复杂度高达的随机线性码的关键原因O（米3.)．
3.2.分布式的实现
的米×n矩阵一个编码生成米e×n编码矩阵一个e在哪里米e=αm。每一行的一个e的随机子集的和是一个如3.1节所述。的行之间映射的知识一个而一排排的一个e是成功解码的关键吗图3一而且3 b．因此，这个映射存储在主服务器上。编码步骤可以被视为预处理步骤，因为它只在最初执行。
的α米所述编码矩阵的行平均分布于p工作节点如图所示图1．把一个用一个向量x，主人交流x工人们。每个工人繁殖x每一行一个e存储在它的内存中，并将乘积(标量)返回给主服务器。主程序收集窗体的行向量积一个e,jx(元素be)，直到它有足够的元素可以恢复b。如果一个worker节点完成了所有的αm / p在主程序能够解码之前分配给它的行向量乘积b,当master从其他worker收集更多的行向量产品时，它将保持空闲状态。
一旦master从workers那里收集到足够数量的编码行向量积，它就可以恢复所需的矩阵向量积b＝斧头元素的子集be＝一个ex它已经收集使用迭代剥离解码器。一旦主解码了乘积向量的所有元素b＝斧头，它发送一个完成通知所有工作节点停止其本地计算。
以下修改可以使当前实现在实际系统中更加高效。
块交流:为了真正监控每个worker完成的部分工作，master需要接收每个编码的行向量乘积一个e,jx从工人。但是，这会带来很大的通信开销，这可能会增加慢速网络中的延迟。为了避免这种情况，在我们的分布式计算实验中，我们使用子矩阵-向量乘积
在哪里
是j编码子矩阵的第n部分一个e我储存在工人我，每一部分大约对应子矩阵总行的10%。注意,如果一个是非常大的，那么对工人来说是不可行的吗我阅读一个e我从记忆中一下子等等一个e我x需要按部分计算任何编码方案。
使用猛禽代码:尽管LT代码易于实现和快速解码，但它仍然是14在实践中是否因开销而次优米的- - - - - -米解码原始文件所需的额外符号米源符号。在我们的实验中，我们观察到对于一个矩阵一个与米= 11,760行，我们需要等待12500个编码的行向量乘积来解码b＝斧头概率为99%。高级无速率代码，如猛禽代码16可以解码米源符号米任意的(1 + ε)符号常数ε甚至有限的价值的m。由于Raptor码是实际无线标准中使用的无速率码，我们希望它能用于我们的编码分布式矩阵向量乘法策略的实际实现，以提高效率。
使用系统的无速率代码:我们可以使用系统的LT/Raptor码来完全避免解码(在没有显著掉队的情况下)16在哪里米源行一个1，一个2、……一个米中已编码行的子集一个e．总体方案可以设计为每个工人先计算系统符号对应的行向量积一个1，一个2、……一个米然后计算其他编码产品(在节点减速的情况下)。这将排除解码的需要，如果没有/很少的散乱，从而减少了整体延迟。
4.性能分析
在本节中，我们从理论上分析了LT编码的性能和三种基准测试策略——理想负载平衡，(磷、钾医学博士,r-复制-根据延迟(定义1)和计算(定义2)。我们的结果总结在表1．
4.1.延迟模型
我们考虑一个简单的延迟模型，如图4,工人我初始延迟(设置时间)为X我之后，它花费常数时间τ每行向量乘积任务。因此,工人我需要时间Y我执行B我行向量积计算
图4。工人我有一个随机的初始延迟X我，之后它完成行向量乘积任务(用小矩形表示)，每个任务的时间τ。延迟T为产品b = Ax完成足够任务的时间。
这个延迟模型是由迪恩的观察得出的3.需要注意的是，延迟的可变性主要是由于工作节点上运行的后台任务造成的延迟，一旦请求真正开始执行，可变性就会大大降低。我们的模型还捕捉到了增加计算量对延迟的影响——如果一个工人被分配了更多的计算量，那么延迟就会更大。当X我是以速率μ为指数分布的，时间工作者我需要执行b计算分布为
4.2.无速率编码与理想的负载平衡
在理想的负载均衡策略中，米行向量积任务(包括乘法的工作米×n大小一个与向量x)保存在主服务器的一个中心队列中，并动态地分配给空闲的worker，每次一个任务。工作完成时米任务是由工人集体完成的。无速率编码策略在两个方面与这种理想策略不同，因为它的延迟更大:(1)每个工人得到米e/ p=αm / p编码行，因此，快速worker可能会在master能够恢复之前耗尽行b＝Ax,和(2)工人集体需要完成米(1 + ε)任务，其中ε是一个小开销，减少为米→∞。我们在下面(非正式)定理中陈述的主要理论结果比较了这两个延迟。
定理1。T的延迟LT和计算CLT我们的LT编码分布式矩阵向量乘法策略在计算一个m的乘积×n矩阵一个用n×1向量x对于大m，满足以下条件:
其中me=α米(α≥1)为编码行数，每个worker的初始延迟为X我∼exp(∝)而且τ是计算每个行向量乘积所花费的时间。由于LT编码的固有设计， ε→0作为米→∞。
这些结果表明只要编码行数米e足够大米，尽管不执行动态任务分配，但无速率编码策略可以无缝地适应不同工作人员的初始延迟。它的运行时TLT和计算CLT渐近收敛于理想策略。这也在表1，这表明无速率编码策略的预期延迟和计算次数与理想策略相同(1 + ε开销对应于成功解码所需的额外符号数量)。最后要注意的是，理想的负载平衡方案在实践中并不能完全实现。窃取工作5可以通过将任务从忙碌的工人转移到空闲的工人身上来潜在地接近这一策略。然而，实现这些方法可能不是在所有情况下都可行，例如，当工作人员之间的通信延迟太大，或由于隐私问题，数据被限制在特定的工作人员上。在这项工作中，我们表明这是可能的从算法上通过使用第3节中描述的无速率编码计算策略，实现矩阵向量乘法接近理想的延迟性能没有在工人之间移动数据。
4.3.与MDS和复制策略的比较
与我们的无速率编码策略不同，mds编码和基于复制的策略给出的延迟和成本要比理想方案差得多，而且差距不会趋近于零。
表1的预期延迟的表达式r复制和(磷、钾(2)中延迟模型的mds编码方案。注意，在这两种情况下，都增加了冗余(增加了r和减少k导致第一项的增加(每个节点的计算量增加)和第二项的减少(掉队者造成的延迟减少)。因此，掉队器缓解的代价是工人额外的计算，这甚至可能导致延迟的增加。这与定理1相反，定理1表明，无速率编码策略的期望延迟总是随着冗余的增加而减少(增加α)。此外，第二项中的log因子会导致延迟T代表，TMDS总是大于T理想的由于在理想和lt编码方案的延迟中不存在log factor 1/∝项表1．
备注1。无速率编码策略的另一个重要优势是，工人执行的计算数量，CLT，总是等于米的不像MDS和复制策略那样随冗余增加而增加(增加α)。此外由于E [米的]=米(1 + ε)和ε→0表示米→∞,E [CLT渐近地逼近最小计算次数(米)需要恢复一个米维矩阵向量乘积。
备注2。而使用所有工人的部分工作的好处可以通过使用行上的任意随机线性代码来获得一个,LT码的关键强度是它们的低O（米ln米)解码复杂度。使用一个(米e，米行上的MDS代码一个有O（米3.)解码的复杂性，这是不可接受的大m。
在我们的延迟模型(1)下，我们模拟了分布式矩阵向量乘法的MDS、复制和lt编码方案米= 10000行矩阵，p= 10个worker，时滞模型参数∝= 1.0，τ = 0.001 (图5)．我们将冗余量限制在α =米e/ m≤2.0，因为这是基本的2复制方案中的冗余量。观察到lt编码策略(α = 2.0)明显优于MDS编码策略(与k= 8)，因为它不仅表现出接近理想的潜伏期(图5一个)，但总计算量更少(图5 b)比MDS编码。此外，增加冗余(减少k)在MDS编码中会导致在某一点之后的延迟更高，如图5 c(和预期的一样表1)．另一方面，在不增加计算量的情况下，LT编码的延迟收敛于理想方案的延迟。
图5。对于复制方案，延迟的尾部概率是最高的。MDS代码在延迟方面表现更好，但它们执行大量冗余计算。LT码的延迟尾是所有方案中最轻的。此外，lt编码方案执行的冗余计算明显少于MDS编码或复制。所有的模拟都是针对矩阵向量乘法任务米= 10000行矩阵，p= 10个工作节点，延迟模型参数∝= 1.0，τ = 0.001。
5.实验结果
我们证明了在并行和分布式计算设置中，无速率代码在加速分布式矩阵向量乘法方面的有效性。
5.1.并行计算
我们考虑1万× 1万矩阵的乘法一个10000 × 1向量的随机整数x使用Python的Multiprocessing Library并行处理100多个进程。7我们比较未编码的2-复制的MDS编码(k= 80,50)， LT编码(α = 1.25, 2.0)接近。编码矩阵的行一个e平均分配给p= 100个进程，将行与x并行执行。实验以不同的随机方式重复10次x每次，我们记录平均延迟(为成功解码收集足够的行向量积所需的时间)和总计算量。平均延迟结果(图6)表明，lt编码和mds编码方法明显比未编码和2-复制方法快(约1.2倍)，而图6 c结果表明，lt编码方法比MDS或2-复制策略执行的总计算量更少，从而导致更有效的资源利用。注意，当MDS使用k= 80的延迟与LT编码的延迟相当(α = 1.25和α = 2.0)， MDS编码的延迟和总计算量都是随减少而增加的k到50，因为每个节点的计算负载更高(如第4节所讨论的)k对应于系统中“快速”工作者的数量。在大多数实际系统中，“快速”工作人员的数量是暂时的，因此是不可预测的。我们的实验表明，MDS编码对的选择是高度敏感的k不正确的选择导致更高的延迟。另一方面，LT编码不仅速度快，而且对冗余量(α)不敏感，因为α可以在不损失性能的情况下达到内存约束所允许的最大冗余量。
图6。并行编码分布式矩阵向量乘法的实验(Python Multiprocessing7)和分布式[AWS EC21]的设置表明，lt编码策略比所有其他方法的平均延迟更低(在不同场景中提高1.2到3倍)，并且比复制或MDS编码执行更少的计算。每个误差条对应一个标准差。
5.2.分布式计算
我们创造了一个70t2的簇。亚马逊网络服务(AWS) EC2上的小型工人1用11,760 × 9216矩阵相乘一个从自学(STL)-102来自同一数据集的不同向量(长度为9216)的数据集。我们再次比较了未编码的2-复制的MDS编码(k= 56, 35)， LT编码(α = 1.25, 2.0)。编码矩阵Ae是平均分配给p= 70个worker，每个worker每次计算大约14个行向量乘积，然后将结果传递给master，以平衡过多的通信(一次通信一行)和过多的数据大小(一次通信所有行)。图6 b展示了不同方法的平均延迟(经过5次试验)。这两种lt编码方法几乎比mds编码方法快两倍，几乎比未编码方法快三倍。图6 d结果表明，lt编码策略的总计算量也比MDS或2-replication策略少。情节中图7还表明，对于我们的无速率编码策略，单个工人时间的可变性显著降低(图7 d)，因为在我们的方法中，快速节点比慢节点执行更多的任务，从而获得更好的负载平衡。此外,TLT是最接近T理想的，理想负载平衡策略的延迟近似为在所有工人中计算11,760个行向量乘积的最小时间。
图7。不同矩阵向量乘法负载均衡的比较。每个工人的条形图的高度表示工人计算行向量积所花费的时间，或者直到它完成分配的任务，或者因为最终的矩阵向量积Ax已被成功解码而被主服务器终止。虚线表示每种情况下的总延迟(矩阵向量乘积Ax可以成功解码的时间)，黑色虚线表示理想负载平衡的延迟。lt编码方法展示了接近理想的负载平衡，并且比其他方法具有更低的延迟。
6.结论
提出了一种基于rateless喷泉码在存在慢节点(掉线节点)的情况下加速分布式矩阵向量乘法。对于一个具有米行，我们的策略要求节点集体完成略多于米行向量的产品。因此，它可以无缝地适应不同的节点速度，并实现近乎完美的负载平衡。此外，它具有较小的冗余计算开销(渐近为零)和较低的解码复杂度。理论分析和实验表明，与现有的非编码、复制和MDS编码方法相比，我们的方法可以获得更好的延迟计算权衡。在未来，我们计划将我们的方法扩展到特殊的线性计算，如稀疏矩阵向量乘法(SpMV)和傅里叶变换，并设计原则性的擦除编码方案来加速分布式非线性计算。
致谢
该项目得到了CMU院长奖学金、高通创新奖学金、美国国家科学基金会CCF资助。1850029，以及亚马逊研究基金。
参考文献
1.亚马逊。亚马逊网络服务EC2, 2006。https://aws.amazon.com/ec2/．
2.Coates, A.， Ng, A.， Lee, H.无监督特征学习中的单层网络分析。在14年的会议记录th人工智能与统计国际会议(2011)，机器学习研究进展(PMLR)， 215-223。
3.迪恩，J，巴罗佐，洛杉矶。Commun。ACM 56， 2(2013)， 74-80。
4.Dean, J.， Ghemawat, S. MapReduce:在大型集群上简化数据处理。Commun。ACM 51， 1(2008)， 107-113。
5.迪南，J.，奥利维尔，S.，萨宾，G.，普林斯，J.，萨达亚潘，P.，曾，c.w。使用消息传递实现不平衡计算的动态负载平衡。在IEEE国际并行与分布式处理研讨会论文集，周志强，2007,1-8。
6.杜塔，S.， Cadambe, V.， Grover, P.。“短点”利用编码短点积分布式计算大型线性变换。在30年会议纪要th国际神经信息处理系统会议(2016)，神经信息处理系统(nps)， 2100-2108。
7.p s的基础。多处理》2008。https://docs.python.org/3/library/multiprocessing.html．
8.Gardner, K.， harcholo - balter, M.， Scheller-Wolf, A.， Van Houdt, B.一个更好的工作冗余模型:解耦服务器减速和工作规模。IEEE / ACM反式。网络25， 6(2017)， 3353-3367。
9.Joshi, G.通过冗余协同:通过自适应复制提升服务能力。ACM SIGMETRICS表演。Eval。牧师45， 3(2018)， 21-28。
10.刘勇，刘志强，刘志强。基于编码分布式存储系统的内容下载延迟存储权衡问题研究。IEEE j .选取。地区Commun 32， 5(2014)， 989-997。
11.Joshi, G.， Soljanin, E.， Wornell, G.减少云系统延迟的有效冗余技术。ACM反式。模型。执行。Eval。第一版。系统2， 2(2017)， 1-30。
12.Lee K.， Lam, M.， Pedarsani, R.， Papailiopoulos, D.， Ramchandran, K.使用代码加速分布式机器学习。IEEE反式。64年正理论。， 3(2017)， 1514-1529。
13.Li S.， Maddah-Ali, m.a.， Avestimehr, A.S.分布式计算的统一编码框架。在IEEE全球通信会议研讨会论文集，北京，2016,1-6。
14.卢比，M. LT密码。在43年的会议记录理查德·道金斯IEEE计算机科学基础年会，纽约，2002,271-271。
15.Severinson, A.， i Amat, A. g .， Rosnes, E.块对角线和LT代码，用于分散服务器的分布式计算。IEEE反式。Commun 67， 3(2018)， 1739-1753。
16.肖克罗拉希，A.，卢比，M.等。“猛禽”代码。发现。趋势®Commun。正无穷。理论6， 3-4(2011)， 213-322。
17.孙，Y.，郑，Z.， Koksal, C. E, Kim, K.， Shroff, N. B.可证明延迟存储云中的有效数据检索。在IEEE计算机通信会议论文集， ieee, ny, 2015。
18.王德，Joshi, G.， Wornell, G. w .大规模并行计算中的高效离散复制。ACM反式。模型。执行。Eval。第一版。系统4， 2(2019)， 7:1-7:23。
19.王松，刘军，施洛夫，N.编码稀疏矩阵乘法。在机器学习国际会议论文集(2018)，机器学习研究进展(PMLR)， 5152-5160。
20.Zaharia, M.， Chowdhury, M.， Franklin, M. j .， Shenker, S.， Stoica, I. Spark:具有工作集的集群计算。HotCloud 10， 10(2010)， 95。
本作品授权于数字图书馆是由计算机协会出版的。版权所有©2022 ACM股份有限公司
没有发现记录