Load Balancing Systems and Methods

• US 20180060138A1
• Filed: 11/28/2016
• Published: 03/01/2018
• Est. Priority Date: 08/24/2016
• Status: Active Grant

• Current Assignee: Improbable Worlds Ltd.
• Original Assignee: Improbable Worlds Ltd.
• Inventors: Whitehead, Robert James Frederick, Tang, Hanying, Lewis, Matthew John Reveley, Lipka, Peter Richard
• Granted Patent: US 10,303,821 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 30/20 Design optimisation, verification or simulation optimisation, verification or simulation of circuit designs G06F30/30
• CPC Class Codes: G06F 9/4856 resumption being on a different machine, e.g. task migration, virtual machine migration G06F9/5088 takes precedence
• CPC Class Codes: G06F 9/5061 Partitioning or combining of resources
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system
• CPC Class Codes: G06F 9/541 via adapters, e.g. between incompatible applications

Abstract

Methods, systems, computer-readable media, and apparatuses for performing, providing, managing, executing, and/or running a spatially-optimized simulation are presented. In one or more embodiments, the spatially-optimized simulation may comprise a plurality of worker modules performing the simulation, a plurality of entities being simulated among the plurality of worker modules, a plurality of bridge modules facilitating communication between workers and an administrative layer including a plurality of chunk modules, at least one receptionist module, and at least one oracle module. The spatially-optimized simulation may be configured to provide a distributed, persistent, fault-tolerate and spatially-optimized simulation environment. In some embodiments, load balancing and fault tolerance may be performed using transfer scores and/or tensile energies determined among the candidates for transferring simulation entities among workers. In some embodiments, the plurality of bridge modules may expose an application programming interface (API) for communicating with the plurality of worker modules.

Claims

1. A method for load-balancing a spatially-optimized simulation comprising:

determining, by a first computing module, a plurality of candidate computing modules for receiving a process to be transferred from the first computing module;

for each candidate computing module;

determining a load density center for that candidate computing module;

determining a distance between a load density center for the first computing module and the load density center for that candidate computing module; and

determining a transfer score for that candidate computing module;

determining a second computing module selected from the plurality of candidate computing modules based on a comparison of transfer scores for the plurality of candidate computing module; and

transferring the process from the first computing module to the second computing module.

2. The method of claim 1, wherein the determining the plurality of candidate computing modules comprises selecting a plurality of other computing modules which subscribe to notifications transmitted by the process to be transferred.

3. The method of claim 1, wherein the determining the one or more candidate computing modules comprises:

determining for each candidate computing module, a load metric indicative of a instantaneous processing load on that candidate computing module; and

eliminating at least one candidate computing module based on the determining of the load metric.

4. The method of claim 1, wherein the determining the load density center of the first computing module comprises:

determining a spatial center of mass of the first computing module based on a spatial position and processing load of a plurality of processes assigned to the first computing module.

5. The method of claim 1, wherein the determining the transfer score for each candidate computing module comprises:

determining a tensile energy of the candidate computing module based on the distance between the load density center for the first computing module and the load density center for the candidate computing module and a predetermined spring factor.

6. The method of claim 5, wherein a value of the predetermined spring factor changes based on a time factor.

7. The method of claim 5, wherein a value of the predetermined spring factor changes based on the distance between the load density center for the first computing module and the load density center for the candidate computing module.

8. The method of claim 5, wherein the determining the receiving computing module comprises selecting a candidate computing module to minimize a tensile energy between the first computing module and second computing module.

9. The method of claim 1, wherein transferring the process from the first computing module to the second computing module comprises:

transmitting, by the first computing module and to the second computing module, state information of the process;

causing, by the first computing module, the second computing module to receive state change notifications from the process; and

stopping, by the first computing module, the receipt of state change notifications from the process.

10. One or more non-transitory computer readable media comprising computer readable instructions that, when execute, configure a system to perform load-balancing a spatially-optimized simulation by:

determining, by a first computing module, a plurality of candidate computing modules for receiving a process to be transferred from the first computing module;

for each candidate computing module;

determining a load density center for that candidate computing module;

determining a distance between a load density center for the first computing module and the load density center for that candidate computing module; and

determining a transfer score for that candidate computing module;

determining a second computing module selected from the plurality of candidate computing modules based on a comparison of transfer scores for the plurality of candidate computing module; and

transferring the process from the first computing module to the second computing module.

11. The computer readable media of claim 10, wherein the determining the plurality of candidate computing modules comprises selecting a plurality of other computing modules which subscribe to notifications transmitted by the process to be transferred.

12. The computer readable media of claim 10, wherein the determining the one or more candidate computing modules comprises:

determining for each candidate computing module, a load metric indicative of a instantaneous processing load on that candidate computing module; and

eliminating at least one candidate computing module based on the determining of the load metric.

13. The computer readable media of claim 10, wherein the determining the load density center of the first computing module comprises:

determining a spatial center of mass of the first computing module based on a spatial position and processing load of a plurality of processes assigned to the first computing module.

14. The computer readable media of claim 10, wherein the determining the transfer score for each candidate computing module comprises:

determining a tensile energy of the candidate computing module based on the distance between the load density center for the first computing module and the load density center for the candidate computing module and a predetermined spring factor.

15. The computer readable media of claim 14, wherein a value of the predetermined spring factor changes based on a time factor.

16. The computer readable media of claim 14, wherein a value of the predetermined spring factor changes based on the distance between the load density center for the first computing module and the load density center for the candidate computing module.

17. The computer readable media of claim 14, wherein the determining the receiving computing module comprises selecting a candidate computing module to minimize a tensile energy between the first computing module and second computing module.

18. The computer readable media of claim 10, wherein transferring the process from the first computing module to the second computing module comprises:

transmitting, by the first computing module and to the second computing module, state information of the process;

causing, by the first computing module, the second computing module to receive state change notifications from the process; and

stopping, by the first computing module, the receipt of state change notifications from the process.

19. A method for load-balancing a spatially-optimized simulation comprising:

determining, by a first computing module, a plurality of candidate computing modules for receiving a process to be transferred from the first computing module;

for each candidate computing module;

determining a load density center for that candidate computing module;

determining a distance between a load density center for the first computing module and the load density center for that candidate computing module; and

determining a tensile energy for that candidate computing module based on the distance and a predetermined spring factor;

determining a second computing module selected from the plurality of candidate computing modules based on a comparison of tensile energies for the plurality of candidate computing module; and

transferring the process from the first computing module to the second computing module.

20. The method of claim 19, wherein a value of the predetermined spring factor changes based on the distance between the load density center for the first computing module and the load density center for the candidate computing module.