Systems and methods to achieve load balancing among a plurality of compute elements accessing a shared memory pool

• US 9,733,988 B1
• Filed: 02/27/2015
• Issued: 08/15/2017
• Est. Priority Date: 12/09/2014
• Status: Active Grant

• Current Assignee: DataRobot, Inc.
• Original Assignee: Parallel Machines Ltd.
• Inventors: Braverman, Avner, Adda, Michael, Khermosh, Lior, Zuckerman, Gal
• Primary Examiner(s): Cao, Diem
• Application Number:
  US14/633,210
• Time in Patent Office: 900 Days
• Field of Search: None
• CPC Class Codes: G06F 12/0623 for memory modules
• CPC Class Codes: G06F 12/0813 with a network or matrix configuration
• CPC Class Codes: G06F 12/084 with a shared cache
• CPC Class Codes: G06F 12/1081 for peripheral access to main memory, e.g. direct memory access [DMA]
• CPC Class Codes: G06F 13/28 using burst mode transfer, e.g. direct memory access DMA, cycle steal G06F13/32 takes precedence
• CPC Class Codes: G06F 13/4022 using switching circuits, e.g. switching matrix, connection or expansion network G06F13/4009 takes precedence
• CPC Class Codes: G06F 2212/1016 Performance improvement
• CPC Class Codes: G06F 2212/154 Networked environment
• CPC Class Codes: G06F 2212/2532 comprising a plurality of modules
• CPC Class Codes: G06F 2212/452 Instruction code
• CPC Class Codes: G06F 2212/621 Coherency control relating to peripheral accessing, e.g. from DMA or I/O device
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching

Abstract

Various systems and methods to achieve load balancing among a plurality of compute elements accessing a shared memory pool. The shared memory pool is configured to store and serve a plurality of data sets associated with a task, a first data interface'"'"'s internal registry is configured to keep track of which data sets have been extracted from the shared memory pool and served to the compute elements, the first data interface is configured to extract from the shared memory pool and serve to the compute elements data sets which have not yet been extracted and served, the rate at which data sets are extracted and served to each particular compute element is proportional to the rate at which that compute element requests data sets, and the system may continues to extract, serve, and process data sets until all of the data sets associated with the task have been processed once.

Claims

1. A system operative to achieve load balancing among a plurality of compute elements accessing a shared memory pool, comprising:

a shared memory pool configured to store a plurality of data sets comprising a first data set and a second data set;

a first data interface configured to extract and serve any of said plurality of data sets from said shared memory pool, and comprising an internal registry configured to keep track of the data sets extracted and served; and

a plurality of compute elements comprising at least a first compute element and a second compute element, in which said plurality of compute elements are communicatively connected with said first data interface, and said plurality of compute elements are configured to execute distributively a first task associated with said plurality of data sets;

wherein;

the first compute element is configured to send a first data request to the first data interface after deciding that said first compute element is currently available or will soon become available to start or to continue contributing to said execution, and the first data interface is configured to;

conclude, according to the internal registry, that the first data set is next for processing;

extract the first data set from the shared memory pool;

serve the first data set extracted to the first compute element, thereby enabling said first compute element to perform said contribution; and

update the internal registry to reflect said serving of the first data set; and

the second compute element is configured to send a second data request to the first data interface after deciding that said second compute element is currently available or will soon become available to start or to continue contributing to said execution, and the first data interface is configured to;

conclude, according to the internal registry reflecting that the first data set has already been served, that the second data set is next for processing;

extract the second data set from the shared memory pool;

serve the second data set extracted to the second compute element, thereby enabling said second compute element to perform said contribution; and

update the internal registry to reflect said serving of the second data set,

such that said decisions regarding said availabilities facilitate said load balancing in conjunction with said executing distributively of said first task, without the plurality of compute elements being aware of the order in which said plurality of data sets are extracted and served.

2. The system of claim 1, wherein:

said plurality of data sets further comprises a third data set; and

the first compute element is further configured to send a next data request to the first data interface after deciding that said first compute element is currently available or will soon become available to continue contributing to said execution, and the first data interface is configured to;

conclude, according to the internal registry, that the third data set is next for processing;

extract the third data set from the shared memory pool;

serve the third data set extracted to the first compute element for performing said contribution; and

update the internal registry to reflect said serving of the third data set.

3. The system of claim 2, wherein said next data request is sent only after said first compute element finishes said processing of the first data set, thereby further facilitating said load balancing.

4. The system of claim 2, wherein said first data request and next data request are sent by said first compute element at a rate that corresponds to a rate at which said first compute element is capable of processing said first data set and third data set, thereby further facilitating said load balancing.

5. The system of claim 1, wherein said concluding and updating guarantee that no data set is served more than once in conjunction with said first task.

6. The system of claim 1, wherein said conclusion by said first data interface regarding said second data set is made after said second data request has been sent, and as a consequence of said second data request being sent.

7. The system of claim 1, wherein said conclusion by said first data interface regarding said second data set is made as a result of said first data set being served, and before said second data request has been sent, such that by the time said second data request has been sent, said conclusion by said first data interface regarding said second data set has already been made.

8. The system of claim 1, wherein said extraction of the second data set from the shared memory pool is done after said second data request has been sent, and as a consequence of said second data request being sent.

9. The system of claim 1, wherein said extraction of the second data set from the shared memory pool is done as a result of said first data set being served, and before said second data request has been sent, such that by the time said second data request has been sent, said second data set is already present in said first data interface and ready to be served.

10. A method for load balancing a plurality of compute elements accessing a shared memory pool, comprising:

starting from an initial state, in which a plurality of data sets belonging to a first data corpus are stored in a shared memory pool associated with a first data interface, such that each of said plurality of data sets is stored only once;

keeping a record, by the first data interface, about which of said plurality of data sets are stored in the shared memory pool and which of said plurality of data sets have been served by the first data interface to any one of a plurality of compute elements;

receiving data requests, in the first data interface, from any one of the plurality of compute elements; and

serving, by the first data interface, as a response to each one of said data requests made to the first data interface, one of said data sets that is stored in the shared memory pool and that is selected for sending to the compute element making the data request based on said record kept by the first data interface, such that the one data set selected and served is guaranteed to not have been sent before by the data interface since said start from said initial state, and such that each of the plurality of compute elements is served at a rate that is proportional to a rate at which the compete element is making such data requests,

thereby eventually resulting in said data sets being served to the plurality of compute elements, while achieving said load balancing among the plurality of compute elements as a result of said proportionality.

11. The method of claim 10, wherein said initial state is associated with a first task to be performed by said plurality of compute elements in conjunction with said first data corpus, and said initial state is set among the first data interface and the plurality of compute elements in conjunction with said first task, thereby allowing said keeping record, receiving, and serving to commence.

12. The method of claim 11, wherein said keeping record, receiving, and serving allow the plurality of compute elements to distributively perform said first task, such that each of the plurality of compute elements performs a portion of the first task that is determined by the compute element itself according to said rate at which the compete element is making such data requests.

13. The method of claim 12, wherein said rate at which each compete element is making such data requests is determined by the compute element itself according to present load or availability or computational capability of the compute element.

14. The method of claim 13, wherein said data requests do not specify specific identities of said data sets, such that the specific identities of the data sets served are determined solely by the first data interface according to said record, thereby allowing the plurality of compute element to perform said first task asynchronously, thereby allowing said plurality of compute elements to achieve said load balancing efficiently.

15. The method of claim 11, wherein said receiving and said serving end when the first data corpus has been served to the plurality of compute elements.

17. The method of claim 11, further comprising:

performing a pre-processing activity associated with said first task, by the first data interface, on the plurality of data sets, after said extracting of the data sets, and prior to said serving of the data sets.

16. The method of 15, wherein said execution of said first task is achieved after said data corpus has been served to the plurality of compute elements, and after each of the compute elements processes the ones of the data sets served to that compute element.