unitarization: a tiling approach

If the dependences in the original PRDG are uniform, the dependences in the tile graph are unitary (from the range {-1,0,+1}). Further, the dependence components are all from the range {0,+1}. Also, the tile graph is a URE, as all nodes are of the same "type". (Check if these statements are true for all tilings.)

Some assumptions are (1) There are a large number of tiles, in any dimension (if there are non-zero number of tiles in that direction, that is) and (2) Each tile has large number of iteration points. What about the boundary points?

So, this means that we have two PRDGs: The (1) URE of the tile graph and the (2) SURE of the iteration points inside a tile. Note that each of these are *much* smaller than the original PRDG. However, we will assume that their number is still large so as to consider the mode. This means that if we begin with a 2-d square iteration space with 1000*1000 points and divide it into 10 tiles of 100 points each. We still have to deal with a 10*10 points in the tile space, that is 100 tiles. Also, a tile has 100*100 points and so has 10000 points. Each of these is a considerable number.

We need to take care about the boundaries of the tile.

All this might lead to a ratio of the following. time taken by a free schedule of the tile graph and time taken by a free schedule of the original PRDG.

We also might add some models. That could make the problem harder.
--
Now we have an agreemnent on the following model:
(1) Define a URE with edges corresponding to the dependences between different tiles. It also has some parameters (which define the number of iteration points inside a tile).
(2) Define a SURE which is parametrrized by some variables defined in problem (1). Now this SURE could be non-infinite.

Question is: what can you say about the computability/scheduling of the combined system?
--
to do: read mails around march end
--
questions/answers from meeting on 07/14:
memory optimization: pareto optimal for memory and schedule. there is no "better" point, because of the multi-criterion optimization. We are talking about the solution space, not the feasible space. The set of interesting solutions form a curve. North-east, south-west points..
--
objections to using SDP for one-shot scheduling. the multi-dimensional schedule operates in a way that the output of the solution at one point is given as input to the next LP program(is this as simple as some edges disappearing?) If we want to use a single program, possibly that is an SDP, what do we minimize?
Right now, with LP formulation of the MDS, there is no way that we can compare two schedules (what does this mean?) with different number of dimensions. We can only compare the schedules of same # of dimensions.
So, we frame the scheduling problem as a polynomial schedule.
--
When is a polynomial representable as a SDP? The set seems to be called semi-algebraic sets.