## Thursday, July 14, 2005

### 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
--