Re: Efficient Evaluation of Image Expressions

> This is part of a landscape dynamic simulation software called
> Dinamica EGO. Basically, Dinamica is a data flow processing
> environment, where you can chain operators forming loops, decisions.
> It has been used mainly to perform simulations concerning the future
> of the Amazon forest by our research team.
>
> The expression posted previously is an example of an real expression
> used in model by an specific operator called CalculateMap. Basically
> the main data flow engine collects the relevant images and passes them
> to the CalculateMap operator. The expressions can be more complicated
> than that, but I4ve tried to keep my example as much didatic as
> possible. :)


Clearly, having things too big to fit in memory is nothing new.
Assuming you start out with eight large conformable matrices, and that
pixel[ i ] does not ever need to know anything about pixel[i + 1] or
pixel[i - 1], you can write them to file and take sizable chunks out
of them and process them piecemeal. There are two optimsations here
you can consider. First, is to process these matrices in parallel.
Second, and not so obvious, is to pick subvector sizes such that the
variables i1 through i8 plus the result and temporaries all fit into
cache memory. This is all very processor-specific, but figure on two
levels of cache between the registers and main memory. You would have
to experiment with what works best on your processors.


Also see p.455 of Compilers, Principles, Techniques, and Tools, by
Aho, Lam, Sethi, Ullman. I have the second edition, Pearson
International Edition.
Also see the "Array Programming" section in Wikipedia, plus the talk
page.


The only problem I can think of is that none of the usual array
languages (J, K, etc.) support short floating point numbers.


> However, the software is mainly used by environment researchers and
> it really difficult to convince them to write efficient code.


I know this problem well.


> This seems to be a good solution. However, the images are huge and the
> models typically deals with several gigabytes of images. As far as I
> can seen, applying each operator to an entire image can have a huge
> impact in memory consumption because you will ending up creating
> several temporary images during the expression evaluation. Even more,
> loops and conditional branches seems to complicate the calculation
> using the entire images at once. Any additionl suggestion?
>
> > The operations +, -, /, *, abs, max, etc. should have the correct
> > missing value handing for nulls. 1 2 3 + 4 MV 6 should be 5 MV 9 and
> > so on.
>
> Again, this is a little bit more complicated than my first explanation
> may suggest. The null values (or nodata, that4s how it is called by
> many map processing software) "poisons" the execution of the
> expression. So, in the following expression
>
> (if i1 + 2 > i2 / 3 then
> // .... do something
> else
> // ... do something else
> ) catch (
> // something if failed
> )


IEEE floating point math supports several magic values, one is NaN,
Not a number, and there are also +infinity and a -infinity. Provided
the host langauge supports it, the NaNs should slide right through
your formula and return a NaN. The question is whether the ratio of
NaNs to real data is worth doing something different. If you have
only a small scattering of NaNs, it probably makes sense to do nothing
about them.


> if the the evalution of the if test failed because the corresponding
> pixel value of i1 or i2 is null, then the execution of the entire if
> is aborted and a null value begins to be propagated as the expression
> result. This null value is caught by the catch operator and the
> evaluation of the remaining of the expression continues.
>
> Of course, the evaluation does not raise an exception, but instead, it
> returns a NaN that is detected and skipped by the other operator,
> except the catch.

Return to the comp.compilers page.
Search the comp.compilers archives again.