CN114730275A - 使用张量在分布式计算系统中进行矢量化资源调度的方法和装置 - Google Patents

Abstract

提供了一种使用具有统一数据类型的多维分层数组进行矢量化资源调度的方法和装置。根据各实施例，在调度上下文中，资源层次结构可以表示为统一数据类型的多维数组。该数据结构称为张量。在各实施例中，张量可以用于对资源使用量、请求的资源、资源容量、租户资源使用量等中的每一个进行建模。提供了张量调度操作(例如，张量调度算法)以利用该资源模型。一些实施例可以利用GPU和张量处理单元等专用硬件来加速所述张量调度操作。

Description

使用张量在分布式计算系统中进行矢量化资源调度的方法和 装置

相关申请交叉引用

本申请要求于2019年9月19日递交的申请号为16/575,763、发明名称为“使用张量在分布式计算系统中进行矢量化资源调度的方法和装置(Method and Apparatus forVectorized Resource Scheduling In Distributed Computing Systems UsingTensors)”的美国专利申请案的优先权，其全部内容通过引用结合在本申请中。

技术领域

本发明涉及分布式计算系统中的资源调度，尤其涉及一种使用张量在分布式计算系统中进行资源管理和调度的方法和装置。

背景技术

在分布式计算系统中，资源调度器将工作请求(即，待执行的工作请求)与完成该工作所需的分布式计算系统的资源进行匹配。换言之，资源调度器将分布式计算系统中的资源分配给一个或多个工作请求。调度之后，可以对分配的资源‘提出’(即，由分配的资源执行)工作请求。

分布式计算系统接收大量工作请求，并且管理和调度大量资源。进一步地，分布式计算系统接收的工作请求的数量以及分布式计算系统中的资源的数量不断增加。由于工作请求和资源的数量较大且不断增加，经常需要对资源管理和调度进行管理，使得资源调度器能够满足资源调度需求。为了管理不断增加的工作请求以及资源管理，需要有效的并行化技术，因为在计算上难以在许多时间间隔内将许多资源请求与许多可消耗资源(例如，CPU、存储器)进行匹配。用于进行资源管理和调度的现有方法和系统，甚至包括使用并行化的技术，都需要提高效率。因此，需要一种方法和装置来解决现有技术中的一个或多个问题。

提供该背景信息是为了揭示申请人认为可能与本发明相关的信息。不必有意承认，也不应该解释任何前述信息构成针对本发明的现有技术。

发明内容

实施例的目的在于提供一种用于在分布式计算系统中进行矢量化资源管理和调度的方法和装置，所述方法和装置涉及使用张量(具有统一数据类型的多维数组)来表示资源请求，并在调度上下文中将资源的层次结构表示为张量。

根据实施例，提供了一种用于在分布式计算系统中进行资源管理和调度的方法。所述方法包括：使用一个或多个资源张量表示所述分布式计算系统中资源的可用性或资源的使用量；接收一个或多个资源请求，每个资源请求指定所述分布式计算系统中满足工作请求所需的资源。所述方法还包括：将所述资源请求表示为一个或多个请求张量；根据所述一个或多个资源张量和所述一个或多个请求张量，调度所述分布式计算系统中的资源。

在一些实施例中，所述方法还包括：使用一个或多个容量张量表示所述分布式计算系统中的所述资源的总量；进一步根据所述一个或多个容量张量，调度所述分布式计算系统中的资源。

在一些实施例中，所述方法还包括：在调度期间，基于所述一个或多个请求张量中的值，更新所述一个或多个资源张量以响应于条件。所述条件是以下各项中的一个：对一个或多个可用资源的子集提出所述工作请求；完成需要所述一个或多个资源的所述工作请求；或释放所述工作请求所请求的所述一个或多个资源。

在一些实施例中，所述方法还包括：确定所述一个或多个资源张量的子集，所述一个或多个资源张量的所述子集具有用于所述工作请求的足够容量。在一些实施例中，所述方法还包括：确定与所述请求的资源最佳匹配的所述一个或多个资源张量的子集，其中，在对所述请求的资源提出所述工作请求时，基于计算所述一个或多个资源张量的每个子集的适合程度得分，确定所述最佳匹配。在一些实施例中，基于在对所述资源提出所述请求之后的总资源使用量与所述资源的总容量之间的相似性(从数学意义上来说，例如，余弦相似性)，确定所述一个或多个资源张量的所述子集中的每个子集的所述适合程度得分。

根据实施例，提供了一种用于在分布式计算系统中进行资源管理和调度的装置。所述装置包括处理器和存储机器可执行指令的存储器。所述指令在由所述处理器执行时，将所述装置配置为：使用一个或多个资源张量表示所述分布式计算系统中资源的可用性或资源的使用量；接收一个或多个资源请求，每个资源请求指定所述分布式计算系统中满足工作请求所需的特定资源的数量。所述指令在由所述处理器执行时，还将所述装置配置为：将所述资源请求表示为一个或多个请求张量；根据所述一个或多个资源张量和所述一个或多个请求张量，调度所述分布式计算系统中的资源。

根据本发明的实施例，提供了一种用于在分布式计算系统中进行资源管理和调度的网络节点。所述网络节点包括：网络接口，用于从连接至分布式计算网络的组件接收数据并向所述组件传输数据；处理器；非瞬时性存储器，用于存储指令。所述指令在由所述处理器执行时，将所述网络节点配置为：使用一个或多个资源张量表示所述分布式计算系统中资源的可用性或资源的使用量；接收一个或多个资源请求，每个资源请求指定所述分布式计算系统中满足工作请求所需的特定资源的数量。所述指令在由所述处理器执行时，还将所述网络节点配置为：将所述资源请求表示为一个或多个请求张量；根据所述一个或多个资源张量和所述一个或多个请求张量，调度所述分布式计算系统中的资源。

上文结合本发明的各方面描述了实施例，这些实施例可以基于这些方面实现。本领域技术人员可以理解，实施例可以结合描述这些实施例的方面来实现，但也可以与该方面的其它实施例一起实现。当实施例相互排斥或彼此不兼容时，对于本领域技术人员是显而易见的。一些实施例可以结合一个方面进行描述，但也可以适用于其它方面，这对本领域技术人员而言是显而易见的。

一些方面和实施例可以提供许多优点，包括由于大规模并行计算提高速度、提高执行的可预测性(例如，缩短尾延迟)、能够使用适当的精度水平(例如，利用低精度算术、提高计算效率)以及降低功耗(例如，以每瓦特较高的每秒输入输出操作数(Input-OutputOperations Per Second，IOPS)运行)。此外，将至少一些调度分流到协处理器可以使主机CPU资源可用于完成所请求的工作。这可以实现改进，其中既不会因调度而干扰完成工作，也不会因完成工作而干扰调度。

附图说明

结合附图，通过以下详细描述，本发明的进一步特征和优点将变得显而易见，在附图中：

图1示出了实施例提供的使用张量进行矢量化资源调度的分布式计算系统；

图2示出了分布式计算系统中资源的层级结构；

图3示出了未来计划运行的工作的资源调度；

图4示出了分布式计算系统中调度操作的示例，具体地，检查主机是否具有用于工作请求的足够资源；

图5A示出了实施例提供的通过将概念资源层次结构转换为张量表示对资源层次结构进行编码的基于张量的资源表示；

图5B示出了实施例提供的将时间维度视为资源层次结构中的可消耗资源的概念；

图6A示出了先验资源模型中资源层次结构表示的示例；

图6B示出了实施例提供的资源张量中的张量目标维度；

图7示出了实施例提供的资源张量中的时间维度的逻辑循环缓冲器和循环缓冲器实现方式；

图8示出了实施例提供的资源调度器确定请求与主机是否相匹配的过程；

图9示出了实施例提供的使用余弦相似性确定对其提出请求的最佳主机的过程；

图10示出了实施例提供的电子设备的示意图。

需要说明的是，在整个附图中，相同的特征由相同的附图标记标识。

具体实施方式

术语说明

本文中使用的术语“约”应当理解为包括相对于标称值的变化，例如，相对于标称值的+/-10％的变化。应当理解的是，无论是否具体提及，本文提供的给定值总是包括这种变化。

术语“高级矢量扩展指令集”(Advanced Vector Extensions，AVX)是指用于支持单指令多数据(single-instruction multiple-data，SIMD)操作的

和

微处理器的一组计算机指令。例如，在与针对一项任务处理相同操作(即，并行处理)所需的相同时间内，AVX可以同时针对多项任务执行特定操作。

术语“分配问题”是指其中一个基本组合优化问题(即，具有从一组有限元的组合中获得的方案的问题)，其中，在加权二分图中寻求最大权重匹配，即识别一组中的节点与另一组中的节点的最大权重匹配，所述节点位于两组(例如，‘请求’和‘主机’)中，并且要求每个请求转到一个主机，每个主机仅连接至一个请求。在调度中，权重可以对每个请求与每个主机的‘匹配’程度进行编码(例如，通过使用余弦相似性)。如果每组中的元素数量不同，则为‘非对称’分配问题。一般而言，调度可以是非对称分配问题。

术语“广播”是指NumPy、PyTorch、TensorFlow和/或其它软件库在矢量化算术运算过程中处理具有不同形状的张量的方式，本质上是对齐和复制张量维度，使得能够继续运算。张量的‘形状’描述如下，它是指维数和每个维度中的元素数(即，分量值)。例如，当存在涉及具有不同形状的两个张量的运算时，对于每个维度，‘广播’技术意味着NumPy的行为就像根据需要多次‘复制’较小的阵列维度(及其值)以匹配较大的维度，使得阵列可以具有兼容的形状，并且能够继续算术运算。与替代方法(例如，明确复制或在软件代码中循环)相比，使用所述广播技术通常可以确保非常高效地实现算法。

在分布式调度上下文中，术语“集群”是指被设置为执行分布式程序(例如，跨多个机器运行的程序)的一组计算机。在物理方面，集群是指链接在一起的多个机器。每个机器都有中央处理器(Central Processing Unit，CPU)内核、存储器等，并且可以被视为应在其上运行工作的‘主机’或‘服务器’。从所述资源调度器的角度来看，在逻辑方面，集群是指一组资源(例如，资源可以是CPU内核、存储器、存储设备、网络、图形处理单元(GraphicsProcessing Unit，GPU)、端口号、软件许可证等)，所述资源调度器必须与请求资源以完成其工作的分布式程序(例如，操作系统(Operating System，OS)进程、串行/并行批处理作业、虚拟机(Virtual Machine，VM)、容器、无服务器函数等)相匹配。

术语“数据类型”是指计算机程序中的变量/数据的属性，所述属性限制所述变量可以取值的类型、可以对这些变量执行的运算以及如何在计算机系统上存储和操作这些变量。常见的示例包括布尔数据类型、整数数据类型和实值(浮点)数据类型。

术语“分布式计算系统”是指组件或资源位于不同联网计算机上的计算系统。

术语“图形处理单元”(Graphics Processing Unit，GPU)是指最初设计用于快速生成图像以输出到显示设备的专用电子电路。GPU已用于执行通用并行算法，尤其是矩阵乘法和相关计算(例如，基于图形处理单元的通用计算器(General-Purpose GraphicsProcessing Unit，GPGPU))。GPU并行处理操作的方式类似于在CPU上处理AVX/SIMD指令的方式，但GPU对所述处理操作进行进一步并行化处理。

术语“主机”是指所述资源调度器在其上运行工作的主机(例如，服务器)。

术语“每秒输入输出操作数”(Input-Output Operations Per Second，IOPS)是指用于基准存储设备的性能测量。

术语“最大权重匹配问题”是指在加权图中找到最大化权重之和的匹配问题。最大权重匹配问题的特殊案例是分配问题(如上所述)，其中输入被限制为二分图。

术语“NumPy”是指Python编程语言的科学(软件)库。NumPy增加了对大型多维数组和矩阵(例如，‘张量’，但在NumPy中，张量通常称为‘数组’)的支持，并对这些数据结构进行了大量操作。

术语“操作系统”(Operating System，OS)是指在计算机上运行的软件，所述软件调度任务、执行应用程序并控制磁盘驱动器、显示器和/或其它外围设备。

术语“PyTorch”是指Python编程语言的机器学习(科学)库。PyTorch为神经网络提供了一组特殊操作。PyTorch可以描述为‘GPU上的NumPy’。

在分布式计算系统上下文中，术语“资源管理”(Resource Management，RM)可以理解为调度，其中，资源跨多个机器，并且要执行的工作包括批处理作业(要并行运行的多批单独任务)。RM也可以被视为调度的一部分，包括(1)资源定义和发现、聚合和呈现；(2)资源生命周期监控。在本申请中，资源管理器跟踪所述分布式计算系统中可用于调度或使用所述分布式计算系统中资源的资源，而所述资源调度器执行所述匹配部分，其中，资源请求与适当资源相匹配。

术语“资源模型”是指数据结构，即数据组织和存储格式，其中，在资源管理系统中记录、更新和传递资源信息，例如指示特定资源的参数(例如，CPU特性、存储器特性、分配的资源使用量等)。资源模型是真实物理资源的计算机内部表示，可以在请求和调度计算资源时使用。

在计算中，术语“调度”是指在一段时间内为完成工作(例如，‘请求’)向所述工作分配资源的方法。调度也可以被视为对资源‘提出’请求。工作请求可以是在操作系统上运行进程的请求、用户指定的批处理作业或在服务器上运行的虚拟机(virtual machine，VM)等。资源可以包括CPU内核、存储器、存储设备、网络端口、GPU等。包括所有智能手机和笔记本电脑在内的每个计算机都具有OS，所述OS包括资源调度器，所述资源调度器确定应在任何给定时间运行哪些进程。类似地，在更大规模中，例如在分布式(多机器)计算系统中，可能需要资源调度器来决定应该对哪些机器提出哪些工作请求等。应当理解的是，在分布式计算系统中，可以对单个主机资源提出多个工作请求。例如，如果主机服务器具有10个CPU内核，且所述调度器接收到放置虚拟机(Virtual Machine，VM)的请求(其中每个VM需要1个CPU内核)，则所述调度器可以在一个主机上放置多达10个VM(假设所述主机上具有用于所有10个VM的足够存储器和其它资源)。

术语“调度操作”可以理解为调度中执行的匹配或工作安排。调度操作可以包括：(i)查看哪些资源具有足够的容量来满足请求(具有满足工作请求的‘足够’容量的子集)；(ii)确定哪些资源与请求‘最佳匹配’；和/或(iii)对资源“提出”请求(例如，在其内部数据结构中记录资源正在使用，因此不可用于其它请求)。

术语“张量”可以被视为具有统一数据类型(例如，布尔、浮点、整数等)的值的多维数组。在编程语言中，可以通过索引访问张量的值。例如，一维数组(一维张量)是一个矢量，其值可以通过数组[0]、数组[1]或数组[10]等访问。二维数组(二维张量)是一个矩阵，其值可以通过两个索引来访问，例如数组[0][1]或数组[5][7]。标量、数组和矩阵到任意维数的推广(例如，通过任意数量的索引被索引)统称为张量。在本申请的上下文中，资源可以具有层级结构，因此可以被定义为张量。例如，每个数据中心具有多个机架，每个机架具有多个主机(即，机器)，每个主机具有多个处理单元，每个处理单元具有多个内核。

术语张量“形状”(或数组“形状”)是指所述张量的维度(多维数组)，例如40x10x3。所述张量“形状”指定所述张量在每个维度的大小。例如，如果所述张量的形状为40x10x3，则所述张量在每个维度的大小分别为40、10和3。在这种情况下，所述张量总共包含40*10*3＝1200个值。张量在每个维度的大小等于所述多维数组在该维度的长度。如果使用零索引(即，数组索引从0开始)，则所述数组的长度等于所述数组的最大索引值加1。(例如，当所述张量的形状为40x10x3时，每个维度的数组大小为40、10和3。使用该张量，数组[35][6][2]表示有效索引，但是数组[50][50][50]不表示有效索引，因为每个索引超出所述张量在相应维度的大小。)

术语“单指令多数据”(Single Instruction Multiple Data，SIMD)是指一种并行计算操作，使得同时对数据点的‘矢量’执行单个‘指令’(例如，“值增加一”)。SIMD指令需要相应硬件来实现所述SIMD操作。

术语“尾延迟”是指高百分位数延迟值，例如第98个百分位数或第99个百分位数延迟。每次在计算机系统上运行操作时，该操作的响应时间都将不同。当每个响应时间的频率被绘制成直方图时，所述响应时间的这种分布将会有一个尾部。所述响应时间分布的尾部将表示所述分布中的值，使得所有延迟的较大百分比低于这些值，例如98％的延迟小于这些值。

术语“租户”是指集群调度器一致对待的用户或用户组。租户通常对应于组织内的业务部门(例如，销售、数据科学、营销和管理)。租户也可以按照层级关系排列。租户的概念随着集群规模的扩大而出现，企业试图通过在多个用户组之间共享资源来提高其利用率。关于共享资源，由(集群)调度器面向租户实施的简单策略之一是每个租户都有权或保证拥有一定数量的集群资源(例如，‘保证份额’)。然而，当一个租户没有使用其资源时，其它租户可以借用未使用的资源，最多可以借用一定数量的所有集群资源(例如，‘最大份额’)。

术语“TensorFlow”是指Google开发的机器学习库，主要通过Python访问。

术语“张量处理单元”(Tensor Processing Unit，TPU)是指Google专门为神经网络机器学习开发的人工智能(Artificial Intelligence，AI)加速器专用集成电路(application-specific integrated circuit，ASIC)。

在计算机科学中，术语“矢量”是指一组数字。在本申请中，‘矢量化’操作是指并行操作多个数值的指令。

术语“虚拟机”是指模拟计算机系统(例如，具有整个文件系统、操作系统等的Windows或Linux计算机)的计算机程序，其本身作为进程在主机上运行。

除非另有定义，否则本文所用的所有技术和/或科学术语都具有与本发明普通技术人员公知的含义相同的含义。

实施例涉及在调度上下文中将资源层次结构表示为统一数据类型的多维数组，以提高资源调度效率。所述统一数据类型的多维数组称为‘张量’。换言之，实施例涉及使用‘张量’资源模型，以及由此类模型实现的相关矢量化张量操作，例如广播。此类资源模型可以用于资源使用量、请求的资源、资源容量、租户资源使用量等中的每一个。实施例使用张量调度操作(例如，张量调度算法)以利用所述新资源模型及其相关操作。一些实施例可以利用GPU和张量处理单元等专用硬件来加速所述张量调度操作。

如前所述，根据实施例，可以通过使用张量(统一数据类型的多维数组)表示资源来处理和解决调度问题。该公共的通用矢量化模型可以用于请求的资源、资源使用量、资源容量、租户资源使用量等。所述资源模型还可以用于有效地表示调度操作(例如，对主机提出请求)。资源表示和调度操作集可以称为“张量调度”。在一些实施例中，循环缓冲器可以用于时间维度。本文其他部分(例如结合图7)描述了所述循环缓冲器的使用，这可以提高更新效率。在一些实施例中，可以利用专用硬件来执行张量调度操作。

本文中所描述的关于资源表示的基本方法可以具有优点，包括提高实现资源调度和调度操作的效率。根据实施例，所述资源表示允许(自动)对内核调度操作应用矢量化和并行化算术运算。通过使用科学(软件)框架或库，例如NumPy和TensorFlow，可以有效地执行张量广播操作。张量算术运算可以用于更有效地实现调度操作。所述调度操作可以包括：(i)在逻辑上对目标资源提出请求；(ii)检查资源容量或可用性是否足以满足调度请求；(iii)计算调度请求的‘最佳匹配’(例如，余弦相似性)；(iv)确定请求能够与一个或多个主机匹配的次数；(v)解决冲突。应当注意的是，在逻辑上对目标资源提出请求时，所述操作更新内部资源模型，以反映在对所述目标资源提出所述请求之后所述目标资源的可用性降低。

通过使用张量表示资源，可以使用针对矩阵运算进行优化的专用硬件(例如，用于SIMD指令的CPU，或者GPU、GPU张量内核和TPU等专用‘协处理器’)来执行调度操作。因此，使用张量表示资源时，在多个方面改进了调度操作。例如，与常规处理单元(例如，常规CPU)相比，GPU、GPU张量内核和TPU等一些专用硬件可以更快地处理调度操作，因为它们利用大规模并行计算，并对调度算术使用适当的精度水平。由于通常不需要极其精确的数字(例如，小数点后20位的数字)来确定服务器上是否有足够的资源(例如，CPU)，因此一些专用硬件可以对调度算术使用较低的精度水平以提高效率。此类专用硬件还可以降低功耗，从而例如实现每瓦特较高的IOPS。此外，GPU、GPU张量内核或TPU等专用硬件可以提高执行的可预测性，从而缩短尾延迟。如果调度操作在专用协处理器上运行，则可以提高执行的可预测性，因为调度操作不会被所述处理单元上运行的其它进程延迟。此外，当调度操作被主机处理单元分流到GPU、GPU张量内核或TPU等专用硬件或加速器时，所述调度操作不会干扰其它主机处理单元操作。换言之，所述主机处理单元的资源不会用于调度操作，而是用于处理单元操作。这样，可以限制为调度操作不干扰处理单元操作，并且限制为处理单元操作不干扰调度操作。

图1示出了实施例提供的使用具有统一数据类型的多维分层数组进行矢量化资源调度的分布式计算系统100的示例。参考图1，每个客户端设备120可以通过网络130通信地和可操作地连接至计算设备140以及服务器机架180a和180b。所述计算设备140以及所述服务器机架180a和180b还可以通过所述网络130通信地和可操作地彼此连接。

根据实施例，所述客户端设备120可以是终端用户直接用于通信的任何设备，例如移动电话、智能手机、具有网络功能的计算机或可以被分类为用户设备(User Equipment，UE)的其它设备。所述客户端设备120可以是机器类通信(Machine Type Communications，MTC)设备(也称为机器对机器(machine-to-machine，m2m)设备)，或者其它此类设备，即使不向用户提供直接服务，所述其它此类设备也可以被分类为UE。

根据实施例，所述计算设备140可以放置在其中放置所述服务器机架180a和180b的同一数据中心中，或者可以放置在其它数据中心中。虽然图1中未示出，但所述分布式计算系统100中可以有一个或多个其它计算设备。这些计算设备可以放置在其中放置所述计算设备140的同一数据中心中，或者可以放置在其它数据中心中。所述计算设备140可以包括一个或多个资源调度器160。虽然图1中未示出，但所述计算设备140中可以有一个或多个其它资源调度器。所述资源调度器160可以执行如上所示的一个或多个调度操作(例如，对主机提出请求、确定请求与主机是否相匹配、找到对其提出请求的最佳主机、解决冲突等)。

根据实施例，所述分布式计算系统100中可以有一个或多个数据中心。每个所述数据中心可以包括一个或多个服务器机架(例如，服务器机架180a或180b)。所述服务器机架可以在一个或多个方面(例如，组件、功能)与图1中所示的服务器机架180a和180b类似。在一些实施例中，所述服务器机架180a和180b可以放置在同一数据中心中。在一些实施例中，所述服务器机架180a或180b可以放置在两个不同的数据中心中。参考图1，所述服务器机架180a包括多个资源服务器110a，所述服务器机架180b包括单个资源服务器110b。虽然图1示出了所述服务器机架180a中仅有两个资源服务器110a，但是容易理解的是，所述服务器机架180a中可以放置两个以上的资源服务器110a。

根据实施例，所述资源服务器110a和110b中的每个资源服务器可以包括资源(例如，资源150)。每个资源可以依次包括一个或多个其它资源，这些资源又可以依次包括其它资源，直到达到可消耗资源(例如，CPU、GPU、存储器等)的水平。例如，参考图1，所述服务器资源150可以包括一个或多个处理单元(例如，CPU 152、GPU 154、TPU等)、存储器(例如，存储器156)、存储设备(例如，存储设备158)以及请求可能需要的其它可消耗资源。在一些实施例中，这些可消耗资源中的每个可消耗资源可以是复合资源，而所述复合资源由其它可消耗资源或复合资源组成。

如上所述，资源调度是指将工作请求与完成工作所需的资源进行匹配。一旦匹配，所述请求可以被视为对其分配的资源‘提出’。由于各种资源之间的层级关系，所述资源调度可能较为复杂。图2示出了分布式计算系统中资源的层级结构。参考图2，名为‘myserver1’的单个主机资源200包括‘cpu’210、‘mem’220、‘disk_capacity’230和‘disk_bandwidth’240作为其资源；因此，所述主机200‘myserver1’与其它资源(例如，‘cpu’210、‘mem’220、‘disk_capacity’230和‘disk_bandwidth’240)之间的关系是层级关系。所述主机200‘myserver1’可以被视为‘复合’资源(即，由其它资源组成)。另一方面，图2中所示的“叶级”资源，例如‘cpu’210、‘mem’220、‘disk_capacity’230和‘disk_bandwidth’240可以被视为‘可消耗’资源。资源层次结构的概念可以扩展。虽然图2中未示出，但是名为‘myserver1’的所述主机200可以只是主机机架中的一个主机；所述主机机架可以是数据中心中的多个主机机架中的一个。进一步地，所述分布式计算系统中可以有多个数据中心。这些较高层级中的每个层级都可以被视为资源层级结构中的复合资源。

对于具有层级结构的资源，调度包括将工作请求与资源层次结构中目标层级的一个目标资源进行匹配。具体地，在目标层级，调度可以包括将工作请求(例如，VM)与一个主机(所述目标资源)进行匹配，其中，单个主机隐式放置在一个数据中心中的一个主机机架上(例如，工作请求将与一个主机‘或’另一个主机相匹配)。同时，在低于所述目标层级的层级，工作请求通常需要低于所述目标资源的所有可消耗资源的指定部分(例如，植根于所述目标资源的层次结构的叶级的数字资源，即，低于所述主机)。因此，在低于所述目标层级的层级，调度可以包括将工作请求中的可消耗值与植根于所述目标资源的所述资源层次结构中的所有可消耗资源进行匹配。例如，VM可能需要所述主机200‘myserver1’的所述‘cpu’210、‘mem’220、‘disk_capacity’230和‘disk_bandwidth’240。

例如，考虑放置VM的工作请求，其中，所述工作请求的资源需求为1个CPU内核和2GB存储器。假设目标是找到主机以对其提出该工作请求。假设存在数据中心，所述数据中心具有主机机架，所述主机机架具有主机，所述主机具有10个CPU内核和35GB可用存储器。调度涉及确定该特定主机具有足够的可消耗资源，使得可以对所述主机提出所述工作请求。如果所述资源调度器确实对所述主机提出所述工作请求，则所述资源调度器需要更新其资源信息，以反映在提出所述工作请求之后，所述主机上现在将仅剩下9个CPU内核和34GB存储器。

由于分布式计算系统的最新趋势，资源调度变得更加复杂且计算量较大。实质上，正在大规模执行资源调度。当前的一个趋势是，具有大量的目标资源。例如，可能有20,000到100,000个主机，每秒可能需要处理超过10,000个请求。因此，考虑到这些主机中的每个主机都有大量需要跟踪的可消耗资源，例如CPU和存储器，资源调度现在非常复杂且计算量很大。

关于计算资源调度的另一个趋势是需要或预期随着时间的推移管理资源调度。过去，任务或工作请求可以立即开始，并且可以安排在任何空闲主机上。然而，目前的资源调度通常需要更多资源，因为现在需要提前预留可用资源，下面将进一步讨论。

参考图3，所示的“资源”可以是指一个主机上的CPU内核，并且工作301计划在未来某个时间执行(使用一个或多个CPU内核)。在这种情况下，所述资源调度器可能需要确定是否可以将工作302、工作303或工作304放置在当前可用的资源上，以便立即可以启动工作302、工作303或工作304中的一个或多个，同时仍然确保工作301将具有足够的资源在其未来的指定时间运行。这种技术称为‘回填’。然而，如果完成工作302、工作303或工作304所需的时间太长，则不能总是使用回填，因为工作301无法按计划启动。

在另一种情况下，如果在未来的某个时间点存在针对所述主机的计划维护，并且因此在该计划维护期间所述主机上的所有CPU内核都不可用(例如，在该计划维护期间无法在所述主机上执行任何工作)，则所述资源调度器可能还需要确定在该计划维护周期开始之前是否有足够的时间在所述主机上启动和运行一个或多个工作请求直至完成。

为了在上述情况下做出关于资源调度的更有效决策，需要确定完成请求的工作所需的时间。如果完成工作所需的时间未知，则所述资源调度器可以预测所述工作在一段时间内的资源使用量以及所述工作使用所述资源的持续时间。

此外，由于存在一些具有固定超时(例如，可以执行所述工作的时间限制或最长持续时间)的工作请求，所述资源调度器可能不需要预测所述工作的确切持续时间，而是将所述时间限制用作所述预测的持续时间。例如，许多无服务器函数具有时间限制，并且许多云服务提供商支持无服务器函数(例如，

Lambda)。

如上所示，在所述分布式计算系统中的资源调度的上下文中，时间维度可能是高度复杂的概念。然而，为了实现有效的资源调度，可能需要考虑所述时间维度。为此，实施例提出将所述时间维度用作资源层次结构中的另一资源维度。

资源调度器通常没有表示模型的通用方法。虽然一些资源调度器可以在其源代码中包含数据结构，但是这些数据结构仅可用于某些相关的特定资源(例如，‘cpu’和‘存储器’)。在许多先验资源表示模型(例如，YARN、OpenStack)中，资源是硬编码的独立对象，仅以标量值表示，并且没有时间维度。此外，这些模型不是可以对用户定义的资源进行编码的资源模型。

存在几种通用的资源模型。一个示例是Chan和Curry在第6829765号美国专利案中提出的平面资源模型。所述平面资源模型通常表示资源管理(resource management，RM)系统中的资源。然而，无法使用这种方法表示层级资源结构。通用资源模型的另一个示例是Guo、Chen和Lam在公开号为2017/0153918A1的美国专利申请案中提出的用于分布式资源管理的通用资源模型。该模型可以表示资源的层级结构。在该通用资源模型中，底层的资源值是不同数据类型的标量值。该资源模型可以具有多种数据类型(例如，布尔值、字符串值和浮动值的组合)，因此该资源模型是一种灵活的模型。然而，当要调度的资源数量增加时，该通用资源模型可能会变得低效。

在层级资源的上下文中，资源调度器的主要功能是将工作请求与资源层次结构中目标维度的目标资源进行匹配。该功能可以包括三个子问题：(i)确定哪些目标资源具有足够的可消耗资源来满足请求；(ii)基于适当的标准(例如，跨主机扩展请求等)确定哪些目标资源与请求‘最佳匹配’；(iii)在发生冲突时解决冲突，在并行做出调度决策时尤其如此。解决这三个子问题可以被视为‘调度操作’。图4示出了分布式计算系统中调度操作的一个示例，具体地，检查主机是否具有用于工作请求的足够资源。

参考图4，上层网格的每个方块表示工作请求410‘i’随时间推移所需的可消耗资源(例如，存储器411、CPU 412和网络413)，而下层网格的每个方块表示主机420‘h’中的所述可消耗资源(例如，存储器421、CPU 422和网络423)随时间推移的当前使用量。具体地，所述上层网格的每个方块处颜色的深浅表示所述工作请求410‘i’在特定时间所需的可消耗资源(例如，存储器411、CPU 412和网络413)的数量，而所述下层网格的每个方块处颜色的深浅表示所述主机420‘h’中的所述可消耗资源(例如，存储器421、CPU 422和网络423)在特定时间的当前使用量。所述上层网格中方块的颜色越深，表示所述工作请求在所述特定时间需要的可消耗资源越多。类似地，所述下层网格中方块的颜色越深，表示所述主机中的每个可消耗资源在所述特定时间的使用量越大。另一方面，白色方块表示不使用或不需要所述可消耗资源，黑色方块表示充分使用或完全需要所述可消耗资源。

参考图4，横轴表示时间或时间步长。对于每个主机/请求检查(例如，工作请求410/主机420)，所述资源调度器可以检查每个可消耗资源(例如，存储器421、CPU 422、网络423，索引为r＝1……R)的使用量在每个时间步长(例如，t＝1……T)处是否都在其容量范围内。换言之，所述资源调度器的任务是检查所述请求所需的可消耗资源(即，所述上层网格的每个方块)和所述主机使用的可消耗资源(即，所述下层网格的每个方块)的总和是否小于所有时间步长中的每个时间步长处的可消耗资源容量。当所述使用量达到100％(例如，所述方块为黑色)时，每个可消耗资源的容量可以等于所述可消耗资源的使用量。当存在‘I’个请求和‘H’个主机资源(每个主机资源具有‘R’个可消耗资源)时，所述资源调度器可以确定每个请求(即，请求i＝1……I)是否与每个主机资源(即，主机资源h＝1……H)相匹配，使得对于每个时间步长(即，时间步长t＝1……T)，每个可消耗资源(即，资源r＝1……R)的使用量在添加所请求值之后在其容量内。对于整个检查过程，所述资源调度器总共需要执行I*H*R*T项检查。

就此而言，相对于资源和时间的调度在计算上较为昂贵(例如，检查次数较多)。如果有5000个主机(即，H＝5000)和6个可消耗资源(即，R＝6)(例如，CPU、存储器、网络等)来执行调度检查，并且所述检查需要完成7200个时间步长(即，T＝7200)(注意：如果1个时间步长等于1分钟，则7200个时间步长等于5天)，则每个请求(即，I＝1)将有2.16亿个值需要检查。如果有500个工作请求(即，I＝500)需要调度，则所述资源调度器需要检查1080亿个值。

为了管理该在计算上较为昂贵(例如，大规模)的资源调度问题，可能需要对资源调度操作进行并行处理。通过上述基于标量的资源模型，只能在请求之间对调度高效进行并行处理(例如，在请求级别进行并行处理)。请求可以在具有或不具有多个资源池(例如，孤岛)的多个资源调度器之间进行负载平衡，如下所示。

在请求之间进行并行处理的一种方法是将资源划分为单独的资源池(例如，孤岛)，并为每个所述资源池指定资源调度器，以便仅将(工作)请求与该资源池中的资源进行匹配。该并行方法可能会导致碎片化。换言之，即使可用资源的总量足以满足工作请求，这些可用资源也不能用于所述工作请求，因为所述资源在不同的资源池中是‘碎片化’资源。

在请求之间进行并行处理的另一种方法是使一个公共资源池具有多个资源调度器，以处理工作请求的子集。应当理解的是，该并行处理方法不会在资源池之间导致碎片化。然而，使用此方法时，由于每个资源调度器独立做出决策，因此始终有可能做出相互冲突的决策。因此，当不同的资源调度器之间出现冲突时，系统需要有一种解决冲突的机制。所述冲突解决机制可能会增加所述系统的额外开销，因此可能会使调度更加复杂。

由于请求之间的调度并行处理存在不足，因此需要一种更好的资源调度并行处理方法。克服上述问题的一种方法是在请求‘内’并行处理调度(即，执行并行操作以调度单个请求)。应当理解的是，在请求内进行并行处理可以与上述在请求之间进行并行处理的方法中的一种或两种同时执行。然而，与在请求之间进行并行处理相比，在请求内进行并行处理在计算上可能更有效。在请求内进行并行处理也可以不那么复杂。然而，在请求内进行并行处理可能需要新的资源模型。因此，提供了一种新的资源模型，所述新的资源模型可以用于在所述请求内进行并行处理。

实施例可以潜在地改进调度的几个版本。实施例可以改进在线一对一请求调度，其中所述调度是在存在或不存在时间维度的情况下执行的(例如，针对2个内核和2GB RAM调度一个请求，持续时间为10分钟或其它固定时间段)。例如，通过使用所述新的资源模型，可以在主机和/或资源上在请求内(如上所述)对调度计算进行并行处理。由于仅在主机上而不是在请求上对所述调度计算进行并行处理，因此可以将该版本视为半矢量化版本。

实施例还可以改进在线小批量调度，其中批处理多个请求，然后并行处理所有请求(在请求内和请求之间进行并行处理，如上所述)。可以在存在或不存在时间维度的情况下执行调度。由于在请求上和主机上对调度计算进行并行处理，因此可以将所述小批量调度案例视为全矢量化版本，这与仅在主机上对调度计算进行并行处理的半矢量化版本形成对比。

实施例还可以改进离线前瞻调度(规划)。在这种情况下，预先了解一组完整的请求。在该版本中，所述时间维度上的调度可能是调度问题的一个重要方面。所述离线前瞻调度也可以在全矢量化版本中执行(或者，可以仅在半矢量化版本中执行)。

应当注意的是，在线调度与离线规划之间的界限可能会变得模糊，因为在在线情况下可能会考虑所述时间维度(例如，工作请求的子集稍后才开始—例如，预订)。

根据实施例，新的资源表示用于调度，其中，资源使用张量(例如，统一数据类型的多维数组)来表示。具体地，资源层次结构可以表示为具有用于每个资源层级的维度的张量。

图5A示出了实施例提供的通过将概念资源层次结构转换为张量表示对资源层次结构进行编码的基于张量的资源模型。根据实施例，可以将不同资源类型之间的层级关系编码为所述张量中的不同维度。所述资源层次结构中的每个‘层级’对应于所述资源张量中的一个‘维度’。较高维度中的资源可以被视为‘具有’较低维度中的资源。例如，所述张量(例如，张量520)可以具有表示主机、可消耗资源和时间步长的维度。因此，所述一个或多个资源张量中的维度顺序表示所述资源的所述层级关系，使得一个维度中的资源包含后续维度中的资源。通过这种方式，所述资源张量能够表示所述资源的所述层级关系，使得处于所述层级关系的第二层级的资源包含处于所述层级关系的第一层级的资源。‘主机’维度521的大小为‘H’，因此在所述分布式计算系统中存在‘H’个主机(例如，主机510)。所述主机维度521之后是‘可消耗资源’维度。所述可消耗资源维度522的大小为‘R’，因此总共存在‘R’个可消耗资源，并且每个主机‘具有’所有这些‘R’个可消耗资源。所述可消耗资源维度中的数组包含可消耗资源的值，例如，‘cpu’(例如，cpu 511)、‘存储器’(例如，mem 512)、‘disk_capacity’、‘disk_bandwidth’等。所述可消耗资源维度522之后是‘时间步长’维度523。所述‘时间步长’维度523的大小为‘T’，因此存在‘T’个时间步长，并且每个可消耗资源‘具有’T个时间步长内的值。关于时间步长，实施例可以将所述时间维度视为资源层次结构中的另一个可消耗资源，例如，如图5B所示。应当注意的是，图5B中的树型资源模型用于示出将时间视为其它可消耗资源的可消耗资源或子资源的概念。

根据实施例，最低维度(即，底部层级)的每个数组包含对“可消耗”资源量进行编码的实际值。例如，resource_tensor[h][r][t]将包含表示时间‘t’时主机‘h’中资源‘r’的量的值。再次参考图5A中所示的资源结构，如果resource_tensor[0][1][2]＝20，则所述资源模型指示在时间步长2处所述主机510(注意：主机510＝主机[1])上存在20个‘cpu’(例如，资源[0]＝cpu)。可以指定每个张量中资源值的数据类型(例如，布尔、整数、Float16、Float32等)。

根据实施例，可以存在“资源张量”(例如，图5A中所示的张量520)，所述资源张量对所有主机上的资源、所有可消耗资源和所有时间步长(例如，形状为H x R x T)进行编码。所述资源张量可以指示每个资源的使用量(“资源使用量张量”)，也可以指示每个资源的剩余量(“资源剩余量张量”)。在本申请中，术语‘资源张量’可以用于可互换地定义“资源使用量张量”和“资源剩余量张量”，需要明确区分‘资源张量’是资源使用量张量还是资源剩余量张量的情况除外。

所述资源使用量张量(指示每个资源的使用量的资源张量)可以与指示每个资源的容量(例如，总量)的张量结合使用。所述总容量张量可以指示在不超过所述资源容量的情况下资源使用量的最大值。为了确保效率，所述总容量张量可以排除值不可变的任何维度。因此，例如，如果所述总容量既不会在不同主机之间变化，也不会随时间变化，则所述总容量张量可以具有1 x R x 1的形状。如果所述总容量值随主机和可消耗资源变化，但不随时间变化，则所述总容量张量可以具有H x R x 1的形状。如果所述总容量值随所有主机、所有可消耗资源和所有时间步长变化，则所述总容量张量可以具有H x R x T的形状。应当注意的是，根据广播规则，每当前导张量维度的大小为1时，可以从所述资源表示中排除维度(层级)，而不改变调度操作的输出。

根据实施例，每当对资源提出(例如，调度)新的工作请求时，或者每当先前请求的工作使用其分配的资源完成时，可以更新所述资源使用量张量。所述资源使用量张量也可以随时间(例如，随时间推移)进行更新。在一些实施例中，可以使用过去时间步长处的资源使用量值来预测新的未来时间步长处的资源使用量。

在一些实施例中，可以使用单个资源剩余量张量(即，‘剩余量容量’或‘可用容量’张量)来代替资源使用量张量和总容量张量。所述资源剩余量张量可以指示剩余的资源量。

在一些实施例中，可以针对资源管理使用一种或多种不同类型的张量。所述一种或多种不同类型的张量可以代替使用或与所述资源使用量张量、所述总容量张量和所述资源剩余量张量中的一个或多个一起使用。

根据实施例，可以存在用于资源调度的请求张量。所述请求张量可以对要调度的工作请求所需的请求资源进行编码。一次处理单个请求时，所述请求张量可以指定所述可消耗资源和时间维度上的资源。在这种情况下，所述请求张量的形状可以为1 x R x T(或等效地，R x T)，所述前导主机维度的大小为1。同时并行处理‘I’个请求时，所述请求张量可以是形状为I x 1 x R x T的张量，因为添加了‘I’个请求的额外维度。稍后处理调度操作时，所述主机维度仍然等于1以便高效使用广播。如果所述资源请求随时间推移在所述可消耗资源中是恒定的，则可以将所述请求指定为R x 1张量，并在调度操作过程中根据需要广播所述张量中的值。

根据实施例，可以有调度器，所述调度器也可以称为资源调度器，用于资源调度。所述调度器可以包括计算机实现的用于将每个请求与所述资源张量中的一个主机进行匹配的一组指令或方法。如上所述，所述目标维度可以是所述主机维度，并且所述请求可以指定该目标层级以下维度所需的资源。

图6A示出了具有不同目标维度的资源层次结构表示的另一示例。在该资源模型中，假设目标是将请求与其中一个数据中心中的其中一个机架(机架1、机架2等)中的其中一个主机(例如，主机1、主机2 600)中的其中一个图形处理单元(例如，GPU 610、GPU 620等)进行匹配。所述目标层级为所述处理单元(例如，GPU 610、GPU 620)。因此，每个请求可以指定其在所述处理单元层级(GPU层级)以下所需的所有资源(或可消耗资源)。在这里，在特定时间段内(例如，T个时间步长)，所述GPU可以相当于一定数量的‘存储器’和‘内核’。调度单个请求时，所述请求张量的形状可以为R x T。在这种情况下，R的值为三(3)，因为有三种类型的可消耗资源：‘GPU存储器’611、‘GPU内核’612和‘GPU磁盘’613。

根据实施例，所述资源张量的形状可以为D x K x H x G x R x T(D个数据中心xH个主机x G个GPU x R个可消耗资源x T个时间步长)。所述资源可以编码为资源[d][k][h][g][r][t]，所述请求可以编码为请求[r][t]。在各实施例中，使用资源张量和请求张量，可以简单地实现调度过程，即使使用单行计算机源代码也是如此，以确定适合每个请求的数据中心、机架、主机或处理单元(例如，GPU 610、GPU 620)。

图6B示出了本发明实施例提供的资源张量中的张量目标维度(例如，目标维度650)。根据实施例，所述资源张量中的一个维度可以显式地或隐式地用作目标维度。将一个维度表示为所述目标维度指示应如何使用所有维度中的资源。在各实施例中，可以认为请求需要处于目标层级的资源中的‘一个’资源，并且隐式地需要处于所述目标层级以上的每个级别的资源中的一个资源。例如，参考图6B，请求可能需要‘一个’数据中心、‘一个’机架、‘一个’主机和‘一个’GPU来满足完成所述请求的资源需求。此外，在各实施例中，可以认为请求需要处于所述目标维度层级以下的所有层级的‘所有’资源。例如，参考图6B，请求可能需要所述张量中的所有时间步长处的“所有”可消耗资源(例如，所有CPU、所有存储器等)。

在一些实施例中，对于一些调度操作，可以将所述资源张量重塑为J x L矩阵(注意：‘矩阵’是2维张量)。将所述资源张量中处于目标层级以上的所有维度合并为单个维度。该单个维度为“J”维度，即所述J x L矩阵中的第一维度。类似地，同时将所述资源张量中处于目标层级及以下的所有维度合并为另一单个维度。该单个维度为“L”维度，即所述J x L矩阵中的第二维度。因此，在图6B中所示的资源张量模型的情况下，所述J维度的大小可以为D*K*H*G，所述L维度的大小可以为R*T。在一些实施例中，可以将所述请求张量重塑为大小为L的单维数组。

与先验工作中使用的资源模型层次结构相比，资源张量具有一些约束条件。与先验模型一样，单个资源张量可以对资源的层次或“树”进行编码。然而，作为一种基于多维数组的数据结构，在层次结构中的不同层级可以对哪些资源进行编码的灵活性较低。具体地，在单个资源张量中，所有数字可消耗资源必须处于叶级(例如，实际CPU、存储器、磁盘值等)。此外，如上所述，所有数字可消耗资源必须具有相同的数据类型，例如，具有统一数据类型。此外，所有非叶资源都是‘复合’资源(例如，包含其它资源的资源)。最后，处于所述树中给定级别的所有资源(例如，所述张量中给定维度的资源)必须具有相同数量的子资源。虽然比先验模型受到更多约束，但资源张量的优点在于，通过并行矢量化操作，可以更快地对这些模型执行操作，如上文进一步描述的。此外，为了在这些约束条件受到太多限制时提高灵活性，本领域技术人员将理解如何调整资源张量以提高灵活性。下面将进一步讨论这些调整的一些示例。

在一些实施例中，可以有多个资源张量(以及多个相应请求张量和容量张量)来管理几种不同的情况。在一些实施例中，当可消耗资源值可以在逻辑上存在于所述资源层次结构的不同层级时(例如，如上所述，违反单个资源张量的其中一个约束条件)，可以有多个资源张量。例如，除了对每个主机中具体可用的资源进行编码的资源张量之外，还可以存在用于主机之间共享的资源的单独资源张量。共享资源的一个示例是软件许可证。软件许可证是一种资源，一次只能供一定数量的请求使用。所述软件许可证可以供所有主机上的请求使用。换言之，所述软件许可证在所有主机的请求之间共享，并且所述软件许可证可以被视为共享资源。由于与其它资源不同，该共享资源不属于特定主机，因此可能需要单独的资源张量。因此，可以存在单独的资源张量用于共享资源，以管理资源调度。此外，还可能需要单独的相应请求张量和容量张量。

在一些实施例中，可以存在对所有租户的资源消耗进行编码的单个张量，因为可能需要跟踪每个租户随时间推移的资源消耗以实现租户共享策略。

在一些实施例中，可以存在单独的资源张量用于过去资源使用量(例如，观察的使用量)和未来资源使用量(例如，预测的使用量)。用于过去资源使用量的张量可以用于预测未来资源使用量，用于未来资源使用量的张量可以用于做出资源放置决策，以确保为未来请求的工作负载提供足够的容量。

如果所述资源层次结构中的一些资源在逻辑上具有不同数量的子资源(例如，一个主机具有一个GPU，另一个主机具有两个GPU)，这似乎也违反单个资源张量的其中一个约束条件，如上所述。然而，在一些实施例中，如果对所述容量张量中缺失的可消耗资源(例如，不存在的GPU)的‘零(0)’容量进行编码，则仍然可以使用单个资源张量。例如，当一些主机具有‘两个’GPU，而一些主机具有‘一个’GPU时，可以使用在逻辑上将每个主机编码为具有两个GPU的单个资源张量。然后，对于所述容量张量中不存在的GPU(例如，实际上仅具有一个GPU的主机上不存在的GPU)，可以对‘零(0)’容量进行编码。然而，在一些实施例中，可以对具有一个GPU的主机和具有两个GPU的主机中的每个主机使用单独的资源张量，而不是对‘零(0)’容量进行编码。

如果所述层次结构中的所有可消耗资源在逻辑上不是相同的数据类型(例如，一些底部层级资源值是数字，其它底部层级资源值是布尔(True/False)值等)，则可能进一步违反单个张量约束条件。在这种情况下，在一些实施例中，可以对每个资源数据类型使用单独的张量。

如果并非所有资源在逻辑上都具有时间维度(例如，如果一些资源是‘静态的’或简单的‘基于标签的’资源)，则可能进一步违反所述单个张量约束条件。在一个实施例中，时间维度可以用于所有资源，但是所述静态资源随时间推移可以是恒定的。在另一实施例中，可以使用单独的资源张量，例如，一个资源张量具有时间维度，一个资源张量不具有时间维度。在此类实施例中，可以分别针对基于时间的张量和基于标签的张量检查请求。

图7示出了实施例提供的资源张量中的时间维度的逻辑循环缓冲器710和循环缓冲器实现方式720。根据实施例，可以使用循环缓冲器710对资源张量中的时间维度进行编码。在张量表示中，可以将时间维度唯一地视为具有一定增量或间隔(例如，每一分钟)的时间步长。因此，随着时间的推移，可能需要更新所有资源值。例如，之前距某个时间点两个时间步长的资源值现在距同一时间点只有一个时间步长。因此，需要更新所述张量中的资源值。然而，不需要在每个时间步长上更新所述张量中的所有资源值，因为此类更新在计算上较为昂贵。

为了解决该问题，可以针对资源张量中的时间维度实现逻辑循环缓冲器710，例如实现为图7中所示的循环缓冲器实现方式720。具体地，可以实现开始指针(例如，开始指针701)和结束指针(例如，结束指针702)，并使所述指针分别保持动态指向时间维度值的‘开始’和‘结束’(或时间维度值的子数组)。在每次更新时，可以插入、从过去的值外推或显式预测每个主机和资源的新的‘结束’值。随着时间的推移，可以根据需要围绕所述时间维度值的实际结束旋转所述开始指针和所述结束指针的值。例如，参考图7，所述开始指针701可以指向位置1(例如，数组索引0)，所述结束指针702可以指向位置10(例如，数组索引9)。随着时间的推移，所述开始指针701和所述结束指针702的位置的值可能会递增。当指针位于所述时间维度值的末尾时，随着时间的推移，所述指针将继续转移到(例如，绕回)到所述时间维度值的开头。例如，在前进4次之后(例如，4个时间步长之后)，所述开始指针701从位置1移动到位置5，所述结束指针702从位置10移动到位置14，所述位置14实际上是存储器内线性缓冲器的位置4。

根据实施例，随着时间的推移，资源张量中的时间维度的循环缓冲器能够更快地更新所述张量中的值。在一些实施例中，所述资源张量更新的速度可以提高‘T’倍，其中，所述时间维度的大小为‘T’。可以将速度提高‘T倍’，因为仅需在T个时间步长中的一个时间步长而不是所有T个时间步长执行所述更新。

根据实施例，可以使用张量来表示资源，以便高效执行调度操作。调度操作可以包括：(i)在逻辑上对主机提出请求；(ii)确定请求与主机是否相匹配；(iii)找到对其提出所述请求的最佳主机；(iv)确定请求能够与一个或多个主机匹配的次数；(iv)解决调度操作期间出现的冲突。在各实施例中，可以使用科学(软件)框架和库(例如，NumPy和PyTorch)执行调度操作。

根据实施例，可以使用张量模型更有效地执行提出请求(例如，对主机提出请求)的调度操作。例如，当存在形状为H x R x T的资源使用量张量以及形状为R x T的请求张量时，对第i个‘主机’提出R x T请求可以实现如下：

resources[i]+＝request

或

resources[i]＝resources[i]+request

由于资源[i]和请求都具有R x T的形状，因此加法运算(例如，‘+’)可以修改所述资源张量的位置‘i’处的R x T子数组中的值。科学(软件)框架或库(例如，NumPy和PyTorch)可以自动编译源代码以高效执行调度操作(例如，对主机提出请求)。在一些实施例中，可以在GPU和张量处理单元(Tensor-Processing Unit，TPU)等专用硬件上更有效地编译源代码。因此，可以在GPU和TPU等专用硬件上更有效地对主机提出请求。

一旦完成所述请求的工作(例如，请求)，所述调度操作可以继续从所述第‘i’个主机中移除所述已完成的工作，并释放其资源用于其它工作请求。从所述第‘i’个主机中移除所述已完成的请求可以实现如下：

resources[i]-＝request

或

resources[i]＝resources[i]-request

根据实施例，张量模型可以用于在调度期间更有效地确定请求与一个或多个主机是否相匹配。换言之，张量模型允许所述资源调度器高效地找到资源子集(在这里，处于所述主机层级)，其中，所述资源子集具有‘充分’或足够的资源以执行所述请求(在这里是为了确定可以接受所述请求的主机)。图8示出了使用一个请求和两个主机执行此类确定的示例。图8示出了不具有时间维度的情况。虽然图8中未示出，但当张量具有时间维度时，可以在所述时间维度的所有值中重复确定请求与主机是否相匹配。

参考图8，可以为主机821和822中的每个主机提供请求810所请求的资源量以及当前资源使用量和总容量。该操作(例如，确定所述请求与所述主机是否相匹配)的目的是找到可以接受所述请求的主机。通过在任何可消耗资源维度(例如，CPU、存储器等)中找出所述请求所请求的资源量与所述主机中的当前资源使用量之和是否不超过所述主机的总容量，可以确定所述请求与所述主机是否相匹配。在图8所示的情况下，所述请求810与所述主机821不匹配，因为所述请求810所请求的资源量与所述主机821中的当前资源使用量之和超过所述主机821在所述存储器维度中的总容量。另一方面，所述请求810与所述主机822相匹配，因为所述请求810所请求的资源量与所述主机822中的当前资源使用量之和不超过所述主机821在任何资源维度中的总容量。

根据实施例，可以使用矢量化操作来确定请求与主机是否相匹配。在各实施例中，单个矢量化操作可以足以实现在所有时间步长内确定多个请求与多个主机是否相匹配。例如，当资源张量(例如，下面代码中的资源)具有H x R x T的形状时，请求张量(例如，下面代码中的请求)具有I x 1 x R x T的形状(即，总共存在‘I’个请求)，并且所述总容量张量(例如，下面代码中的resource_capacity)具有H x R x 1的形状(即，容量随时间推移是恒定的)，确定所述多个请求中的每个请求与所述多个主机中的每个主机是否相匹配可以简单地使用NumPy中的单个命令实现，如下所示：

server_fits＝np.all(request+resources<＝resource_capacity,axis＝(2,3))

输出将是形状为I x H的布尔张量，如果索引(i,h)处的输出张量值为‘True’，则所述请求‘i’与所述主机‘h’相匹配。如果索引(i,h)处的输出张量的值为‘False’，则所述请求‘i’与所述主机‘h’不匹配。形状为I x H的输出张量的示例可以如下所示。每个Fits_i,h可以保留布尔值(例如，True或False)。

上面的代码说明了‘广播’的概念。如上所述，算术运算‘request+resources<＝capacity’中的三个张量都具有不同的维度(分别为I x 1 x R x T、H x R x T和H x R x1)。为了执行计算，在一些实施例中，源代码隐式地在所有主机维度之间广播请求、在所有请求维度之间广播主机并在所有请求和所有时间步长内广播容量。例如，执行其中所述请求张量和所述资源张量是所述操作的参数的调度操作时，资源调度器或其它计算设备可以高效且自动地(i)对齐所述请求与所述资源张量之间的维度，(ii)广播(例如，在逻辑上复制)请求和资源张量数值，以便所述请求张量隐式地具有与所述资源张量相同的维度，而实际上无需复制存储器中的数据，(iii)执行所需的操作(例如，将所述请求数值添加到资源数值中)。根据实施例，广播可以为张量表示带来一定的灵活性和效率。例如，对于随时间推移的固定请求(即，静态、非动态请求)，可以使用维度为R x 1的张量(而不是维度为R x T的张量)，并且可以在调度操作期间的所有时间步长内广播可消耗资源值。又例如，考虑到前述形状为D x K x H x G x R x T的复杂资源张量，所述请求张量可能不需要在维度方面与所述资源张量完全匹配，以便执行调度操作，其中所述请求张量和该资源张量是所述操作的参数。例如，如果所述请求张量具有R x 1的形状，则可以在调度操作期间，自动广播所有复合资源维度(D、K、H和G)之间以及所有时间步长内的请求张量可消耗资源值。实际上可能不需要复制数据，即实际上不需要在存储器中实例化维度为D x K x H x G x R x T的请求张量即可继续所述操作。

参考上述源代码，可以使用‘所有’操作(例如，np.all)，因为所述请求需要处于所述目标层级/维度以下的所有资源。仅当输入张量中沿给定维度或一组维度(NumPy术语中的(一个或多个)‘轴’)的‘所有’元素评估为True时，‘所有’操作才返回True。在这种情况下，所述输入张量是加法运算和比较运算(例如，request+resources<＝resource_capacity)的输出，并且要使用的轴是时间维度和可消耗资源维度。参考上述源代码，要检查真值的维度表示为‘axis＝(2,3)’。

上述源代码可以被视为基于张量的调度的‘全矢量化’版本，因为所有请求和所有主机都是同时处理的。可以使用‘for’循环实现相同的功能，其中，在每次迭代时处理单个请求(例如，确定请求与每个主机是否相匹配，但仅针对每次迭代时的单个请求)。基于for循环的方法可以被视为“半矢量化”版本。

根据实施例，确定对其提出请求的最佳主机时，可以使用张量模型。确定对其提出请求的最佳主机时，可能需要避免所述主机上的可消耗资源在一个维度上耗尽而在其它维度上未耗尽的情况。例如，当大部分存储器仍然可用时，可能不需要耗尽主机上的所有CPU。在这种情况下，尽管主机上具有大量可用存储器容量，但是由于所述主机上CPU已充分利用，无法在所述主机上放置新任务，因此该容量将被浪费。为了避免此类低效的资源使用，资源调度器可以以如下方式提出请求：提出请求之后，主机中的总资源使用量在矢量相似性方面与所述主机的总容量类似。

根据实施例，通过计算‘余弦相似性’，可以找到所述主机中的所述总资源使用量与所述主机的所述总容量之间的矢量相似性。余弦相似性可以指多维空间中两个矢量之间夹角的余弦值，其中，一个向量表示提出所述请求之后所述主机中的所述总资源使用量，另一个矢量表示所述主机的所述总容量。如果所述两个矢量彼此接近(即，在提出所述请求之后所述主机中的所述资源使用量和所述主机的所述总容量彼此相似)，则所述两个矢量之间的夹角较小，并且所述夹角的余弦值将接近1。另一方面，如果所述两个向量彼此相距较远(即，在发出所述请求时，考虑到一个维度的总资源容量的情况下所述维度的资源使用量远高于考虑另一个维度的总资源容量的情况下所述另一个维度的资源使用量)，则所述两个矢量之间的夹角较大，并且所述夹角的余弦值将接近0。

图9示出了实施例提供的使用余弦相似性确定对其提出请求的最佳主机的示例。此操作的目的是找到对其提出请求的最佳主机。根据实施例，可以通过计算每个主机中的总资源使用量(例如，总资源使用量＝请求的数量+每个主机中的当前资源使用量)与每个主机中的总资源容量之间的余弦相似性来确定最佳主机。所述最佳主机可以是总容量与请求的资源量与所述主机使用的资源量之和最相似的主机。

参考图9，可以提供请求910所请求的资源量，同时可以为主机921和922中的每个主机提供当前资源使用量和总容量。矢量931表示所述主机921的总资源使用量的矢量(例如，所述请求910所请求的资源量与所述主机921中的当前资源使用量之和)，矢量932表示所述主机921的总资源容量的矢量。类似地，矢量941表示所述主机922的总资源使用量的矢量(例如，所述请求910所请求的资源量与所述主机922中的当前资源使用量之和)，矢量942表示所述主机922的总资源容量的矢量。为了找到对其提出请求的最佳主机(在这种情况下，为所述主机921或所述主机922)，计算所有主机(例如，主机921和922)的总资源使用量(例如，请求的数量与主机使用量之和)与总资源容量之间的余弦相似性。在这种情况下，可以通过计算所述矢量931与932之间夹角的余弦来获得主机921的余弦相似性。类似地，可以通过计算所述矢量941与942之间夹角的余弦来获得主机922的余弦相似性。由于所述矢量941与942之间的夹角小于所述矢量931与932之间的夹角，因此所述主机922的余弦相似性将大于所述主机921的余弦相似性。因此，对所述主机921提出所述请求910将更好地平衡各维度中与其容量成比例的资源使用量。

如果存在I个请求和J个主机，在对每个主机提出每个请求时，可能需要针对余弦相似性生成I x J矩阵(即，I x J浮点张量)。可以使用NumPy中的以下“半矢量化”(即，一次一个请求)源代码计算余弦相似性：

for each request:

proposed＝request+resources

proposed_norm＝torch.norm(proposed,dim＝1)

cosine_dot＝torch.einsum(“ijk,ijm->i”,proposed,resources_capac)

cosines[i]＝cosine_dot/(proposed_norm*resources_capac_norm)

针对所有请求(加主机使用量)矢量和所有主机容量矢量的计算的余弦相似性的输出张量的示例可以如下所示。所述输出张量可以具有I x J的形状。每个cosθ_i,j(例如，i＝1……I，j＝1……J)可以保留浮点值(例如，0.866025404)，所述浮点值指示请求+使用量与主机容量向量之间夹角的余弦。

参考上面的NumPy源代码，所述代码的最后一行(例如，cosine[i]＝cosine_dot/(proposed_norm*resources_capac_norm))等同于以下数学表达式，所述数学表达式表明可以通过计算矢量的点积值与每个矢量的范数之商来获得余弦值。

参考上述NumPy源代码，‘爱因斯坦求和’运算(例如，torch.einsum)用于计算所有可消耗资源和时间步长内的点积。然后，该点积成为最后一行代码中表达式中的分子，如上所述。

根据实施例，通过在多个CPU和GPU之间划分请求(以及因此在每次迭代时执行的相应余弦相似性计算)，可以对上面所示的源代码的“半矢量化”版本进行并行处理，其中，每个CPU或GPU可以在循环中完成部分迭代工作。这可能会提高整个I x J余弦相似性输出矩阵的计算速度。

根据实施例，使用余弦相似性是执行可以在资源调度中采用的‘最佳匹配’操作(例如，确定对其提出请求的最佳主机)的一种方式。替代地，在其它实施例中，可能需要尽可能“分散”请求，以使资源使用量尽可能保持均匀。关于使用“分散”标准计算“最佳匹配”，还可以轻松地进行矢量化。例如，可以计算每个主机中的总(即，聚合)资源使用量的范数，以查看每个主机使用的资源量。有几种方法可以随着时间的推移高效地重新计算每个主机中的聚合资源使用量，例如仅加减随时间推移移除或删除的值。一旦计算出每个主机的资源使用量的范数，即可对最少使用的主机(即，使用最少资源量的主机)提出请求。在这里，所述最少使用的主机可以是具有最小范数的主机。

除了用于确定“最佳匹配”得分的主机的余弦相似性和“最少使用”评分之外，本领域技术人员将容易理解，根据实施例，使用资源和请求张量时，还有其它可能的方法来执行‘最佳匹配’计算。在本申请中，所述‘得分’可以被视为对给定工作请求使用给定资源作为主机的‘适合程度’度量。

根据一些实施例，所述资源调度器可以预先计算(即，“预先确定”)所有可能的建议放置(即，所有可能的总资源使用量，其为所有可能的请求量与主机使用量之和)与每个主机上的总资源容量之间的余弦相似性得分。所述预先计算的余弦相似性得分中的每一个可以存储在得分函数张量中。实质上，所述得分函数张量可以为每个可能的请求放置提供值，包括集群中当前不存在的建议放置。例如，在一些实施例中，可以针对所有可能的资源组合(例如，所有可能的CPU和存储器组合：<1个内核，1GB>、<1个内核，2GB>、<2个内核，1GB>、<2个内核，2GB>等)预先计算所述得分函数。

一旦将所述预先计算的余弦相似性得分存储在所述得分张量中，则可以使用相应的请求放置对所述得分张量(以矢量化方式)进行索引，从而针对所有建议的请求放置高效地生成余弦相似性得分。

在一些实施例中，可以访问所述预先计算的得分以找到与主机的‘最佳匹配’，如使用以下NumPy源代码所示：

for each request:

proposed＝request+resources

proposed_indices＝np.split(proposed,proposed.shape[-1],axis＝-1)

proposed_scores＝scoring_tensor[proposed_indices]

placement_spot＝proposed_scores.argmax()

参考上述源代码，可以以与计算每个请求的余弦相似性的半矢量化NumPy源代码相同的方式获得建议的请求放置(即，“建议”)。所述获得的建议请求放置(即，“建议”)将被转换为多维索引。可以通过沿最终资源维度拆分所述建议的请求放置来获得该多维索引(即，proposed_indices)。在各实施例中，如上所示，可以简单地使用通过NumPy提供的‘拆分’函数来获得所述多维索引，同时还可以使用其它替代方法(例如，获取按所述可消耗资源维度分组的资源的‘视图’的方法，而不是将其复制到新数组中)来获得所述多维索引。所述多维索引(例如，proposed_indices)可以用于检索每个建议的请求放置的相应余弦相似性得分。所述资源调度器可以对所述建议的请求放置得分最高(例如，如果scoring_tensor对余弦相似性进行编码，则这将是具有最高余弦相似性得分的主机)的所述主机提出请求。可以针对每个请求重复上述步骤。

使用预先计算的得分函数来确定对其提出请求的最佳主机有以下几个原因。主要原因在于，与在资源调度器操作期间多次重新计算得分相比，仅计算一次得分并缓存所述得分以备将来检索更为高效。另一个原因在于灵活性，例如，当需要从余弦相似性切换到‘最少使用’评分函数时，不需要对调度源代码进行相应的更改；只需将使用所述‘最少使用’的评分函数预先计算的得分张量加载到所述资源调度器中作为余弦相似性函数的替代，即可更改所述评分函数。

应当注意的是，仅当存在有限数量的可能得分时，才能预先计算所有得分；并且仅当所述分布式计算系统中存在有限数量的可能资源值组合时，才会出现这种限制。在各实施例中，可以从有限数量的“类别”或CPU和存储器要求的离散选项中提取请求的工作。因此，可以提出有限数量的离散请求放置(例如，现有资源使用量与请求资源量之和)。由于最多需要每个可能的建议放置的得分，因此在开始调度之前需要预先计算有限数量的可能得分。另一方面，在一些实施例中，仅预先计算得分的子集。

根据实施例，确定可以将工作请求与一个或多个主机匹配的次数时，可以使用张量模型。例如，考虑到当前资源可用性，系统运营商可能希望确定可以成功提出的特定指定资源需求的工作请求数量。例如，所述系统运营商可能希望确定是否可以将100个VM全部放置到所述分布式计算系统中，其中每个VM需要1个CPU和2GB存储器。张量模型使得能够使用矢量化操作以计算高效的方式计算该数量。张量模型还能够使用矢量化操作针对多个不同的工作请求以高效的方式并行计算该数量。

根据实施例，解决调度操作期间产生的冲突时，可以使用张量模型。调度时，如果一次仅提出一个请求(即，上述半矢量化版本)，则可能不存在冲突。然而，如果并行提出多个请求或批量处理提出请求(即，使用全矢量化操作版本)，则并行调度可能会导致冲突。例如，当两个请求与同一主机最佳匹配时，则仅在所述两个请求中的一个请求与所述主机相匹配的情况下，才可能会产生冲突。因此，在找出请求是否与每个主机单独匹配之后，或者在确定对其提出每个请求的单个最佳主机之后，可能需要一种解决冲突的算法。因此，在各实施例中，可能需要一种冲突解决机制。

可能有几种方法来解决调度操作期间产生的冲突。在一些实施例中，当一个或多个请求之间产生冲突时，所述资源调度器可以任意选择获胜者请求，并在稍后重新调度失败者请求。在一些实施例中，所述资源调度器可以使用可并行处理的特殊冲突解决算法。一种此类可并行处理的冲突解决算法是Bertsekas和Castanon(Bertsekas、Dimitri P.和David A.Castanon，“拍卖算法的并行同步和异步实现(Parallel synchronous andasynchronous implementations of the auction algorithm)”，《并行计算》17.6-7(1991年)：第707-732页)提出的并行非对称拍卖算法。所述提出的算法通过找到向主机的最佳请求分配来解决分配问题。所述提出的算法的工作原理是，让请求并行迭代地‘出价’，以确定需要对每个主机提出所述请求的程度，并迭代地让每个主机挑选出价最高的请求。将重复执行这些迭代，直到找到最终方案。

根据实施例，在实现调度操作时使用张量具有潜在的优点。一个潜在的优点在于，可以通过非常简洁、易于读取且清晰的源代码来实现调度操作。通常可以通过单行源代码而不是嵌套的for循环中的复杂语句来实现调度操作。使用张量的另一个潜在的优点在于，科学(软件)框架和库(例如，NumPy和PyTorch)可以具有将源代码转换为可以在处理单元(例如，CPU)上高效运行的矢量化指令的内置功能。转换后的指令可以在GPU和TPU等专用硬件上更高效地运行。

根据实施例，使用张量进行调度可以利用专用硬件来执行调度操作。例如，可以针对张量处理操作优化现代GPU、TPU和其它专用AI芯片。通过使用张量对调度操作进行编码，可以(自动)利用专用硬件来对调度操作进行并行处理并且更高效地运行调度操作算法。所述科学(软件)框架和库还可以使用或允许使用并行处理的机器指令和硬件。例如，如果机器支持SIMD指令，NumPy将Python代码编译为底层C代码，并进一步编译所述底层C代码以利用所述指令(例如，

AVX)。与纯Python代码相比，所述SIMD指令的运行速度快得多。与英特尔AVX上的NumPy相比，PyTorch可以在GPU存储器上分配和更新张量，并且(自动)利用GPU并行处理功能进一步提高速度。张量资源模型还可以部署在专用AI硬件或张量处理硬件(例如，TPU)或其它AI加速器芯片上。

根据实施例，可以使用张量(即，具有统一数据类型的多维(分层)数组)对用于在分布式计算系统中进行调度的资源进行建模。所述张量可以表示不同资源之间的层级关系。具体地，将所述时间维度编码为循环缓冲器时，可以使用张量。在一些实施例中，可以使用过去和未来时间的一个或多个单独张量(例如，使用来自过去时间的值来预测未来值时)。

根据实施例，可以使用张量对所有资源使用量、资源容量、剩余或可用资源、请求的资源和所述系统中每个租户使用的资源进行编码。使用张量表示资源时，可以使用张量运算(例如，采用广播的张量计算)来实现标准调度操作。可以使用张量实现的调度操作的一些示例可以是：对主机提出请求；计算请求可以匹配的位置；确定对其提出请求的最佳主机；解决由并行调度操作引起的冲突。可以在专用矢量化CPU、GPU、TPU或其它专用处理单元等专用硬件上放置和执行这些调度操作和相应张量。在各实施例中，可以在分布式计算系统(例如，所述资源调度器可以在其中执行分布式资源管理)中完成上述调度操作和张量资源建模。

图10示出了本发明的不同实施例提供的电子设备1100的示意图，所述电子设备1100可以执行本文中显式地或隐式地描述的上述方法和特征的任意或全部操作。例如，可以将移动电话、智能手机、具有网络功能的计算机、网络节点或机器类通信(Machine TypeCommunications，MTC)设备等UE配置为电子设备1100。进一步地，可以将包括资源调度器的计算设备和本文中所描述的数据中心中的资源服务器配置为电子设备1100。

如图所示，所述设备包括处理器1110(例如，中央处理器(Central ProcessingUnit，CPU)或专用处理单元(例如，图形处理单元(Graphics Processing Unit，GPU)或其它此类处理器单元)、存储器1120、非瞬时性大容量存储设备1130、I/O接口1140、网络接口1150和收发器1160，它们都通过双向总线1170进行通信耦合。根据某些实施例，可以利用所述元件中的任意或所有元件，或者仅利用所述元件的子集。进一步地，所述设备1100可以包含某些元件的多个实例，例如多个处理器(包括CPU和专用处理器的组合)、存储器或收发器。此外，硬件设备的元件可以在没有所述双向总线的情况下直接耦合至其它元件。附加地或替代地，除处理器和存储器之外，还可以采用集成电路等其它电子器件来执行所需的逻辑操作。

所述存储器1120可以包括任何类型的非瞬时性存储器，例如静态随机存取存储器(static random access memory，SRAM)、动态随机存取存储器(dynamic random accessmemory，DRAM)、同步DRAM(synchronous DRAM，SDRAM)、只读存储器(read-only memory，ROM)或其任意组合等。所述大容量存储元件1130可以包括任何类型的非瞬时性存储设备，例如固态磁盘、硬盘驱动器、磁盘驱动器、光盘驱动器、USB驱动器或用于存储数据和机器可执行程序代码的任何计算机程序产品。根据某些实施例，所述存储器1120或大容量存储设备1130可以在其上记录可由所述处理器1110执行的用于执行上述任意方法操作的语句和指令。

应当理解的是，尽管为了说明的目的在此描述了该技术的具体实施例，但是可以在不脱离该技术范围的情况下进行各种修改。因此，说明书和附图仅被视为所附权利要求书限定的对本发明的说明，并且预期覆盖在本发明的范围内的任何和所有修改、变化、组合或等同物。具体地，在该技术的范围内，提供一种计算机程序产品或程序元件，或一种程序存储设备或存储器设备(例如，磁导线或光导线、磁带或磁盘等)，用于存储机器可读信号，根据该技术的方法控制计算机的操作，和/或根据该技术的系统构造其部分或全部组件。

与本文中所描述的方法相关联的动作可以实现为单个计算机程序产品中的编码指令。换言之，所述计算机程序产品是一种计算机可读介质，当所述计算机程序产品加载到存储器中并在所述无线通信设备的微处理器上执行时，在所述计算机可读介质上记录软件代码以执行所述方法。

与本文中所描述的方法相关联的动作可以实现为多个计算机程序产品中的编码指令。例如，所述方法的第一部分可以通过一个计算设备执行，所述方法的第二部分可以通过其它计算设备、服务器等执行。在这种情况下，每个计算机程序产品是一种计算机可读介质，当所述计算机程序产品加载到存储器中并在计算设备的微处理器上执行时，在所述计算机可读介质上记录软件代码以执行所述方法的适当部分。

进一步地，可以在个人计算机、服务器、个人数字助理(personal digitalassistant，PDA)等任何计算设备上，并且根据从C++、Java等任何编程语言生成的一个或多个程序单元、模块或对象或所述一个或多个程序单元、模块或对象的一部分来执行所述方法的每个操作。此外，可以由专用硬件或为此目的设计的电路模块来执行每个操作或实现每个所述操作的文件或对象等。

通过上述实施例的描述，本发明可以仅通过使用硬件实现，也可以通过使用软件和必要的通用硬件平台实现。基于这种理解，本发明的技术方案可以通过软件产品的形式体现。所述软件产品可以存储在非易失性或非瞬时性存储介质中，所述非易失性或非瞬时性存储介质可以是光盘只读存储器(compact disk read-only memory，CD-ROM)、USB闪存盘或可移动硬盘。所述软件产品包括多个指令，所述多个指令使得计算机设备(个人计算机、服务器或网络设备)能够执行本发明实施例中提供的方法。例如，此类执行可以对应于本文中描述的逻辑操作的模拟。所述软件产品可以附加地或可选地包括多个指令，所述多个指令使得计算机设备能够执行用于配置或编程根据本发明实施例所述的数字逻辑装置的操作。

尽管已经参考本发明的特定特征和实施例描述了本发明，但是明显可以在不脱离本发明的情况下制定本发明的各种修改和组合。因此，说明书和附图仅被视为所附权利要求书限定的对本发明的说明，并且预期覆盖在本发明的范围内的任何和所有修改、变化、组合或等同物。

Claims (20)

1.一种用于在分布式计算系统中进行资源管理和调度的方法，其特征在于，所述方法包括：

使用一个或多个资源张量表示所述分布式计算系统中资源的可用性或资源的使用量；

接收一个或多个资源请求，每个资源请求指定所述分布式计算系统中满足工作请求所需的资源；

将所述资源请求表示为一个或多个请求张量；

根据所述一个或多个资源张量和所述一个或多个请求张量，调度所述分布式计算系统中的资源。

2.根据权利要求1所述的方法，其特征在于，还包括：

使用一个或多个容量张量表示所述分布式计算系统中的所述资源的总量；

其中，进一步根据所述一个或多个容量张量，调度所述分布式计算系统中的资源。

3.根据权利要求2所述的方法，其特征在于，调度还至少部分包括对所述一个或多个资源张量、所述一个或多个请求张量或所述一个或多个容量张量进行的使用矢量化张量广播操作的操作。

4.根据权利要求1至3中任一项所述的方法，其特征在于，还包括：

在调度期间，基于所述一个或多个请求张量中的值，更新所述一个或多个资源张量以响应于条件，其中所述条件是以下各项中的一个：

对一个或多个可用资源的子集提出所述工作请求；

完成需要所述一个或多个资源的所述工作请求；或

释放所述工作请求所请求的所述一个或多个资源。

5.根据权利要求1至4中任一项所述的方法，其特征在于，还包括：确定所述一个或多个资源张量的子集，所述一个或多个资源张量的所述子集具有用于所述工作请求的足够容量。

6.根据权利要求1至5中任一项所述的方法，其特征在于，还包括：确定与所述请求的资源最佳匹配的所述一个或多个资源张量的子集，其中，在对所述请求的资源提出所述工作请求时，至少基于计算所述一个或多个资源张量的每个子集的适合程度得分，确定所述最佳匹配。

7.根据权利要求6所述的方法，其特征在于，基于在对所述资源提出所述请求之后的总资源使用量与所述资源的总容量之间的相似性，确定所述一个或多个资源张量的所述子集中的每个子集的所述适合程度得分。

8.根据权利要求6至7中任一项所述的方法，其特征在于，所述适合程度得分是预先确定的。

9.根据权利要求1至8中任一项所述的方法，其特征在于，还包括：确定可以对所述请求的资源的子集提出工作请求的总次数。

10.根据权利要求1至9中任一项所述的方法，其特征在于，调度还包括：

解决对所述一个或多个资源张量的子集提出所述工作请求时产生的冲突。

11.根据权利要求1至10中任一项所述的方法，其特征在于，所述资源具有层级关系，其中，处于所述层级关系的第二层级的资源包含处于所述层级关系的第一层级的资源，所述一个或多个资源张量中的维度顺序表示所述层级关系，使得一个维度中的资源包含后续维度中的资源。

12.根据权利要求1至11中任一项所述的方法，其特征在于，所述一个或多个资源张量的维度中的资源表示定义时间维度的不同时间步长的值。

13.根据权利要求12所述的方法，其特征在于，所述时间维度的所述时间步长存储在循环缓冲器中。

14.根据权利要求1至13中任一项所述的方法，其特征在于，所述一个或多个资源张量包括以下各项中的一个或多个：用于过去资源使用量的一个或多个资源张量以及用于未来资源使用量的一个或多个资源张量。

15.一种用于在分布式计算系统中进行资源管理和调度的装置，其特征在于，所述装置包括：

处理器；

存储机器可执行指令的存储器，所述指令在由所述处理器执行时，将所述装置配置为：

使用一个或多个资源张量表示所述分布式计算系统中资源的可用性或资源的使用量；

接收一个或多个资源请求，每个资源请求指定所述分布式计算系统中满足工作请求所需的资源；

将所述资源请求表示为一个或多个请求张量；

根据所述一个或多个资源张量和所述一个或多个请求张量，调度所述分布式计算系统中的资源。

16.根据权利要求15所述的装置，其特征在于，所述指令在由所述处理器执行时，还将所述装置配置为：

使用一个或多个容量张量表示所述分布式计算系统中的所述资源的总量；

使用所述一个或多个资源张量、所述一个或多个请求张量和所述一个或多个容量张量进行调度。

17.根据权利要求15至16中任一项所述的装置，其特征在于，所述指令在由所述处理器执行时，还将所述装置配置为：

在调度期间，基于所述一个或多个请求张量中的值，更新所述一个或多个资源张量以响应于条件，其中所述条件是以下各项中的一个：

对一个或多个可用资源的子集提出所述工作请求；

完成需要所述一个或多个资源的所述工作请求；或

释放所述工作请求所请求的所述一个或多个资源。

18.根据权利要求15至17中任一项所述的装置，其特征在于，所述指令在由所述处理器执行时，还将所述装置配置为：确定与所述请求的资源最佳匹配的所述一个或多个资源张量的子集，其中，在对所述请求的资源提出所述工作请求时，至少基于计算所述一个或多个资源张量的每个子集的适合程度得分，确定所述最佳匹配。

19.根据权利要求18所述的装置，其特征在于，基于在对所述资源提出所述请求之后的总资源使用量与所述资源的总容量之间的相似性，确定所述一个或多个资源张量的所述子集中的每个子集的所述适合程度得分。

20.一种用于在分布式计算系统中进行资源管理和调度的网络节点，其特征在于，所述网络节点包括：

网络接口，用于从连接至分布式计算网络的组件接收数据并向所述组件传输数据；

处理器；

非瞬时性存储器，用于存储指令，所述指令在由所述处理器执行时，使得所述网络功能被配置为：

使用一个或多个资源张量表示所述分布式计算系统中资源的可用性或资源的使用量；

接收一个或多个资源请求，每个资源请求指定所述分布式计算系统中满足工作请求所需的资源；

将所述资源请求表示为一个或多个请求张量；

根据所述一个或多个资源张量和所述一个或多个请求张量，调度所述分布式计算系统中的资源。

Images