NODE DEVICE FUNCTION AND CACHE AWARE TASK ASSIGNMENT

• US 20170223097A1
• Filed: 02/01/2017
• Published: 08/03/2017
• Est. Priority Date: 02/01/2016
• Status: Active Grant

• Current Assignee: SAS Institute Incorporated
• Original Assignee: SAS Institute Incorporated
• Inventors: Zhang, Chaowang, Bequet, Henry Gabriel Victor, Du, Juan
• Granted Patent: US 9,900,378 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 9/30043 LOAD or STORE instructions; Clear instruction
• CPC Class Codes: G06F 9/30145 Instruction analysis, e.g. decoding, instruction word fields
• CPC Class Codes: G06F 9/30181 Instruction operation extension or modification
• CPC Class Codes: G06F 9/3885 using a plurality of independent parallel functional units
• CPC Class Codes: G06F 9/4806 Task transfer initiation or dispatching
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• 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/5072 Grid computing
• CPC Class Codes: H04L 41/0896 Bandwidth or capacity management, i.e. automatically increasing or decreasing capacities flow or congestion control using dynamic resource allocation, e.g. in-call renegotiation, H04L47/76
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

An apparatus includes a processor and storage to store instructions that cause the processor to perform operations including: receive an indication of completion of a first task with a first partition such that the first node device is available to assign to perform another task; delay assignment of performance of a second task on a second partition to the first node device for up to a predetermined period of time, in spite of readiness of the second task to be performed on the second partition and availability of the first node device; determine whether an indication of completion of the first task with the second partition such that the second node device is available to assign to perform another task is received within the predetermined period of time; and assign performance of the second task on the second partition to the second node device based on the determination.

Claims

1. An apparatus comprising a processor and a storage to store instructions that, when executed by the processor, cause the processor to perform operations comprising:

for each node device of a plurality of node devices, derive an assignment of performance of a first task with a first data set, wherein;

the first data set is divisible into a plurality of partitions;

a first node device of the plurality of node devices is assigned to perform the first task with a first partition of the plurality of partitions of the first data set; and

a second node device of the plurality of node devices is assigned to perform the first task with a second partition of the plurality of partitions of the first data set;

transmit an indication of the assignment of performance of the first task with the first partition to the first node device to cause performance of the first task with the first partition by the first node device and to cause storage of at least some of the first partition within volatile storage of the first node device;

transmit an indication of the assignment of performance of the first task with the second partition to the second node device to cause performance of the first task with the second partition by the second node device and to cause storage of at least some of the second partition within volatile storage of the second node device;

receive an indication from the first node device of completion of performance of the first task with the first partition by the first node device such that the first node device is available to assign to perform another task;

delay assignment of performance of a second task on the second partition to the first node device after receipt of the indication of completion of the performance of the first task with the first partition by the first node device for up to a predetermined period of time, in spite of readiness of the second task to be performed on the second partition, and in spite of availability of the first node device as a result of the completion of the performance of first task with the first partition;

determine whether an indication of completion of performance of the first task with the second partition by the second node device such that the second node device is available to assign to perform another task is received from the second node device within the predetermined period of time;

in response to receipt of the indication of completion of the first task with the second partition by the second node device within the predetermined period of time;

assign performance of the second task on the second partition to the second node device to enable accesses to at least some of the second partition within the volatile storage of the second node device; and

transmit an indication of the assignment of performance of the second task on the second partition to the second node device to avoid retrieval of the second partition by the first node device; and

in response to a lack of receipt of the indication of completion of the first task with the second partition by the second node device within the predetermined period of time;

assign performance of the second task on the second partition to the first node device; and

transmit an indication of the assignment of performance of the second task on the second partition to the first node device to cause retrieval of the second partition by the first node device.

2. The apparatus of claim 1, wherein the processor is caused to perform operations comprising derive the predetermined period of time from at least one measurement of an amount of time between transmission of an assignment to perform the first task to a node device of the plurality of nodes devices and receipt of an indication of completion of performance of the first task from the node device.

3. The apparatus of claim 1, wherein the processor is caused to perform operations comprising:

determine a quantity of node devices of the plurality of node devices that are available to perform the first task; and

derive a division of the first data set into the plurality of partitions of the first data set based on the quantity of node devices and a metadata descriptive of a manner in which the first data set is organized.

4. The apparatus of claim 3, wherein:

the first data set is stored within one or more storage devices;

the processor is caused to perform operations comprising retrieve the metadata from the one or more storage devices;

the transmission of the indication of the assignment of performance of the first task with the first partition to the first node device causes the first node device to retrieve the first partition from the one or more storage devices; and

the transmission of the indication of the assignment of performance of the first task with the second partition to the second node device causes the second node device to retrieve the second partition from the one or more storage devices.

5. The apparatus of claim 1, comprising at least one volatile storage component coupled to the processor, wherein the processor is caused to perform operations comprising:

assign the processor performance of the first task with a third partition of the plurality of partitions of the first data set;

store at least some of the third partition within the at least one volatile storage component; and

perform the first task with the third partition.

6. The apparatus of claim 1, wherein the processor is caused to perform operations comprising:

for each node device of a subset of the plurality of node devices, derive an assignment to retrieve and store one of the plurality of partitions of the first data set from one or more storage devices to enable use of each node device of the subset as a backup node device to respond to a failure of one of the node devices of the plurality of node devices, wherein;

a third node device of the plurality of node devices is assigned to perform the first task with a third partition of the plurality of partitions of the first data set; and

the third node is assigned to retrieve and store the second partition from the one or more storage devices to enable use of the third node device as a backup node device to respond to a failure of the second node device;

receive an indication, during the predetermined period of time, from the third node device of completion of performance of the first task with the third partition by the third node device such that the third node device is available to assign to perform another task; and

in response to receipt of the indication of completion of the first task with the third partition by the third node device during the predetermined period of time, and in response to a lack of receipt of the indication of completion of the first task with the second partition by the second node device within the predetermined period of time;

assign performance of the second task on the second partition to the third node device; and

transmit an indication of the assignment of performance of the second task on the second partition to the third node device.

7. The apparatus of claim 1, wherein:

the performances of the first task with the first and second partitions comprises use of the first and second partitions as inputs to performances of the first task to generate corresponding partitions of a second data set; and

the performance of the second task on the second partition comprises use of the second partition as an input to a performance of the second task to generate a corresponding partition of a third data set.

8. The apparatus of claim 7, wherein:

the transmission of the indication of the assignment of the performance of the first task with the first partition to the first node device causes the first node device to;

retrieve the first partition from one or more storage devices;

use at least some of the first partition stored within the volatile storage of the first node device as an input to the performance of the first task by the first node device; and

transmit the indication of completion of the performance of the first task with the first partition while at least some of the first partition remains stored within the volatile storage of the first node device;

the transmission of the indication of the assignment of the performance of the first task with the second partition to the second node device causes the second node device to;

retrieve the second partition from the one or more storage devices;

use at least some of the second partition stored within the volatile storage of the second node device as an input to the performance of the first task by the second node device; and

transmit the indication of completion of the performance of the first task with the second partition while at least some of the second partition remains stored within the volatile storage of the second node device; and

the transmission of the indication of the assignment of the performance of the second task on the second partition to the second node device causes the second node device to use at least some of the second partition still stored within the volatile storage of the second node device as an input to the performance of the second task by the second node device to minimize accesses to the second partition stored within non-volatile storage of the second node device.

9. The apparatus of claim 1, wherein:

the performances of the first task with the first and second partitions comprises performances of the first task to generate the first and second partitions as outputs of the first task using corresponding partitions of a second data set as inputs; and

the performance of the second task on the second partition comprises use of the second partition as an input to a performance of the second task to generate a corresponding partition of a third data set.

10. The apparatus of claim 9, wherein:

the transmission of the indication of the assignment of the performance of the first task with the first partition to the first node device causes the first node device to;

generate the first partition as an output of the performance of the first task by the first node device; and

transmit the indication of completion of the performance of the first task with the first partition while at least some of the first partition remains stored within the volatile storage of the first node device;

the transmission of the indication of the assignment of the performance of the first task with the second partition to the second node device causes the second node device to;

generate the second partition as an output of the performance of the first task by the second node device; and

transmit the indication of completion of the performance of the first task with the second partition while at least some of the second partition remains stored within the volatile storage of the second node device; and

the transmission of the indication of the assignment of the performance of the second task on the second partition to the second node device causes the second node device to use at least some of the second partition still stored within the volatile storage of the second node device as an input to the performance of the second task by the second node device to minimize accesses to the second partition stored within non-volatile storage of the second node device.

11. A computer-program product tangibly embodied in a non-transitory machine-readable storage medium, the computer-program product including instructions operable to cause a processor to perform operations comprising:

for each node device of a plurality of node devices, derive an assignment of performance of a first task with a first data set, wherein;

the first data set is divisible into a plurality of partitions;

a first node device of the plurality of node devices is assigned to perform the first task with a first partition of the plurality of partitions of the first data set; and

a second node device of the plurality of node devices is assigned to perform the first task with a second partition of the plurality of partitions of the first data set;

transmit an indication of the assignment of performance of the first task with the first partition to the first node device to cause performance of the first task with the first partition by the first node device and to cause storage of at least some of the first partition within volatile storage of the first node device;

transmit an indication of the assignment of performance of the first task with the second partition to the second node device to cause performance of the first task with the second partition by the second node device and to cause storage of at least some of the second partition within volatile storage of the second node device;

receive an indication from the first node device of completion of performance of the first task with the first partition by the first node device such that the first node device is available to assign to perform another task;

delay assignment of performance of a second task on the second partition to the first node device after receipt of the indication of completion of the performance of the first task with the first partition by the first node device for up to a predetermined period of time, in spite of readiness of the second task to be performed on the second partition, and in spite of availability of the first node device as a result of the completion of the performance of first task with the first partition;

determine whether an indication of completion of performance of the first task with the second partition by the second node device such that the second node device is available to assign to perform another task is received from the second node device within the predetermined period of time;

in response to receipt of the indication of completion of the first task with the second partition by the second node device within the predetermined period of time;

assign performance of the second task on the second partition to the second node device to enable accesses to at least some of the second partition within the volatile storage of the second node device; and

transmit an indication of the assignment of performance of the second task on the second partition to the second node device to avoid retrieval of the second partition by the first node device; and

in response to a lack of receipt of the indication of completion of the first task with the second partition by the second node device within the predetermined period of time;

assign performance of the second task on the second partition to the first node device; and

transmit an indication of the assignment of performance of the second task on the second partition to the first node device to cause retrieval of the second partition by the first node device.

12. The computer-program product of claim 11, wherein the processor is caused to perform operations comprising derive the predetermined period of time from at least one measurement of an amount of time between transmission of an assignment to perform the first task to a node device of the plurality of nodes devices and receipt of an indication of completion of performance of the first task from the node device.

13. The computer-program product of claim 11, wherein the processor is caused to perform operations comprising:

determine a quantity of node devices of the plurality of node devices that are available to perform the first task; and

derive a division of the first data set into the plurality of partitions of the first data set based on the quantity of node devices and a metadata descriptive of a manner in which the first data set is organized.

14. The computer-program product of claim 13, wherein:

the first data set is stored within one or more storage devices;

the processor is caused to perform operations comprising retrieve the metadata from the one or more storage devices;

the transmission of the indication of the assignment of performance of the first task with the first partition to the first node device causes the first node device to retrieve the first partition from the one or more storage devices; and

the transmission of the indication of the assignment of performance of the first task with the second partition to the second node device causes the second node device to retrieve the second partition from the one or more storage devices.

15. The computer-program product of claim 11, wherein the processor is caused to perform operations comprising:

assign the processor performance of the first task with a third partition of the plurality of partitions of the first data set;

store at least some of the third partition within at least one volatile storage component coupled to the processor; and

perform the first task with the third partition.

16. The computer-program product of claim 11, wherein the processor is caused to perform operations comprising:

for each node device of a subset of the plurality of node devices, derive an assignment to retrieve and store one of the plurality of partitions of the first data set from one or more storage devices to enable use of each node device of the subset as a backup node device to respond to a failure of one of the node devices of the plurality of node devices, wherein;

a third node device of the plurality of node devices is assigned to perform the first task with a third partition of the plurality of partitions of the first data set; and

the third node is assigned to retrieve and store the second partition from the one or more storage devices to enable use of the third node device as a backup node device to respond to a failure of the second node device;

receive an indication, during the predetermined period of time, from the third node device of completion of performance of the first task with the third partition by the third node device such that the third node device is available to assign to perform another task; and

in response to receipt of the indication of completion of the first task with the third partition by the third node device during the predetermined period of time, and in response to a lack of receipt of the indication of completion of the first task with the second partition by the second node device within the predetermined period of time;

assign performance of the second task on the second partition to the third node device; and

transmit an indication of the assignment of performance of the second task on the second partition to the third node device.

17. The computer-program product of claim 11, wherein:

the performances of the first task with the first and second partitions comprises use of the first and second partitions as inputs to performances of the first task to generate corresponding partitions of a second data set; and

the performance of the second task on the second partition comprises use of the second partition as an input to a performance of the second task to generate a corresponding partition of a third data set.

18. The computer-program product of claim 17, wherein:

the transmission of the indication of the assignment of the performance of the first task with the first partition to the first node device causes the first node device to;

retrieve the first partition from one or more storage devices;

use at least some of the first partition stored within the volatile storage of the first node device as an input to the performance of the first task by the first node device; and

transmit the indication of completion of the performance of the first task with the first partition while at least some of the first partition remains stored within the volatile storage of the first node device;

the transmission of the indication of the assignment of the performance of the first task with the second partition to the second node device causes the second node device to;

retrieve the second partition from the one or more storage devices;

use at least some of the second partition stored within the volatile storage of the second node device as an input to the performance of the first task by the second node device; and

transmit the indication of completion of the performance of the first task with the second partition while at least some of the second partition remains stored within the volatile storage of the second node device; and

the transmission of the indication of the assignment of the performance of the second task on the second partition to the second node device causes the second node device to use at least some of the second partition still stored within the volatile storage of the second node device as an input to the performance of the second task by the second node device to minimize accesses to the second partition stored within non-volatile storage of the second node device.

19. The computer-program product of claim 11, wherein:

the performances of the first task with the first and second partitions comprises performances of the first task to generate the first and second partitions as outputs of the first task using corresponding partitions of a second data set as inputs; and

the performance of the second task on the second partition comprises use of the second partition as an input to a performance of the second task to generate a corresponding partition of a third data set.

20. The computer-program product of claim 19, wherein:

the transmission of the indication of the assignment of the performance of the first task with the first partition to the first node device causes the first node device to;

generate the first partition as an output of the performance of the first task by the first node device; and

transmit the indication of completion of the performance of the first task with the first partition while at least some of the first partition remains stored within the volatile storage of the first node device;

the transmission of the indication of the assignment of the performance of the first task with the second partition to the second node device causes the second node device to;

generate the second partition as an output of the performance of the first task by the second node device; and

transmit the indication of completion of the performance of the first task with the second partition while at least some of the second partition remains stored within the volatile storage of the second node device; and

the transmission of the indication of the assignment of the performance of the second task on the second partition to the second node device causes the second node device to use at least some of the second partition still stored within the volatile storage of the second node device as an input to the performance of the second task by the second node device to minimize accesses to the second partition stored within non-volatile storage of the second node device.

21. A computer-implemented method comprising:

for each node device of a plurality of node devices, deriving at a coordinating device an assignment of performance of a first task with a first data set, wherein the first data set is divisible into a plurality of partitions, and the deriving comprises;

deriving a first assignment of a first node device of the plurality of node devices to perform the first task with a first partition of the plurality of partitions of the first data set; and

deriving a second assignment of a second node device of the plurality of node devices is assigned to perform the first task with a second partition of the plurality of partitions of the first data set;

transmitting an indication of the assignment of performance of the first task with the first partition to the first node device to cause performance of the first task with the first partition by the first node device and to cause storage of at least some of the first partition within volatile storage of the first node device;

transmitting an indication of the assignment of performance of the first task with the second partition to the second node device to cause performance of the first task with the second partition by the second node device and to cause storage of at least some of the second partition within volatile storage of the second node device;

receiving, at the coordinating device, an indication from the first node device of completion of performance of the first task with the first partition by the first node device such that the first node device is available to assign to perform another task;

delaying assignment of performance of a second task on the second partition to the first node device after receipt of the indication of completion of the performance of the first task with the first partition by the first node device for up to a predetermined period of time, in spite of readiness of the second task to be performed on the second partition, and in spite of availability of the first node device as a result of the completion of the performance of the first task with the first partition;

determining, at the coordinating device, whether an indication of completion of performance of the first task with the second partition by the second node device such that the second node device is available to assign to perform another task is received from the second node device within the predetermined period of time; and

in response to receipt of the indication of completion of the first task with the second partition by the second node device within the predetermined period of time;

assigning performance of the second task on the second partition to the second node device to enable accesses to at least some of the second partition within the volatile storage of the second node device; and

transmitting an indication of the assignment of performance of the second task on the second partition to the second node device to avoid retrieval of the second partition by the first node device.

22. The computer-implemented method of claim 21, comprising deriving, at the coordinating device, the predetermined period of time from at least one measurement of an amount of time between transmission of an assignment to perform the first task to a node device of the plurality of nodes devices and receipt of an indication of completion of performance of the first task from the node device.

23. The computer-implemented method of claim 21, comprising:

determining, at the coordinating device, a quantity of node devices of the plurality of node devices that are available to perform the first task; and

deriving, at the coordinating device, a division of the first data set into the plurality of partitions of the first data set based on the quantity of node devices and a metadata descriptive of a manner in which the first data set is organized.

24. The computer-implemented method of claim 23, wherein:

the first data set is stored within one or more storage devices;

the method comprises retrieving, by the coordinating device, the metadata from the one or more storage devices;

the transmission of the indication of the assignment of performance of the first task with the first partition to the first node device causes the first node device to retrieve the first partition from the one or more storage devices; and

the transmission of the indication of the assignment of performance of the first task with the second partition to the second node device causes the second node device to retrieve the second partition from the one or more storage devices.

25. The computer-implemented method of claim 21, comprising:

assigning, to the coordinating device, performance of the first task with a third partition of the plurality of partitions of the first data set;

storing at least some of the third partition within at least one volatile storage component of the coordinating device; and

performing, at the coordinating device, the first task with the third partition.

26. The computer-implemented method of claim 21, comprising in response to a lack of receipt of the indication of completion of the first task with the second partition by the second node device within the predetermined period of time:

assign performance of the second task on the second partition to the first node device; and

transmit an indication of the assignment of performance of the second task on the second partition to the first node device to cause retrieval of the second partition by the first node device.

27. The computer-implemented method of claim 21, wherein:

the performances of the first task with the first and second partitions comprises use of the first and second partitions as inputs to performances of the first task to generate corresponding partitions of a second data set; and

the performance of the second task on the second partition comprises use of the second partition as an input to a performance of the second task to generate a corresponding partition of a third data set.

28. The computer-implemented method of claim 27, wherein:

the transmission of the indication of the assignment of the performance of the first task with the first partition to the first node device causes the first node device to;

retrieve the first partition from one or more storage devices;

use at least some of the first partition stored within the volatile storage of the first node device as an input to the performance of the first task by the first node device; and

transmit the indication of completion of the performance of the first task with the first partition while at least some of the first partition remains stored within the volatile storage of the first node device;

the transmission of the indication of the assignment of the performance of the first task with the second partition to the second node device causes the second node device to;

retrieve the second partition from the one or more storage devices;

use at least some of the second partition stored within the volatile storage of the second node device as an input to the performance of the first task by the second node device; and

transmit the indication of completion of the performance of the first task with the second partition while at least some of the second partition remains stored within the volatile storage of the second node device; and

the transmission of the indication of the assignment of the performance of the second task on the second partition to the second node device causes the second node device to use at least some of the second partition still stored within the volatile storage of the second node device as an input to the performance of the second task by the second node device to minimize accesses to the second partition stored within non-volatile storage of the second node device.

29. The computer-implemented method of claim 21, wherein:

the performances of the first task with the first and second partitions comprises performances of the first task to generate the first and second partitions as outputs of the first task using corresponding partitions of a second data set as inputs; and

the performance of the second task on the second partition comprises use of the second partition as an input to a performance of the second task to generate a corresponding partition of a third data set.

30. The computer-implemented method of claim 29, wherein:

the transmission of the indication of the assignment of the performance of the first task with the first partition to the first node device causes the first node device to;

generate the first partition as an output of the performance of the first task by the first node device; and

transmit the indication of completion of the performance of the first task with the first partition while at least some of the first partition remains stored within the volatile storage of the first node device;

the transmission of the indication of the assignment of the performance of the first task with the second partition to the second node device causes the second node device to;

generate the second partition as an output of the performance of the first task by the second node device; and

transmit the indication of completion of the performance of the first task with the second partition while at least some of the second partition remains stored within the volatile storage of the second node device; and

the transmission of the indication of the assignment of the performance of the second task on the second partition to the second node device causes the second node device to use at least some of the second partition still stored within the volatile storage of the second node device as an input to the performance of the second task by the second node device to minimize accesses to the second partition stored within non-volatile storage of the second node device.