Home » forums » LtU Forum

Graph processing

Hi all,

Not sure if this is a good forum to post this question on, but it's the best I could come up with, so hopefully someone will have some insights or pointers as to where to look for research :)

I've been thinking about 'graph processing' systems (for want of a better name) - for example, say an image editing system where an output image is described by a process on various input images, and those input images are again described by more processes on further inputs, and so on. A DAG basically, where each node is a process that produces an item of data, and the edges represent dependencies on input data.

Now say I wrote an image editing application based on such a system. I'd like to allow users to edit any process, thereby meaning all downstream nodes need recalculating, but to achieve best performance, ideally upstream nodes of the thing being edited would be cached somewhere - so you don't need to continually re-evalute any inputs whilst editing. However, clearly you've only got a limited amount of memory to cache stuff in, and therefore can't cache everything, so how do you decide which nodes should be cached and which shouldn't?

Kind of feels like if you could assign each process a cost (i.e. how expensive it is to recalculate the output of a node from its inputs), and a probability that it will be edited (i.e. there's no point in caching something if nothing downstream of it changes, but if a process is continually edited you'll probably want to cache it's inputs), then there ought to be some way of determining roughly which processes should be cached and which shouldn't. Seems like it ought to be possible to do better than just a simple LRU cache of node outputs for example.

Feels like it's probably a problem that's been researched somewhere in some form or other, or it's some computer science 101 problem I happened to miss out on phrased in somewhat odd terms, but I'm at a loss as to where to start looking...

Any pointers appreciated...!

By richk at 2010-01-24 21:37 | LtU Forum | previous forum topic | next forum topic | other blogs | 5619 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Sounds like a spreadsheet for images...

As far as I know, spreadsheets cache all cells, and thus don't have a answer for your question.

Keeping track of cost and probability that it will be edited seems like a very good place to start, though you should also factor in the quantity and speed of memory.

Some similar questions have been raised in the thread Functional Anti-Memoization, and the paper Lazy and Forgetful Polynomial Arithmetic and Applications employs forgetful arithmetic to save space.

By Leon P Smith at Sun, 2010-01-24 22:53 | login or register to post comments

Reactive, Live Programming

You seem to be basically asking about a graphical, reactive, live programming system, which has been discussed a lot on LtU recently (my fault, partially). Whether what you're asking about is 'Functional' Reactive Programming would depend on whether or not some process nodes in the graph keep state or introduce delay semantics.

I'll point you towards a few prior discussions on LtU that may be relevant to you:

By dmbarbour at Mon, 2010-01-25 00:03 | login or register to post comments

Adaptive, incremental, self-adjusting computing

A DAG basically, where each node is a process that produces an item of data, and the edges represent dependencies on input data.

Sounds like a lot of compositing systems. If you have a Mac, I suggest you check out Quartz Composer.

ideally upstream nodes of the thing being edited would be cached somewhere - so you don't need to continually re-evalute any inputs whilst editing

I suggest using a continuous damage/repair process. If a change occurs during a repair, throw out any results invalidated by the change and keep going. Worklist algorithms especially enable this style of evaluation.

Kind of feels like if you could assign each process a cost (i.e. how expensive it is to recalculate the output of a node from its inputs), and a probability that it will be edited (i.e. there's no point in caching something if nothing downstream of it changes, but if a process is continually edited you'll probably want to cache it's inputs), then there ought to be some way of determining roughly which processes should be cached and which shouldn't.

Complicated and maybe unnecessary. What works for me is fixing the granularity of what is memoized based on tuning. You obviously don't want to bother memoizing small operations, as its more overhead then the performance benefit you are gaining. A big operation probably warrants memoization. And, of course anything stateful is already memoized by definition (if you must remember an output, you can detect whether the new output is different from the old output).

Feels like it's probably a problem that's been researched somewhere in some form or other, or it's some computer science 101 problem I happened to miss out on phrased in somewhat odd terms, but I'm at a loss as to where to start looking...

There isn't a lot to look at in this area, just locked up knowledge from active practitioners. Functional reactive programming is some place where you can look, but they don't really focus on efficient memoization, as far as I can tell [it feels like most FRP systems just memoize everything! Hopefully an FRP expert will correct me!]. My Superglue work is the extreme opposite, I memoize nothing unless its necessary because state is involved. My Scala IDE work (continuous compilation is very related) memoizes Scala tree parse and type information at some fixed granularity chosen via tuning.

There is this weird field of PL called incremental computing. Then you can check out Magnus's paper from the wiki page, or check out the adaptive functional programming paper. I haven't found these to be particularly useful from a practitioner stand point, although they are clearly related.

By Sean McDirmid at Mon, 2010-01-25 01:31 | login or register to post comments

Complicated and maybe

Complicated and maybe unnecessary. What works for me is fixing the granularity of what is memoized based on tuning. You obviously don't want to bother memoizing small operations, as its more overhead then the performance benefit you are gaining. A big operation probably warrants memoization. And, of course anything stateful is already memoized by definition (if you must remember an output, you can detect whether the new output is different from the old output).

Yeah, having read what folks have posted and thought about it a bit more, think you're right. It would seem figuring out what to cache and what not to cache is either not a trivial problem, or not actually a problem at all in practice (or probably both!).

As you say, sounds like just caching anything that costs more than some threshold to regenerate, with I guess just a normal LRU policy to throw stuff away when you run out of RAM, probably gives a pretty good solution for not a lot of effort.

Thanks!

By richk at Mon, 2010-01-25 17:43 | login or register to post comments

As you say, sounds like just

As you say, sounds like just caching anything that costs more than some threshold to regenerate, with I guess just a normal LRU policy to throw stuff away when you run out of RAM, probably gives a pretty good solution for not a lot of effort.

This isn't exactly what I meant. There is overhead deciding to memoize something at all, because now you have to indirect access to that thing in anything that refers to it, you can't inline or optimize the code, and so on... Just deciding that something could be memoized is expensive, then there is the actual memoization, which can definitely be optional if we can reproduce the value by executing code.

For most programs, you probably aren't going to run out of RAM, you'll just start thrashing your VM system. If you are going to do LRU, you might want to consider hooking into the VM system somehow via phantom or weak references (weak is probably too weak, you want GC to throw away memoized evaluation only if cleaning up other garbage isn't useful).

By Sean McDirmid at Mon, 2010-01-25 23:26 | login or register to post comments

Self-adjusting computation

Take a look at this. Umut was the invited speaker at PEPM last year and described an overview of this work. It sounds very close to what you want. In their work partial changes to input propagate through through the system just recomputing the bits that are necessary. When you say image processing I'm assuming that you're talking about destructive array operations over the images, so avoiding downstream computations will be difficult, although the decisions about how much to cache in limited RAM will be the same.

By Andrew Moss at Mon, 2010-01-25 12:06 | login or register to post comments

the so called `node based` computer generated image

Any non-mundane computer image generation/animation/processing software works exactly the way you described.

[~3D]
Sidefx Houdini (ex. Prism), One of the first commercial program using that paradigm (1)(2)

Autodesk Maya (ex Alias|Waveform Maya) is another great example.

Autodesk Softimage XSI, but only for the dynamics/particle system.

[~2D]
Apple Shake(ex. Nothing Real Shake), used to be one of the fastest compositing software around 2000~

The Foundry Nuke, similar to Shake at first, but extended to support 3D projections too.

(1) Funny cause they refer to that way of doing things as "procedural" but has nothing to do with imperative paradigm and is close to the functional paradigm, for the real imperative paradigm see 3D Studio Max, there was a little history stack for undo/redo purposes, but you mainly modify objects like a memory assignement.

(2) Houdini isn't "purely functional" either, sometimes parameters are scattered around .. but beside that corner it's infinitely open, you can build first order graphs( graphs ~ function ) that can be used in other graphs .. it's like tangible math to abuse conal elliot idea. Live, reactive, lazy maths.

I wonder how much of a subset of .. Haskell let's say.

for the story, I used to toy with all those before entering college, then tried to fit java/uml into my head (with that DAG philosophy..) before reading about haskell (and later rediscovering spreadsheets). aHA moment

By fasteez at Mon, 2010-01-25 17:22 | login or register to post comments

Yeah, realise that's how

Yeah, realise that's how they work (along with lots of other apps in other areas)... Was more wondering if there were any particular techniques they used for caching intermediate results and optimising how much of the graph was regenerated after a change. Sounds like probably not beyond the obvious... not that the companies you listed would likely say if there were ;)

Thanks all - lots of good reading :)

By richk at Mon, 2010-01-25 17:49 | login or register to post comments

my bad

I was so eager to talk about `graph systems` that I missed one part of your post and jumped into propaganda mode.

good luck with your search

By fasteez at Mon, 2010-01-25 18:04 | login or register to post comments