SYSTEMS AND METHODS FOR CHANGING COMPUTATIONAL TASKS ON COMPUTATION NODES TO MINIMIZE PROCESSING TIME VARIATION

• US 20110131578A1
• Filed: 12/02/2009
• Published: 06/02/2011
• 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, Yamada, Akio, Seo, Yoshiki, Hosomi, Takeo
• Granted Patent: US 8,214,521 B2
• Time in Patent Office: Days
• US Class Current: 718/100
• 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 have a predetermined processing time requirement; and

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 processing unit, on a tuple-by-tuple basis.

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. a plurality of processing units to receive tuples for an application, the application have a predetermined processing time requirement; and

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

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 have a predetermined processing time requirement;

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 processing unit, on a tuple-by-tuple basis; and

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

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 processing unit, on a tuple-by-tuple basis;

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

c. assigning the potential operators to the processing units.

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.