ASAP - (J.Hummel et. al.)

• Programmer describes structures using axioms that detail independent sections of the structure.
• Analyse programs by attempting to prove blocks independent.

Integer programming - (J.-F. Collard et. al.)

• Approximate using techniques for array dependancy analysis.
• Tackle harder dataflow analysis / `fuzzy' analysis for dealing with conditionals.

Graph Types - (M. Schwartzbach et. al.)

• Tree-based backbone of structure with additional pointers.
• Allows use of runtime features in description e.g. `Is node a leaf-node'.
• No dependancy analysis.

Alternative approach - (J. Saltz et. al.)

• No programmer supplied information.
• Infers structure from sections of code that traverse/update it.
• Use that information to infer dependencies between blocks.

Our Approach

• Structures are to be completely specified, each node needs to be able to receive a unique name at compile time.
• Require structures to be described in a simple high level way.
• Possible solutions : Markov algorithms, normalise each possible path to a unique one, e.g. for n-body tree:

  $$l.n \rightarrow r$$

  $$r.n \rightarrow n.l$$

• Format based: identical nodes are described using parameterised strings. For the next direction we have:

  $$x.l.r^p \rightarrow x.r.l^p$$

• Programs: Initially simple recursive functions, extend to more general program model.
• Fine grained approach: aim is to find parallelism between individual instructions