Systems and methods for processing data sets according to an instructed order

• US 9,690,705 B1
• Filed: 09/29/2015
• Issued: 06/27/2017
• Est. Priority Date: 12/09/2014
• Status: Active Grant

• Current Assignee: DataRobot, Inc.
• Original Assignee: Parallel Machines Ltd.
• Inventors: Adda, Michael, Amar, Lior, Braverman, Avner, Khermosh, Lior, Zuckerman, Gal
• Primary Examiner(s): Thai, Tuan
• Assistant Examiner(s): Waddy, Jr., Edward
• Application Number:
  US14/868,893
• Time in Patent Office: 637 Days
• Field of Search: 711E12019, 711E12033, 711E1204, 711118, 711217, 711103, 711137, 711E12001, 712 1, 712205, 712207
• CPC Class Codes: G06F 12/0806 Multiuser, multiprocessor or multiprocessing cache systems
• CPC Class Codes: G06F 12/0815 Cache consistency protocols
• CPC Class Codes: G06F 12/0842 for multiprocessing or multitasking
• CPC Class Codes: G06F 12/0855 Overlapped cache accessing, e.g. pipeline G06F12/0846 takes precedence
• CPC Class Codes: G06F 13/1673 using buffers
• CPC Class Codes: G06F 2212/1016 Performance improvement
• CPC Class Codes: G06F 2212/1024 Latency reduction
• CPC Class Codes: G06F 2212/154 Networked environment
• CPC Class Codes: G06F 2212/62 Details of cache specific to multiprocessor cache arrangements
• CPC Class Codes: G06F 2212/621 Coherency control relating to peripheral accessing, e.g. from DMA or I/O device
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/0658 Controller construction arrangements
• 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 process efficiently, according to a certain order, a plurality of data sets arranged in data blocks. In one embodiment, a first compute element receives from another compute element a first set of instructions that determine an order in which a plurality of data sets are to be processed as part of a processing task. Relevant data sets are then streamed into a cache memory associated with the first compute element, but the order of streaming is not by order of storage but rather by the order conveyed in the first set of instructions.

Claims

1. A system operative to efficiently process, in a particular order, a plurality of data sets arranged in data blocks, comprising:

a first compute element associated with a first cache memory;

a first data interface associated with a first data source and configured to obtain data sets from the first data source in a form of data blocks, such that each of the data blocks obtained comprises a plurality of data sets; and

an intermediary medium, which is non-transitory, operative to store and access data, in which the intermediary medium is communicatively connected with the first cache memory and the first data source,

wherein;

the first compute element is configured, in conjunction with a first processing task associated with the pluralities of data sets, to instruct the first data interface to obtain and deliver the data blocks from the first data source to the intermediary medium; and

the first compute element is further configured to stream the pluralities of data sets from the intermediary medium to the first cache memory according to a first streaming order dictated by a second compute element managing the first processing task, thereby facilitating (i) just-in-time availability of the data sets in the cache memory, and therefore (ii) efficient execution of the first processing task by the first compute element.

2. The system of claim 1, wherein the first compute element, in carrying out said streaming, is further configured to:

determine, according to the first streaming order, an address within the intermediary medium that points to next one of the data sets for streaming; and

issue at least one pre-fetch instruction in conjunction with said address determined, consequently causing an update of the cache memory with said next data set for streaming.

3. The system of claim 2, wherein each of the pre-fetch instructions is operative to update one cache-line of the first cache memory with data associated with the next data set for streaming.

4. The system of claim 3, wherein said one cache line is 64 (sixty four) bytes in length.

5. The system of claim 3, wherein said updating of the cache lines is done essentially without involvement of the first compute element, thereby freeing the first compute element to perform the first processing task in conjunction with a previous one of the data sets already in the cache memory.

6. The system of claim 5, wherein the obtaining and delivering of the data blocks from the first data source to the intermediary medium is done essentially without involvement of the first compute element, thereby further freeing the first compute element to perform the first processing task.

7. The system of claim 6, wherein the obtaining and delivering of the data blocks from the first data source to the intermediary medium is done in conjunction with a direct-memory-access (DMA) procedure.

8. The system of claim 1, wherein the first data source is a data source that is optimized at least in part to operate in conjunction with the data blocks having a certain size.

9. The system of claim 8, wherein the first data source is selected from a group of data sources consisting of:

(i) a flash memory, (ii) a network interface, (iii) a 3D-Xpoint non-volatile memory, (iv) a dynamic random access memory, (v) a magnetic disk, and (vi) any data source presenting any kind of advantage by accessing and delivering data in conjunction with the data blocks having a certain size.

10. The system of claim 9, wherein said intermediary medium is any memory capable of accessing and delivering data using random-access memory transactions, thereby allowing a data granularity necessary to facilitate said streaming of the data sets having a certain size that is smaller than the size of the data blocks.

11. The system of claim 10, wherein the intermediary medium is a dynamic random access memory.

12. The system of claim 10, wherein the intermediary medium is a memory module.

13. A method for efficiently processing a plurality of data sets according to an instructed order, comprising:

receiving, by a first compute element, from a second compute element, a first set of instructions operative to determine a first order in which a plurality of data sets, which are stored respectively in a plurality of addresses in a memory module, are to be processed in conjunction with a first processing task that is under management of said second compute element;

issuing, by the first compute element, a first sequence of pre-fetch instructions, in which each of the pre-fetch instructions is operative to copy one of the data sets from the corresponding address in the memory module into a cache memory associated with the first compute element, in which the first sequence is issued according to the first order, thereby causing the plurality of data sets to stream into the cache memory according to the first order, and in which the memory module is a non-transitory intermediate medium for the data sets in transition from an external source into the cache memory; and

processing, by the first compute element, the plurality of data sets streaming into the cache memory, according to the first order, and on-the-fly as the stream enters the cache memory according to the first order, thereby efficiently executing the first processing task.

14. The method of claim 13, further comprising:

receiving, by the first compute element, a second set of instructions operative to determine a second order in which the same plurality of data sets are to be processed in conjunction with a second processing task;

issuing, by the first compute element, a second sequence of pre-fetch instructions, in which each of the pre-fetch instructions is operative to copy one of the data sets from the corresponding address in the memory module into the cache memory, in which the second sequence is issued according to the second order, thereby causing the same plurality of data sets to stream again into the cache memory, but now according to the second order; and

processing again, by the first compute element, the plurality of data sets streaming into the cache memory, but now according to the second order, and on-the-fly as the stream enters the cache memory according to the second order, thereby efficiently executing the second processing task.

15. The method of claim 13, further comprising:

sending, by the first compute element, to the second compute element, a result of the first processing task.

16. The method of claim 14, wherein the second set of instructions is received from a third compute element, in which the second order is determined by the third compute element according to the second processing task that is under management of the third compute element.

17. The method of claim 16, further comprising:

sending, by the first compute element, to the third compute element, a result of the second processing task.

18. The method of claim 13, wherein:

the plurality of data sets are a plurality of values associated respectively with a plurality of keys; and

the first set of instructions is in a form of a list of the keys arranged in the first order.

19. The method of claim 18, further comprising:

deriving, by the first compute element, using the plurality of keys in the list, respectively said plurality of addresses in the memory module associated respectively with the plurality of values.

20. The method of claim 19, wherein the plurality of addresses derived is kept in the list, or in another list, in the first order, and further comprising:

including, by the first compute element, in each of the first sequence of pre-fetch instructions, one of the addresses, according to the order of appearance of the addresses in the list.

21. The method of claim 20, wherein the list or the another list is stored in the first memory module or in the cache memory, and further comprising:

reading, by the first compute element, the addresses in the list or the another list, according to the first order in which said addresses appear in the list or in the another list; and

issuing each of the first sequence of pre-fetch instructions with one of the addresses read according to the first order, thereby producing said stream.

22. The method of claim 13, wherein the first set of instructions is in a form of a list of the plurality of addresses arranged in the first order, and further comprising:

reading, by the first compute element, the addresses in the list, according to the first order in which said addresses appear in the list; and

issuing each of the first sequence of pre-fetch instructions with one of the addresses read according to the first order, thereby producing said stream.

23. The method of claim 22, wherein the plurality of data sets are a plurality of values associated respectively with a plurality of keys, and further comprising:

before said reception of the first set of instructions, deriving, by the first compute element, using the plurality of keys, respectively said plurality of addresses in the memory module associated respectively with the plurality of values;

conveying the plurality of addresses derived to a second compute element; and

later, but before said streaming, receiving from the second compute element the plurality of addresses conveyed, in a form of a list ordered in the first order determined by the second compute element, in which the list constitutes the first set of instructions.

24. The method of claim 13, wherein each of the pre-fetch instructions is operative to update one cache-line of the cache memory with the corresponding data set.

25. The method of claim 13, wherein each of the pre-fetch instructions is a sequence of several sub-instructions and each sub-instruction is operative to update one cache-line of the cache memory, in which said several sub-instructions are operative together to update one of the data sets in the cache memory, in which the data set is bigger than one cache-line.