zhaojinm/polyhedral_feautrier_algo

Polyhedral_Feautrier_algo

This is a briefly introduction/summary/review about Feautrier algorithm based on Some efficient solutions to the affine scheduling problem Part I One-dimensional Time and Some efficient solutions to the affine scheduling problem Part II Multidimensional time. Many corrent polehedral models are based on Feautrier's model. Feautrier's orginal paper is very long(80+pages intotal). Next, I will pick the key points so that people can understand faster.

Generalized Dependence Graph

A Generalized Dependence Graph (GDG) is a directed multigraph. A vertex represents a set of related statements. Each statement belongs to one (and only one) vertex of the GDG. An edge represents a timing constraint(dependence relation) between two operations which belong respectively to its source and destination. The GDG may have loops (i.e. an edge whose source and destination are the same vertex) and cycles.

• Each vertex is associated with a domain polyhedron .
• Each edge is associated with a dependence relation polyhedron .

Fig.1 - Program 1

Take above program as an example, there are two statements(vertex). Whose domain are:

And two edges, first one has the dependence polyhedron:

Second edge is an uniform loop with dependence polyhedron:

These two dependence can be simplfied to the following(typo: not 1 should be 0, not 2 should be 1):

It is clear that each dependence polyhedral can be simplified into a pair of polyhedral and an affine transformation :

In this case we can eliminate x. Use this way, dependence polyhedral of edges in above example would be:

one-dimensional algorithm

1d - Schedule

Each schedule has the form:

where a,b are unknown vectors and c is unknown number. n is the structure parameters(known). The problem is that given a GDG, find the solutions which satisfy the causality condition above. Will talk about picking an optimal solution later. To find the solution of schedules, Farkas lemma will be used.

Now, each domain polyhedral D is represented by a set of inequalities:

Each dependence polyhedral R is repensented by a set of inequalities similarly:

And dependence polyhedral can be simplified as the description of P:

Each schedule must be nonnegative, so first use Farkas multiplier to represent schedule in this way:

For each edge in GDG, there is delay associate with it where is the destination of egde and is the source of the edge :

Each edge must have non-negative delay. So there are Farkas multiplier(typo: should be e not f):

As we discussed above, R can be represented by P and h, so above can be rewrite as:

then we can use Linear programminng tools to solve Farkas multipliers. Usually choose with minimum absolute value in lexicographical order.

1-d schedule example

Use program 1 above as an example. Here are schedules with Farkas multipliers:

Delay for the first edge:

which results:

Delay for the second edge do not need to use Farkas Lemma since it is uniform:

Eliminate unknowns will give:

Finally:

Below is one possible solution:

with parallel form of the program:

There might be many other solutions.

1-d how to select a good solution

• Minimize Latency

\bf{Lemma}: if domains are bounded, and exists at least one affine schedule, then there exist at least one affine form of structure parameters:

We may apply Farkas Lemma:

Make h and k be the leading unknown, so that Linear Programming solver will give the minimal values for h. Applying this to above program gives the min latency L=n+1. The problem of this method is that the order of structure parameters and unknowns matter.

• Bounded delay schedule

Want to find the minimun such that for each edge:

Smaller delay tend to have better schedule(cache?). method is very obvious, apply Farkas Lemma and make the leading unknown. Bounded delay is more constrained than minimum latency.

• Dual

So want to find the minimum schedule:

This might return a isolated numerical values of , rather than a closed form solution. Since parameters(n?) occur in the objective function, not suitable for Linear Programming solver. By the following thm:

We can have:

Dual method and minimum latency method have the same latency. But dual method and bound delay method may have different delay.

• Uniform recurrences

For the uniform dependences no need to use Farkas Lemma. The condition for edge e simply be:

The dual form:

Consider following as an uniform example:

let schedule be:

the dual form is：

Linear Programming solver gives:

drawbacks of 1-d algo

• Some programs whose free schedule if not concave, then cannot find piecewise affine schedule.

For this program:

the best schedule is：

The dule Farkas algo will gives:

The best schedule has latency 1 while the algo will give latency O(n).

• Some program do not have affine schedule:

Take the following program as example:

This program has schedule which is not linear. The term ni is not linear.

multi-dimension algorithm

Basic Algorithm

delay with edge

Schedule must satisfy:

So:

First iteration starts:

May not all strongly satisfy, update polyhedral for next iteration:

Way to update:

If P is not empty, go to next iteration.

mult-dimension example

Greedy multi-dimension

Lemma1: The solution is that all e are either 0 ot 1.

Lemma2: The solution is unique.

Theorem: Let U be an arbitrary subset of the edges of a static program. The solving programing for U always satisfies at least one edge of U(Greedy algorithm terminates).