Difference between revisions of "Chart uncertainties"

Revision as of 23:50, 13 December 2005

Head back to Chart_research for some perspective.

Here is a space for our goals, challengs, ideas, restrictions, thoughts, worries, and anything else.

• Streams vs. single arguments?
• How do you preserve state?
• How do you accumulate transparently when a node's execution is split?

Control Charts

What happens if we use charts, with their current limitations, to describe program flow instead of data flow? If each node executes after its parents and before its children -- and that's the only guarantee -- what do we see? It's intimately related to our larger problem.

To reduce a dataflow chart to a control chart, realize it with nodes that take unary input (no information is exchanged).

Control charts can work with global data, particularly if each node needs a guarantee of state before it runs and gives a guarantee of state after it runs. Now think of a program in a classic language, where not every line really depends on the lines before it, but will still be run in order. What if you marked off the dependencies of lines of code, and structured the program that way? It would be convenient, among other things, for debugging and efficient compilation. It might also offer interesting ways to do conditional expressions.

I think I might study these as a simpler case.

Network Charts

I once listened to a lecture where declaritive overlay networks were being constructed using SQL like query commands. This greatly allows for the simplification of creating overlay networks, or at least reducing the amount of code required per system as so much became abstrated away.

Might a chart be used in some way to describe how nodes interact and are connected?

Ideally we need to find exactly what operations on a Network_chart would be necessary to make this useful. Once we know that, we can apply that knowledge in studying more general computational charts: what operations on a network chart turn it into a computational chart?

Computation Charts

Charts can be used to declare areas of computation and the interactions/dependancies between them. This is the obvious applicaiton of charts, but is significant. It would allow for increased modularity of code, parallelism and diversity in code base. Predominantly the chart abstracts the computation further away from the computer it is being processed on.

Layering

Thus far we have described charts as residing above all other code, no matter how nested the charts themselves are. Could perhaps the charts themselves be used as programming level constructs? Similar to a function or an event handler a programmer could set up inputs or outputs to a chart.

This is, in general, a difficult problem. Consider the following line of arguments:

• Most input systems to the computer require output to trigger. Certainly a node that is considered to be input can be fulfilled with a program that technically performs both input and output, but if we find a way to describe both aspects of this, it will be lovely. [incidentally: a program's output is needed, so its input is needed; its input needs to give an output, so it gives an output. This is a subset of the problems we already have. it's not all too bad.]

• Charts themselves must be loaded into memory. Therefore the solution to the previous point can be applied to the loading of a chart. Simpler methods can be applied, too, ultimately.

• In general, chart meta-programming is acceptable. We need to understand what properties can be known in such a case.

Prior work

• Sawzall
• Cilk is simple, solid, and down-to-earth and there is likely to be some work we can draw from it. It gives us one more model for program interaction. It requires POSIX threads and the general form does not allow distributed memory. There is information about a distributed memory version, developed as part of Keith Randall's PhD thesis, at a page deep in the Cilk website.