Systems and methods to distributively process a plurality of data sets stored on a plurality of memory modules

• US 9,720,826 B1
• Filed: 02/27/2015
• Issued: 08/01/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): Rojas, Midys
• Assistant Examiner(s): DOAN, KHOA D
• Application Number:
  US14/633,196
• Time in Patent Office: 886 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 embodiments of systems and methods to allow and control simultaneous access and processing by multiple compute elements of multiple data sets stored in multiple memory modules. The compute elements request data to be processed without specifying any particular data sets to be received. Data interfaces receive the data requests from the compute elements, determine which data sets have not yet been served to the compute elements, select data sets to be served from among those that have not yet been served, and fetch these data sets from the memory modules. The process of requesting additional data by the compute elements, selection by the data interfaces of data sets to be served among those that have not yet been served, and providing such data sets by the data interfaces to the compute elements, may continue until all of the data sets have been served to the compute elements.

Claims

1. A system operative to distributively process a plurality of data sets stored on a plurality of memory modules, comprising:

a plurality of compute elements;

a shared memory pool comprising a plurality of memory modules configured to distributively store a plurality of data sets;

a plurality of data interfaces associated respectively with said plurality of memory modules, each of said data interfaces is configured to;

receive data requests from any one of the plurality of compute elements;

identify from the data sets of the respective memory modules which stored data sets were not served;

serve, as reply to the data requests, the data sets identified; and

keep track of the stored data sets already served;

wherein each of the plurality of compute elements is configured to;

send some of said data requests to at least some of the plurality of data interfaces;

receive some of said replies comprising some of said data sets; and

process said data sets received, wherein said sending, receiving, and processing is done until entire of the plurality of data sets is served and processed.

2. The system of claim 1, wherein said data requests do not specify certain ones of the plurality of data sets to be served, such that said identification and keeping track is the only way by which said plurality of data interfaces know which one of said plurality of data sets is to be specifically served to the one of said plurality of compute elements making the data request, and such that said identification and keeping track is the only way of making sure, by the system, that none of the data sets is served more than once.

3. The system of claim 2, wherein:

said plurality of compute elements comprises a first compute element and a second compute element;

said plurality of data interfaces comprises a first data interface comprising a first internal registry that is configured to facilitate said identification and keeping track; and

said plurality of memory modules comprises a first memory module associated with said first data interface and configured to store a first data set and a second data set,

such that;

the first compute element is configured to send a first of said data requests to the first data interface, and the first data interface is configured to;

conclude, according to the first internal registry, that the first data set is next for processing from the ones of the data sets stored in the first memory module, extract the first data set from the first memory module, serve the first data set extracted to the first compute element, and update the first internal registry to reflect said serving of the first data set; and

the second compute element is configured to send a second of said data requests to the first data interface, and the first data interface is configured to;

conclude, according to the first internal registry, that the second data set is next for processing from the ones of the data sets stored in the first memory module, extract the second data set from the first memory module, serve the second data set extracted to the second compute element, and update the first internal registry to reflect said serving of the second data set.

4. The system of claim 3, wherein:

said plurality of data interfaces comprises a second data interface comprising a second internal registry that is configured to facilitate said identification and keeping track; and

said plurality of memory modules comprises a second memory module associated with said second data interface and configured to store a third data set and a fourth data set,

such that;

the first compute element is configured to send a third of said data requests to the second data interface, and the second data interface is configured to;

conclude, according to the second internal registry, that the third data set is next for processing from the ones of the data sets stored in the second memory module, extract the third data set from the second memory module, serve the third data set extracted to the first compute element, and update the second internal registry to reflect said serving of the third data set; and

the second compute element is configured to send a fourth of said data requests to the second data interface, and the second data interface is configured to;

conclude, according to the second internal registry, that the fourth data set is next for processing from the ones of the data sets stored in the second memory module, extract the fourth data set from the second memory module, serve the fourth data set extracted to the second compute element, and update the second internal registry to reflect said serving of the fourth data set.

5. The system of claim 1, wherein said plurality of compute elements are configured to execute distributively a first task associated with said plurality of data sets by performing said processing of said data sets received.

6. The system of claim 5, wherein said execution of said first task can be done in any order of said processing of said plurality of data sets, such that any one of said plurality of data sets can be processed before or after any other of said plurality of data sets.

7. The system of claim 6, wherein said plurality of data sets constitute a first data corpus, and said first task is selected from a group consisting of:

(i) counting number of occurrences of specific items in said first data corpus, (ii) determining size of said data corpus, (iii) calculating a mathematical property for each of said data sets, and (iv) running a mathematical filtering process on each of said data sets.

8. The system of claim 1, wherein each of the compute elements is configured, per each said sending of one of said data requests made by such compute element, to select one of said plurality of data interfaces as a target of receiving such data request, and wherein said selection is done using a first technique.

9. The system of claim 8, wherein said first technique is round robin selection.

10. The system of claim 8, wherein said first technique is pseudo-random selection.

11. The system of claim 8, wherein said selection is unrelated and independent of said identification and keeping track.

12. The system of claim 1, wherein said keeping track of the ones of the data sets already served facilitates a result in which none of the data sets is served more than once.

13. A method for storing and sending data sets in conjunction with a plurality of memory modules, comprising:

starting from an initial state, in which a plurality of data sets belonging to a first data corpus are stored among a plurality of memory modules associated respectively with a plurality of data interfaces, wherein each of said plurality of data sets is stored only once in only one of said plurality of memory modules;

keeping a record of, by each of the data interfaces, which of said plurality data sets that are stored in a respective memory module and were served by the data interface to any one of a plurality of compute elements;

and serving to the requesting compute element, by each data interface, as a response to any one of said data requests made to the data interface, one of said data sets that is stored in the respective memory module and which is selected by the data interface based on said record kept by the data interface for sending to the compute element, wherein the data set that is selected and served is guaranteed to not have been sent to any of said compute elements by the data interface since said start from said initial state,

wherein the keeping record, receiving request and serving request are continue until all of said data sets being served distributively to the plurality of compute elements, and plurality of compute elements distributively process said first data corpus.

14. The method of claim 13, wherein said plurality of data sets is a plurality of values associated respectively with a plurality of keys, and wherein said data requests are requests for said values associated with said keys.

15. The method of claim 14, wherein the plurality of compute elements do not need to track which values were already served as a result of said record kept by each of said data interfaces, and therefore the requests do not need to specify said keys and do not need to specify said values.