Method and apparatus for evaluating expressions with cancellation of requests for operands that are no longer required

• US 6,374,233 B1
• Filed: 06/02/1999
• Issued: 04/16/2002
• Est. Priority Date: 07/28/1998
• Status: Expired due to Term

• Current Assignee: International Computers Limited (Fujitsu Limited)
• Original Assignee: International Computers Limited (Fujitsu Limited)
• Inventors: Gardner, Paul Anton Richardson
• Primary Examiner(s): Black, Thomas
• Assistant Examiner(s): CHEN, TE Y
• Application Number:
  US09/324,216
• Time in Patent Office: 1,049 Days
• Field of Search: 706/45-47, 706/925, 707/2-5, 707/7, 709/100, 709/223, 709/243, 709/314, 709/224, 709/228, 717/6-7, 712/245, 712/236, 712/222, 712/223, 708/204, 708/205, 711/123, 711/150-155
• US Class Current: 1/1
• CPC Class Codes: G06F 8/311 Functional or applicative languages; Rewrite languages
• CPC Class Codes: G06F 9/4494 data driven
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing

Abstract

A method for evaluating an expression comprises issuing parallel requests to acquire a plurality of operands. If, upon receipt of a first subset of the operands, it is determined that a second subset of the operands is no longer required in respect of a particular time span, the request for the second subset cancelled for that particular time span. If one operand contains an error indication for a particular time span, the method continues with the request for the other operand for that particular time span, and returns an “error” for that particular time span only if the request for the other operand is not cancelled.

Claims

1. A data processing method comprising the steps:

(a) inputting to an evaluation unit an expression defining an operator and a plurality of operands, said operands comprising at least a first subset of operands and a second subset of operands;

(b) operating said evaluation unit to issue parallel requests for said operands;

(c) in response to said parallel requests, initiating a plurality of parallel acquisition processes to acquire said operands;

(d) operating said evaluation unit, upon receipt of said first subset of operands, to determine whether said second subset of operands is still required for evaluating the expression;

(e) in the event that the evaluation unit determines that said second subset of operands is no longer required for evaluating the expression, operating said evaluation unit to cancel the request for said second subset of operands; and

(f) operating said evaluation unit to evaluate said expression.

2. A data processing method according to claim 1 including:

(a) converting an expression into a data flow graph, including a root node representing the result of the evaluation, leaf nodes representing the operands, and intermediate nodes representing operators;

(b) propagating a Require message through the data flow graph towards the leaf nodes, the Require message indicating which operands are required;

(c) when a Require message reaches a leaf node, acquiring an operand, and propagating a Data message through the data flow graph towards the root node, the Data message including an operand value acquired by the leaf nodes; and

(d) when a Data message reaches an intermediate node, determining whether an operand is still required by that node and, if the operand is no longer required, propagating a Cancel message through the data flow graph towards the leaf nodes.

3. A data processing method according to claim 1, wherein

(a) each of the operands comprises a sequence of one or more value instances, each value instance including a data item, a start time, and an end time, the start time and end time defining a time span for which the data item is valid;

and

(b) in the event that the evaluation unit determines that said second subset of operands is no longer required for evaluating the expression in respect of a particular time span, operating said evaluation unit to cancel the request for said second subset of operands in respect of said particular time span.

4. A data processing method according to claim 1, wherein:

(a) said operator comprises a logical “

and”

operator, having two operands; and

(b) in the event that either operand is “

false”

for a particular time span, operating said evaluation unit to cancel the request for the other operand for said particular time span, and returning a “

false”

result for that particular time span.

5. A data processing method according to claim 1, wherein:

(a) said operator comprises a logical “

or”

operator, having two operands; and

(b) in the event that either operand is “

true”

for a particular time span, operating said evaluation unit to cancel the request for the other operand for said particular time span, and returning a “

true”

result for that particular time span.

6. A data processing method according to claim 1, wherein:

(a) said operator comprises an arithmetic “

multiply”

operator, having two operands; and

(b) in the event that either operand is zero for a particular time span, operating said evaluation unit to cancel the request for the other operand for said particular time span, and returning a zero result for that particular time span.

7. A data processing method according to claim 1, wherein:

(a) said operator comprises an-arithmetic “

divide”

operator, having two operands, namely a dividend and a divisor; and

(b) in the event that the dividend is zero for a particular time span, operating said evaluation unit to cancel the request for the divisor for said particular time span, and returning a zero result for that particular time span.

8. A data processing method according to claim 1 including:

(a) operating the evaluation unit, in the event an error indication in connection with one of said operands for a particular time span, to continue with a request for another of said operands for that particular time span; and

(b) operating said evaluation unit, upon receipt of said another of said operands, to determine whether said one of said operands is still required for evaluating the expression;

(c) in the event that the evaluation unit determines that said one of said operands is no longer required for evaluating the expression, operating said evaluation unit evaluate said expression even though said error indication has occurred.

9. A data processing apparatus comprising:

(a) an evaluation unit for evaluating expressions;

(b) at least one operand acquisition unit;

(c) means for inputting to said evaluation unit an expression defining an operator and a plurality of operands, said operands comprising at least a first subset of operands and a second subset of operands;

(d) said evaluation unit comprising means for issuing parallel requests for said operands to said operand acquisition unit;

(e) said operand acquisition unit comprising means responsive to said parallel requests, for initiating a plurality of parallel acquisition processes to acquire said operands and for returning said operands to said evaluation unit;

(f) said evaluation unit including means operative upon receipt of said first subset of operands, for determining whether said second subset of operands is still required for evaluating the expression;

(g) said the evaluation unit also including means operative when said second subset of operands is no longer required, for sending a message to said operand acquisition unit, canceling the request for said second subset of operands.

10. Data processing apparatus according to claim 9 wherein the evaluation unit comprises:

(a) means for converting an expression into a data flow graph, including a root node representing the result of the evaluation, leaf nodes representing the operands, and intermediate nodes representing operators;

(b) means for propagating Require messages through the data flow graph towards the leaf nodes, the Require messages indicating which operands are required;

(c) the leaf nodes comprising means for acquiring operands in response to the Require messages, and means for propagating Data messages through the data flow graph towards the root node, the Data messages including operand values acquired by the leaf nodes; and

(d) the intermediate nodes comprising means for determining whether an operand that has not yet been returned in a Data message is still required and, if an operand is no longer required, propagating Cancel messages through the data flow graph towards the leaf nodes.

11. A data processing apparatus according to claim 9, wherein

(a) each of the operands comprises a sequence of one or more value instances, each value instance including a data item, a start time, and an end time, the start time and end time defining a time span for which the data item is valid;

and

(b) said evaluation unit includes means operative when said second subset of operands is no longer required for evaluating the expression in respect of a particular time span, for sending a message to said operand acquisition unit, canceling the request for said second subset of operands in respect of said particular time span.

12. A data processing apparatus according to claim 9, wherein:

(a) said operator comprises a logical “

and”

operator, having two operands; and

(b) said evaluation unit includes means operative in the event that either operand is “

false”

for a particular time span, for canceling the request for the other operand for said particular time span, and returning a “

false”

result for that particular time span.

13. A data processing apparatus according to claim 9, wherein:

(a) said operator comprises a logical “

or”

operator, having two operands; and

(b) said evaluation unit includes means operative in the event that either operand is “

true”

for a particular time span, for canceling the request for the other operand for said particular time span, and returning a “

true”

result for that particular time span.

14. A data processing apparatus according to claim 9, wherein:

(a) said operator comprises an arithmetic “

multiply”

operator, having two operands; and

(b) said evaluation unit includes means operative in the event that either operand is zero for a particular time span, for canceling the request for the other operand for said particular time span, and returning a zero result for that particular time span.

15. A data processing apparatus according to claim 9, wherein:

(a) said operator comprises an arithmetic “

divide”

operator, having two operands, namely a dividend and a divisor; and

(b) said evaluation unit includes means operative in the event that the dividend is zero for a particular time span, for canceling the request for the divisor for said particular time span, and returning a zero result for that particular time span.

16. A data processing apparatus according to claim 9, wherein:

(a) said evaluation unit includes means operative, in the event an error indication in connection with one of said operands for a particular time span, for continuing with a request for another of said operands for that particular time span; and

(b) said evaluation unit includes means operative, upon receipt of said another of said operands, for determining whether said one of said operands is still required for evaluating the expression;

(c) said evaluation unit includes means operative in the event that said one of said operands is no longer required for evaluating the expression, for evaluating said expression even though said error indication has occurred.

17. A data carrier incorporating a computer program for performing a method comprising the steps:

(a) inputting to an evaluation unit an expression defining an operator and a plurality of operands, said operands comprising at least a first subset of operands and a second subset of operands;

(b) operating said evaluation unit to issue parallel requests for said operands;

(c) in response to said parallel requests, initiating a plurality of parallel acquisition processes to acquire said operands;

(d) operating said evaluation unit, upon receipt of said first subset of operands, to determine whether said second subset of operands is still required for evaluating the expression;

(e) in the event that the evaluation unit determines that said second subset of operands is no longer required for evaluating the expression, operating said evaluation unit to cancel the request for said second subset of operands; and

(f) operating said evaluation unit to evaluate said expression.