4.5 Optimization: Removing Conditionals

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

has been performed, the evaluation of

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

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

Given that the evaluation of during the computation of falls into the first case, the evaluation of during the computation of , for , 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 . 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 over , using constant interval arithmetic. Each operator is evaluated by one of the following rules:

while the compound operator is evaluated by the following rule:

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

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

which was again automatically deduced from the associated 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 ,

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

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

The derivative of g,

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

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

The improved rule is thus given by the following:

and is valid for any interval . 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.

Jeff Tupper

March 1996