A Caching Structure!

[altenbach]

I often have a situation where certain code parts don't really need to be recalcuated, because their inputs have not changed from an earlier encounter.

For example if a function is the sum of two different complicated and slow calculations where each of the two depend on a different subset of parameters, often only one needs to be recalculated, while the other intermediary result could be grabbed from a cached value. (This occurs for example during the calcuation of partial derivatives).

In some cases, the compiler could probably recognize these situations, but I think we should have a special structure to allow caching of intermediary results.

I typically use a case structure and two feedback nodes as shown in the example on the left. If the value is different, the code in the TRUE case is executed, else the value stored in the SR is returned immediately. (If the code depends on several values, I bundle them all before the comparison operation)

I propose an simple Caching Structure as show on the right that retains that same functionality with less baggage.

Details: The containing code is calculated at first run and stored in the output tunnel. In later calls, it is either (A) recalculated, or (B) the previously stored value returned at the output tunnels. Recalculation only occurs under some conditions (.i.e. usually when actually needed)

The structure has the following features:

• Two possible types of input tunnels (the functionality is indicated by a different look).
1. One where a value change triggers a recalcuation of the containing code
2. One where a value change does not trigger a recalculation of the containing code
• A special boolean terminal to force a recalculation unconditionally
• output tunnels that retain data between calls

There can be an unlimited number of input and output tunnels of any type described above. A recalculation of the inner code occurs if any of the triggering tunnels have a changed value.

We can think of it similar to "short-term folding". 

[Ironman99]

Just for my better understanding, altenbach, but it appear to me that the first feedback node should be configured in "Initialize On Compile Or Load" mode, isn't it?

If not, what am I missing?

In any case, kudos! Great idea.

Cheers.

[Intaris]

I don't know.

It seems somewhat counterintuitive.

What's the expected overhead?

Shane.

[Ironman99]

Intaris wrote: It seems somewhat counterintuitive.

I suppose that the altenbach intent were much more to show us a new structure's functionality than the best way for representing it.

In the following pictures I tried to imagine a different representation, with exactly the same functionalities proposed.

Merely an attempt to be imaginative, even though I know that people in NI is much better than me in this field. 

          

Cheers.

Marco.

[Ironman99]

Since in Italy we say "L'appetito vien mangiando" that more or less means :"your appetite comes with eating" I'd like to add a feature to the Caching structure.

Starting from the "double frame" picture that I've included in my previous comment, we can also imagine a "multi frames" structure, each for different input variation ranges. May be we don't want a recalculation if the input has not changed more than a certain amount. Or may be we prefer to use a different calculation model for small variations. Just brainstorming...

Cheers

Marco

[spatry]

This could be extended to be a "memoization" block, see http://en.wikipedia.org/wiki/Memoization for indepth description of the term.

Rather than caching the last input, it could cache a set of inputs, allowing you to make the same speed/space trade off for a wider array of problems.

[altenbach]

> Just for my better understanding, altenbach, but it appear to me that the first feedback node should be configured in "Initialize On Compile Or Load" mode, isn't it?

If you read the help, as soon as you wire an initializer value, the default is to initialize on first call. (Quote: If you set an initial value, the Feedback Node initializes to that value on the first call of the VI in an execution.) You want to initialze with an impossible value to force an initial calculation. You can initialize with a value and set to initialze on compile or load, but I don't think it would make a real difference here.

> Merely an attempt to be imaginative, even though I know that people in NI is much better than me in this field.

The point of the structure was that we don't need any other cases. Your "other" case does not provide anything useful, just helps illustrate the functionality. I don't think we need it, it just adds complexity.

> we can also imagine a "multi frames" structure, each for different input variation ranges.

Again, I want it to be simple. If you need more complexity, you could stack several of these structures, e.g. a big one that enables as a function of two values containing two small such structures, one for each value.

> This could be extended to be a "memoization" block

Exactly. I did not know this term, but that is basically what I want. In the current proposal we keep one output, assuming that the value rarely changes (this is true in many of my application). For example for tikhonov regularization, I need to setup large matrices, and they only change if I load a new dataset with different ranges.

Of course the structure could be extended to "remember" the result for the last N possible input combinations. This would e.g. help if the input constantly flickers between the same few values. For fancier and more extended caching I have implemented an associative memory cache (See also). It could be fully and transparently integrated into this new structure. All it would need is an additional input for "cache size" (and maybe an output for "cache hit?" so we can keep statistics). Of course we need to be careful with memory bloat. 😄

[Intaris]

I would add the requirement that if there are multiple inputs to the structure then we should be able to right click ont hem and select which ones trigger recalculation on change.  Also, in the event that one wants complete control over the things, it should be allowed to have NO autorecalculate inputs but just the manual override (Force).

I'm still not quite getting it, but that doesn't mean others shouldn'^t benefit from it. Anyone got examples where this would be of benefit?

Shane.

[altenbach]

> I would add the requirement that if there are multiple inputs to the structure then we should be able to right click on them and select which ones trigger recalculation on change.

Yes, that's exactly what I meant wit the following quote:

• Two possible types of input tunnels (the functionality is indicated by a different look).
1. One where a value change triggers a recalcuation of the containing code
2. One where a value change does not trigger a recalculation of the containing code"

Sorry, I did not explicitely mention that we can freely pick the functionality of each input tunnel by right-clicking, but that was implied. 😉

[Dragis]

For those that aren't digital designers, you may want to take a look at sensitivity lists in VHDL or Verilog for ideas. Essentially, these lists are qualifications on a process that allow the designer to designate which signals force a re-evaluation of process contents. From a tutorial on VHDL ...

... a list of signals in parenthesis, called the sensitivity list. Since the process statement's contents may not have indicated any structural characteristics, there is no way to know when the process should be re-evaluated to update the outputs. The signal sensitivity list is used to specify which signals should cause the process to be re-evaluated. Whenever any event occurs on one of the signals in the sensitivity list, the process is re-evaluated.

Also note that the compiler should (and usually can) automatically detect what will cause a reevaluation by default.

Great feature idea, I do this memoization all the time for performance critical code. I actually wish the compiler would just do it automatically, but it is a much harder problem for a compiler alone to know which code is performance critical without feedback from another tool on the side. 

[Ironman99]

I have a doubt... Is this proposal thought only for integers numbers as input?

If not (as would maybe desiderable) may be that the "input changed" definition should be in some way configurable.

For doubles numbers (15 bits of precision) a definition as simple as [N] != [N-1] could be too easy to meet,

in some situations, making this structure practically useless.

In that cases some sort of trigger threshold should be introduced, separately configurable for each input.

A value of "abs([N] - [N-1]) = 1" could be the default threshold value.

Moreover... should this structure accept ALL type of LV data, in your opinion?

Cheers.

Marco.