Design Discussion: Parallel IR

Me and @shashi have discussed how we might use a graph-program-format as a kind of parallel IR.

The idea is to have an hourglass design; the DAG is a small core abstraction, above it you build parallel programs, libraries, algorithms, below it you build custom optimisation passes, integrate with other backends and hardware and so on. If things are loosely coupled enough then the problem statement and its implementation become orthogonal; everything is very plug-and-play, and you start building a parallel computing ecosystem rather than just a bunch of apps on top of a single framework.

From 10,000 feet, the building blocks are:
1. Graph data structures and functions on them – they need to be as natural to work with as trees.
2. A design for how to specify programs as graphs. (What protocol do operations in the graph satisfy, if any? Are they black boxes? Do they provide a cost model, hardware affinity? etc.)
3. Splitting packages like ComputeFramework into modular pieces which communicate via the above.
4. ???
5. Profit

Flow.jl is a start on (1). Shashi has had (3) in mind while designing CF. (2) and (4) involve a lot of tough design decisions that we haven't figured out yet. For example, how do we get optimisation passes or schedulers to cooperate without explicitly knowing about each other? (5) will take a while.

Of course, it's absolutely key that the DAG is expressive enough to represent a useful subset of parallel programs. Dynamic sizing is enough to express recursive / irregular problems. What about other abstractions, like distributed channels – how do they fit in? Do they need to?

To reason about this I think it may be useful to evaluate the dimensions along which parallel programs may vary. Off the top of my head:
- "Small model, big data" vs. "Large model, small data"
- Evaluate-once vs. evaluate-repeatedly
- Regular vs. irregular

e.g. BigLinalg is 001, NNs are 111. What other dimensions exist, and can we come up with practical examples across all of them?

Any obvious holes in this plan?