Systems and methods for changing computational tasks on computation nodes to minimize processing time variation

• US 8,214,521 B2
• Filed: 12/02/2009
• Issued: 07/03/2012
• Est. Priority Date: 12/02/2009
• Status: Active Grant

• Current Assignee: IP Wave Pte. Ltd.
• Original Assignee: NEC Laboratories America Inc (NEC Corporation)
• Inventors: Takagi, Masamichi, Seo, Yoshiki, Yamada, Akio, Hosomi, Takeo
• Primary Examiner(s): Avellino, Joseph
• Assistant Examiner(s): Conaway, James
• Application Number:
  US12/629,048
• Publication Number:
  US 20110131578A1
• Time in Patent Office: 944 Days
• Field of Search: 709/201, 709/235, 718/100, 718/105
• US Class Current: 709/235
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups

Abstract

Systems and methods are disclosed to process streaming data units (tuples) for an application using a plurality of processing units, the application have a predetermined processing time requirement, by changing an operator-set applied to the tuple by a processing unit, on a tuple-by-tuple basis; estimating code requirement for potential operators based on processing unit capability; and assigning the potential operators to the processing units.

Claims

1. A system to process streaming data units (tuples), comprising:

a. a plurality of processing units to receive tuples for an application, the application having a predetermined processing time requirement, wherein the processing units are connected through a network which applies operators to tuples in a pipe-lined manner, wherein the processing units are organized in a processing unit graph;

b. a tuple-by-tuple operator set movement unit coupled to the processing units to change an operator-set applied to the tuple by a selected processing unit, on a tuple-by-tuple basis, wherein said tuple-by-tuple operator set movement unit determines whether the processing time for the assigned operators of the selected processing unit exceeds the predetermined processing time requirement and, if said requirement is exceeded, the tuple-by-tuple operator set movement unit selects an operator sub-set and tuple sub-set to be moved to another processing unit;

wherein a sub-graph of the processing unit graph is chosen as input and descendant processing units in the sub-graph are selected in an inverse-topological order;

wherein a slack for the selected descendant processing unit is determined by determining the difference between an estimated processing time for the processing unit and a processing time requirement;

wherein if there is sufficient slack for the selected descendant processing unit at least a portion of the operator sub-set and tuple-sub-set are selected to be moved to the selected descendant processing unit; and

c. a process direction module for moving operators to processing units according to the selection made by the tuple-by-tuple operator set movement unit.

2. The system of claim 1, wherein the tuple-by-tuple operator-set movement unit inspects and determines a processing unit to perform one or more assigned operators for a particular application within the application'"'"'s processing time requirement.

3. The system of claim 1, wherein the tuple-by-tuple operator-set movement unit moves a time-gap among processing units by moving operator assignments among processing units.

4. The system of claim 1, wherein the tuple-by-tuple operator-set movement unit determines a processing unit unable to perform assigned operators within the processing time requirement.

5. The system of claim 4, wherein the tuple-by-tuple operator-set movement unit moves operator-sub-set and tuple-sub-set to another processing unit to meet the processing time requirement.

6. The system of claim 1, wherein the tuple-by-tuple operator-set movement unit moves a tuple-subset to decrease a predetermined number of tuples to apply an operator to from a processing unit and increase the predetermined number tuples on another processing unit.

7. The system of claim 1, comprising a time estimator coupled to the tuple-by-tuple operator-set movement unit to estimate processing time for a current node to apply assigned operators.

8. The system of claim 7, wherein the time estimator measures an actual processing time or operates an analytical model comprising current tuple input rate, operator type, and processing unit capability.

9. The system of claim 1, comprising a direction unit coupled to the tuple-by-tuple operator-set movement unit to control a direction of the processing unit.

10. The system of claim 9, wherein the direction unit instructs the processing units on operators to be performed on a tuple through an interconnection network.

11. A system to process streaming data units (tuples), comprising:

a plurality of processing units to receive tuples for an application, the application having a predetermined processing time requirement, wherein the processing units are connected through a network which applies operators to tuples in a pipe-lined manner, wherein the processing units are organized in a processing unit graph;

a code estimation and loading unit coupled to the processing units to estimate potential operators and assign operators to the processing units;

a tuple-by-tuple operator set movement unit coupled to the processing units to change an operator-set applied to the tuple by a selected processing unit, on a tuple-by-tuple basis, wherein said tuple-by-tuple operator set movement unit determines whether the processing time for the assigned operators of the selected processing unit exceeds the predetermined processing time requirement and, if said requirement is exceeded, the tuple-by-tuple operator set movement unit selects an operator sub-set and tuple sub-set to be moved to another processing unit;

wherein a sub-graph of the processing unit graph is chosen as input and descendant processing units in the sub-graph are selected in an inverse-topological order;

wherein a slack for the selected descendant processing unit is determined by determining the difference between an estimated processing time for the processing unit and a processing time requirement;

wherein if there is sufficient slack for the selected descendant processing unit at least a portion of the operator sub-set and tuple-sub-set are selected to be moved to the selected descendant processing unit; and

a process direction module for moving operators to processing units according to the selection made by the tuple-by-tuple operator set movement unit.

12. The system of claim 11, wherein the code estimation and loading unit inspects and determines if a processing unit is unable to perform assigned operator application within the processing time requirement.

13. The system of claim 12, wherein the code estimation and loading unit simulates moving an operator-set and a tuple-set to another processing unit to meet the processing time requirement and to estimate potential operators to be moved to the processing units.

14. The system of claim 11, wherein the code estimation and loading unit estimates a worst-case or typical-case processing time of the processing unit by utilizing processing time variation.

15. The system of claim 11, comprising a timing module coupled to the code estimation and loading unit to store processing time requirement for each processing unit.

16. The system of claim 11, comprising a code loading direction unit coupled to the code estimation and loading unit to direct codes to be loaded on the processing units.

17. A system to process streaming data units (tuples), comprising:

a. a plurality of processing units to receive tuples for an application, the application having a predetermined processing time requirement, wherein the processing units are connected through a network which applies operators to tuples in a pipe-lined manner, wherein the processing units are organized in a processing unit graph;

b. a tuple-by-tuple operator set movement unit coupled to the processing units to change an operator-set applied to the tuple by a selected processing unit, on a tuple-by-tuple basis, wherein said tuple-by-tuple operator set movement unit determines whether the processing time for the assigned operators of the selected processing unit exceeds the predetermined processing time requirement and, if said requirement is exceeded, the tuple-by-tuple operator set movement unit selects an operator sub-set and tuple sub-set to be moved to another processing unit;

wherein a sub-graph of the processing unit graph is chosen as input and descendant processing units in the sub-graph are selected in an inverse-topological order;

wherein a slack for the selected descendant processing unit is determined by determining the difference between an estimated processing time for the processing unit and a processing time requirement;

wherein if there is sufficient slack for the selected descendant processing unit at least a portion of the operator sub-set and tuple-sub-set are selected to be moved to the selected descendant processing unit; and

c. a code estimation and loading unit coupled to the processing units to estimate potential operators and assign operators to the processing units;

d. a process direction module for moving operators to processing units according to the selection made by the tuple-by-tuple operator set movement unit.

18. A method to process streaming data units (tuples) for an application, using a plurality of processing units, the application have a predetermined processing time requirement comprising:

a. changing an operator-set applied to the tuple by a selected processing unit, on a tuple-by-tuple basis;

wherein the application utilizes a plurality of processing units, the application having a predetermined processing time requirement,

wherein the processing units are connected through a network which applies operators to tuples in a pipe-lined manner,

wherein the processing units are organized in a processing unit graph;

wherein a tuple-by-tuple operator set movement unit determines whether the processing time for the assigned operators of the selected processing unit exceeds the predetermined processing time requirement and, if said requirement is exceeded, the tuple-by-tuple operator set movement unit selects an operator sub-set and tuple sub-set to be moved to another processing unit;

wherein a sub-graph of the processing unit graph is chosen as input and descendant processing units in the sub-graph are selected in an inverse-topological order;

wherein a slack for the selected descendant processing unit is determined by determining the difference between an estimated processing time for the processing unit and a processing time requirement;

wherein if there is sufficient slack for the selected descendant processing unit at least a portion of the operator sub-set and tuple-sub-set are selected to be moved to the selected descendant processing unit;

b. estimating code requirement for potential operators based on processing unit capability; and

c. assigning the potential operators to the processing units using a process direction module for moving operators to processing units according to the selection made by the tuple-by-tuple operator set movement unit.

19. The method of claim 18, comprising selecting a processing unit unable to perform an assigned operator application within the predetermined processing time requirement and moving the operator-set and tuple-set to other processing units to meet the processing time requirement.

20. The method of claim 18, comprising inspecting and selecting a processing unit to perform one or more assigned operators for a particular application within the application'"'"'s processing time requirement.