next up previous notation contents
Next: 4.6 Alternative Formalisms Up: 4 Graphs Previous: 4.4 Optimization: Caching

4.5 Optimization: Removing Conditionals

The ideas behind caching may be extended; after the evaluation of

math28616

has been performed, the evaluation of

math28622

may be simplified. An example will sufficiently expose the ideas.

Consider rendering tex2html_wrap_inline38477 with constant interval arithmetic. Eventually, tex2html_wrap_inline38479 is computed using interval arithmetic, by the following rule:

math28628

Given that the evaluation of tex2html_wrap_inline38479 during the computation of tex2html_wrap_inline37779 falls into the first case, the evaluation of tex2html_wrap_inline38479 during the computation of tex2html_wrap_inline38487 , for tex2html_wrap_inline38489 , may drop immediately into the first case, without testing x. Similarly with the second case; the other two cases require that x be tested, to produce optimal bounds of tex2html_wrap_inline38479 . The example given is simple; other operators perform many tests on their arguments before falling into one of many cases. The structure which holds cache information may also hold the additional information needed by the method alluded to in this section.

When rendering a small portion of a specific graph to a high resolution, it may be worthwhile to assemble a new operator to expose the conditionals. Consider rendering tex2html_wrap_inline38497 over tex2html_wrap_inline38499 , using constant interval arithmetic. Each operator is evaluated by one of the following rules:

math28655

math28678

math28701

while the compound operator tex2html_wrap_inline38501 is evaluated by the following rule:

math28709

The rule given was found automatically; the rule was determined by combining the cases of the basic operators. Over the area tex2html_wrap_inline38499 , the rule may be simplified to the following:

math28738

The simplified rule was found automatically, by simply evaluating the operator over the domain of interest. Rounding control is accounted for, when evaluating with tex2html_wrap_inline32517 or tex2html_wrap_inline32893 . The example rule would instead be the following:

math28746

which was again automatically deduced from the associated tex2html_wrap_inline32517 rules for the appropriate basic operators. The larger rules, with larger chains of computation, let an optimizing compiler obtain better CPU utilization. Additionally, fewer rounding mode controls need to be issued with larger chains of computation. Rounding control is often overly expensive; on many systems changing the current rounding mode consumes more resources than a floating point operation, such as multiplication.

A more involved example is evaluating tex2html_wrap_inline38511 ,

math28757

for tex2html_wrap_inline38513 . After evaluating tex2html_wrap_inline38515 , it is known that evaluation of each basic operator falls into one case; combining these cases gives the following rule for evaluating tex2html_wrap_inline38511 :

math28764

for any tex2html_wrap_inline38513 . Given a specification S, the interval evaluation tex2html_wrap_inline37715 may be quite involved; the challenge is to expose the salient features of tex2html_wrap_inline37715 to a sophisticated automatic optimizer.

The derivative of g,

math28781

when evaluated over the interval tex2html_wrap_inline38531 , is total, continuous, and negative:

math28787

This implies that g is monotonically decreasing over [1.5,2] and the preceding evaluation may be improved, by application of the following truth:

math28804

The improved rule is thus given by the following:

math28816

and is valid for any interval tex2html_wrap_inline38539 . Clearly, this rule may be found automatically, given the evaluation rules for the basic operators. Such determination may be naturally performed using an interval arithmetic with automatic differentiation.


next up previous notation contents
Next: 4.6 Alternative Formalisms Up: 4 Graphs Previous: 4.4 Optimization: Caching
Jeff TupperMarch 1996