METHOD AND APPARATUS FOR LOAD BALANCING OF JOBS SCHEDULED FOR PROCESSING

• US 20180336063A1
• Filed: 05/20/2017
• Published: 11/22/2018
• Est. Priority Date: 05/20/2017
• Status: Active Grant

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: Cavium, LLC (Marvell Technology Group Limited)
• Inventors: Nakada, Timothy Toshio, Zebchuk, Jason Daniel, Bouchard, Gregg Alan, Bhatt, Tejas Maheshbhai, Kim, Hong Jik, Shahid, Ahmed, Kwong, Mark Jon
• Granted Patent: US 10,713,089 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/5044 considering hardware capabilities
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system

Abstract

Method and system embodying the method for load balancing of scheduled jobs among a plurality of engines encompassing determining a number of cluster credits for each of a plurality of clusters that comprise at least one engine capable of processing a scheduled job; determining a number of engine credits for each of the plurality of engines comprising each of the at least one engine in accordance with a number of jobs assigned to each of the plurality of engines; evaluating the determined number of cluster credits and the determined number of engine credits in accordance with a credit evaluation policy; and assigning the job to one of the plurality of engines in accordance with the evaluation, is disclosed.

Claims

1. An apparatus for load balancing of scheduled jobs among multiple engines, comprising:

a job arbitrator and assignor, communicatively coupled to the multiple engines, configured to;

determine a number of cluster credits for each of a plurality of clusters that comprise at least one engine capable of processing a scheduled job;

determine a number of engine credits for each of the plurality of engines comprising each of the at least one engine in accordance with a number of jobs assigned to each of the plurality of engines;

evaluate the determined number of cluster credits and the determined number of engine credits in accordance with a credit evaluation policy; and

assign the job to one of the plurality of engines in accordance with the evaluation.

2. The apparatus as claimed in claim 1, wherein the job arbitrator and assignor determines a number of cluster credits for each of a plurality of clusters that comprise at least one engine capable of processing a scheduled job by being configured to:

determine for each designated cluster of the plurality of clusters the number of cluster credits equal to a set pre-determined value; and

determine for each non-designated cluster of the plurality of clusters the number of cluster credits in accordance with a number of jobs capable to be assigned to each of the at least one engine in the non-designated cluster.

3. The apparatus as claimed in claim 2, wherein the set pre-determined value comprises a value of zero.

4. The apparatus as claimed in claim 2, wherein the set pre-determined value comprises a value greater than a maximum number of credits of any of the non-designated cluster.

5. The apparatus as claimed in claim 1, wherein the the job arbitrator and assignor is further configured to:

determine whether one or more of each of the plurality of engines have a maximum number of engine credits; and

/or

determine whether one or more clusters of the plurality of clusters have a maximum number of cluster credits.

6. The apparatus as claimed in claim 5, wherein the job arbitrator and assignor evaluates the determined number of cluster credits and the determined number of engine credits in accordance with a credit evaluation policy and assigns the job to one of the at least one engines in accordance with the evaluation by being configured to:

assign the job to the one of the plurality of engines determined to have the maximum number of engine credits;

perform the determining whether one or more clusters of the plurality of clusters comprises a maximum number of cluster credits when more than one of the plurality of engines is determined to have the maximum number of engine credits;

assign the job to one of the at least one engine in the one cluster determined to have maximum cluster credits, wherein the one engine is determined in accordance with a pre-determined policy when the at least one engine comprises more than one engine; and

assign the job according to a pre-determined policy otherwise.

7. The apparatus as claimed in claim 5, wherein the job arbitrator and assignor evaluates the determined number of cluster credits and the determined number of engine credits in accordance with a credit evaluation policy and assigns the job to one of the at least one engines in accordance with the evaluation by being configured to:

perform the determining whether one or more clusters of the plurality of clusters have a maximum number of cluster credits; and

assign the job to one of the at least one engine from the determined one or more clusters with a maximum number of cluster credits in accordance with the evaluation by being configured to;

assign the job to the one of the at least one engine determined to have maximum number of engine credits; and

assign the job to one of the at least one engine determined in accordance with a pre-determined policy when more than one of the at least one engine is determined to have the maximum number of engine credits.

8. The apparatus as claimed in claim 1, wherein the plurality of clusters comprises:

at least one physical cluster and/or at least one virtual cluster and/or at least one implicit virtual cluster.

9. The apparatus as claimed in claim 6, wherein the pre-determined policy is selected from a group consisting of:

round-robin;

random selection;

least recently used engine;

most recently used engine

the lowest numbered engine;

the highest numbered engine; and

according to a configurable, complete, and fixed order between the engines.

10. The apparatus as claimed in claim 5, wherein the job arbitrator and assignor determines whether one or more entities of the plurality of entities have a maximum value of entity credits, by being configured to:

encode a value of entity credits less than or equal to a threshold as a one-hot vector and the value of the entity credits greater than the threshold as a vector by applying a bitwise OR operation to a one-hot vector encoded threshold and a binary encoded value;

perform the bitwise OR operation on all the encoded values; and

determine at least one of the plurality of entities, entity credits of which have a value of logical 1 at the highest bit position less than the bit position determined by the threshold,

wherein the entity comprises;

an engine for determining the maximum number of engine credits, and

a cluster for determining the maximum number of cluster credits.

11. The apparatus as claim in claim 10, therein the job arbitrator and assignor is further configured to:

determine the at least one of the plurality of entities, the entity credits of which have the value of logical 1 is at the bit position determined by the threshold according to the binary encoded values.

12. The apparatus as claimed in claim 10, wherein the job arbitrator and assignor encodes a value of entity credits for each of the plurality of entities comprises applying the equations:

for x==0;

mt(x)=0 

 

Eq. (1)

for x∈

(0,W];

mt(x)=1<

<

(x−

1) 

 

Eq. (2)

for x∈

(W,N];

mt(x)=(1<

<

(W−

1))∨

(x−

W) 

 

Eq. (3)

wherein;

x is the value to be encoded;

mt is the encoding function;

W is the threshold of entity credit values;

<

<

is a bitwise left shift operator;

N is the highest value to be represented; and

∨

is a bitwise OR operator.

13. The apparatus as claimed in claim 1, wherein the job arbitrator and assignor is further configured to:

reserve the one engine for processing a sequence of jobs dependent upon the job assigned to the one engine, the sequence being enqueued in a single command queue;

assign jobs from the sequence of jobs to the reserved engine; and

release the reservation upon the reserved engine concluding processing of the last job of the sequence of jobs.

14. The apparatus as claimed in claim 1, wherein the job arbitrator and assignor is further configured to:

determine the at least one engine capable of processing the scheduled job in accordance with a content of one of a plurality of programmable vectors corresponding to a type of the job.

15. The apparatus as claimed in claim 14, further comprising:

a host, communicatively coupled to the job arbirator and assignor, executing a software configured to define the plurality of programmable vectors.

16. A method for load balancing of scheduled jobs among multiple engines, comprising:

determining a number of cluster credits for each of a plurality of clusters that comprise at least one engine capable of processing a scheduled job;

determining a number of engine credits for each of the plurality of engines comprising each of the at least one engine in accordance with a number of jobs assigned to each of the plurality of engines;

evaluating the determined number of cluster credits and the determined number of engine credits in accordance with a credit evaluation policy; and

assigning the job to one of the plurality of engines in accordance with the evaluation.

17. The method as claimed in claim 16, wherein the determining a number of cluster credits for each of a plurality of clusters that comprise at least one engine capable of processing a scheduled job comprises:

determining for each designated cluster of the plurality of clusters the number of cluster credits equal to a set pre-determined value; and

determining for each non-designated cluster of the plurality of clusters the number of cluster credits in accordance with a number of jobs capable to be assigned to each of the at least one engine in the non-designated cluster.

18. The method as claimed in claim 17, wherein the set pre-determined value comprises a value of zero.

19. The method as claimed in claim 17, wherein the set pre-determined value comprises a value greater than a maximum number of credits of any of the non-designated cluster.

20. The method as claimed in claim 16, further comprising:

determining whether one or more of each of the plurality of engines have a maximum number of engine credits; and

/or

determining whether one or more clusters of the plurality of clusters have a maximum number of cluster credits.

21. The method as claimed in claim 20, wherein the evaluating the determined number of cluster credits and the determined number of engine credits in accordance with a credit evaluation policy and the assigning the job to one of the at least one engines in accordance with the evaluation comprises:

assigning the job to the one of the plurality of engines determined to have the maximum number of engine credits;

performing the determining whether one or more clusters of the plurality of clusters comprises a maximum number of cluster credits when more than one of the plurality of engines is determined to have the maximum number of engine credits;

assigning the job to one of the at least one engine in the one cluster determined to have maximum cluster credits, wherein the one engine is determined in accordance with a pre-determined policy when the at least one engine comprises more than one engine; and

assigning the job according to a pre-determined policy otherwise.

22. The method as claimed in claim 20, wherein the evaluating the determined number of cluster credits and the determined number of engine credits in accordance with a credit evaluation policy and the assigning the job to one of the at least one engines in accordance with the evaluation comprises:

performing the determining whether one or more clusters of the plurality of clusters have a maximum number of cluster credits; and

assigning the job to one of the at least one engine from the determined one or more clusters with a maximum number of cluster credits in accordance with the evaluation comprises;

assigning the job to the one of the at least one engine determined to have maximum number of engine credits; and

assigning the job to one of the at least one engine determined in accordance with a pre-determined policy when more than one of the at least one engine is determined to have the maximum number of engine credits.

23. The method as claimed in claim 16, wherein the plurality of clusters comprises:

at least one physical cluster and/or at least one virtual cluster and/or at least one implicit virtual cluster.

24. The method as claimed in claim 21, wherein the pre-determined policy is selected from a group consisting of:

round-robin;

random selection;

least recently used engine;

most recently used engine

the lowest numbered engine;

the highest numbered engine; and

according to a configurable, complete, and fixed order between the engines.

25. The method as claimed in claim 20, wherein the determining whether one or more entities of the plurality of entities have a maximum value of entity credits, comprises:

encoding a value of entity credits less than or equal to a threshold as a one-hot vector and the value of the entity credits greater than the threshold as a vector by applying a bitwise OR operation to a one-hot vector encoded threshold and a binary encoded value;

performing the bitwise OR operation on all the encoded values; and

determining at least one of the plurality of entities, entity credits of which have a value of logical 1 at the highest bit position less than the bit position determined by the threshold,

wherein the entity comprises;

an engine for determining the maximum number of engine credits, and

a cluster for determining the maximum number of cluster credits.

26. The method as claim in claim 25, further comprising:

determining the at least one of the plurality of entities, the entity credits of which have the value of logical 1 is at the bit position determined by the threshold according to the binary encoded values.

27. The method as claimed in claim 25, wherein the encoding a value of entity credits for each of the plurality of entities comprises applying the equations:

for x==0;

mt(x)=0 

 

Eq.(1)

for x∈

(0,W];

mt(x)=1<

<

(x−

1) 

 

Eq.(2)

for x∈

(W,N];

mt(x)=(1<

<

(W−

1))∨

(x−

W) 

 

Eq. (3)

wherein;

x is the value to be encoded;

mt is the encoding function;

W is the threshold of entity credit values;

<

<

is a bitwise left shift operator;

N is the highest value to be represented; and

∨

is a bitwise OR operator.

28. The method as claimed in claim 16, further comprising:

reserving the one engine for processing a sequence of jobs dependent upon the job assigned to the one engine, the sequence being enqueued in a single command queue;

assigning jobs from the sequence of jobs to the reserved engine; and

releasing the reservation upon the reserved engine concluding processing of the last job of the sequence of jobs.

29. The method as claimed in claim 16, further comprising:

determining the at least one engine capable of processing the scheduled job in accordance with a content of one of a plurality of programmable vectors corresponding to a type of the job.

30. The method as claimed in claim 29, further comprising:

defining the plurality of programmable vectors by control software executed by a host.