Systems and methods for executing actions using cached data

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

• Current Assignee: DataRobot, Inc.
• Original Assignee: Parallel Machines Ltd.
• Inventors: Adda, Michael, Braverman, Avner, Amar, Lior, Khermosh, Lior, Zuckerman, Gal
• Primary Examiner(s): Nguyen, Than
• Application Number:
  US14/806,861
• Time in Patent Office: 600 Days
• Field of Search: 711/113, 711/130, 711/119
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0811 with multilevel cache hierarchies
• 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/0862 with prefetch
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 12/0868 Data transfer between cache memory and other subsystems, e.g. storage devices or host systems
• CPC Class Codes: G06F 12/1081 for peripheral access to main memory, e.g. direct memory access [DMA]
• 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 16/244 Grouping and aggregation
• CPC Class Codes: G06F 2212/1024 Latency reduction
• CPC Class Codes: G06F 2212/2532 comprising a plurality of modules
• CPC Class Codes: G06F 2212/283 Plural cache memories
• CPC Class Codes: G06F 2212/6026 Prefetching based on access pattern detection, e.g. stride based prefetch
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

Described herein are systems and methods to execute efficiently a plurality of actions, in which multiple actions require the use of a single data set. The data set is fetched from a data source, across a switching network, to a memory associated with a first compute element. This is the only fetching of the data set from the data source, and the only fetching across a switching network, thereby minimizing fetching across the switching network, reducing the load on the switching network, decreasing the time by which the data set will be accessed in second and subsequent processes, and enhancing the efficiency of the system. In some embodiments, processes are migrated from second and subsequent compute elements to the compute element in which the data set is stored. In some embodiments, second and subsequent compute elements access the data set stored in the memory associated with the first compute element.

Claims

1. A system operative to execute efficiently a plurality of actions, comprising:

a first compute element;

a cache memory belonging to the first compute element; and

a first data set associated with a first data source;

wherein the system is configured to;

fetch the first data set from the first data source to the cache memory;

execute, in the first compute element, as directed by a first application program running on the first compute element, and in conjunction with the first data set now in the cache memory, a first action involving said first data set;

identify, within a second application program, a second action that, like the first action, involves the first data set; and

instruct the first compute element, after said execution of the first action and while the first data set is still in the first memory, to;

at least temporarily halt execution of the first application program, while leaving the first data set in the cache memory; and

temporarily execute the second application program, at least until the second action is performed by the second application program in conjunction with the first data set still in the cache memory,

thereby avoiding a need to re-fetch the first data set.

2. The system of claim 1, wherein said identification of the second action is facilitated by estimating, by the system, that the second application program, if allowed to run on the first compute element, will reach execution of the second action not later than a predetermined amount of time after said allowance to run.

3. The system of claim 2, wherein the predetermined amount of time is 10 (ten) milliseconds.

4. The system of claim 2, further comprising a second compute element, wherein:

said estimation is done by the second compute element, by analyzing the second application program; and

said instructing the first compute element is done by said second compute element.

5. The system of claim 4, wherein the second application program is executed in said second compute element before the estimation and said instructing take place, and prior to said temporary halt and the temporary execution of the second application program in the first compute element.

6. The system of claim 4, wherein the second compute element has access to both the first application program and the second application program, thereby enabling the second compute element to achieve said identification.

7. The system of claim 1, wherein:

said identification of the second action is facilitated by detecting, in the second application program, a fetching request for the first data set, in which said fetching request for the first data set is similar to another fetching request, in the first application program, for said first data set.

8. The system of claim 7, wherein said identification of the second action is further facilitated by detecting, in the second application program, that the fetching request precedes the second action, while also detecting, in the first application program, that the another fetching request precedes the first action, thereby realizing an association between the first action and the second action via the first data set and the fetching thereof.

9. The system of claim 7, wherein the fetching request, in conjunction with the second action, is never executed, such that the another fetching request is the only one executed by the system.

10. The system of claim 7, wherein said fetch is a result of the another fetching request in the first application program.

11. The system of claim 1, wherein said first data source is configured to produce, store, or obtain the first data set.

12. The system of claim 11, wherein the first data source is selected from a group consisting of:

(i) an element of a distributed data store, (ii) a memory module, (iii) a data interface, and (iv) another compute element.

13. The system of claim 1, wherein the fetch is done via a switching network, thereby introducing a first latency in conjunction with said fetch, in which said first latency is circumvented as a result of avoiding the need to re-fetch the first data set.

14. The system of claim 1, wherein said first action is selected form a group of actions consisting of:

(i) a matrix multiplication in which the first data set is a first matrix that is multiplied by a second matrix, (ii) a filtering or sorting process to be applied on the first data set, and (iii) any mathematical function involving the first data set.

15. The system of claim 14, wherein said second action is selected form a group of actions consisting of:

(i) a matrix multiplication in which the first data set is the first matrix that is multiplied by a third matrix, (ii) another filtering or sorting process to be applied on the first data set, and (iii) any other mathematical function involving the first data set.

16. A system operative to execute efficiently a plurality of actions, comprising:

a first compute element associated with a first memory; and

a first data set associated with a first data source;

wherein the system is configured to;

fetch the first data set from the first data source to the first memory;

execute, in the first compute element, and in conjunction with the first data set now in the first memory, a first action that is a part of a first algorithm comprising a first part and said first action and involving said first data set;

identify a second action that is a part of a second algorithm comprising the first part and said second action and that, like the first action, involves the first data set; and

cause the second action to be executed in the first compute element, and in conjunction with the first data set already in the first memory, while the first data set is still in the first memory, thereby avoiding a need to re-fetch the first data set;

in which;

the system is further configured to execute the first part prior to said execution of the first action, thereby facilitating execution of the first algorithm and the second algorithm up to a point where the first part ends;

the execution of the first action follows said execution of the first part, such that the execution of the first action is a continuation of said execution of the first algorithm; and

said causing of the second action to be executed in the first compute element is facilitated by the system instructing the first compute element, after said execution of the first action, to switch to executing the second action.

17. The system of claim 16, wherein said identification of the second action is facilitated by detecting, by the system, that the first part is a common part of both the first algorithm and the second algorithm, and that the first action, which follows the common part, is different than the second action that also follows the common part, while both the first action and the second action are operating on the first data set.

18. The system of claim 17, wherein:

said identification of the second action is further facilitated by detecting, in the second algorithm, a fetching request for the first data set, in which said fetching request for the first data set is similar to another fetching request, in the first algorithm, for said first data set; and

said identification of the second action is further facilitated by detecting that said another fetching request terminates the common part of the first algorithm, and that said fetching request terminates the common part of the second algorithm.