Systems and methods for automatic generation of parallel data processing code

• US 9,594,696 B1
• Filed: 06/16/2015
• Issued: 03/14/2017
• Est. Priority Date: 12/09/2014
• Status: Active Grant

• Current Assignee: DataRobot, Inc.
• Original Assignee: Parallel Machines Ltd.
• Inventors: Braverman, Avner, Adda, Michael, Amar, Lior, Khermosh, Lior, Finer, Eli, Zuckerman, Gal
• Primary Examiner(s): Doan, Duc
• Application Number:
  US14/740,793
• Time in Patent Office: 637 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 11/3624 by performing operations on the source code, e.g. via a compiler
• CPC Class Codes: G06F 12/084 with a shared cache
• CPC Class Codes: G06F 12/0846 Cache with multiple tag or data arrays being simultaneously accessible
• CPC Class Codes: G06F 12/1081 for peripheral access to main memory, e.g. direct memory access [DMA]
• CPC Class Codes: G06F 13/1663 Access to shared memory
• CPC Class Codes: G06F 2212/154 Networked environment
• CPC Class Codes: G06F 2212/2532 comprising a plurality of modules
• CPC Class Codes: G06F 8/10 Requirements analysis; Specification techniques
• CPC Class Codes: G06F 8/451 Code distribution considering CPU load at run-time G06F9/505; load rebalancing G06F9/5083
• CPC Class Codes: G06F 9/461 Saving or restoring of program or task context
• CPC Class Codes: G06F 9/4843 by program, e.g. task dispatcher, supervisor, operating system
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/5016 the resource being the memory
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451
• CPC Class Codes: G06F 9/542 Event management; Broadcasting; Multicasting; Notifications
• CPC Class Codes: G06F 9/544 Buffers; Shared memory; Pipes

Abstract

Various systems and methods to generate automatically a procedure operative to distributively process a plurality of data sets stored on a plurality of memory modules. Under the instruction of the automatically generated procedure, compute elements request data sets relevant to a particular task, such data sets are fetched from memory modules by data interfaces which provide such data sets to the requesting compute elements, and the compute elements then process the received data sets until the task is completed. Relevant data sets are fetched and processed asynchronously, which means that the relevant data sets need not be fetched and processed in any particular order.

Claims

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

a first database configured to store a code sequence describing an action to be performed by a target system on each of a plurality of data sets stored in a shared memory pool comprising a plurality of memory modules associated respectively with a plurality of data interfaces all belonging to the target system, in which the action per each of the plurality of data sets comprises;

(i) fetching the data set from the shared memory pool in the target system, and (ii) processing said data set fetched; and

a first compute element outside the target system, having access to said first database, and configured to convert said code sequence into a sequence of executable instructions, in which said sequence of executable instructions, when executed simultaneously by each of a plurality of compute elements of the target system, results in a distributive fetching-and-processing procedure operative, per each of the plurality of compute elements, to;

send a plurality of data requests to at least some of the plurality of data interfaces, in which each of the data requests is sent to one of the plurality of data interfaces;

receive, as a response to each of the data requests, from the data interface receiving the data request, a reply comprising a specific one of the data sets stored in the memory module associated with the data interface; and

process said data sets received,

such that;

said sending, receiving, and processing, by each of the plurality of compute elements, are done asynchronously with any other of the sending, receiving, processing done by any other of the compute elements, until a first condition is met.

2. The system of claim 1, wherein said specific one of the data sets is selected by the data interface from the memory module such as to guarantee that said specific one of the data sets has not previously been sent in conjunction with previous replies made by the data interface.

3. The system of claim 2, wherein said sequence of executable instructions, when executed simultaneously by each of the plurality of data interfaces of the target system, facilitates said selections, said replies, and therefore said guarantee.

4. The system of claim 2, wherein each of said data interfaces is configured to:

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

identify from the data sets of the respective memory module the ones that were not served yet, thereby facilitating said guarantee;

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

keep track of the ones of the data sets already served, thereby further facilitating said guarantee.

5. The system of claim 4, wherein said data requests, according to said sequence of executable instructions, 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 target system, that none of the data sets is served more than once, thereby facilitating said guarantee.

6. The system of claim 4, wherein said sequence of executable instructions, when executed simultaneously by each of the plurality of data interfaces of the target system, facilitates said identification, said serving, and said keeping track.

7. The system of claim 1, wherein:

said first condition is a condition in which the plurality of data sets is served and processed in its entirety by the plurality of compute elements; and

said plurality of compute elements is configured to execute distributively a first task associated with said plurality of data sets by performing said processing of said data sets received, in which 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.

8. The system of claim 1, wherein each of the compute elements is configured, according to said sequence of executable instructions, 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, in which said selection is a round robin selection or a pseudo-random selection.

9. The system of claim 1, wherein:

said code sequence is written in a high-level programming language; and

said conversion is a compilation process.

10. A system configured to generate and execute a procedure operative to distributively process a plurality of data sets stored on a plurality of memory modules, comprising:

a target system comprising;

a shared memory pool comprising a plurality of memory modules associated respectively with a plurality of data interfaces; and

a plurality of compute elements;

a first database configured to store a code sequence describing an action to be performed by the target system on each of a plurality of data sets stored in the shared memory pool, in which the action per each of the plurality of data sets comprises;

(i) fetching the data set from the shared memory pool, and (ii) processing said data set fetched; and

a first compute element outside the target system, having access to said first database, and configured to convert said code sequence into a sequence of executable instructions, wherein the plurality of compute elements is configured to execute simultaneously said sequence of executable instructions, resulting in a distributive fetching-and-processing procedure operative, per each of the plurality of compute elements, to;

send a plurality of data requests to at least some of the plurality of data interfaces, in which each of the data requests is sent to one of the plurality of data interfaces;

receive, as a response to each of the data requests, from the data interface receiving the data request, a reply comprising a specific one of the data sets stored in the memory module associated with the data interface; and

process said data sets received,

such that;

said sending, receiving, and processing, by each of the plurality of compute elements, are done asynchronously with any other of the sending, receiving, and processing done by any other of the compute elements until a first condition is met.

11. The system of claim 10, wherein:

said first condition is a condition in which the plurality of data sets is served and processed in its entirety by the plurality of compute elements; and

said plurality of compute elements is configured to execute distributively a first task associated with said plurality of data sets by performing said processing of said data sets received, in which 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.

12. The system of claim 10, wherein said specific one of the data sets is selected by the data interface from the memory module, such as to guarantee that said specific one of the data sets has not previously been sent in conjunction with previous replies made by the data interface.

13. The system of claim 12, wherein said sequence of executable instructions, when executed simultaneously by each of the plurality of data interfaces, facilitates said selections, said replies, and therefore said guarantee.

14. The system of claim 10, wherein said conversion is performed by the first compute element just before the plurality of compute elements starts executing simultaneously said sequence of executable instructions.

15. The system of claim 14, wherein said first compute element communicates the sequence of executable instructions to the plurality of compute elements just before the plurality of compute elements starts executing simultaneously said sequence of executable instructions.

16. The system of claim 10, wherein said first compute element is one of the plurality of compute elements.

17. A method for generating automatically a procedure operative to distributively process a plurality of data sets stored on a plurality of memory modules, comprising:

receiving, by a first compute element outside a target system, a code sequence describing an action to be performed by the target system on each of a plurality of data sets stored in a shared memory pool comprising a plurality of memory modules associated respectively with a plurality of data interfaces all belonging to the target system, in which the action per each of the plurality of data sets comprises;

(i) fetching the data set from the shared memory pool in the target system, and (ii) processing said data set fetched;

recognizing, by inspecting the code sequence in the first compute element, that (i) the plurality of data sets is stored across the plurality of memory modules associated respectively with the plurality of data interfaces, that (ii) any one of said plurality of data sets can be processed before or after any other of said plurality of data sets, and therefore that (iii) each fetch for one of the data sets can be done by any one of the plurality of compute elements in conjunction with the data interface associated with the memory module storing that data set, asynchronously with any other of the fetches done by any other of the plurality of compute elements in conjunction with any one of the data interfaces; and

converting, according to said recognition, said code sequence into a sequence of executable instructions, in which said sequence of executable instructions, when executed simultaneously by each of a plurality of compute elements of the target system, results in a distributive fetching-and-processing procedure operative, per each of the plurality of compute elements, to;

send, asynchronously with any other of the plurality of compute elements, a plurality of data requests to at least some of the plurality of data interfaces, in which each of the data requests is sent to one of the plurality of data interfaces;

receive, asynchronously with any other of the plurality of compute elements, as a response to each of the data requests, from the data interface receiving the data request, a reply comprising a specific one of the data sets stored in the memory module associated with the data interface; and

process, asynchronously with any other of the plurality of compute elements, said data sets received,

such that;

said sending, receiving, and processing are done, by each of the plurality of compute elements, until a first condition is met.

18. The method of claim 17, wherein said recognition is achieved by:

identifying, in the code sequence, a loop, in which each iteration of the loop describes said action to be performed on one of the plurality of data sets; and

identifying, in the code sequence, that said plurality of data sets are of a data type intended for storage across said plurality of memory modules.

19. The method of claim 18, wherein said recognition is further achieved by identifying, in the loop, that said processing of each of the plurality of data sets is unrelated to any other of the plurality of data sets.

20. The method of claim 17, wherein said recognition is achieved by:

identifying, in the code sequence, a single instruction to be performed on multiple data (SIMD), in which said single instruction is associated with said processing and said multiple data are associated with said plurality of data sets; and

identifying, in the code sequence, that said plurality of data sets are of a data type intended for storage across said plurality of memory modules.