Using predictive determinism within a streaming environment

• US 8,954,713 B2
• Filed: 11/20/2012
• Issued: 02/10/2015
• Est. Priority Date: 07/26/2011
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Santosuosso, John M., Schulz, Brandon W.
• Primary Examiner(s): Fennema, Robert
• Assistant Examiner(s): NIELSEN, KEITH A
• Application Number:
  US13/681,919
• Publication Number:
  US 20130080653A1
• Time in Patent Office: 812 Days
• Field of Search: 712/25
• US Class Current: 712/30
• CPC Class Codes: G06F 15/17 using an input/output type connection, e.g. channel, I/O port
• CPC Class Codes: G06F 9/06 using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
• CPC Class Codes: H04L 65/65 Network streaming protocols, e.g. real-time transport protocol [RTP] or real-time control protocol [RTCP]

Abstract

Techniques are described for transmitting predicted output data on a processing element in a stream computing application instead of processing currently received input data. The stream computing application monitors the output of a processing element and determines whether its output is predictable, for example, if the previously transmitted output values are within a predefined range or if one or more input values correlate with the same one or more output values. The application may then generate a predicted output value to transmit from the processing element instead of transmitting a processed output value based on current input values. The predicted output value may be, for example, an average of the previously transmitted output values or a previously transmitted output value that was transmitted in response to a previously received input value that is similar to a currently received input value.

Claims

1. A computer-implemented method for processing data, comprising:

receiving streaming data to be processed by a plurality of processing elements, the processing elements processing at least a portion of the received streaming data by operation of one or more computer processors;

establishing an operator graph of the plurality of processing elements, the operator graph defining at least one execution path and wherein at least one of the processing elements of the operator graph is configured to receive data from at least one upstream processing element and transmit data to at least one downstream processing element;

determining that an output of a first processing element of the plurality of processing elements is predictable based on at least one previously transmitted output value;

receiving a current input value at a second processing element of the plurality of processing elements, wherein the second processing element is unable to meet one or more throughput requirements for the streaming data by processing the received current input value; and

in response to receiving the current input value, and instead of processing the received current input value, transmitting a predicted output value from the second processing element, wherein the predicted output value is based on previously computed output values generated by the second processing element.

2. The method of claim 1, wherein the first and second processing elements are the same processing element.

3. The method of claim 1, wherein the one or more performance requirements include at least one of power consumption, a predicted time required to process the input value, CPU usage, tuple throughput rate, and buffer usage.

4. The method of claim 1, wherein the output is predictable based on at least one previously received input value that corresponds with the at least one previously transmitted output value.

5. The method of claim 4, further comprising:

determining if the current input value is within a range based on the at least one previously received input value; and

if so, transmitting the predicted output value from the second processing element, wherein the first and second processing element are the same processing element.

6. The method of claim 4, wherein the first processing element receives a plurality of corresponding inputs, wherein the output is not predictable based on at least one of the plurality of corresponding inputs that is received from the second processing element, and wherein the second processing element is upstream from the first processing element.

7. The method of claim 1, wherein determining whether the output is predictable further comprises:

determining whether a plurality of previously transmitted output values transmitted by the first processing element are within a predetermined value of each other; and

if so, generating the predicted output value irrespective of the received current input value.

8. The method of claim 1, further comprising, adding a score to the predicted output value that represents the accuracy of the predicted output value.

9. The method of claim 1, wherein the predicted output value is an average of a plurality of previously transmitted output values generated by the second processing element.

10. The method of claim 1, wherein the first and second processing elements are distinct processing elements.

11. The method of claim 1, further comprising determining whether the second processing element is unable to meet one or more performance requirements in response to receiving the current input value.

12. A computer-implemented method for processing data, comprising:

receiving streaming data to be processed by a plurality of processing elements, the processing elements processing at least a portion of the received data by operation of one or more computer processors;

establishing an operator graph of the plurality of processing elements, the operator graph defining at least one execution path and wherein at least one of the processing elements of the operator graph is configured to receive data from at least one upstream processing element and transmit data to at least one downstream processing element;

determining whether an output of a first processing element of the plurality of processing elements is predictable based on at least one previously transmitted output value being within a first predefined range of at least one corresponding previously received input value;

receiving a current input value at a second processing element of the plurality of processing elements;

determining if the current input value is within a second predefined range of one of the at least one corresponding previously received input value; and

in response to determining that the output of the first processing element is predictable and the current input value is within the second predefined range, transmitting the current input value as the output from the second processing element.

13. A computer-implemented method for processing data, comprising:

receiving streaming data to be processed by a plurality of processing elements, the processing elements processing at least a portion of the received streaming data by operation of one or more computer processors;

establishing an operator graph of the plurality of processing elements, the operator graph defining at least one execution path and wherein at least one of the processing elements of the operator graph is configured to receive data from at least one upstream processing element and transmit data to at least one downstream processing element;

determining that an output of a first processing element of the plurality of processing elements is predictable based on at least one previously transmitted output value;

receiving a current input value at a second processing element of the plurality of processing elements, wherein the first and second processing elements are distinct processing elements; and

in response to receiving the current input value, and instead of processing the received current input value, transmitting a predicted output value from the second processing element, wherein the predicted output value is based on previously computed output values generated by the second processing element.

14. The method of claim 13, wherein the second processing element is downstream of the first processing element.

15. The method of claim 13, further comprising:

determining whether the second processing element is unable to meet one or more performance requirements by processing the received current input value,

wherein the predicted output value is transmitted if the second processing element is unable to meet the one or more performance requirements.

16. The method of claim 15, wherein the one or more performance requirements include at least one of power consumption, a predicted time required to process the input value, CPU usage, tuple throughput rate, and buffer usage.

17. The method of claim 13, wherein the output is predictable based on at least one previously received input value that corresponds with the at least one previously transmitted output value.

18. The method of claim 13, further comprising adding a score to the predicted output value that represents the accuracy of the predicted output value.