Next: 4.6 Alternative Formalisms
Up: 4 Graphs
Previous: 4.4 Optimization: Caching
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.
Next: 4.6 Alternative Formalisms
Up: 4 Graphs
Previous: 4.4 Optimization: Caching