Method and apparatus for vectorized resource scheduling in distributed computing systems using tensors

Patent metadata

Field	Value
Publication number	US-11907770-B2
Application number	US-201916575763-A
Country	US
Kind code	B2
Filing date	Sep 19, 2019
Priority date	Sep 19, 2019
Publication date	Feb 20, 2024
Grant date	Feb 20, 2024

Abstract

There is provided a method and apparatus for vectorized resource scheduling using multi-dimensional hierarchical arrays with a uniform data type. According to embodiments, the hierarchy of resources may be represented as a multi-dimensional array of a uniform data type in a scheduling context. This data structure is known as a tensor. In various embodiments, a tensor may be used to model each of resource usage, requested resources, resource capabilities, tenant resource usage, etc. There is provided tensor scheduling operations (e.g. tensor scheduling algorithms) to make use of this resource model. Some embodiments may exploit specialized hardware, such as GPUs and tensor-processing units, in order to accelerate the tensor scheduling operations.

First claim

We claim:

1. A method for managing and scheduling one or more resources in a distributed computing system, the method comprising:
representing availability of the resources or usage of the resources in the distributed computing system using one or more resource tensors, each resource tensor comprising a multi-dimensional resource array having a uniform data type, wherein at a lowest dimension of the multi-dimensional resource array, the multi-dimensional resource array contains information indicative of an amount of available resources or an amount of used resources;
receiving one or more requests for the resources, each request for the resources specifying the resources in the distributed computing system required to satisfy a work request of the one or more requests;
representing the requests for resources as one or more request tensors, each request tensor comprising a multi-dimensional request array having a uniform data type, wherein at a lowest dimension of the multi-dimensional request array, the multi-dimensional request array contains information indicative of an amount of requested resources;
scheduling the resources in the distributed computing system in accordance with the one or more resource tensors and the one or more request tensors, wherein scheduling includes placing the work request on a subset of one or more resources that are available; and
completing the work request using the subset of one or more resources that are available;
wherein the resources have a hierarchical relationship, wherein the resources at a second level of the hierarchical relationship contain resources at a first level of the hierarchical relationship, and an order of dimensions in the one or more resource tensors represents the hierarchical relationship, such that the resources in one dimension contain the resources in a subsequent dimension.

2. The method of claim 1 further comprising:
representing a total amount of the resources in the distributed computing system using one or more capacity tensors; and
wherein scheduling resources in the distributed computing system is further in accordance with the one or more capacity tensors.

3. The method of claim 2 , wherein scheduling further comprises at least in part operations using a vectorized tensor broadcasting operation on the one or more resource tensors, the one or more request tensors, or the one or more capacity tensors.

4. The method of claim 1 further comprising,
during scheduling, updating the one or more resource tensors based on values in the one or more request tensors in response to a condition, wherein the condition is one of:
placement of the work request on the subset of one or more resources that are available,
completion of the work request using the subset of one or more resources that are available, or
release of the one or more resources requested by the work request.

5. The method of claim 1 further comprising determining a subset of the one or more resource tensors that has sufficient capacity for the work request.

6. The method of claim 1 , further comprising determining a subset of the one or more resource tensors that is a best fit for requested resources, wherein the best fit is determined based at least on calculating an extent of suitableness score for each subset of the one or more resource tensors when placing the work request on the requested resources.

7. The method of claim 6 , wherein the extent of suitableness score for each of the subset of the one or more resource tensors is determined based on similarity between total resource usage upon placement of the request thereon and total capacity of the resources.

8. The method of claim 6 , wherein the extent of suitableness score is predetermined.

9. The method of claim 1 , further comprising determining a total number of times that the work request can be placed on the subset of resources that are available or another subset of resources that are available.

10. The method of claim 1 , wherein scheduling further comprises:
resolving conflicts arising when placing the work request on the subset of the one or more resources that are available.

11. The method of claim 1 , wherein the resources at a dimension of the one or more resource tensors represent values at different timesteps defining a time dimension.

12. The method of claim 11 , wherein the timesteps of the time dimension are stored in a circular buffer.

13. The method of claim 1 , wherein the one or more resource tensors include one or more of: one or more resource tensors for past resource usage and one or more resource tensors for future resource usage.

14. An apparatus for managing and scheduling one or more resources in a distributed computing system, the apparatus comprising;
a processor; and
a memory storing machine executable instructions, the instructions when executed by the processor configure the apparatus to:
represent availability of the resources or usage of the resources in the distributed computing system using one or more resource tensors, each resource tensor comprising a multi-dimensional resource array having a uniform data type, wherein at a lowest dimension of the multi-dimensional resource array, the multi-dimensional resource array contains information indicative of an amount of available resources or an amount of used resources;
receive one or more requests for the resources, each request for the resources specifying the resources in the distributed computing system required to satisfy a work request of the one or more requests;
represent the requests for the resources as one or more request tensors, each request tensor comprising a multi-dimensional request array having a uniform data type, wherein at a lowest dimension of the multi-dimensional request array, the multi-dimensional request array contains information indicative of an amount of requested resources;
schedule the resources in the distributed computing system in accordance with the one or more resource tensors and the one or more request tensors, wherein scheduling includes placing the work request on a subset of one or more resources that are available; and
complete the work request using the subset of one or more resources that are available;

wherein the resources have a hierarchical relationship, wherein the resources at a second level of the hierarchical relationship contain resources at a first level of the hierarchical relationship, and an order of dimensions in the one or more resource tensors represents the hierarchical relationship, such that the resources in one dimension contain the resources in a subsequent dimension.

15. The apparatus of claim 14 , wherein the instructions when executed by the processor further configure the apparatus to:
represent a total amount of the resources in the distributed computing system using one or more capacity tensors, and
schedule using the one or more resource tensors, the one or more request tensors, and the one or more capacity tensors.

16. The apparatus of claim 14 , wherein the instructions when executed by the processor further configure the apparatus to:
during scheduling, update the one or more resource tensors based on values in the one or more request tensors in response to a condition, wherein the condition is one of:
placement of the work request on the subset of one or more resources that are available,
completion of the work request using the subset of one or more resources that are available, or
release of the one or more resources requested by the work request.

17. The apparatus of claim 14 , wherein the instructio

Assignees

• Hauwei Cloud Computing Tech Co Ltd
• Huawei Cloud Computing Tech Co Ltd

Inventors

• Bergsma Shane Anthony
• ZEYL Timothy James
• Guo Lei
• Ke Xiaodi

Classifications

• G06F9/5083 Primary

  Techniques for rebalancing the load in a distributed system · CPC title

• G06F9/4881

  Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues · CPC title

• G06F9/5027 Primary

  the resource being a machine, e.g. CPUs, Servers, Terminals · CPC title

• G06F9/5044

  considering hardware capabilities · CPC title

• G06F2209/501

  Performance criteria · CPC title