Systems and methods for efficiently implementing functional commands in a data processing system

• US 9,639,407 B1
• Filed: 06/16/2015
• Issued: 05/02/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): PATEL, HIREN P
• Application Number:
  US14/741,028
• Time in Patent Office: 686 Days
• Field of Search: None
• 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 perform efficiently a first processing task in conjunction with a plurality of data sets. A first code sequence comprises a plurality of general commands, and a specific command including a description of a first data processing task to be performed in conjunction with the data sets. The general commands are received and processed in a standard manner. The specific command is identified automatically by its nature, and the description within the specific command is then converted into a first sequence of executable instructions executable by a plurality of compute elements holding the plurality of data sets. The ultimate result is an efficient implementation of the first processing task. In some embodiments, the implementation of the first processing task is assisted by a pre-defined procedure that allocates the data sets to the compute elements and shares instances of executable instructions with the compute elements.

Claims

1. A system configured to perform efficiently a first processing task in conjunction with each of a plurality of data sets, comprising:

a first code sequence comprising (i) a plurality of commands, and (ii) a specific command comprising a description of a first processing task, in which said description is expressed in a form of a lambda expression or a mathematical expression, and in which the first processing task is to be performed in conjunction with each of a plurality of data sets;

a first compute element in a form of a first core of a central processing unit (CPU), having access to the code sequence and configured to;

(i) identify automatically, by inspecting the specific command within the first code sequence, that the first processing task is to be performed in conjunction with each of said plurality of data sets, and (ii) according to said identification, convert, specifically, said description, into a first sequence of executable instructions constituting an efficient implementation of said first processing task, in which only the description of the first processing task is used as an input in said conversion and such that the specific command itself does not play a role in the conversion; and

a second compute element in a form of a second core of the CPU or in a form of a core of another CPU, having access to at least the plurality of commands, and configured to;

follow the plurality of commands, until the specific command is reached; and

then

initiate a plurality of processing events, in which each of the processing events comprises executing an instance of the first sequence of executable instructions in conjunction with one of the data sets, thereby resulting in performing efficiently the first processing task in conjunction with each of the plurality of data sets.

2. The system of claim 1, further comprising a plurality of compute elements in a form of a plurality of CPU cores, wherein the plurality of processing events occur respectively in said plurality of compute elements.

3. The system of claim 2, wherein the instances of the first sequence of executable instructions are available to the plurality of compute elements through said system sending said instances to said plurality of compute elements, or through said plurality of compute elements obtaining said instances from the system.

4. The system of claim 2, wherein the plurality of data sets is available respectively to the plurality of compute elements through the plurality of compute elements respectively being pointed to the plurality of data sets by the system.

5. The system of claim 2, wherein said initiation is done by the second compute element sending a plurality of initiation requests respectively to the plurality of compute elements.

6. The system of claim 5, wherein said plurality of initiation requests also convey to the plurality of compute elements respectively the plurality of data sets.

7. The system of claim 5, wherein said plurality of initiation requests also convey to the plurality of compute elements respectively a plurality of instances of the first sequence of executable instructions.

8. The system of claim 5, wherein the sending of said plurality of initiation requests is directed by a procedure of the system, in which said procedure is associated with managing and communicating data across the system, and such that each of said plurality of compute elements and the second compute element is operative to execute at least a portion of said procedure relevant to that compute element.

9. The system of claim 8, wherein execution of the procedure together with execution of the instances of said first sequence of executable instructions implement the specific command.

10. The system of claim 2, wherein the plurality of compute elements together with the second compute element constitute at least a part of a distributed processing system.

11. The system of claim 1, wherein the plurality of processing events occur in the second compute element.

12. The system of claim 1, wherein the first compute element and the second compute element are a same compute element.

13. The system of claim 1, wherein said following the plurality of commands is started after the conversion of said description.

14. The system of claim 1, wherein the conversion of said description is done after said following of at least some of said plurality of commands, but before said initiation of the plurality of processing events.

15. The system of claim 14, wherein the conversion of said description is performed just-in-time for said initiation of the plurality of processing events.

16. The system of claim 1, wherein said following the plurality of commands is an interpretation process associated with said plurality of commands.

17. The system of claim 16, wherein the initiation of said plurality of processing events is performed instead of the second compute element interpreting said specific command, thereby further facilitating said performing efficiently of the first processing task in conjunction with each of the plurality of data sets.

18. The system of claim 1, wherein the code sequence is a source code written in a high level language, the description of said first processing task is written using the high level language, and the conversion of said description is a compilation process.

19. A method for performing efficiently and distributively a first processing task in conjunction with each of a plurality of data sets, comprising:

receiving, in a distributed processing system comprising a plurality of compute elements and an additional compute element, a first code sequence comprising (i) a plurality of commands and (ii) a specific command comprising a description of a first processing task, in which said description is expressed in a form of a lambda expression or a mathematical expression, and in which the first processing task is to be performed in conjunction with each of a plurality of data sets stored in said distributed processing system;

obtaining a first sequence of executable instructions converted from said description of the first processing task, in which only the description of the first processing task is used as an input in said conversion and such that the specific command itself does not play a role in the conversion, and in which said first sequence of executable instructions is operative to be effectively executed by each of the plurality of compute elements thereby implementing effectively the first processing task;

following, by the additional compute element, the plurality of commands, until the specific command is reached;

initiating, by the additional compute element, a procedure associated with the distributed processing system, in which said procedure is operative to (i) allocate the plurality of data sets to the plurality of compute elements, and (ii) share instances of the first sequence of executable instructions with the plurality of compute elements; and

activating, by each of the plurality of compute elements, the respective instance of the first sequence of executable instructions in conjunction with the data set allocated to the compute element, thereby performing efficiently and distributively the first processing task in conjunction with each of the plurality of data sets.

20. The method of claim 19, further comprising:

identifying, by inspecting the specific command within the first code sequence, that the first processing task, as described in the specific command, is to be performed in conjunction with each of the plurality of data sets,

wherein said obtaining of the first sequence of executable instructions is done as a result of said identification.

21. The method of claim 20, wherein said obtaining of the first sequence of executable instructions comprises performing the conversion of said description, in which said conversion is done by the distributed processing system.

22. The method of claim 21, wherein the code sequence is a source code written in a high level language, the description of said first processing task is written using the high level language as part of the source code, and the conversion of said description is a compilation process.

23. The method of claim 22, wherein said following the plurality of commands is an interpretation process associated with said plurality of commands.

24. The method of claim 19, wherein the specific command is a single instruction to be performed on multiple data (SIMD), in which said single instruction is associated with the first processing task and the multiple data is associated with the plurality of data sets.

25. The method of claim 19, wherein the specific command is a map function associated with the lambda expression and an array of data, in which the array of data is the plurality of data sets.