不确定环境下的云负载优化

151···不确定环境下的云负载Moshe Babaioff以色列赫兹利亚微软研究院moshe@microsoft.comIshai Menache微软研究院美国华盛顿州雷德蒙德ishai@microsoft.com龙尼·莱姆·佩·勒Googlerlempel@google.com华盛顿州柯克兰亚历山大·斯利夫金斯美国纽约州纽约市微软研究院slivkins@microsoft.comBrendan Lucier微软研究院美国马萨诸塞brlucier@microsoft.comSamChiu-waiWong，微软研究院，美国华盛顿州雷德蒙德sam.cw.wong@gmail.com摘要云计算客户通常在近似规则的时间表上提交重复的作业和计算管道，其中到达和运行时间表现出差异。这种模式是机器学习中典型的训练任务，允许客户部分预测未来的工作要求。 我们开发了一个云计算平台的模型，以在线方式接收工作报表（SoW）。工作说明书描述了未来的工作，其到达时间和持续时间是概率性的，其效用提交代理下降的完成时间。到达和持续时间分布，以及效用函数，被认为是私人客户信息，并由战略代理报告给一个调度器，优化社会福利。我们设计了定价、调度和淘汰机制，以激励真实报告工作说明书。一个重要的挑战是，尽管该平台有可能饱和，但仍要保持激励措施。我们引入了一个框架，以减少调度的不确定性下的松弛调度问题没有不确定性。使用这个框架，我们解决了对抗性和随机提交的工作报表，并分别获得对数和常数竞争机制。CCS概念• 计算理论→气动机构设计·网络→云计算。关键词调度，云计算，在线算法，机制设计ACM参考格式：MosheBabaioff ， Ronny Lempel ， Brendan Lucier ， Ishai Menache ，AleksandrsSlivkins，and Sam Chiu-wai Wong. 2022.真实的在线调度大部分工作是作者在Mic r osoft时完成的。允许免费制作本作品的全部或部分的数字或硬拷贝，以供个人或课堂使用，前提是制作或分发副本的目的不是为了盈利或商业利益，并且副本的第一页上必须尊重作者以外的其他人拥有的本作品组件的版权。允许使用学分进行摘要 以其他方式复制、重新发布、在服务器上发布或重新分发到列表，需要事先获得特定许可和/或付费。请求权限请发邮件至permissions@acm.org。TheWebConf 2022，2022年4月25日©2022版权归所有者/作者所有。授权给ACM的出版权。ACM ISBN 978-1-4503-9096-5/22/04。. . 十五块https://doi.org/10.1145/3485447.3512060不 确 定 性 下 的 云 工 作 负 载 在 procACM Web Conference 2022（TheWebConf 2022），2022年4月25日至29日，法国里昂虚拟活动。ACM，美国纽约州纽约市，11页。https://doi.org/10.1145/3485447.35120601介绍云计算平台为其客户提供了无与伦比的计算资源要充分利用这种不断增长的规模，需要使用大量云资源同时调度许多客户的工作负载。近年来，对特定类型工作负载的需求急剧增长：生产级机器学习模型的训练管道。这些工作负载具有特定的特征和挑战，必须通过云平台来解决不确定的随机工作要求。部署到生产中的机器学习模型通常需要定期运行的数据处理和训练管道，例如， 每周或每小时。训练步骤可能取决于几个数据准备工作（清理数据、特征工程和编码等）的完成情况。按照某种先决条件的顺序运行这种结构使得预测未来的作业和提前调度资源成为可能然而，任何特定作业实例的确切定时将取决于诸如训练数据的大小之类的因素，训练数据的大小可能仅在作业要被执行的时刻（并且甚至可能不在那时）被揭示。因此，云计算系统和客户可以获知已提交的和即将到来的作业的持续时间的分布延迟相关实用程序。客户从重复训练管道的每个实例中获得的效用将取决于完成时间。 在某些应用程序中，刷新后的模型越早可用于部署越好。 在其他情况下，客户可能在严格的截止日期之前具有恒定的效用，并且在此之后具有较低的效用或没有效用。对完成时间的准确敏感度在不同客户之间差异很大，因为它源于每个客户的业务问题和模型部署策略。信息不对称与激励。客户可能比云平台拥有更多关于他们即将到来的工作的信息，以及操纵工作要求的能力。例如，战略客户可能会人为地夸大其训练数据的大小，或者引入不必要的并发量，如果这样做可以带来更好的价格或更低的延迟。因此，我们认为这些属性是私人信息。的152≤（）下一页（）下一页TheWebConf 2022，2022年4月25日Moshe Babaioff等人面对战略代理人的平台必须激励真实的报告，以确保客户不会通过操纵工作需求的预测来获得1云平台如何应对这三大挑战？大多数遗留任务处理器都是被动的：它们对即将到来的工作负载几乎没有预见性，在工作到达时处理它们，并且不支持提前提交。 在另一个极端，是要求工作负载提前足够多地宣布其需求的部署者，以便更好地计划其执行。这两种方法都不能完全解决机器学习培训管道，其中工作只能部分预测。1.1我们的贡献和技术随机工作需求模型 我们的第一个贡献是云调度模型，捕获部分可预测的作业需求。在我们的模型中，作业被在线声明给调度系统 每个作业都有并发需求和确定不同完成时间值的效用函数，调度程序的目标是最大化总效用（即， 社会福利）。我们假设计算节点的总供应量远远大于任何一个作业的并发需求。重要的是，作业的规范还包括可能到达时间的分布（即，最早可能的执行时间）和持续时间（即，完成所需的时间）。 我们将此规范称为工作声明（SoW）。2该平台可以做出调度决策，并根据SoW提供的预先知识宣布价格。然而，作业的到达时间仅在作业到达的时刻在线显示，并且作业的真实持续时间可能仅部分地知道，直到作业完成的时刻作业是不可抢占的，但可以被逐出。付款可以取决于实际使用情况。在作业需求上指定分配而不是提前预留资源的能力可以显著影响客户效用。举一个小例子，假设在时间0提交的作业将在某个（整数）时间k X到达，对于每个kX，到达时间k是2k-X（否则它到达<在时间X）。作业总是在一个时间单位内需要一个计算单位，但不需要在到达时立即调度：如果它在第k轮完成，如果这作业一到达就被调度，那么它只使用一个计算单位，客户但是，如果要求客户在提交时预留计算时间块，则需要预留至少k个单元以获得期望效用Θk。 对于许多这样的作业，强制代理提交确定性请求将大大减少福利（即使每个作业都很短）。 因此，允许代理提交概率请求并让平台在需要时仅分配所需的资源（并仅对所使用的资源收费）将是非常有利的。1虽然云计算客户倾向于提交许多工作负载，但我们认为客户是短视的，他们会分别为每个工作进行优化。2我们的理论模型提出了一个接口，客户可以直接向平台声明分发。 这是一个突出客户激励的抽象，因为概率信息的任何方面都可以被操纵。 更一般地，由平台实现的预测引擎可以代表客户提供一些或全部分布信息。我们将在第6节进一步讨论这一点。有驱逐的标价机制 我们发展了一个设计真实工作表在线调度算法的框架. 我们的算法采用公布价格机制的形式，该机制公开了一个价格菜单，每个价格菜单对应于资源的每个潜在分配。调度算法可以随着新的SoW到达系统而随时间增加这些价格当为即将到来的作业显示SoW时，调度程序将立即分配将可能的到达时间映射到作业开始时间的扩展计划，选择该扩展计划以在当前价格下最大化预期的客户效用（并且受到驱逐概率的影响，如下所述）。这样的计划激励真实的报告，因为系统代表战略代理人进行优化。这种方法具有重要的好处，即系统可以在提交SoW时提交从实现到结果和价格的映射。在线分配的标价机制并不新鲜，已在各种情况下使用。我们的环境面临的一个挑战是，由于工作需求是随机的，执行计划的竞争性分配有时会无意中过度分配事后可用的供应。 一个常见的解决方案是在分配资源时留出间隙，以减少过度分配的机会。不幸的是，这并不足以解决我们的问题：由于我们的调度程序旨在运行任意长的时间范围，即使是低概率的过度分配事件最终也会发生，在这种情况下，平台必须驱逐正在运行的作业和/或取消未来的承诺。在发生过度分配的情况下（非常罕见），简单地驱逐所有作业并重置系统是很有诱惑力的然而，这种极端的政策可能会对激励措施产生重大影响 一个怀疑平台接近饱和的客户可能会通过歪曲他们的工作来提前完成，从而避免即将发生的驱逐。相反，我们的机制以特定的顺序驱逐作业也就是说，最先清除其工作说明书最近到达的工作。这可能包括尚未开始执行作业，则将取消这些作业。这个LIFO策略有一个重要的属性，即作业被驱逐的概率在提交SoW时就确定了，并且与未来的提交无关这使我们能够将驱逐概率纳入执行计划的选择，这对激励至关重要。事实上，我们证明，任何属于这个框架内的算法将激励每个SoW的真实启示，即使当系统接近饱和。减少不确定性的调度 我们提供了一个简化框架，用于设计上述形式的机制。 我们考虑一个松弛的排序问题，其中供应约束只需要保持在期望的工作需求的分布。因此，没有饱和的危险，所以设计有竞争力的在线算法的问题是显着简单。给出了一个在线多时间公布的价格算法ALG这个宽松的问题，我们展示了如何设计一个多时间机制，使用ALG作为指导，并（近似）继承其性能保证的原始问题定理1.1（形式1）。假设ALG是一个鲁棒的在线标价算法，该算法对于松弛调度问题是α -竞争的. 然后，对于任何n> 0，假设有足够的计算资源供应，在我们的框架中存在一种机制，对于原始调度问题是α-真实的和α（1 + α）-竞争的。153[客户端]（）下一页（）下一页（（））（（））（）不确定性下的云工作负载的真实在线调度TheWebConf 2022，2022年4月25日至29日，虚拟活动，法国里昂。随着SoW的到来，我们的机制模拟ALG的进展（放松供应约束），并在选择效用最大化的执行计划时使用ALG的价格。我们的机制还跟踪驱逐的概率，由于饱和和驱逐时调度帐户。当饱和概率足够低时，效用最大化分配方案的选择在真实问题和模拟问题之间是一致然而，当饱和概率变得太高时，真实分配可能与模拟偏离。为了处理这种可能性，我们要求算法ALG是鲁棒的，在这个意义上，它的福利下降优雅，如果一些作业分配被破坏的对手。 面对去系统化，我们的机制将扮演一个腐败对手的角色，并迫使ALG以与所选择的执行计划一致的方式进行分配。一个重要的技术挑战是饱和事件在时间上是相关的。事实上，如果该系统目前已经饱和，那么在不久的将来，它很可能会保持接近饱和的状态，从而扭曲未来的分配决定。原则上，这可能导致过度分配导致更多过度分配的颠簸状态，并且系统永远不会恢复。我们排除了这一点，证明了总的实现使用很快回到集中在其预期。证明涉及到建立一个新的浓度界的鞅，可能是独立的利益。我们框架内的在线机制最后，我们提供了两个示例polytime机制来说明如何实例化我们的框架。首先，我们考虑一个对抗的变体，其中SoW以对抗但非自适应的方式在线到达。3在这种情况下，我们设计了一个OlogDmH-竞争性的实时在线调度器，其中Dm是任何作业的最大持续时间，并且正作业值被归一化为位于1，H。 这反映了用于资源分配的已知的基于指数增加的价格阈值的竞争性在线算法。事实上，我们使用这样的算法作为我们的约简的“输入”。其次，我们考虑一个随机变量的工作的到达时间是任意的，但他们的工作说明书是独立于已知的（但不一定相同）分布。（由于每个SoW都包含一个分布，因此先验信息是分布上的分布。我们将我们的减少应用于最近的O1竞争性标价机制的变化，以间隔调度[15]，获得O1竞争性真实的在线调度器。与第一个示例不同，该机制将要求作业的持续时间在到达时间（即，当准备执行时）。定理1.2（形式1）. 对于任何n> 0，假设有足够的计算资源供应，对于随机作业需求的调度，存在一个α-真实的，α-竞争的在线机制，其中α=O log DmH用于对抗变体，α=O1用于随机变体。随机变量的机制假设工作持续时间在工作到达时被揭示。1.2相关工作云资源管理。 云资源管理在过去十多年中一直是一个非常活跃的研究课题。特别相关的是为工作提供某种形式的表现的想法3每个SoW仍然描述了工作需求的分布，并根据期望对绩效进行评估; SoW规范是对立的。保证，通常称为服务水平协议（SLA）[17，27，36]。为了实现SLA，系统分析作业以估计其资源需求、持续时间，有时甚至基于数据推断其截止日期;参见，例如，[16，22，27]和其中的参考文献。最近的许多工作都致力于调度机器学习工作负载。特别相关的是依赖于预测某些作业属性的调度系统。为了突出一些这样的系统，Tiresias [23]是一个在GPU上调度ML作业的实用系统它使用估计的资源消耗概率和作业完成时间来确定资源分配的优先级。 Optimus [33]是深度学习集群的作业调度器，它构建了性能模型，用于估计作为分配资源的函数的训练时间。然后，该模型用于通过集中优化问题动态分配资源，以最小化总完成时间。与我们的模型不同，没有考虑到未来的就业机会，也没有解决激励问题。云定价云业务的出现自然引起了人们对各种经济考虑的关注。一些主要的研究课题包括设计适当的定价机制（例如，导致效率或利润最大化，但对于最终用户仍然是简单和可理解的价格结构），如何最大化投资回报（例如，通过现货定价[1，32]），如何利用数据来完善定价机制参数等;有关云定价的调查，请参阅[2，37]。让我们关注一下作业所有者和云提供商之间的SLA定价[5，24，25，30]假设工作对计算资源有一定需求，并有一个截止日期（或更一般地说，完成的价值函数，如我们的模型），并设计激励相容的定价方案，使社会福利最大化。[8，26]采取市场方法，而不放大特定客户。我们的论文与所有这些作品的不同之处在于明确考虑了随机设置，其中作业到达和持续时间都是随机的，这是一个与ML作业更相关的模型。机器学习工作负载的定价是一个相对较新的研究领域。[9]提出了一个训练作业调度的原-对偶框架，其中资源价格是该框架的对偶变量。其他最近的作品[12，31]考虑了基于拍卖的GPU调度机制，其总体目标是平衡效率和公平性。这些论文都没有明确的模型在工作的到来和持续时间的随机性。在线预约 大量的在线调度算法研究了在执行过程中同时到达的逆向选择作业，而调度算法必须在线选择接纳哪些作业。当工作价值与工作长度相关时，例如当价值密度（长度上的价值）是固定的或具有有界的比率时，恒定竞争近似是可能的，并且可以变得真实[28，35]。 当值是任意的时，任何随机化调度器的功率都有一个下界，该下界在（a）最长和最短作业长度之间的比率，或（b）最小和最大作业值之间的比率[11]中是多对数的，并且这样的界限已经被某些特殊类别的作业值[4]所匹配。我们同样获得了一个对数近似值，使用随使用呈指数增长的资源价格;类似的方法用于激励兼容的在线资源分配，可以追溯到[10]，在此之前，作为在线路由[29，34]和负载平衡[3，6]的算法方法。154（）下一页≥（）下一页（）下一页（）≥（·）∞（∞）.（）下一页（）下一页≥（）下一页≥/（）下一页（·）≥（）−（·）≥（·）∈{}[]TheWebConf 2022，2022年4月25日Moshe Babaioff等人本文的一个技术挑战是限制连锁故障的影响，这种故障是由于一轮中的过度分配导致另一轮需求的增加而产生的。Chawla等人也面临着类似[14]，他们考虑了一种设置，其中在线调度器设置时间依赖资源价格的时间表，并且每个作业在其截止日期之前被调度到最便宜的可用时隙中。在这种情况下的主要困难是保持真实性，进一步的工作还探索了在有状态的在线资源分配中保持真实性的方法[13，18，20]。另一个密切相关的调度机制出现在Chawla等人。 [15]，他们考虑了贝叶斯设置，其中工作要求来自已知的分布，并构建了一个标价O 1竞争机制。 相对于这些论文，我们的模型引入了额外程度的随机性，其中提交的工作要求本身是概率性的。2我们的模型我们考虑一个理想化的云计算平台的模型，它捕捉了上面讨论的挑战该平台具有C同构计算单元，称为节点。时间以离散的时间步长（或轮次）进行，t表示时间步长。在每一轮中，每个节点都可以被分配给整个轮的某个作业存在一个有限的已知时间范围T。4.平台与自利的工作所有者互动，称为代理人。每个agent只拥有一个job;我们使用索引j来表示两者。每个作业j在其执行期间需要固定数量的节点c j，称为并发需求。 作业不能在节点较少的情况下运行，也不能从额外的节点中受益。作业到达（准备执行），到达时间为aj。在时间t aj开始运行的作业j将在执行中，并且在从时间t开始的dj个连续时间步中的每一个处使用cj个节点（其中dj被称为持续时间）。如果没有中断，作业在时间fj=t+dj成功完成。 作业是不可抢占的：它们必须连续运行才能完成。调度程序可以在任何时候驱逐正在运行的作业，终止其执行并回收其节点。5每个工作j都给它的所有者带来一些价值，这取决于它是否完成以及何时完成。这个值是Vjfj0，如果作业在时间fj完全完成（完成），对于某个称为值函数的非增函数Vj。否则（即，如果作业被逐出或从未开始运行），则值为0。按照惯例，如果作业从未完成，则完成时间为fj=，并且V=0。每个作业j在称为出生或提交时间的某个时间bj提交此时，代理知道并发需求cj和值函数Vj，但不知道到达时间aj和持续时间dj。然而，智能体知道aj，dj的联合分布，用Pj表示。在作业实际到达之前不会透露其他信息，此时平台会学习j。它还可能在作业到达时学习有关dj的一些信息，在观测信号的形式σj=σaj，dj。6在作业完成之前，不会透露有关dj的进一步4 T的有限性是为了方便定义问题实例。 我们的保证和分析将不依赖于T的大小。5.可以重新调度一个被逐出的作业，但是我们的机制和基准不会。因此，为了方便起见，我们将驱逐视为永久性的。6例如，如果σj=dj，则平台在作业到达时学习持续时间，并且如果σj是常数，则平台不获得关于持续时间的信息大部分除了定理5.2之外，我们的结果对任意信号都成立。因此，在作业出生时间bj，代理知道元组SoWj=（Vj，cj，Pj），称为真实工作声明（SoW），并报告元组SoWj=Vj′，cj′，Pj′，具有与真实SoW相同的语义，称为报告的SoW。 由于我们的机制激励代理重新输出他们的真实SoW，因此情况将是SoWj=SoWj。工作的数量，他们的出生时间，和他们真正的工作说明书-取代了出生顺序出生顺序最初对于代理和平台是未知的我们将为两种设置设计随机数：对抗和随机。在对抗性变体中，出生顺序完全相反地选择在随机变量中，每个SoW_n_j都是从一个公开已知（不一定相同）的分布中独立绘制的，并且出生时间选择相反。sarially。对于一个统一的介绍，我们正式定义一个问题的实例作为一个分布在出生序列。7一旦作业j已经完成（在时间fj）或被逐出，代理被收取πj0的支付。代理人一个从未分配过资源的作业的报酬（和效用）为零。代理人是风险中性的，并希望最大化其预期效用。我们的机制对于一些（小的）Sw0是真实的，这意味着对于每个代理j，给定其他代理的任何报告的SoW和其他代理的工作要求（持续时间和到达时间）的任何实现期望值超过了aj，dj的实现。我们机制价值（或福利）jobsjVjfj.我们感兴趣的是期望福利，其中期望被所有适用的随机性所取代。为了比较，我们考虑福利最大化的时间表在事后，给定的价值函数，到达时间，和持续时间的所有工作。离线基准测试是该调度在给定问题实例上的预期福利。我们感兴趣的是相对于这一基准的竞争比率。 我们的机制被称为α-竞争，α 1，如果它的预期福利至少是每个问题实例的离线基准的1 α。技术假设。我们给出了作业属性的一些已知上限 ：所有并发需求cj最大为Cm，所有作业持续时间dj最大为Dm，所有值Vj最大为H.此外，对于某个已知的Sm，Vj bj+Sm=0;换句话说，在作业出生后，每个智能体我们假设V j1为正值，即，Vj01，H.为了简化标记，我们假设每轮最多提交一个作业 我们的算法和分析很容易扩展到每轮多个提交，模符号;见备注1。附录A中总结了主要符号。3总框架本节给出了我们的调度机制（算法1）的一般框架，并建立了该框架中所有机制共同的激励属性。公布的信息。 在每一轮t，调度器更新并公布提交的作业的两条信息（以及[7]出生序列的对抗性选择对应于未知点分布。在随机变量中，平台部分地知道分布[8]我们使用这个假设来获得一个乘法竞争比。否则，我们的福利结果将受到额外的附加损失。这种福利损失相当于排除所有价值足够小的工作。15534567891011如果提交了作业j，则按照（2）选择启动计划Lj;对于到达轮t的每个活动作业j，当当前提交的负载超过Cdo时逐出/取消最近提交的活动作业;开始执行计划在t开始的每个活动作业j;对于在回合t成功完成的每个作业j，调度j在时间Lj（t，σj）处开始;Update：（πt+1，Et+1）←UpdateInfo（）;收费代理j支付πbj（L（aj），c，dj）;.EEE（）下一页≥·（）≤（）≤（∞）•（）下一页（）∈[]∈[]∈[]H..（）下一页（）∞t′算法1的实例化应该实现InitInfo（）发射计划L，使得PrL（aj，σj）=t′和dj=d>0。然后E|E（t′，c，d）−Et（t′，c，d）|不确定性下的云工作负载的真实在线调度TheWebConf 2022，2022年4月25日至29日，虚拟活动，法国里昂。算法1：算法调度的用户名为REMARK1。为了方便起见，我们在下面描述了算法1：1初始化：（π1，1E）← InitInfo（）;假设每轮最多提交一个作业这可以放松：如果r份工作说明书在时间t同时提交，我们将2 每一轮t做为每个作业顺序地选择一个启动计划（以任何顺序），在每个作业之后更新公告的信息，然后在所有r个作业都被处理之后移动到调度到达的作业（第4行）。取消和驱逐。调度程序可以取消尚未开始执行的作业，或驱逐已开始执行的作业。 我们从不重新启动被逐出或取消的作业。如果作业已提交，但尚未完成、取消或收回，则该作业在给定时间点被称为活动作业9我们说活动作业j被调度为如果它已经到达并且t=L（a，σ），则在轮t处开始。当前固定负载工作J是总并发需求，JJjcj 在所有活跃的Born）：价格菜单πt和估计的失败概率t。计算函数πt和t时不观察这些作业的SoW。πt和t的含义如下。假设在时间t提交的作业j报告了并发需求cj，实现了持续时间d，并在某个回合t′t开始执行。调度程序宣布价格πtt′，c，d，如果这样的作业成功完成，它不会完成，记为tt′，c，d）。这些被宣布正在执行或计划在当前回合中开始的如果当前提交的负载高于总供应C，则调度器以出生时间的LIFO顺序（最近出生的优先）驱逐或取消活动作业，直到当前负载最多为C。如果一个工作被驱逐或取消，则不收取任何费用。第二章. 后进先出顺序适用于所有活动作业，包括未计划在当前轮次中运行的作业。虽然此功能对于解决超额预订失败不是必需的，但它对我们的分析至关重要，如下所述。10我们观察到，对于a，对所有相关t′，c，d三元组，iE. e. ，（对于所有圆t′t，t+Sm，要求c Cm，持续时间d Dm。按照惯例，我们将πt，c，d=0。价格可能随t变化，有两个不变量：πt t ′，c，d不随宣告时间t而减小。成本在持续时间和并发性方面都是不减的πtt′，c，dπt t ′，c ′，d ′对任意cc ′，d d ′。同样，估计的故障概率可能随时间而变化，但在持续时间和并发性方面都是非递增的：tt′，c，d）≤给定的工作是在出生/提交时确定的形式上，让FAILj表示作业j没有成功完成的事件，并且让t表示由算法观察到的事件的完整历史。直到（不包括）第t轮（包括所有提交的SoW、选择的启动计划、实现的到达、作业完成和驱逐/取消）。此外，让SoW[t，t′]表示在时间间隔[t，t′]内提交的所有作业的SoW。让我们来看看3.1. 考虑某个循环t和固定元组（t，t ′，c，d）。什么...不2019 - 05 - 2200：00：00（E（t，c，d），对所有c≤c，d≤d。假设作业j在r o u中被提交。ndt，其中cj=c，且supp。我的意思是，UpdateInfo（）。算法的其余部分则是固定的。发射计划在每一轮t，在接收到给定的SoW时，如果为j选择发射计划L（即，忽略（2），则PR 未通过j|Ht，L（aj，σj）=t′，dj=d，SoW[1，T]（3）作业j，调度器计算该作业的启动计划Lj，其将每个可能的到达时间aj和信号σj（如果有的话）映射到开始由Ht和（t，t′，c，d）确定（且与SoW无关[t，T]）。执行的时间发射计划可能决定在某个到达时间aj内不执行作业;我们将此时间记为Lj aj，σj=。启动计划是有约束力的：作业j必须在时间Lj aj，σj开始执行，除非它事先被取消（如下所述）。下文所述的发射计划的选择对于确保引理3.1直接从LIFO排序得出：只有当提交的负载超过C时，即使在删除所有先前提交的作业之后，作业jjobs. 给定引理3.1，我们可以用Et（t′，c，d）表示（3），并调用激励对于给定的启动计划L和其真实SoW是（V，c，P），我们定义估计效用U t（L |V，C，P）作为它是（真实的）失效概率。我们将解读Et（t′，c，d）的近似。E（t，c，d）作为代理人在公式中Ut（L |V，c，P）⑴虽然（3）在原则上可以精确计算，但这种计算在实践中可能是不可行的 我们只要求估计近似正确：我们将误差限制在某个μ> 0，=E. .不–·V（ta，σ + d）− πt（ta，σ，c，d）<$。、将不实报道可能带来的收益限制在µm以内。具体来说，我们假设，取Et上的期望，（a，d）联合国难民事务高级专员办事处.t.1<μ（μc，d，t′≥t）.（四）Σ156←Ljargmax发射计划Ut（L |Vj，cj，Pj）。（二更）9作为惯例，在最后一轮（t = T）之后，所有活动作业都被取消或逐出。[10]在实践中，可能会决定不取消尚未开始执行的作业。虽然这样的修改会扰乱客户的激励，但在实际系统中，以便在给定所报告的SoW的情况下最大化所估计的效用。可以接受，因为发现有益的误报可能具有挑战性。其中ta，σ=L（a，σ（a，d））。我们选择一个发射计划157（）下一页（）下一页（）下一页.（）下一页（）下一页（）下一页（（））（）下一页∈.J（·）≥·.（）（）（）下一页--·（）≥（）∞≥.·的作业j的分配，表示为xj=xijt：任务i，轮次t.由算法产生的总值jvj（xj）（包括超过C，即，i，jxijt≤C。松弛问题TheWebConf 2022，2022年4月25日Moshe Babaioff等人激励在没有详细说明如何选择价格以及如何计算估计的成功概率的情况下，我们已经可以在MainProblem中的每个SoWj=（Vj，cj，Pj），对应的frac-常规SoW具有相同的Vj和cj，并且任务τi =（a. ij，dij）为。每个保证近似真实。从本质上讲，这是因为启动计划优化了代理商（aij，dij）在Pj的支持下，权重为λi=Pj将该分数SoW表示为Relax（SoWj）。（aij，dij）. 我们近似失效概率。定理3.2. 算法1是2 µ H-真实的，其中µ限制成功概率估计误差（如（4）中所示），并且正作业值被归一化为位于[1，H]中。计算。为了计算（2）中的最优L j，可以针对每个潜在到达时间a j和信号σ j分别优化Ljaj、σj。这种优化可以通过在Pj和每个潜在开始时间的支持下对每个a、d进行因此，可以计算时间为O（Sm·m）的最优发射计划。|支持（Pj）|）的。4递阶约简算法我们将原来的问题（以下称为主问题）简化为它的松弛问题RelaxedProblem。后者是一个不同的，但相关的调度问题，其中的工作要求是frac-MainProblem中针对作业j的任何启动计划Lj为每个aij，dij分配从Lj aij，σaij，dij开始的dij轮的cj资源的间隔分配。这对应于分数调度问题中每个任务τi的间隔分配xij，其中每轮分配的资源按λi缩放。我们将写xj Lj作为聚合分配（对于所有任务）。然后注意，ixijt Lj是在启动时在时间t处的资源的预期使用关于概率分布Pj的规划Lj。一类算法。 我们的简化需要算法，RelaxedProblem具有以下特殊结构。首先，一个算法维护一个价格函数π， 也就是一个菜单，为任何区间分配x分配一个非负价格。菜单可以随着算法的进展而改变，因此我们将时间t处的值写为πtx。当在时间t提交给定作业j时，算法根据πt优化分配xj：而不是不确定的，和负载对应的预期负载在MainProblem。我们的还原需要一个算法xjargmax总分配额xjVj（xj）−π t（xj），（5）对于RelaxedProblem，其中过度承诺永远不会成为问题，并使用它来解决系统在某些实现中可能饱和的MainProblem。在第5节中 ， 我 们 通 过 采 用 已 知 的 在 线 资 源 分 配 技 术 来 解 决RelaxedProblem来完成这种方法。4.1放松的问题RelaxedProblem类似于MainProblem，但有以下变化：每个作业j由分数SoW表征，分数SoW如前所述包含值函数Vj0和并发需求cj，但是分布Pj被k j个任务τ1，. . .，τ kj和权重λ1，. . . ，λk >0与iλi=1。每个任务τi由一个到达时间和持续时间（aij，dij）。其中，总工作价格为π txj为任务iπ txij. 这种出租被称为基于菜单的。[11]为方便起见，我们将从时间t ′开始的d步的所有运动资源的价格记为πt tt′，c，d。第二，该算法的测量相对于以下强基准：对于任何子集N的工作，OPTN是离线最优福利可达到的工作N在一个随机版本的RelaxedProblem，其中的选择分配给每个任务可以随机化和供应约束只需要绑定在期望在这个随机化。我们写OPT=OPT所有工作。第三，算法应该支持以下部分对抗场景。当一个工作诞生时，对手可以任意地打破选择规则（5）中的束缚。此外，对手可以绕过对作业j资源或分配给每个任务τi要么没有(5) ，并且替代地选择任何全0阳离子xj，使得Vjxjπ txj。当/如果发生这种情况时，算法应该观察新的xjλicj连续时间步的资源单元开始。不早于ij。注意，λicj可能是分数。写x ijt 0表示在时间t分配给任务τ i的资源量，写f ij表示该任务的完成时间，或者f ij=如果尚未完成。一个任务的分配被称为一个内-然后继续称这种算法为接受性算法。该算法不需要与OPT竞争相反，它只需要与OPT N竞争，其中N是其分配满足（5）的作业的集合（即，不被对手切换）。该算法是鲁棒的α-将所有的值表示为dxij=。 xijt：t∈[T]<$。《反腐败公约》在给定的问题实例中，α≥1。如果有任何广告，• 整数x的值。ij是λiVj（fij）。的值iλiVj（fij）.由对手调度的作业）至少是1个OPTN。总之，α的算法是菜单-当提交给定作业的部分SoW时，必须立即做出合理的决定任务不能被驱逐，抢占或取消之后。• 总的A。在任何时间t对所有作业j和任务i的分配不能1. 如果新作业j到达，则按照（5）选择分配2. 如适用，用对抗性分配取代，3. 更新价格菜单。4.2简化为松弛问题我们使用基于菜单的接收算法实例化算法1和以前一样，作业序列，这是提前从出生序列的一些分布中选择的。这种分布构成了一个问题实例。给定一个MainProblem的实例I，我们构造一个实例RelaxedProblem，表示为Relax（I），以一种相当自然的方式。为松弛问题的算法。该实例化（算法2）是[11]请注意，（5）中的argmax是在所有与发射计划相对应的总分配xj上，其中一些可能违反容量约束。 为了可行，菜单必须确保argmax的输出保持在约束范围内。aggregateallocationxjisVj（xj）=基于和接收在每一轮t中使用以下协议：158∈（（））我（）下一页（一）（）（）（）/Eα′E–EEαα/·（−/）（−（））≥（−（））（/）（）原问题的O（λH）-真实和α（1+O（λ））E（t，c，d）>λ<（Sm）·λ·eMMM不确定性下的云工作负载的真实在线调度TheWebConf 2022，2022年4月25日至29日，虚拟活动，法国里昂。算法2：算法1通过RelaxedProblem参数：>0，基于菜单，接受算法ALG算法2得到的模拟值与我们模拟ALG得到的模拟值接近，并且（ii）ALG的模拟值较大//ALG使用供给约束C′=C·（1−N/ 10）Require：Oracle for failure probabilitiesEt//算法1的第1行的InitInfo（）相比之下，OPT我们现在将这种直觉形式化。固定一些出生序列，为了方便，将算法2中ALG得到的总模拟值写成V ALG。设N是作业j的集合，对于该作业j，来自算法2的第41初始化价格π1的方式与ALG相同;设置E1←0;最大化（5）。也就是说，N是其分配被在我们的ALG模拟中没有反向切换。自从ALG//算法1的第11行的UpdateInfo（）是鲁棒α-竞争的，我们知道VALG ≥1OPTN.2如果作业j在轮t中提交，则既然我们想比较VALGα对于OPT，我们需要3向ALG报告工作放松（SoWj）;4告诉ALG：对于作业j，使用分配xj（Lj）;//声明4.2：xj（Lj）“典型地”最大化（5）通过权利要求4.2，只要作业j的所有驱逐概率都足够小，我们就有j N。 因此，我们的目标是建立每个工作都很可能面临非常低的5将菜单πt+1更新为ALG更新后的价格菜单;算法2中的故障概率。这是最技术性的一步6通过oracle更新Et+1，t+1E← f（Et+1），其中在证明。直观地说，由于ALG构造的分配服从于减少的供应约束C′，集中度界限表明，f（q）= q，如果q> f/10，否则为0。对于MainProblem的任何实例I都是竞争的，只要ALG在松弛实例Relax（I）上是鲁棒竞争的。定理4.1. 修复> 0，使系统的容量C超过C m −2 log −1 + S m。考虑一个MainProblem的实例和一个用于RelaxedProblem的基于菜单的接收算法ALG。假设ALG对于松弛问题是鲁棒α-竞争的在任何一轮中，总的实现使用量都不太然而，在不同回合中的失败概率之间存在相关性因此，人们可能会担心，即使第一次驱逐发生需要指数级的时间，此后驱逐将变得更加普遍。因此，我们必须限制相关性在时间上的影响。这是由下面的引理（在附录中证明）完成的让我们来看看4.3. 修复作业出生时间和SoW的任何序列，选择任意λ> 0和δ> 0。如果C′<（1-δ）（C-Cm），则松弛（I）和某些α≥1。则具有参数λ的算法2为Pr.不’。2−1−（（C/C−1） ·δ2/（1+δ））（6）实例I. 时间复杂度为O（log（log-1DmSm））+对所有t，t′>t，c≤C，d≤D.概率大于ALG的每轮运行时间。我们的缩减过程如下。形式上，在算法2中，我们填写了算法1中未指定的两个步骤，InitInfo和UpdateInfo。实质上，我们模拟了一个运行的ALG放松的问题实例放松。每当提交新作业j时，我们将其部分版本Relax SoWj报告给ALG，并使用ALG先前计算的价格菜单来优化启动计划Lj。然后，我们强制ALG对该作业遵循相同的启动计划：即，对作业j使用聚合分配xj（Lj）。如果所有相关所有作业的到达时间和持续时间设γ表示（6）中的右侧。现在假设，γ=O如果我们设置λ=λ10（算法2中的阈值），引理4.3意味着如果故障概率的预言是完全准确的，则每个作业将以至少（