**The uniformization problem of Darte-Vivien:**Take a PRDG with possibly non-uniform dependences and

*uniformize*the graph so that all dependences in the graph are uniform (constant vectors). How can you answer the computability and scheduling problems of the original graph using the transformed graph?

**The unitarization problem:**Suppose we

*unitarize*the input PRDG so that all components of dependence vectors are from the set {+1,-1,0}? How can you answer the computability/scheduling queries of the original graph using the unitarized graph? How can you use TUM property for this? How is the presence of null weight cycles in the new PRDG related to its TUMness?

**The size of the unitarized graph, measured in number of nodes/edges, could be exponential in the number of bits used to encode the problem!!!**This is because its size dependences on the weights of the original graph, not just the nodes or vertices of the original graph. The proposed unitarization may not be the only way in which we obtain a resultant unitarized-PRDG. We may be able to compress it. Can we just look at the actual nodes of the program, keeping aside the virtual nodes and reason about the computability? Since the depencence distances are in the set {+1,-1,0}, what we have is a kind lattice with edges of unit distance. Even if we forget that its size is large, how do you determine its computability? Let M be the matrix. The computability question is answered very simply by answering the question "Is Mx = 0 for all x?

--

This question is exactly equivalent to asking:"Is M a TUM matrix?"

**this does not seem right**

## No comments:

Post a Comment